CS525 - FINAL EXAM - MAY 12, 2003 - SOLUTIONS % Q1 p=[4 1]'; A=[2 3 ; 1 1; -1 0]; b=[-2 5 -10]'; T=totbl(A,b,p); x1 x2 1 --------------------------------- x3 = | 2.0000 3.0000 2.0000 x4 = | 1.0000 1.0000 -5.0000 x5 = | -1.0000 0.0000 10.0000 --------------------------------- z = | 4.0000 1.0000 0.0000 T=ljx(T,2,2); x1 x4 1 --------------------------------- x3 = | -1.0000 3.0000 17.0000 x2 = | -1.0000 1.0000 5.0000 x5 = | -1.0000 0.0000 10.0000 --------------------------------- z = | 3.0000 1.0000 5.0000 T=delcol(T,'x4'); x1 1 ---------------------- x3 = | -1.0000 17.0000 x2 = | -1.0000 5.0000 x5 = | -1.0000 10.0000 ---------------------- z = | 3.0000 5.0000 T=permrows(T,[1 3 4 2]); x1 1 ---------------------- x3 = | -1.0000 17.0000 x5 = | -1.0000 10.0000 ---------------------- z = | 3.0000 5.0000 x2 = | -1.0000 5.0000 % optimal tableau! solution: (x1,x2) = (0,5) with objective z=5. % % Q2 % a) dual: max b'u s.t. A'u <= p, u >= 0 % b) strong duality => b'u=0 for solution u. Since % components of b are all strictly positive, and % since u >=0, must have u=0. % c) since the solution u=0 is feasible, must have % 0 = A'u <= p. % % Q3 A=[1 -1; -2 1]; p=[1 0]'; q=[-2 -1]'; b=[-2 -4]'; T=totbl(A,b,p); x1 x2 1 --------------------------------- x3 = | 1.0000 -1.0000 2.0000 x4 = | -2.0000 1.0000 4.0000 --------------------------------- z = | 1.0000 0.0000 0.0000 T=addrow(T,[q' 0],'z0',4); x1 x2 1 --------------------------------- x3 = | 1.0000 -1.0000 2.0000 x4 = | -2.0000 1.0000 4.0000 --------------------------------- z = | 1.0000 0.0000 0.0000 z0 = | -2.0000 -1.0000 0.0000 % this tableau is optimal for 1-2t>=0, -t>=0, that is, % t in (-infty,0]. Solution is (x1,x2)=0 and z(t)=0. % as t increases above zero, reduced cost for col 2 % becomes negative. Ratio test gives row 1 as pivot row: T=ljx(T,1,2); x1 x3 1 --------------------------------- x2 = | 1.0000 -1.0000 2.0000 x4 = | -1.0000 -1.0000 6.0000 --------------------------------- z = | 1.0000 0.0000 0.0000 z0 = | -3.0000 1.0000 -2.0000 % this tableau optimal when 1-3t>=0, t>=0, that is, for % t in [0,1/3]. Solution is (x1,x2)=(0,2) with objective % z(t) = -2t. % as t increases above 1/3, first reduced cost goes negative. % Ratio test indicates that row 2 is the pivot row. T=ljx(T,2,1); x4 x3 1 --------------------------------- x2 = | -1.0000 -2.0000 8.0000 x1 = | -1.0000 -1.0000 6.0000 --------------------------------- z = | -1.0000 -1.0000 6.0000 z0 = | 3.0000 4.0000 -20.0000 % this tableau optimal when -1+3t>=0, -1+4t>=0, i.e. % for t in [1/3,infty). solution is (x1,x2)=(6,8) with % objective value z(t)=6-20t. % %Q4 % a) set (x1,x2,x3) = (-1,0,-2). lhs of constraints is % [-9, -3]. Introduce slacks x4,x5 as follows: % % x1 + 2*x2 + 4*x3 + x4 = 10, % -x1 + 3*x2 + 2*x3 - x5 = -5, % % with initial values x=(-1,0,-2,19,2) % bounds are % % lower=(-1,0,-2,0,0), % upper = (2,2,infty,infty,infty) % % objective is x4+x5. % % b) initial basic feasible point is (-1,0,-2,19,2) % %Q5 % a) min t s.t. -te <= Ax-b <= te, x>=0, where e=(1,1)'. % b) write in standard form as follows: % min [0 0 1]'(x;t) s.t. % Ax + te >= b, % -Ax + te >= -b, % x >=0, t >= 0 A=[1 1; 1 -1]; e=[1 1]'; b=[0 2]'; M=[A e; -A e]; h=[b; -b]; p=[0 0 1]'; T=totbl(M,h,p); x1 x2 x3 1 -------------------------------------------- x4 = | 1.0000 1.0000 1.0000 0.0000 x5 = | 1.0000 -1.0000 1.0000 -2.0000 x6 = | -1.0000 -1.0000 1.0000 0.0000 x7 = | -1.0000 1.0000 1.0000 2.0000 -------------------------------------------- z = | 0.0000 0.0000 1.0000 0.0000 T=ljx(T,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | 1.0000 2.0000 0.0000 2.0000 x1 = | 1.0000 1.0000 -1.0000 2.0000 x6 = | -1.0000 -2.0000 2.0000 -2.0000 x7 = | -1.0000 0.0000 2.0000 0.0000 -------------------------------------------- z = | 0.0000 0.0000 1.0000 0.0000 T=ljx(T,3,3); x5 x2 x6 1 -------------------------------------------- x4 = | 1.0000 2.0000 0.0000 2.0000 x1 = | 0.5000 0.0000 -0.5000 1.0000 x3 = | 0.5000 1.0000 0.5000 1.0000 x7 = | 0.0000 2.0000 1.0000 2.0000 -------------------------------------------- z = | 0.5000 1.0000 0.5000 1.0000 % optimal with (x1,x2)=(1,0) and optimal objective 1.