15.093J Recitation 5 Notes

15.093 - Recitation 5 1 BT Exercise 5.5 Solution The tableau is: 0 0 c̄3 0 c̄5 1 0 1 -1 0 β 2 0 0 2 1 γ 3 1 0 4 0 δ a) The necessary and sufficient conditions for optimality are c̄3 ≥ 0 and c̄5 ≥ 0. b) Continuing the simplex method, with x3 the entering variable, x1 will leave the basis. In the new tableau, the optimal bfs is obtained; 0 0 0 0 1/4 1 0 0 β + δ/4 1/2 -1/2 0 0 1 γ − δ/2 3/4 0 1 0 δ/4 7/4 1/4 c̄5 c) If c̄3 ≥ 0 and c̄5 ≥ 0, then the current solution is optimal. Now consider the case when c̄3 < 0 or c̄5 < 0. Note any feasible solution must satisfy Ax = b, x ≥ 0 and so B −1 Ax = B −1 b for any basis B. Hence we read the followign three equations from the tableau: x2 − x3 + βx5 = 1 2x3 + x4 + γx5 = 2 x1 + 4x3 + δx5 = 3 1 (1) (2) (3) Eqn (2) tells us x3 , x4 and x5 are bounded, then eqns (1) and (3) tell us x2 and x1 , respectively, are bounded. So the polyehdron is bounded and so has an optimal cost, since it is nonempty. d) The current basis is optimal. B −1 is the last three columns of the tableau. Why? We need to ensure primal feasibility is maintained. We require B −1 (b + ǫe1 ) = B −1 b + ǫB −1 e1 = (1, 2, 3)′ + ǫ(−1, 2, 4)′ ≥ 0, which occurs iff −3/4 ≤ ǫ ≤ 1. e) Note that x1 is the third basic variable. So we have then that the new ĉB = cB +ǫe3 . Feasibility is not affected. The optimality condition is ĉ − ĉ′B B −1 A = c′ + ǫe′1 − c′B B −1 A−ǫe′3 B −1 A = c̄′ +ǫe′1 −ǫ(1, 0, 4, 0, δ) = c̄′ −ǫ(0, 0, 4, 0, δ) ≥ 0. So we require ǫ ≤ c̄3 /4, ǫ ≤ c̄5 /δ, ǫ ≥ c̄5 /δ, 2 δ > 0, δ < 0. Dantzig-Wolfe Decomposition See Bertsimas and Tsitsklis, chapter 6. 2