15 093 Recitation 3 Michael Frankovich and Shubham Gupta September 25 2009 1 Simplex Full Tableau method Example 1 Solve the following problem using the full tableau method min s t x1 x2 x1 x2 2 x1 x2 0 x1 x2 0 Solution We rst rewrite the problem in standard form using slack variables min s t x1 x2 x1 x2 s1 2 x1 x2 s2 0 x1 x2 s1 s2 0 For the initial tableau we choose the slack variables to be the basic variables 0 1 1 0 0 s1 2 1 1 1 0 s2 0 1 1 0 1 The solution in this tableau is not optimal because we have negative reduced costs Select x1 as the entering variable Then we have 2 and s1 will leave the basis The next tableau is 2 0 x1 2 1 s2 2 0 0 1 2 1 1 1 0 0 1 The solution in this tableau is optimal since all reduced costs are nonnegative Notice however that there is a nonbasic variable with zero reduced cost which indicates that there may be another optimal solution Let s see what happens if we go back and choose x2 as the entering variable instead of x1 Again here is the initial tableau 1 Thanks Allison Chang for previous notes 1 0 1 1 0 0 s1 2 1 1 1 0 s2 0 1 1 0 1 If x2 enters the basis then 0 and s2 leaves This is a case in which degeneracy causes the simplex method to choose the same basic feasible solution with di erent basis of course 0 2 0 0 1 s1 2 2 0 1 1 x2 0 1 1 0 1 The solution is not optimal and we choose x1 to enter the basis Then 1 and s1 leaves the basis The next tableau is 2 0 x1 1 1 x2 1 0 0 0 1 1 0 1 2 1 2 1 2 1 2 So we have found the other optimal solution and we can see that c 4 0 again indicates that the solution may not be unique What if the objective function is x1 The initial tableau is 0 1 s1 2 1 s2 0 1 0 1 1 0 1 0 0 0 1 This solution is already optimal and we have c 2 0 However the 0 which means we do not have multiple optimal solutions in this case Example 2 Solve the following linear programming problem by full tableau simplex min s t 15x1 7x1 7x1 x1 x1 x1 0 x2 0 13x2 6x2 3x2 x2 2x2 84 63 4 2 Solution First put the problem in standard form min s t 15x1 13x2 7x1 6x2 7x1 3x2 x1 x2 x1 2x2 x1 x2 s1 s2 s3 s4 0 s1 s2 s3 84 63 4 s4 2 For the initial tableau we choose the slack variables as basic variables 2 0 15 13 0 0 0 0 s1 84 7 6 1 0 0 0 s2 63 7 3 0 1 0 0 s3 4 1 1 0 0 1 0 s4 2 1 2 0 0 0 1 Not optimal x1 enters the basis and s4 leaves 30 s1 70 s2 49 s3 2 x1 2 0 43 0 0 0 15 0 20 1 0 0 7 0 17 0 1 0 7 0 1 0 0 1 1 1 2 0 0 0 1 Still not optimal x2 enters and s3 leaves 116 s1 30 s2 15 x2 2 x1 6 0 0 0 0 1 0 43 28 0 20 13 1 17 10 0 1 1 0 2 1 0 0 0 1 0 0 1 0 0 0 28 0 10 1 13 10 1 0 10 1 0 10 1 0 10 Almost done s4 enters and s2 leaves 158 s1 21 2 s4 32 x2 72 x1 15 2 0 0 0 0 1 0 0 0 1 0 181 s3 5 s4 10 x2 7 x1 6 0 0 0 0 1 46 0 21 10 0 21 17 0 21 1 1 3 1 0 7 1 21 13 21 20 21 13 2 7 23 5 21 10 17 10 7 10 3 10 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 And nally s3 s4 x2 s2 182 18 30 14 21 1 6 13 6 10 3 7 6 7 2 13 0 6 1 0 6 1 0 3 1 1 6 0 12 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 Our nal solution is x1 x2 s1 s2 s3 s4 0 14 0 21 18 30 If we draw the feasible region of the original problem we will nd that the simplex method traverses through every extreme point before it hits the optimal one However if at the rst pivot we choose x2 to enter then after one pivot we are done 3 2 Exercise While solving a standard form problem we arrive at the following tableau with x3 x4 and x5 being the basic variables 10 2 0 0 0 4 1 1 0 0 1 4 0 1 0 3 0 1 0 The entries are unknown parameters For each one of the following state ments nd some parameter values that will make the statement true a The current solution is optimal and there are multiple optimal bases b The optimal cost is c The current solution is feasible but not optimal Solution a Let 0 0 0 0 0 With these choices if we let x2 enter the basis we obtain 3 0 and we stay at the same feasible solution The resulting reduced costs turn out to be nonnegative implying optimality b Let 0 0 0 If we attempt to bring x1 into the basis we see that the optimal cost is c Let 0 Nonoptimality is seen if we bring x2 into the basis 4 MIT OpenCourseWare http ocw mit edu 15 093J 6 255J Optimization Methods Fall 2009 For information about citing these materials or our Terms of Use visit http ocw mit edu terms 1