CS525 - Spring 2005 - Final Exam - Solutions. Q1. >> A=[1 1; 2 -1;-1 0]; b=[-2 2 -5]'; p=[3 2]'; >> T=totbl(A,b,p); x1 x2 1 --------------------------------- x3 = | 1.0000 1.0000 2.0000 x4 = | 2.0000 -1.0000 -2.0000 x5 = | -1.0000 0.0000 5.0000 --------------------------------- z = | 3.0000 2.0000 0.0000 >> T=ljx(T,2,2); x1 x4 1 --------------------------------- x3 = | 3.0000 -1.0000 0.0000 x2 = | 2.0000 -1.0000 -2.0000 x5 = | -1.0000 -0.0000 5.0000 --------------------------------- z = | 7.0000 -2.0000 -4.0000 >> T=delcol(T,'x4'); x1 1 ---------------------- x3 = | 3.0000 0.0000 x2 = | 2.0000 -2.0000 x5 = | -1.0000 5.0000 ---------------------- z = | 7.0000 -4.0000 >> T=permrows(T,[1 3 4 2]); x1 1 ---------------------- x3 = | 3.0000 0.0000 x5 = | -1.0000 5.0000 ---------------------- z = | 7.0000 -4.0000 x2 = | 2.0000 -2.0000 % It's optimal! Solution is x=(0,-2)' ======================================================================== Q2. >> Q = [4 2; 2 2]; A=[2 2 ; 1 -1]; b=[1 -2]'; p=[-1 -2]'; M=[Q -A'; A zeros(2,2)]; q=[p;-b]; >> T=addcol(T,ones(4,1),'z0',5); ??? Error using ==> addcol label already in use >> T=lemketbl(M,q); z1 z2 z3 z4 1 ------------------------------------------------------- w1 = | 4.0000 2.0000 -2.0000 -1.0000 -1.0000 w2 = | 2.0000 2.0000 -2.0000 1.0000 -2.0000 w3 = | 2.0000 2.0000 0.0000 0.0000 -1.0000 w4 = | 1.0000 -1.0000 0.0000 0.0000 2.0000 >> T=addcol(T,ones(4,1),'z0',5); z1 z2 z3 z4 z0 1 ------------------------------------------------------------------ w1 = | 4.0000 2.0000 -2.0000 -1.0000 1.0000 -1.0000 w2 = | 2.0000 2.0000 -2.0000 1.0000 1.0000 -2.0000 w3 = | 2.0000 2.0000 0.0000 0.0000 1.0000 -1.0000 w4 = | 1.0000 -1.0000 0.0000 0.0000 1.0000 2.0000 >> T=ljx(T,2,5); z1 z2 z3 z4 w2 1 ------------------------------------------------------------------ w1 = | 2.0000 0.0000 0.0000 -2.0000 1.0000 1.0000 z0 = | -2.0000 -2.0000 2.0000 -1.0000 1.0000 2.0000 w3 = | 0.0000 0.0000 2.0000 -1.0000 1.0000 1.0000 w4 = | -1.0000 -3.0000 2.0000 -1.0000 1.0000 4.0000 >> T=ljx(T,2,2); z1 z0 z3 z4 w2 1 ------------------------------------------------------------------ w1 = | 2.0000 -0.0000 0.0000 -2.0000 1.0000 1.0000 z2 = | -1.0000 -0.5000 1.0000 -0.5000 0.5000 1.0000 w3 = | 0.0000 -0.0000 2.0000 -1.0000 1.0000 1.0000 w4 = | 2.0000 1.5000 -1.0000 0.5000 -0.5000 1.0000 >> Solution x1=z1=0, x2=z2=1, so x*=(0,1)' ======================================================================== Q3. A = [1 -2; 2 1]; b=[5 3]'; >> Aaug=[A eye(2); -A eye(2)]; baug=[b; -b]; p=[0 0 1 1]'; >> T=totbl(Aaug,baug,p); x1 x2 x3 x4 1 ------------------------------------------------------- x5 = | 1.0000 -2.0000 1.0000 0.0000 -5.0000 x6 = | 2.0000 1.0000 0.0000 1.0000 -3.0000 x7 = | -1.0000 2.0000 1.0000 0.0000 5.0000 x8 = | -2.0000 -1.0000 0.0000 1.0000 3.0000 ------------------------------------------------------- z = | 0.0000 0.0000 1.0000 1.0000 0.0000 >> T=ljx(T,1,1); x5 x2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 2.0000 -1.0000 -0.0000 5.0000 x6 = | 2.0000 5.0000 -2.0000 1.0000 7.0000 x7 = | -1.0000 0.0000 2.0000 0.0000 0.0000 x8 = | -2.0000 -5.0000 2.0000 1.0000 -7.0000 ------------------------------------------------------- z = | 0.0000 0.0000 1.0000 1.0000 0.0000 >> T=ljx(T,4,3); x5 x2 x8 x4 1 ------------------------------------------------------- x1 = | 0.0000 -0.5000 -0.5000 0.5000 1.5000 x6 = | 0.0000 0.0000 -1.0000 2.0000 0.0000 x7 = | 1.0000 5.0000 1.0000 -1.0000 7.0000 x3 = | 1.0000 2.5000 0.5000 -0.5000 3.5000 ------------------------------------------------------- z = | 1.0000 2.5000 0.5000 0.5000 3.5000 Solution: x=(1.5,0) You can do an extra pivot to find other solutions (not necessary to get full points): ======================================================================== Q4. >> A = [-1 1; 0 -1]; b= [-1 -3]'; p = [-1 0]'; q=[3 1]'; >> T=totbl(A,b,p); x1 x2 1 --------------------------------- x3 = | -1.0000 1.0000 1.0000 x4 = | 0.0000 -1.0000 3.0000 --------------------------------- z = | -1.0000 0.0000 0.0000 >> T=addrow(T,[q' 0],'z0',4); x1 x2 1 --------------------------------- x3 = | -1.0000 1.0000 1.0000 x4 = | 0.0000 -1.0000 3.0000 --------------------------------- z = | -1.0000 0.0000 0.0000 z0 = | 3.0000 1.0000 0.0000 >> % already optimal for -1+3t>=0, t>=0, i.e. t in [1/3,infty) >> % solution is x(t)=(0,0)', z(t)=0. >> T=ljx(T,1,1); x3 x2 1 --------------------------------- x1 = | -1.0000 1.0000 1.0000 x4 = | -0.0000 -1.0000 3.0000 --------------------------------- z = | 1.0000 -1.0000 -1.0000 z0 = | -3.0000 4.0000 3.0000 >> % optimal for 1-3t>=0, -1+4t>=0, i.e. t in [1/4,1/3] >> % solution is x(t)=(1,0)', z(t)=-1+3t >> T=ljx(T,2,2); x3 x4 1 --------------------------------- x1 = | -1.0000 -1.0000 4.0000 x2 = | -0.0000 -1.0000 3.0000 --------------------------------- z = | 1.0000 1.0000 -4.0000 z0 = | -3.0000 -4.0000 15.0000 >> % optimal for 1-3t>=0, 1-4t>=0, i.e. t in (-infty,1/4] >> % solution is x(t)=(4,3)', z(t)=-4+15t Summary: Range x(t) z(t) -------------------------- (-infty,1/4] (4,3)' -4+15*t [1/4,1/3] (1,0)' -1+3*t [1/3,infty) (0,0)' 0 ======================================================================== Q5. Write the dual as max -c'u s.t. A'u \le c,, u >= 0, which by using A'=-A becomes min c'u s.t. Au >= -c, u >= 0, which is just a restatement of the primal (with different notation for the variable). This problem is "self-dual". We know that the primal has a solution, say x*. This vector also solves the dual. By using strong duality (equality of the optimal objectives for primal and dual), we have c'x* = -c'x* => c'x* = 0. Hence, the optimal objective is zero.