Big M Method 5s44e

Unit 1 Lesson 9 : The Big M Method Learning outcomes •

The Big M Method to solve a linear programming problem.

In the previous discussions of the Simplex algorithm I have seen that the method must start with a basic feasible solution. In my examples so far, I have looked at problems that, when put into standard LP form, conveniently have an all slack starting solution. An all slack solution is only a possibility when all of the constraints in the problem have <= inequalities. Today, we are going to look at methods for dealing with LPs having other constraint types. that simplex needs a place to start – it must start from a basic feasible solution then move to another basic feasible solution to improve the objective value. With these assumptions, I can obtain an initial basic feasible solution /dictionary by letting all slack variables be basic, all original variables be non basic Obviously, these assumptions do not hold for every LP. What do I do when they don’t? When a basic feasible solution is not readily apparent, the Big M method or the two-phase simplex method may be used to solve the problem. The Big M Method If an LP has any > or = constraints, a starting basic feasible solution may not be readily apparent. The Big M method is a version of the Simplex Algorithm that first finds a basic feasible solution by adding "artificial" variables to the problem. The objective function of the original LP must, of course, be modified to ensure that the artificial variables are all equal to 0 at the conclusion of the simplex algorithm. Steps 1. Modify the constraints so that the RHS of each constraint is nonnegative (This requires that each constraint with a negative RHS be multiplied by 1. that if you multiply an inequality by any negative number, the direction of the inequality is reversed!). After modification, identify each constraint as a <, >, or = constraint. 2. Convert each inequality constraint to standard form (If constraint i is a < constraint, we add a

slack variable si; and if constraint i is a > constraint, we subtract an excess variable ei). 3. Add an artificial variable ai to the constraints identified as > or = constraints at the end of Step 1. Also add the sign restriction ai > 0. 4. If the LP is a max problem, add (for each artificial variable) -Mai to the objective function where M denote a very large positive number. 5. If the LP is a min problem, add (for each artificial variable) Mai to the objective function. 6. Solve the transformed problem by the simplex . Since each artificial variable will be in the starting basis, all artificial variables must be eliminated from row 0 before beginning the simplex. Now (In choosing the entering variable, that M is a very large positive number!). If all artificial variables are equal to zero in the optimal solution, we have found the optimal solution to the original problem. If any artificial variables are positive in the optimal solution, the original problem is infeasible!!! Let’s look at an example. Example 1 Minimize Subject to:

z =

4x1 + x2 3x1 + x2 = 3 4x1 + 3x2 >= 6 x1 + 2x2 <= 4 x1, x2 >= 0

By introducing a surplus in the second constraint and a slack in the third we get the following LP in standard form: Minimize z = Subject to:

4x1 + x2 3x1 + x2 =3 4x1 + 3x2 – S2 =6 x1 + 2x2 + s3 = 4 x1, x2, S2, s3 >= 0

Neither of the first two constraint equations has a slack variable or other variable that we can use to be basic in a feasible starting solution so we

must use artificial variables. If we introduce the artificial variables R1 and R2 into the first two constraints, respectively, and MR1 + MR2 into the objective function, we obtain: Minimize z = Subject to:

4x1 + x2 + MR1 + MR2 3x1 + x2 + R1 =3 4x1 + 3x2 – S2 + R2 =6 x1 + 2x2 + s3 = 4 x1, x2, S2, s3, R1, R2 >= 0

We can now set x1, x2 and S2 to zero and use R1, R2 and s3 as the starting basic feasible solution. In tableau form we have: Basic z R1 R2 s3

z

1 0 0 0

x1 -4 3 4 1

x2 -1 1 3 2

S2 0 0 -1 0

R1 -M 1 0 0

R2 -M 0 1 0

s3 0 0 0 1

Solution 0 3 6 4

At this point, we have our starting solution in place but we must adjust our zrow to reflect the fact that we have introduced the variables R1 and R2 with non-zero coefficients (M). We can see that if we substitute 3 and 6 into the objective function for R1 and R2, respectively, that z = 3M + 6M = 9M. In our tableau, however, z is shown to be equal to 0. We can eliminate this inconsistency by substituting out R1 and R2 in the z-row. Because each artificial variable’s column contains exactly one 1, we can accomplish this by multiplying each of the first two constraint rows by M and adding them both to the current zrow. New z-row = Old z-row + M*R1-row + M*R2-row Old z-row: + M*R1-row: (0 + M*R2-row: (0

(1 3M 4M

-4 M 3M

-1 0 –M

0 M 0

New z-row:

( 1 -4+7M –1+4M –M

-M 0 M

-M 0 0

0 3M ) 6M )

0

0

0

0)

9M)

