bigM

Figure 1Mathematics 236 The Big-M Method: What if you cannot find an initial Basic Feasible Sol ution? (Reference: Winston, fourth ed., Section 4.12) An example to illustrate the difficulty: Suppose we had the linear programming problem of minimizing z = 4x1 + 5x2 subject to the constraints (1) x1 + 2x2 > 10; (2) 2x1 + 3x2 < 60; and x1, x2 both nonnegative. The feasible region is shown in Figure 1. Note that the origin is not in the feasible region. Suppose we start to solve this using the Simplex Algorithm: we would convert the problem to one in standard form, rewriting the constraints as (1) x1 + 2x2 -e1 = 10, and (2) 2x1 + 3x2 +s2 = 60, with all of x1, x2, e1, and s2 nonnegative. Next, we would set up the data table:. z x1 x2e1 s2RHS Note that we cannot get an initial basic feasible solution (because the coefficient of e1 is -1, not +1). If we made it a +1 be multiplying Row 1 (or constraint 1) by -1, the RHS would become -10, and this is no good. (ALL RHS’s must be > 0 for the Simplex Algorithm to work.)1 -4 -5 0 0 0 0 1 2 -1 0 10 0 2 3 0 1 60 We’re stuck! Remember the very first step in the Simpl ex Procedure was “Get an initial basic feasible solution.” The way we get around this problem is to “expand the fea sible region” by embedding it into a higher dimensional space. This is done by introducing one or more Artificial Variables – these come from new, additional dimensions that are purely figments of our imagination. We introduce one such variable for every constraint that causes us difficulty. In the present case, the “problem constraint” is the f irst one, x1 + 2x2 > 10; so we introduce the artificial variable A1, changing the constraint to (1 revised) x1 + 2x2 + A1 > 10, with A1 > 0 also. After having done this, our (revised) problem is: Math 236: Big M method page 2 Mimimize z = 4x1 + 5x2 , subject to the constraints (1) x1 + 2x2 + A1 > 10; (2) 2x1 + 3x2 < 60; with all of x1, x2 , A1 nonnegative. Figure 2: Expanded Feasible RegionYou can think of our “Expanded Feasible Region” as being in 3-d space. (Figure 2) It is the 3- dimensional region bounded by the two planes coming towards us; the “back wall (where A1 = 0) and the floor (where x2 = 0) . The “Real Feasible Region” is the part of the expanded region that is ON the back wall. Let’s try to solve this using the Simplex Method. Con vert to standard form (introduce e1 and s2); and then set up our data table. We get z x1 x2A1e1 s2RHS 1 -4 -5 0 0 0 0 0 1 2 1 -1 0 10 0 2 3 0 0 1 60 This is a “proper Simplex Tableau”: the two basic variables are A1 and s2. Moreover, since the goal is to MINIMIZE z, this appears to be an optimal solution. Th e solution is x1 = x2 = 0; A1 =10, e1 = 0 (it’s non-basic) and s2 = 60. Here, z = 0. The only problem with this is that it is not TRULY a feasible solution. The point where x1 = x2 = 0 is not part of the feasible region for our “real problem”. What’s gone wrong? It is this: we have introduced th is artificial dimension, and we know that when A1 = 0, we are in the “real feasible region”. However, our st ated goal of minimizing 4x1 + 5x2 includes NO INCENTIVE for us to make A1 equal to zero. There is no reason, in this “expanded problem”, for us to try to get to the back wall ( the real feasible region). The way we will deal with this is to provide an incentive for A1 to be zero. Or, to be more precise, we’ll levy a tax, a PENALTY, if we are at a place where A1 is non-negative. The more non- negativc A1 is, the bigger the penalty will be. Math 236: Big M method page 3 We revise the objective function, so our goal becomes Minimize z = 4x1 + 5x2 + (penalty term) = 4x1 + 5x2 + MA1 where M represents a “Monstrously Large Positive Number ”. How big will M be? Think of how many hamburgers MacDonald’s has made. Think of the deficit of the USA. Multiply the two – if we took M to be that value, it should be big enough to make us want A1 equal to zero. If not, we’ll take M to be even bigger. We don’t need to specify in advance what the value of M is: just think of it as a “Monstrously Large Positive Number”. Note: we want to make sure the penalty for having A1 not zero is truly a penalty and not a reward. Therefore, we must MAKE SURE THE PENALTY TERM works opposite to the goal we seek. For example, if the problem had been to MAXIMIZE z = 4x1 + 5x2 , we don’t want to add MA1 , we’d want to subtract it making our revised goal Maximize z = 4x1 + 5x2 - MA1 Returning to the problem at hand, it is now Minimize z = 4x1 + 5x2 + MA1 subject to the constraints (1) x1 + 2x2 + A1 > 10; and (2) 2x1 + 3x2 < 60, with all of x1, x2 , A1 nonnegative. Let’s try to solve this problem using the Simplex Algor ithm. As usual, we would put it in standard form (introduce exce ss, slack variables as needed); then set up the initial data table. This is what we get .... z x1 x2A1e1 s2RHS Note that this is not a “Proper Simplex tableau”. We want A1 and s2 to be basic variables, so we need a zero in the z-row, in each of these columns. To get this, we ...1 -4 -5 -M 0 0 0 0 1 2 1 -1 0 10 0 2 3 0 0 1 60 adjust the z row: Add multiples of the CONSTRAINT rows to the z-row to get 0 in the A1 column. Here, the operation we need to do is Row 0 <------- Row 0 + M(Row 1) 1 -4+M -5+2M 0 -M 0 10 M Adjusted row 0 1 2 1 -1 0 10 same 0 2 3 0 0 1 60 same Math 236: Big M method page 4 This is not optimal (we are minimizing), so we pivot. The pivot column is the x2 column; (remember that M = BIG POSITIVE number). The row ratios are 10/2 and 60/3; the pivot row is Row 1. The boxed element marked is the pivot element. Now we pivot. The operations we have to do are Row 0 <— (Row 0) + (5-2M)/2 (Row 1) (ugghhh !! - but do no t panic!) Row 1 <— (½)(Row 1) Row 2<— (Row 2) - (3/2)(Row 1) z x1 x2A1e1 s2RHS 1 - 3/2* 0 5/2-M - 5/2 0 25* * details: In the x1 column: -4+M +(5-2M)/2 *(1) = -4+M +5/2 - M = (-8+5)/2 = - 3/2 and in the RHS column: 10 M +(5-2M)/2*(10) = 10M +25 - 10M = 250 1/2 1 1/2 -1/2 0 5 0 1/2 0 -3/2 3/2 1 45 This is optimal. The basic variables here are x2 and s2 . The optimal solution to our problem is x1 = 0 (non basic); x2 = 5; A1 = e1 = 0 (non-basic); and s2 = 45. The minimum attainable z-value is z= 25. Check your work!! Are these numbers consistent with the original equati ons? (1) Is x1 + 2x2 + A1- e1 = 10? LHS = 0+ 2(5) + 0 - 0 = 10 = RHS. Good! (2) 2x1 + 3x2 +s2 = 60 ? LHS = 2(0) + 3(5) + 45 = 60 = RHS. Good again! Finally, does the z-value work out? At this point, z = 4x1 + 5x2 - MA1 = 4(0) + 5(5)-M(0) = 25. If these had NOT worked out, we’d know we’d made an error somewhere. When do we NEED to introduce artificial variables? We need to introduce a new artificial variable or va riables in two cases:whenever we have a > constraint (with nonnegative RHS). As in the example above, we needed to replace x1 + 2x2 > 10 by x1 + 2x2 + A1 > 10.whenever we have an equality constraint. For example, if we had the constraint 7x1 + 8x2 - 6x3 = 16; we’d to replace it by 7x1 + 8x2 - 6x3 + A’ = 16, where A ’is a new artificial variable. Of course, we’d need to add a penalty term to z, the objective function, for each artificial variable. For example:Maximizing: new z = (old z) minus (penalty term) = ( old z) - MA1 - MA2 - ....Minimizing: new z = (old z) plus (penalty term) = ( old z) + MA1 + MA2 + .... Math 236: Big M method page 5 Summary of the Big M Method (compare with page 174, Winston)introduce a new artificial variable for each > constraint and each equality constraint. Make sure ALL these new variables are nonnegative, too;modify the objective function to include the right kind of penalty term for each artificial variable introduced;convert the (revised) problem to standard form; then set up the initial data table;in your initial simplex tableau, EACH artificial variable will be basic. (Some others may be basic, too.) DON’T FORGET to adjust the z-row to get 0 in the z-r ow in each column coming from an artificial variable. Once all these preparations have been done, proceed as normal. NOTE - initially all the artificial variables will be basic. Most of the time, the initial pivots will (on e by one) choose an artificial variable as the pivot column . After pivoting, this artificial variable will become non-basic (and so have the value = zero at the current BF solution). Once an artificial variable becomes non-basic, there s hould NEVER be a reason to bring it back into the basis. THEREFORE, it will never become non-zero again . We can forget about it. ONCE AN ARTIFICIAL VARIABLE LEAVES THE BASIS IT IS SAFE TO DELETE THAT VARIABLE FROM THE PROBLEM. Just cross out the column for that variabl e. Math 236: Big M method page 6 Computational Note for Hand Calculations As we saw in the example above, hand calculations get m essy when the objective row has “M-terms”. A way to make the work less cumbersome is to split the z-row into two parts: a non-M part and an M-part, and work with each part separately. Here’s how to re-do the calculations this way. Our fi rst data table is z x1 x2A1e1 s2RHS We could just leave the 0M terms blank Again, this is not a “Proper Simplex tableau”. We want A1 and s2 to be basic variables, so we need a zero in the z-row, in each of these columns. To get this, we ...1 -4 -5 0 0 0 0 +0M +0M +0M -M +0M +0M +0M 0 1 2 1 -1 0 10 0 2 3 0 0 1 60 Adjust the z row: Add multiples of the CONSTRAINT rows to the z-row to get 0 in the A1 column. Here, the operation we need to do is Row 0 <------- Row 0 + M(Row 1) 1 -4 -5 0 0 Row 0 +M +2M -M 10 M + M(Row 1) 0 1 2 1 -1 0 10 same 0 2 3 0 0 1 60 same This is not optimal (we are minimizing), so we pivot. The pivot column is the x2 column; (remember that M = BIG POSITIVE number); The row ratios are 10/ 2 and 60/3; the pivot row is Row 1. The boxed element the pivot element. Now we pivot. The operations we perform are: Row 0 <— (Row 0) + (5/2)(Row 1) -(M)(Row 1) Row 1 <— (½)Row 1 Row 2<— (Row 2) - (3/2)(Row 1) z x1 x2A1e1 s2RHS Work on the separate parts of Row 0: 1 - 3/2 0 5/2 - 5/2 0 25 Row 0 +(5/2) (Row 1) ... -M ... -M(Row 1) 0 1/2 1 1/2 -1/2 0 5 0 3/2 0 -3/2 3/2 1 45 Again, this is optimal (since M>>0). The solution is x1 = 0 (non basic); x2 = 5, and the optmal z-value is z= 25. The other variables have values e1 = 0 (non-basic); s2 = 45 and A1 = 0 . Because A1 is zero, this solution is “truly feasible”. Math 236: Big M method page 7 Worked Example: The Bevco Problem ( Pages 172-177, Winston t ext.) Your job is to fill in the blank spaces in the tableaux bel ow. Original Problem: Minimize z = 2x1 + 3x2 subject to (1/2) x1 +(1/4) x2 < 4 x1 + 3x2 > 20 x1 + x2 = 10 and x1, x2 nonnegative Revised Problem in Standard Form: Minimize z = 2x1 + 3x2 + MA2 + MA3 subject to (1/2) x1 +(1/4) x2 +s1 = 4 x1 + 3x2 -e2 + A2 = 20 x1 + x2 +A3 = 10 and x1, x2, e2 , A2 , A3 nonnegative Our first data table. We can avoid having to recopy t he constraint rows. z x1x2s1e2A2A3 RHS 1 -2 -3 0 0 0 0 0 Original Row 0 -M -M 1 0 0 0 Revised Row 0 = Row 0 ... ... +M(Row 2) + M(Row 3) 0 1/2 1/4 1 0 0 0 4 0 1 3** 0 -1 1 0 20 0 1 1 0 0 0 1 10 This isn’t optimal. (Why not?) The pivot column is the Column. And the row ratios are ______, ________, and ______. The pivot row is Row _________________ . After our first pivot, the tableau is ... Row 0 + Row 2 - (4/3)M Row 2 Row 1 -(1/4)(1/3) Row 2 (1/3) Row 2 Row 3 - (1/3) Row 2 continued .... Math 236: Big M method page 8 Your answer should be this: z x1x2s1e2A2A3RHS 1 -1 + 0 0 -1 1 0 20 2/3 M 1/3 M -4/3 M +10/3 M Row Ratios 0 5/12 0 1 1/12 -1/12 0 7/3 0 1/3 1 0 -1/3 1/3 0 20/3 0 2/3 0 0 1/3 -1/3 1 10/3 Note the following.z has improved (decreased) from 30M to 20 + 10/3 M A2 is now a non-basic variable, so we could delete the A2 column. That’s why it’s shaded. This isn’t optimal. Do you see why? The pivot col is the ______________ column. (We are minimizing so we want the most POSITIVE / NEGATIVE z-row coefficient. ) The pivot row is ________________________ Our next tableau is ... 1 -1/2 1/2 Row 0 + 3/2(Row 3) 0 0 - M -M (Row 3) 0 0 0 1 1/8 Row 1 -(5/12)(3/2)Row 3 = Row 1 -5/8 Row 3 0 0 1 0 -1/2 1/2 -1/2 15/3 Row 2 - (½) Row 3 0 1 0 0 1/2 -1/2 3/2 5 (3/2) Row 3 The top row would be read as z x1x2s1e2A2A3 RHS 1 0 0 0 -1/2 ½ -M 3/2 -M 25 All the z-row coefficients (except z’s) are negative or zero, so we are at an optimal solution. The optimal z-value is 25, and it is attained at the pla ce where x1 = 5 and x2 = 5.