CS525 Midterm Spring 2005: Solution. % Q1 a) A=[-1 2 -4 1; 3 -1 2 0; 1 3 -6 2]; b=[1 2 5]'; T=totbl(A,b); x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | -1.0000 2.0000 -4.0000 1.0000 -1.0000 y2 = | 3.0000 -1.0000 2.0000 0.0000 -2.0000 y3 = | 1.0000 3.0000 -6.0000 2.0000 -5.0000 T=ljx(T,1,1); y1 x2 x3 x4 1 ------------------------------------------------------- x1 = | -1.0000 2.0000 -4.0000 1.0000 -1.0000 y2 = | -3.0000 5.0000 -10.0000 3.0000 -5.0000 y3 = | -1.0000 5.0000 -10.0000 3.0000 -6.0000 T=ljx(T,2,2); y1 y2 x3 x4 1 ------------------------------------------------------- x1 = | 0.2000 0.4000 0.0000 -0.2000 1.0000 x2 = | 0.6000 0.2000 2.0000 -0.6000 1.0000 y3 = | 2.0000 1.0000 0.0000 0.0000 -1.0000 % no solutions! Dependence between rows is (row 3) = 2*(row 1) + (row 2); % % Q1 b) b=[1 2 4]'; T=totbl(A,b); x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | -1.0000 2.0000 -4.0000 1.0000 -1.0000 y2 = | 3.0000 -1.0000 2.0000 0.0000 -2.0000 y3 = | 1.0000 3.0000 -6.0000 2.0000 -4.0000 T=ljx(T,1,1); y1 x2 x3 x4 1 ------------------------------------------------------- x1 = | -1.0000 2.0000 -4.0000 1.0000 -1.0000 y2 = | -3.0000 5.0000 -10.0000 3.0000 -5.0000 y3 = | -1.0000 5.0000 -10.0000 3.0000 -5.0000 T=ljx(T,2,2); y1 y2 x3 x4 1 ------------------------------------------------------- x1 = | 0.2000 0.4000 0.0000 -0.2000 1.0000 x2 = | 0.6000 0.2000 2.0000 -0.6000 1.0000 y3 = | 2.0000 1.0000 0.0000 0.0000 0.0000 % feasible! Get solutions by setting x3, x4 arbitrary and setting % x1=1-.2*x4, x2=1-2*x3-.6*x4. More neatly, let x3=lambda and x4=mu, % then have x= (1,1,0,0)' + (0,-2,1,0)*lambda + (-.2,-.6,0,1)*mu. % % Q2. p=[1 -2 2]'; A=[-1 1 -3; -1 -4 -4; -4 -1 6]; b=[1 -3 -4]'; T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | -1.0000 1.0000 -3.0000 -1.0000 x5 = | -1.0000 -4.0000 -4.0000 3.0000 x6 = | -4.0000 -1.0000 6.0000 4.0000 -------------------------------------------- z = | 1.0000 -2.0000 2.0000 0.0000 % need phase I since this tableau is not feasible T=addcol(T,[1 0 0 0]','x0',4); x1 x2 x3 x0 1 ------------------------------------------------------- x4 = | -1.0000 1.0000 -3.0000 1.0000 -1.0000 x5 = | -1.0000 -4.0000 -4.0000 0.0000 3.0000 x6 = | -4.0000 -1.0000 6.0000 0.0000 4.0000 ------------------------------------------------------- z = | 1.0000 -2.0000 2.0000 0.0000 0.0000 T=addrow(T,[0 0 0 1 0],'z0',5); x1 x2 x3 x0 1 ------------------------------------------------------- x4 = | -1.0000 1.0000 -3.0000 1.0000 -1.0000 x5 = | -1.0000 -4.0000 -4.0000 0.0000 3.0000 x6 = | -4.0000 -1.0000 6.0000 0.0000 4.0000 ------------------------------------------------------- z = | 1.0000 -2.0000 2.0000 0.0000 0.0000 z0 = | 0.0000 0.0000 0.0000 1.0000 0.0000 T=ljx(T,1,4); x1 x2 x3 x4 1 ------------------------------------------------------- x0 = | 1.0000 -1.0000 3.0000 1.0000 1.0000 x5 = | -1.0000 -4.0000 -4.0000 0.0000 3.0000 x6 = | -4.0000 -1.0000 6.0000 0.0000 4.0000 ------------------------------------------------------- z = | 1.0000 -2.0000 2.0000 0.0000 0.0000 z0 = | 1.0000 -1.0000 3.0000 1.0000 1.0000 T=ljx(T,2,2); x1 x5 x3 x4 1 ------------------------------------------------------- x0 = | 1.2500 0.2500 4.0000 1.0000 0.2500 x2 = | -0.2500 -0.2500 -1.0000 0.0000 0.7500 x6 = | -3.7500 0.2500 7.0000 0.0000 3.2500 ------------------------------------------------------- z = | 1.5000 0.5000 4.0000 0.0000 -1.5000 z0 = | 1.2500 0.2500 4.0000 1.0000 0.2500 % phase I is optimal, but the problems is infeasible since the optimal % phase=I objective is nonzero. % Q3 p=[2 1 1]'; A=[3 2 -1; 1 1 -1; -3 -1 1]; b=[-2 1 3]'; T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 3.0000 2.0000 -1.0000 2.0000 x5 = | 1.0000 1.0000 -1.0000 -1.0000 x6 = | -3.0000 -1.0000 1.0000 -3.0000 -------------------------------------------- z = | 2.0000 1.0000 1.0000 0.0000 %scheme 2 T=ljx(T,2,3); x1 x2 x5 1 -------------------------------------------- x4 = | 2.0000 1.0000 1.0000 3.0000 x3 = | 1.0000 1.0000 -1.0000 -1.0000 x6 = | -2.0000 0.0000 -1.0000 -4.0000 -------------------------------------------- z = | 3.0000 2.0000 -1.0000 -1.0000 T=delcol(T,'x5'); x1 x2 1 --------------------------------- x4 = | 2.0000 1.0000 3.0000 x3 = | 1.0000 1.0000 -1.0000 x6 = | -2.0000 0.0000 -4.0000 --------------------------------- z = | 3.0000 2.0000 -1.0000 T=permrows(T,[1 3 4 2]); x1 x2 1 --------------------------------- x4 = | 2.0000 1.0000 3.0000 x6 = | -2.0000 0.0000 -4.0000 --------------------------------- z = | 3.0000 2.0000 -1.0000 x3 = | 1.0000 1.0000 -1.0000 At this point, you could observe that the tableau is dual feasible, but if you try a step of dual simplex, you immediately find that the dual is unbounded. hence, the primal is infeasible. Alternatively, you could try to solve using (primal) simplex. % need phase I because tableau is infeasible. T=addcol(T,[0 1 0 0]','x0',3); x1 x2 x0 1 -------------------------------------------- x4 = | 2.0000 1.0000 0.0000 3.0000 x6 = | -2.0000 0.0000 1.0000 -4.0000 -------------------------------------------- z = | 3.0000 2.0000 0.0000 -1.0000 x3 = | 1.0000 1.0000 0.0000 -1.0000 T=addrow(T,[0 0 1 0],'z0',4); x1 x2 x0 1 -------------------------------------------- x4 = | 2.0000 1.0000 0.0000 3.0000 x6 = | -2.0000 0.0000 1.0000 -4.0000 -------------------------------------------- z = | 3.0000 2.0000 0.0000 -1.0000 z0 = | 0.0000 0.0000 1.0000 0.0000 x3 = | 1.0000 1.0000 0.0000 -1.0000 T=ljx(T,2,3); x1 x2 x6 1 -------------------------------------------- x4 = | 2.0000 1.0000 0.0000 3.0000 x0 = | 2.0000 -0.0000 1.0000 4.0000 -------------------------------------------- z = | 3.0000 2.0000 0.0000 -1.0000 z0 = | 2.0000 0.0000 1.0000 4.0000 x3 = | 1.0000 1.0000 0.0000 -1.0000 % this is the optimal phase I tableau, and it has a nonzero optimal % objective, so the problem is infeasible. Q4: a) after transforming the final constraint to -x1 >= -1, we find that the dual is max u1 + 2*u2 - u3 s.t. u1 + u2 - u3 <= 1, 2*u1 - u2 <= 1 u2 <= 3, u1, u2, u3 >= 0. b) a feasible point is u=(0, 1, 0)' c) weak duality says that the dual objetcive for any dual feasible point gives a lower bound on the optimal primal objective. Hence, we obtain 2 as a lower bound on the optimal value of the primal. (In fact, better lower bounds are avaialble.) Q5. The dual is standard: max b'u s.t. A'u <= p, u >= 0. Since both are feasible, strong duality shows that both primal and dual have a solution, and their optimal values are equal. Since b>=0 and u>=0, the optimal dual value b'u is nonnegative. Hence, the optimal primal value is nonnegative.