Midterm Spring 2004 Solution. A=[-1 3 5; 1 1 -1; -1 7 9]; b=[1 2 4]'; T=totbl(A,b); x1 x2 x3 1 -------------------------------------------- y1 = | -1.0000 3.0000 5.0000 -1.0000 y2 = | 1.0000 1.0000 -1.0000 -2.0000 y3 = | -1.0000 7.0000 9.0000 -4.0000 T=ljx(T,1,1); y1 x2 x3 1 -------------------------------------------- x1 = | -1.0000 3.0000 5.0000 -1.0000 y2 = | -1.0000 4.0000 4.0000 -3.0000 y3 = | 1.0000 4.0000 4.0000 -3.0000 T=ljx(T,2,2); y1 y2 x3 1 -------------------------------------------- x1 = | -0.2500 0.7500 2.0000 1.2500 x2 = | 0.2500 0.2500 -1.0000 0.7500 y3 = | 2.0000 1.0000 0.0000 0.0000 % Blocked! No more useful pivots are possible. % The tableau represents a feasible solution, since the right-hand side % element corresponding to the remaining dependent variable y3 is zero. % solutions have the form (x1,x2,x3)=(1.25+2 lambda, .75 - lambda, lambda), % for any lambda. (Infinitely many solutions.) % % row dependency: row3 = 2*row1 + row2 4 points for tableau 6 points for pivots 6 points for description of solution 4 points for row dependency %Q2. A=[-1 1 -1; 1 -1 2]; b=[-8 -6]'; p=[-1 -1 2]'; T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | -1.0000 1.0000 -1.0000 8.0000 x5 = | 1.0000 -1.0000 2.0000 6.0000 -------------------------------------------- z = | -1.0000 -1.0000 2.0000 0.0000 % feasible tableau; go straight to phase 2 T=ljx(T,1,1); x4 x2 x3 1 -------------------------------------------- x1 = | -1.0000 1.0000 -1.0000 8.0000 x5 = | -1.0000 0.0000 1.0000 14.0000 -------------------------------------------- z = | 1.0000 -2.0000 3.0000 -8.0000 % Problem is unbounded! We can increase x2 away from 0 without limit. % setting x2=lambda, we have (x1,x2,x3)=(8+lambda,lambda,0) for lambda>=0, % which is (x1,x2,x3) = (8,0,0) + lambda*(1,1,0). So the direction of % unboundedness is (1,1,0) 5 points for tableau 8 points for pivots 7 points for unbounded direction and conclusion %Q3 A=[2 -3 1; 7 -10 1]; p=[4 6 2]'; b=[4 9]'; T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 2.0000 -3.0000 1.0000 -4.0000 x5 = | 7.0000 -10.0000 1.0000 -9.0000 -------------------------------------------- z = | 4.0000 6.0000 2.0000 0.0000 % Scheme II: pivot x4 to the top (equality constraint) and x3 to the side % (free variable). Can do this with a single Jordan exchange: T=ljx(T,1,3); x1 x2 x4 1 -------------------------------------------- x3 = | -2.0000 3.0000 1.0000 4.0000 x5 = | 5.0000 -7.0000 1.0000 -5.0000 -------------------------------------------- z = | 0.0000 12.0000 2.0000 8.0000 % delete x4 column, move x3 row to the bottom: T=delcol(T,'x4'); x1 x2 1 --------------------------------- x3 = | -2.0000 3.0000 4.0000 x5 = | 5.0000 -7.0000 -5.0000 --------------------------------- z = | 0.0000 12.0000 8.0000 T=permrows(T,[2 3 1]); x1 x2 1 --------------------------------- x5 = | 5.0000 -7.0000 -5.0000 --------------------------------- z = | 0.0000 12.0000 8.0000 x3 = | -2.0000 3.0000 4.0000 % Now start on simplex. Tableau is not feasible, so we need a Phase 1. T=addcol(T,[1 0 0]','x0',3); x1 x2 x0 1 -------------------------------------------- x5 = | 5.0000 -7.0000 1.0000 -5.0000 -------------------------------------------- z = | 0.0000 12.0000 0.0000 8.0000 x3 = | -2.0000 3.0000 0.0000 4.0000 T=addrow(T,[0 0 1 0],'z0',3); x1 x2 x0 1 -------------------------------------------- x5 = | 5.0000 -7.0000 1.0000 -5.0000 -------------------------------------------- z = | 0.0000 12.0000 0.0000 8.0000 z0 = | 0.0000 0.0000 1.0000 0.0000 x3 = | -2.0000 3.0000 0.0000 4.0000 % "special" pivot for phase 1: T=ljx(T,1,3); x1 x2 x5 1 -------------------------------------------- x0 = | -5.0000 7.0000 1.0000 5.0000 -------------------------------------------- z = | 0.0000 12.0000 0.0000 8.0000 z0 = | -5.0000 7.0000 1.0000 5.0000 x3 = | -2.0000 3.0000 0.0000 4.0000 % continue with phase 1 T=ljx(T,1,1); x0 x2 x5 1 -------------------------------------------- x1 = | -0.2000 1.4000 0.2000 1.0000 -------------------------------------------- z = | -0.0000 12.0000 0.0000 8.0000 z0 = | 1.0000 0.0000 0.0000 0.0000 x3 = | 0.4000 0.2000 -0.4000 2.0000 % phase 1 complete! Delete the artificial column and the phase-1 cost row T=delcol(T,'x0'); x2 x5 1 --------------------------------- x1 = | 1.4000 0.2000 1.0000 --------------------------------- z = | 12.0000 0.0000 8.0000 z0 = | 0.0000 0.0000 0.0000 x3 = | 0.2000 -0.4000 2.0000 T=delrow(T,'z0'); x2 x5 1 --------------------------------- x1 = | 1.4000 0.2000 1.0000 --------------------------------- z = | 12.0000 0.0000 8.0000 x3 = | 0.2000 -0.4000 2.0000 % This tableau is feasible for phase 2 as well, no more pivots needed! % solution is (x1,x2,x3)=(1,0,2) with optimal objective 8. % 4 points for initial tableau 6 points for scheme II 6 points for phase 1 4 points for conclusion %Q4 % (a) Translating this problem into "general" form we obtain % min 2*x1 + x2 - x3 s.t. % -x1 - x2 >= -1 % 6*x2 + x3 >= 3, % 2*x1 + x2 + x3 = -2, % (x1,x2)>=0, x3 free. % % The dual is % % max -u1 + 3*u2 -2* u3 s.t. % -u1 + 2*u3 <=2, % -u1 + 6*u2 + u3 <= 1, % u2 + u3 = -1, % (u1,u2) >=0, u3 free. % % (b) A feasible point is (0,0,-1) with objective 2. % % (c) By weak duality, 2 is a lower bound on the optimal objective. % 4 points for general form of primal in (a) 8 points for dual in (a) 4 points for (b) 4 points for (c) >> % Q5 >> % (a) >> A=[1 1 -1; 2 1 6]; b=[-1 6]'; p=[3 2 9]'; >> T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 1.0000 1.0000 -1.0000 1.0000 x5 = | 2.0000 1.0000 6.0000 -6.0000 -------------------------------------------- z = | 3.0000 2.0000 9.0000 0.0000 >> T=ljx(T,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | 0.5000 0.5000 -4.0000 4.0000 x1 = | 0.5000 -0.5000 -3.0000 3.0000 -------------------------------------------- z = | 1.5000 0.5000 0.0000 9.0000 >> % optimal tableau! Solution is (x1,x2,x3)=(3,0,0). >> % >> % (b) Can get another vertex solution by pivoting on the zero-reduced-cost >> % column - column 3: >> T=ljx(T,1,3); x5 x2 x4 1 -------------------------------------------- x3 = | 0.1250 0.1250 -0.2500 1.0000 x1 = | 0.1250 -0.8750 0.7500 0.0000 -------------------------------------------- z = | 1.5000 0.5000 -0.0000 9.0000 >> % gives solution (x1,x2,x3) = (0,0,1) >> % Can get a third solution by taking a convex combination of the first two >> % (1/2) * (3,0,0) + (1/2) * (0,0,1) = (3/2,0,1/2). 10 points for (a) 10 points for (b)