Solution to CS525 Midterm, Spring 2003. >> % Q1. >> A=[1 1 -3; 2 -1 1; -2 7 -15]; >> b=[3 2 -1]'; >> T=totbl(A,b); x1 x2 x3 1 -------------------------------------------- y1 = | 1.0000 1.0000 -3.0000 -3.0000 y2 = | 2.0000 -1.0000 1.0000 -2.0000 y3 = | -2.0000 7.0000 -15.0000 1.0000 >> T=ljx(T,1,1); y1 x2 x3 1 -------------------------------------------- x1 = | 1.0000 -1.0000 3.0000 3.0000 y2 = | 2.0000 -3.0000 7.0000 4.0000 y3 = | -2.0000 9.0000 -21.0000 -5.0000 >> T=ljx(T,2,2); y1 y2 x3 1 -------------------------------------------- x1 = | 0.3333 0.3333 0.6667 1.6667 x2 = | 0.6667 -0.3333 2.3333 1.3333 y3 = | 4.0000 -3.0000 0.0000 7.0000 >> % blocked! Cannot exchange y3 with any x variables - >> % the only possible candidate is x3, and there is a zero >> % pivot in this position. >> % >> % the system is infeasible, since the right-hand side element >> % that corresponds to the y variable that remains as a column label >> % is not zero. >> % >> % Dependence between rows of the coefficient matrix is reflected im >> % the dependence between the y variables. We have >> % >> % (row 3) = 4*(row 1) - 3*(row 2) >> % >> % >> % Q2. >> A=[-2 1 -1; 2 1 -2]; >> p=[-1 3 1]'; >> b=[1 -4]; >> T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | -2.0000 1.0000 -1.0000 -1.0000 x5 = | 2.0000 1.0000 -2.0000 4.0000 -------------------------------------------- z = | -1.0000 3.0000 1.0000 0.0000 >> % tableau not feasible; need Phase I >> newcol=[1 0 0]; >> newcol=[1 0 0]'; >> T=addcol(T,newcol,'x0',4); x1 x2 x3 x0 1 ------------------------------------------------------- x4 = | -2.0000 1.0000 -1.0000 1.0000 -1.0000 x5 = | 2.0000 1.0000 -2.0000 0.0000 4.0000 ------------------------------------------------------- z = | -1.0000 3.0000 1.0000 0.0000 0.0000 >> newrow=[0 0 0 1 0]; >> T=addrow(T,newrow,'z0',4); x1 x2 x3 x0 1 ------------------------------------------------------- x4 = | -2.0000 1.0000 -1.0000 1.0000 -1.0000 x5 = | 2.0000 1.0000 -2.0000 0.0000 4.0000 ------------------------------------------------------- z = | -1.0000 3.0000 1.0000 0.0000 0.0000 z0 = | 0.0000 0.0000 0.0000 1.0000 0.0000 >> % initial pivot for Phase 1 >> T=ljx(T,1,4); x1 x2 x3 x4 1 ------------------------------------------------------- x0 = | 2.0000 -1.0000 1.0000 1.0000 1.0000 x5 = | 2.0000 1.0000 -2.0000 0.0000 4.0000 ------------------------------------------------------- z = | -1.0000 3.0000 1.0000 0.0000 0.0000 z0 = | 2.0000 -1.0000 1.0000 1.0000 1.0000 >> % continue with Phase 1 >> T=ljx(T,1,2); x1 x0 x3 x4 1 ------------------------------------------------------- x2 = | 2.0000 -1.0000 1.0000 1.0000 1.0000 x5 = | 4.0000 -1.0000 -1.0000 1.0000 5.0000 ------------------------------------------------------- z = | 5.0000 -3.0000 4.0000 3.0000 3.0000 z0 = | 0.0000 1.0000 0.0000 0.0000 0.0000 >> % Phase 1 complete; delete row and column >> T=delcol(T,'x0'); x1 x3 x4 1 -------------------------------------------- x2 = | 2.0000 1.0000 1.0000 1.0000 x5 = | 4.0000 -1.0000 1.0000 5.0000 -------------------------------------------- z = | 5.0000 4.0000 3.0000 3.0000 z0 = | 0.0000 0.0000 0.0000 0.0000 >> T=delrow(T,'z0'); x1 x3 x4 1 -------------------------------------------- x2 = | 2.0000 1.0000 1.0000 1.0000 x5 = | 4.0000 -1.0000 1.0000 5.0000 -------------------------------------------- z = | 5.0000 4.0000 3.0000 3.0000 >> % No need for Phase 2 as this tableau is optimal. >> % solution is (x1,x2,x3)=(0,1,0) with objective z=3. >> % >> % >> % Q3. >> % convert the <= constraint to >= constraint by multiplying both >> % sides by -1; >> % -2*x1 -6*x2 >= -16 >> % convert objective to a "min" by multiplying by -1: >> % min x1 + 4*x2 - x3 >> % now construct initial tableau >> A=[2 4 -1; 1 1 0; -2 -6 0]; >> b=[4 8 -16]'; >> p=[1 4 -1]'; >> T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 2.0000 4.0000 -1.0000 -4.0000 x5 = | 1.0000 1.0000 0.0000 -8.0000 x6 = | -2.0000 -6.0000 0.0000 16.0000 -------------------------------------------- z = | 1.0000 4.0000 -1.0000 0.0000 >> % want to pivot the equality constraint slack x5 to the top of >> % tableau and delete it. Want to pivot the free variable x1 to the >> % side of the tableau, then shift it to the bottom. We can achieve >> % both these goals in a single pivot: >> T=ljx(T,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | 2.0000 2.0000 -1.0000 12.0000 x1 = | 1.0000 -1.0000 -0.0000 8.0000 x6 = | -2.0000 -4.0000 0.0000 0.0000 -------------------------------------------- z = | 1.0000 3.0000 -1.0000 8.0000 >> T=delcol(T,'x5'); x2 x3 1 --------------------------------- x4 = | 2.0000 -1.0000 12.0000 x1 = | -1.0000 -0.0000 8.0000 x6 = | -4.0000 0.0000 0.0000 --------------------------------- z = | 3.0000 -1.0000 8.0000 >> T=permrows(T,[1 3 4 2]); x2 x3 1 --------------------------------- x4 = | 2.0000 -1.0000 12.0000 x6 = | -4.0000 0.0000 0.0000 --------------------------------- z = | 3.0000 -1.0000 8.0000 x1 = | -1.0000 -0.0000 8.0000 >> % now proceed with two-phase simplex. In fact, we don't need Phase 1 >> % because the tableau is feasible. So proceed with Phase 2: >> T=ljx(T,1,2); x2 x4 1 --------------------------------- x3 = | 2.0000 -1.0000 12.0000 x6 = | -4.0000 -0.0000 0.0000 --------------------------------- z = | 1.0000 1.0000 -4.0000 x1 = | -1.0000 0.0000 8.0000 >> % this tableau is optimal;. We can read off the solution as follows: >> % (x1,x2,x3)=(8,0,12). The optimal objective is z=4 (note that we have >> % to switch the sign of the objective, to reverse the original >> % transformation from a max to a min. >> % >> % >> % Q4. >> A=[-2 1 1; 1 -1 -2]; >> b=[2 -3]'; >> p=[1 2 2 ]'; >> T=totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | -2.0000 1.0000 1.0000 -2.0000 x5 = | 1.0000 -1.0000 -2.0000 3.0000 -------------------------------------------- z = | 1.0000 2.0000 2.0000 0.0000 >> % tableau is dual feasible, so can start dual simplex method >> % immediately. >> T=ljx(T,1,2); x1 x4 x3 1 -------------------------------------------- x2 = | 2.0000 1.0000 -1.0000 2.0000 x5 = | -1.0000 -1.0000 -1.0000 1.0000 -------------------------------------------- z = | 5.0000 2.0000 0.0000 4.0000 >> % this tableau is optimal, with solution >> % (x1,x2,x3)=(0,2,0) >> % Although the questions doesn't ask for this, we could explore the >> % space of solutions by performing further pivots. Pivoting on >> % column 3 we obtain >> T=ljx(T,2,3); x1 x4 x5 1 -------------------------------------------- x2 = | 3.0000 2.0000 1.0000 1.0000 x3 = | -1.0000 -1.0000 -1.0000 1.0000 -------------------------------------------- z = | 5.0000 2.0000 -0.0000 4.0000 >> % which gives another solution (x1,x2,x3)=(0,1,1). >> % If we pivot on column 3 again, we recover the first vertex solution. >> % We conlcude that there are exactly two vertex solutions, and that >> % all points on the line joining these two vertices are also solutions. >> % >> % >> % >> % Q5. >> % a. >> % Dual is >> % max -u1 + 3*u2 - v1 subject to >> % -u1 + v1 <= 1, >> % -u1 + 5*u2 + v1 <= 1, >> % u2 + v1 = -1. >> % (u1,u2) >=0, v1 free. >> % >> % b. >> % a dual feasible point is (u1,u2,v1)=(0,0,-1), with objective >> % value 1. >> % >> % c. from (b) and using weak duality, 1 is a lower bound on the >> % optimal objective of the primal. >> %