Our tableau now becomes Basic z R1 R2 s3

z

1 0 0 0

x1 -4+7M 3 4 1

x2 -1+4M 1 3 2

S2 -M 0 -1 0

R1 0 1 0 0

R2 0 0 1 0

s3 0 0 0 1

Solution 9M 3 6 4

Now we have the expected form for our starting solution. We now apply the simplex method as before. Since this is a minimization problem we select the entering variable with the most positive objective row coefficient. In this case, that is x1. Calculating the intercept ratios we get: R1 – 3/3 = 1 R2 – 6/4 = 1.5 s3 -- 4/1 = So we select R1 as our leaving variable. Performing the Gauss-Jordan row operations, we obtain the new tableau: Basic z x1 R2 s3

z

1 0 0 0

x1 0 1 0 0

x2 (1+5M)/3 1/3 5/3 5/3

S2 -M 0 -1 0

R1 (4-7M)/3 1/3 -4/3 -1/3

R2 0 0 1 0

s3 0 0 0 1

Solution 4+2M 1 2 3

In this tableau, we can see that x2 will be our next entering variable and R2 will leave. We can thus see that the simplex algorithm will quickly remove both R1 and R2 from the solution just as we intended when we assigned them the coefficient of M in the objective function. If we continue to apply the simplex algorithm, we will find that the optimal solution is: x1 = 2/5 x2 = 9/5 S2 = 1 with z = 17/5 Two important considerations accompany use of the M method.

The use of the penalty M may not always force the artificial variable to zero level by the final iteration. This can occur in the case where the given LP has no feasible solution. If any artificial variable is positive in the final iteration than the LP has no feasible solution space. Theoretically, the application of the M technique requires that M approaches infinity but to computerize the solution algorithm, M must be finite while being “sufficiently large.” The pitfall in this case is, however, if M is too large it can lead to substantial round-off error yielding an incorrect optimal solution. For this reason, most commercial LP solvers do not apply the Mmethod but use, rather, an artificial variable method called the two-phase method. For educational purposes, TORA, allows the implementation of the Mmethod with a selected value for M where M is sufficiently large to allow solution of the problem. The definition of the term “sufficiently large” is dependent upon the problem in question and requires some judgment for implementation. Example 2 Minimise z = 2x1 -3x2 + x3 subject to 3x1 -2x2 + x3 ≤ 5, x1 +3x2 -4x3 ≤ 9, x2 +5x3 ≥ 1, x1 + x2 + x3 = 6, x1, x2, x3 ≥ 0.

Solution We obtain the linear programming problem: minimise x8 subject to 3x1 -2x2 + x3 + x4=5, x1 +3x2 -4x3 + x5=9, x1 + x2 + x3 + x6=6, - x2 -5x3 + x7=-1, -2x1 +3x2 - x3 + x8=0, x1,..., x7 ≥ 0, •

where x6 is an artificial variable. In tableau T1 of Table 1, pivoting about y33 (= 1) removes a6 from the basis. The rows of tableau T2 are then rearranged to give tableau T3 so that the bad row is below the others, and column a6 is ignored from here on. Pivoting in T3 about y12 (= 7) gives tableau T4 which has the basic feasible solution (0, 33/7, 9/7, 92/7, 0, 0, 71/7, - 90/7). This has x6 = 0 and is an optimal solution, so x1 = 0, x2 = 33/7, x3 = 9/7 is an optimal solution of the original problem with optimal value -90/7.

Min z = 2x1+3x2 s.t. 1/2x1+1/4x2 ≤ 4…………………1 x1+3x2 ≥ 20………………………2 x1+x2=10…………………………3 x1,x2 ≥ 0 Step1: Make the right hand side of all constraints positive. We don’t have any negative right hand side. Step2:Identify each constraint which is ≥ or=. Constraints 2 and 3 apply the above conditions. Step3: For each<= constraint add a slack variable and for each constraint subtract an excess variable to make them equalities. 1……………………….1/2x1+1/4x2+s1 =4 2…………………………..x1+ 3x2

-e1=20

Step4:For each>=or = constraint add an artificial variable ai(ai’s>0),which is to be chosen in the starting bfs. 2……………………….x1+3x2-e1+a2=20 3……………………….x1+x2+

+a3=10

Step5: If the LP is a min add +Mai to the objective function. If it is a max add –Mai to the objective function. Here M represents a very big number such that in the min problem +Mai is arbitrarily large so that ai the artificial variable is best to be chosen as zero, which we require . Similar reasoning applies in the max problem. Min z =2x1+3x2+Ma2+Ma3 Step6: Choose those artificial variables in the starting bfs and proceed to find the Optimal Tableau. If in the end, artificial variables

