>> % Solution to 525 final, Spring 2004. >> % >> % Q1. Use dual simplex method >> A = [4 -1 2; 2 2 -1]; >> b=[4 3]'; >> p=[2 1 2]'; >> T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 4.0000 -1.0000 2.0000 -4.0000 x5 = | 2.0000 2.0000 -1.0000 -3.0000 -------------------------------------------- z = | 2.0000 1.0000 2.0000 0.0000 >> T=ljx(T,1,1); x4 x2 x3 1 -------------------------------------------- x1 = | 0.2500 0.2500 -0.5000 1.0000 x5 = | 0.5000 2.5000 -2.0000 -1.0000 -------------------------------------------- z = | 0.5000 1.5000 1.0000 2.0000 >> T=ljx(T,2,2); x4 x5 x3 1 -------------------------------------------- x1 = | 0.2000 0.1000 -0.3000 1.1000 x2 = | -0.2000 0.4000 0.8000 0.4000 -------------------------------------------- z = | 0.2000 0.6000 2.2000 2.6000 >> % optimal! Solution is x=(1.1, 0.4, 0). >> % >> % Q2. Follow procedure in the notes to set up phase I for an LP >> % in canonical form with bounds. >> % >> % min y1 + y2 s.t. >> % 2*x1 - 2*x2 + x3 + y1 = 8, >> % x1 + 6*x2 + 3*x3 + y2 = 12, >> % -5 <= x1, >> % 0 <= x2 <= 2, >> % x3 <= 3, >> % 0 <= y1 >> % 0 <= y2. >> % >> % An initial basic feasible starting point is (x1,x2,x3,y1,y2) = >> % (-5, 0, 3,15,8). >> % >> % Q3. >> % solve first for t=0: >> A = [1 -1; -1 4]; b=[0 -3]'; p=[1 2]'; >> T=totbl(A,b,p); x1 x2 1 --------------------------------- x3 = | 1.0000 -1.0000 -0.0000 x4 = | -1.0000 4.0000 3.0000 --------------------------------- z = | 1.0000 2.0000 0.0000 >> T=addrow(T,[2 -1 0],'z0',4); x1 x2 1 --------------------------------- x3 = | 1.0000 -1.0000 -0.0000 x4 = | -1.0000 4.0000 3.0000 --------------------------------- z = | 1.0000 2.0000 0.0000 z0 = | 2.0000 -1.0000 0.0000 >> % already optimal for t=0. In fact, optimal for t satisfying the conditions >> % 1+2t>=0, 2-t>=0, i.e. t in interval [-.5,2]. Solution on this interval is x=(0,0) and objective value is z(t)=0. >> % >> % as t decreases through -.5, the reduced cost is col 1 becomes negative. >> % Ratio test shows that (2,1) is the right pivot element: >> T=ljx(T,2,1); x4 x2 1 --------------------------------- x3 = | -1.0000 3.0000 3.0000 x1 = | -1.0000 4.0000 3.0000 --------------------------------- z = | -1.0000 6.0000 3.0000 z0 = | -2.0000 7.0000 6.0000 >> % this tableau is optimal for t satisfying -1-2t>=0, 6+7t>=0, >> % i.e. t in the interval [-6/7,-1/2]. Solution on this interval is x=(3,0) and objective is z(t)=3+6t. >> % >> % as t decreases through -6/7, reduced cost in col 2 becomes negative. >> % ratio test reveals no pivot rows, so the LP is unbounded for t < -6/7. >> % >> % now consider what happens as t increases through the original >> % upper bound of 2. In this case the reduced cost in the second >> % column becomes negative, and the ratio test indicates that >> % (1,2) is the appropriate pivot element. >> % >> % undo the (2,1) pivot to restore the original tableau: >> T=ljx(T,2,1); x1 x2 1 --------------------------------- x3 = | 1.0000 -1.0000 0.0000 x4 = | -1.0000 4.0000 3.0000 --------------------------------- z = | 1.0000 2.0000 0.0000 z0 = | 2.0000 -1.0000 0.0000 >> % now do the (1,2) pivot: >> T=ljx(T,1,2); x1 x3 1 --------------------------------- x2 = | 1.0000 -1.0000 0.0000 x4 = | 3.0000 -4.0000 3.0000 --------------------------------- z = | 3.0000 -2.0000 0.0000 z0 = | 1.0000 1.0000 0.0000 >> % this tableau is optimal for t satisfying the conditions 3+t>=0, -2+t>=0, >> % that is, t in the interval [2,infty). The objective in this interval >> % is just the constant 0. >> % >> % to summarize, we have the following table: >> % >> % t interval | solution | z(t) >> % (-infty,-6/7] | UNBOUNDED >> % [-6/7,-1/2] | (3,0) | 3+6t >> % [-1/2, 2] | (0,0) | 0 >> % [2, infty) | (0,0) | 0 >> % >> % (to express more compactly, can combine the last two rows of the table). >> % >> % Q4 >> % >> % 3*x1 + 2*x2 + y1 >= 5, >> % -y2 <= x1 - x2 - 2 <= y2, >> % (x1,x2,y1) >= 0, >> % >> % objective is y1+y2. To express in "general LP" form, write it as min y1+y2 s.t. 3*x1 + 2*x2 + y1 >= 5, x1 - x2 + y2 >= 2, -x1 + x2 + y2 >= -2 (x1,x2,y1) >= 0, >> % >> % Q5. Consider the following LP in standard form: (primal) min 0'x s.t. Ax >= b, x >= 0, whose dual is (dual) max b'u s.t. A' u <= 0, u >= 0. Note that the primal cannot be unbounded (since its objective is always 0, it can't go to -infty along any direction). Note that the dual is always feasible (u=0 is a feasible point). ( <= )Suppose first that there exists NO x with Ax >= b, x >= 0. Then the primal is infeasible, so strong duality tells us that the dual is either infeasible or unbounded. Since we have already noted that the dual is feasible, it must be unbounded. In particular, there exists a vector z such that b'z>0, A'z <= 0, z >= 0. ( => ) Now assume there exists a vector z with b'z>0, A'z <= 0, z >= 0. Obviously the dual is feasible in this case. If the primal were feasible too, then strong duality would tell us that both primal and dual would have solutions and that there objectives would be equal at the solutions. But the dual optimum must be strictly positive (since it is at least equal to b'z, which is strictloy positive) while the primal optimal must be zero. This is a contradiction, so the primal must NOT be feasible. Hence, there is no point x with Ax >= b, x >= 0.