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 −x1 − x2 s.t. x1 + x2 ≤ 2 −x1 + x2 ≤ 0 x1, x2 ≥ 0 Solution. We first rewrite the problem in standard form using slack variables: min −x1 − x2 s.t. 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 0 1 0 x1 = 2 1 1 1 0 s2 = 2 0 2 1 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: 1Thanks Allison Chang for previous notes. 10 −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 different 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 0 1 0 x1 = 1 1 0 1/2 −1/2 x2 = 1 0 1 1/2 1/2 So we have found the other optimal solution, and we can see that ¯c4 = 0 again indicates that the solution may not be unique. What if the objective function is x1? The initial tableau is: 0 1 0 0 0 s1 = 2 1 1 1 0 s2 = 0 −1 1 0 1 This solution is already optimal and we have ¯c2 = 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 −15x1 − 13x2 s.t. 7x1 + 6x2 84≤7x1 + 3x2 63≤ −x1 + x2 ≥ −4 x1 2x2 2− ≤ x1 ≥ 0, x2 ≥ 0 Solution. First put the problem in standard form: min −15x1 − 13x2 s.t. 7x1 + 6x2 +s1 = 84 7x1 + 3x2 +s2 = 63 x1 − x2 +s3 = 4 x1 − 2x2 +s4 = 2 x1, x2, s1, s2, s3, s4 ≥ 0 For the initial tableau, we choose the slack variables as basic variables: 20 −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 0 −43 0 0 0 15 s1 = 70 0 20 1 0 0 −7 s2 = 49 0 17 0 1 0 −7 s3 = 2 0 1∗ 0 0 1 −1 x1 = 2 1 −2 0 0 0 1 Still not optimal: x2 enters and s3 leaves. 116 0 0 0 0 43 −28 s1 = 30 0 0 1 0 −20 13 s2 = 15 0 0 0 1 −17 10∗ x2 = 2 0 1 0 0 1 −1 x1 = 6 1 0 0 0 2 −1 Almost done: s4 enters and s2 leaves. 158 s1 = 21 2 s4 = 3 2 x2 = 7 2 x1 = 15 2 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 28 10 −13 10 1 10 1 10 1 10 −23 5 21 10 ∗ −17 10 − 7 10 3 10 0 0 1 0 0 181 s3 = 5 s4 = 10 x2 = 7 x1 = 6 0 0 46 21 − 1 21 0 0 0 10 21 −13 21 1 0 0 17 21 −20 21 0 0 1 1 3 −1 3 0 1 0 −1 7 2 7 ∗ 0 0 0 1 0 0 182 s3 = 18 s4 = 30 x2 = 14 s2 = 21 1 6 13 6 10 3 7 6 7 2 0 0 0 1 0 13 6 1 6 1 3 1 6 −1 2 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 And finally... Our final 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 find that the simplex method traverses through every extreme point before it hits the optimal one. However, if at the first 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 0 1 The entries α, β, γ, δ, η are unknown parameters. For each one of the following state-ments, find 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. 4MIT OpenCourseWarehttp://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.