are zero we find the solution, but if they are not equal to zero then we don’t have a optimal solution. Thus, original LP is infeasible. After these steps we have the LP: Min z=2x1+3x2+Ma2+Ma3 st 1/2x1+1/4x2+s1 x1+3x2 x1+x2

=4 -e1+a2=20 +a3=10

After all, we have the table:

In the optimal solution, we have: {z,s1, x2, x1}={25,1/4,5,5}. Since we don’t have any of artificial variables a1and a2in the optimal solution, the solution is feasible. If any of the artificial variablesa1, a2were not equal to zero then we would have infeasibility as described below: Min z=x1+3x2 s.t.

1/2x1+1/4x2 ≤ 4 x1+3x2 ≥ 10 x1+x2

=10

After going through all the steps described above we end with the optimal tableau:

In the above example, we have the optimal tableau since reduced costs of all non basic variables are non positive. However note that the optimal solution contains the very big number M, which should not have been the case for a min problem, thus we say that our original LP was infeasible. We also say that from the fact that we have the artificial variablea2 in the basic variables, which shouldn’t have been the case for a feasible LP. Example 3 Maximize Z = x1 + 5x2 Subject to: 3x1 + 4x2 £ 6 x1 + 3x2 ³ 2 Where x1, x2 ³ 0 Solution Introducing slack and surplus variables 3x1 + 4x2 + x3 = 6 x1 + 3x2 – x4 = 2 Where: x3 is a slack variable x4 is a surplus variable. The surplus variable x4 represents the extra units.

Now if we let x1 and x2 equal to zero in the initial solution, we will have x3 = 6 and x4 = –2, which is not possible because a surplus variable cannot be negative. Therefore, we need artificial variables. Maximize x1 + 5x2 – MA1 Subject to: 3x1 + 4x2 + x3 = 6 x1 + 3x2 – x4 + A1 = 2 Where: x1 ³ 0, x2 ³ 0, x3 ³ 0, x4 ³ 0, A1 ³ 0

Cj

1

5

0

0

–M

CB

Basic variables B

x1

x2

x3

x4

A1

Solution values b (= XB)

0

x3

3

4

1

0

0

6

–M

A1

1

3

0

–1

1

2

–M – 1

–3M –5

0

M

0

Zj – Cj

Here, a11 = 3, a12 = 4, a13 = 1, a14 = 0, a15 = 0, b1 = 6 a21 = 1, a22 = –3, a23 = 0, a24 = –1, a25 = 1, b2 = 2 Calculating Zj – Cj First column = 0 * 3 + (–M) * 1 – 1 = –M – 1 Second column = 0 * 4 + (–M) * 3 – 5 = –3M–5 Third column = 0 * 1 + (–M) * 0 – 0 = 0 Fourth column = 0 * 0 + (–M) * (–1) – 0 = M Fifth column = 0 * 0 + (–M) * 1 – (–M) = 0 Choose the smallest negative value from Zj – Cj. Substitute M = 0 Smallest negative value is –5. So second column is the element column. Now find out the minimum positive value.

Minimum (6 / 4, 2 / 3) = 2 / 3 So second row is the element row. Here, the pivot (key) element = 3. Therefore, A1 departs and x2 enters. Calculating values for table 2 Calculating values for first row a11 = 3 – 1 * 4 / 3 = 5 /3 a12 = 4 – 3 * 4 / 3 = 0 a13 = 1 – 0 * 4 / 3 = 1 a14 = 0 – (–1) * 4 / 3 = 4 / 3 b1 = 6 – 2 * 4 / 3 = 10 / 3 Calculating values for key row a21 = 1 / 3 a22 = 3 / 3 =1 a23 = 0 / 3 = 0 a24 = –1 / 3 b2 = 2 / 3 Table 2 Cj

1

5

0

0

CB

Basic variables B

x1

x2

x3

x4

Solution values b (= XB)

0

x3

5/3

0

1

4/3

10 / 3

5

x2

1/3

1

0

–1 / 3

2/3

2/3

0

0

–5 / 3

Zj – Cj Table 3 Cj

1

5

0

0

CB

Basic variables B

x1

X2

x3

x4

Solution values b (= XB)

0

x4

5/4

0

3/4

1

5/2

5

x2

3/4

1

1/4

0

3/2

Zj – Cj

11 / 4

0

5/4

0

Since all the values of Zj – Cj are positive, this is the optimal solution. x1 = 0, x2 = 3 / 2 Z = 0 + 5 * 3 / 2 =15 / 2