CS525 - Midterm Exam Solutions - March 19, 2002. >> A = [1 1 3 2; 0 -1 0 1; 2 1 6 5]; >> b = [5;-1;6]; >> H = totbl(A,b); x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | 1.0000 1.0000 3.0000 2.0000 -5.0000 y2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 1.0000 6.0000 5.0000 -6.0000 >> H = ljx(H,1,1); y1 x2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 -1.0000 -3.0000 -2.0000 5.0000 y2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 -1.0000 0.0000 1.0000 4.0000 >> H = ljx(H,2,2); y1 y2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 1.0000 -3.0000 -3.0000 4.0000 x2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 1.0000 0.0000 0.0000 3.0000 >> % blocked! We cannot make y3 a column label. >> % problem is infeasible, since when we set y1=y2=y3=0, the last >> % row of the tableau is inconsistent. >> % If R1, R2, R3 denote the three rows of the coefficient matrix, >> % we have the dependence relationship R3 = 2*R1 + R2. >> % >> % 1 (b) >> b(3) = 9; >> H = totbl(A,b); x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | 1.0000 1.0000 3.0000 2.0000 -5.0000 y2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 1.0000 6.0000 5.0000 -9.0000 >> H = ljx(H,1,1); y1 x2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 -1.0000 -3.0000 -2.0000 5.0000 y2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 -1.0000 0.0000 1.0000 1.0000 >> H = ljx(H,2,2); y1 y2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 1.0000 -3.0000 -3.0000 4.0000 x2 = | 0.0000 -1.0000 0.0000 1.0000 1.0000 y3 = | 2.0000 1.0000 0.0000 0.0000 0.0000 >> % blocked again, but this time the system is consistent. >> % denoting x3=a, x4=b, the solutions have the form >> % (-3*a - 3*b + 4, b + 1, a, b) >> % >> % 2. Use simplex, with starting point 0 (no need for Phase I) >> p = [-1;-2;1]; >> A = [3 -1 1; -1 1 -2]; >> b = [-5;-2]; >> H = totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 3.0000 -1.0000 1.0000 5.0000 x5 = | -1.0000 1.0000 -2.0000 2.0000 -------------------------------------------- z = | -1.0000 -2.0000 1.0000 0.0000 >> H = ljx(H,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | -3.0000 2.0000 -5.0000 11.0000 x1 = | -1.0000 1.0000 -2.0000 2.0000 -------------------------------------------- z = | 1.0000 -3.0000 3.0000 -2.0000 >> % problem is unbounded! We can increase x2 without limit, while >> % decreasing the objective function and staying feasible. >> % A direction of unboundedness is (2+b, b, 0) along which the >> % objective function is -2-3*b. >> % >> % 3. Transform to >> % min x1 + 4*x2 - x3 s.t. >> % 2*x1 + 4*x2 - x3 >= 4, >> % x1 + x2 = 8, >> % -2*x1 - 6*x2 >= -18, >> % x1 free, x2>=0, x3>=0. >> p = [1;4;-1]; >> A = [2 4 -1; 1 1 0; -2 -6 0]; >> b = [4;8;-18]; >> H = 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 18.0000 -------------------------------------------- z = | 1.0000 4.0000 -1.0000 0.0000 >> % make x5 a column label, x1 a row label >> % can do this in a single pivot >> H = ljx(H,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 2.0000 -------------------------------------------- z = | 1.0000 3.0000 -1.0000 8.0000 >> % delete column corresponding to equality constraint x5 >> H = delcol(H,'x5'); x2 x3 1 --------------------------------- x4 = | 2.0000 -1.0000 12.0000 x1 = | -1.0000 -0.0000 8.0000 x6 = | -4.0000 0.0000 2.0000 --------------------------------- z = | 3.0000 -1.0000 8.0000 >> % move row for free variable x1 to bottom of tableau >> H = permrows(H,[1 3 4 2]); x2 x3 1 --------------------------------- x4 = | 2.0000 -1.0000 12.0000 x6 = | -4.0000 0.0000 2.0000 --------------------------------- z = | 3.0000 -1.0000 8.0000 x1 = | -1.0000 -0.0000 8.0000 >> % no need for Phase I; initial point x2=x3=0 is feasible. >> % Start on Phase II >> H = ljx(H,1,2); x2 x4 1 --------------------------------- x3 = | 2.0000 -1.0000 12.0000 x6 = | -4.0000 -0.0000 2.0000 --------------------------------- z = | 1.0000 1.0000 -4.0000 x1 = | -1.0000 0.0000 8.0000 >> % optimal for Phase II! >> % solution is (8,0,12) >> % >> % 4 (a). >> % Dual is >> % max 2*u1 + 6*u2 s.t. >> % u1 + 2*u2 <= 3 >> % u1 + u2 <= 2 >> % -u1 + 6*u2 <= 5 >> % u1 >=0, u2 >= 0. >> % >> % feasible point for the dual is (1,1). >> % >> % (b) Dual objective at the feasible point (1,1) is 8. By the weak >> % duality theorem, this gives a lower bound on the primal objective. >> diary off