>> % 1. >> A = [1 3 -2 1; 0 2 0 1; 3 7 -6 2]; >> b = [1;2;1]; >> H = totbl(A,b); x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | 1.0000 3.0000 -2.0000 1.0000 -1.0000 y2 = | 0.0000 2.0000 0.0000 1.0000 -2.0000 y3 = | 3.0000 7.0000 -6.0000 2.0000 -1.0000 >> H = ljx(H,1,1); y1 x2 x3 x4 1 ------------------------------------------------------- x1 = | 1.0000 -3.0000 2.0000 -1.0000 1.0000 y2 = | 0.0000 2.0000 0.0000 1.0000 -2.0000 y3 = | 3.0000 -2.0000 0.0000 -1.0000 2.0000 >> H = ljx(H,2,4); y1 x2 x3 y2 1 ------------------------------------------------------- x1 = | 1.0000 -1.0000 2.0000 -1.0000 -1.0000 x4 = | -0.0000 -2.0000 -0.0000 1.0000 2.0000 y3 = | 3.0000 0.0000 0.0000 -1.0000 0.0000 >> % blocked! Cannot make y3 a column label >> % but the tableau is consistent and the linear system has >> % infinitely many solutions. Using a to represent the value of x2 >> % and b to represent x3, the solutions have the form >> % x = (-a + 2*b -1, a, b, -2*a + 2) >> % The rows of the original tableau are dependent. >> % Using R1, R2, R3 to represent rows 1,2,3 of the matrix, we have that >> % R3 = 3*R1 - R2. >> % >> % 2. Multiply the 2nd and 3rd constratints by -1 to get >= constraints. >> A = [-1 1 -3; -1 -4 -4; -4 -1 6]; >> p = [1 -2 3]'; >> b = [1 -3 -4]'; >> H = 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 3.0000 0.0000 >> % need a phase I >> H = addcol(H,[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 3.0000 0.0000 0.0000 >> H = addrow(H,[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 3.0000 0.0000 0.0000 z0 = | 0.0000 0.0000 0.0000 1.0000 0.0000 >> % special pivot first: >> H = ljx(H,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 3.0000 0.0000 0.0000 z0 = | 1.0000 -1.0000 3.0000 1.0000 1.0000 >> H = ljx(H,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 5.0000 0.0000 -1.5000 z0 = | 1.2500 0.2500 4.0000 1.0000 0.2500 >> % problem is infeasible! At the end of phase I, the objective >> % z0 is strictly positive. >> % >> % 3. Need to transform this problem to form suitable >> % for Phase II: >> % (NB In this solution, we did NOT use the suggested transformation >> % of x2; hence, more than 3 pivots are required.) >> % >> % min -x1 + x2 - x3 - 3 s.t. >> % >> % -x1 + x2 - 4*x3 >= 0 >> % x1 - x2 = -1 >> % x1 + x3 >= -2 >> % x2 >= 4 >> % x1, x2 free, x3 >= 0 >> % >> A = [-1 1 -4; 1 -1 0; 1 0 1; 0 1 0]; >> b = [0; -1; -2; 4]; >> p = [-1; 1; -1]; >> H = totbl(A,b,p,-3); x1 x2 x3 1 -------------------------------------------- x4 = | -1.0000 1.0000 -4.0000 -0.0000 x5 = | 1.0000 -1.0000 0.0000 1.0000 x6 = | 1.0000 0.0000 1.0000 2.0000 x7 = | 0.0000 1.0000 0.0000 -4.0000 -------------------------------------------- z = | -1.0000 1.0000 -1.0000 -3.0000 >> % x5 an equality constraint; x1 and x2 free. >> % do initial Jordan exchanges to make x1, x2 row labels, and x5 a >> % column label >> H = ljx(H,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | -1.0000 0.0000 -4.0000 1.0000 x1 = | 1.0000 1.0000 -0.0000 -1.0000 x6 = | 1.0000 1.0000 1.0000 1.0000 x7 = | 0.0000 1.0000 0.0000 -4.0000 -------------------------------------------- z = | -1.0000 0.0000 -1.0000 -2.0000 >> H = ljx(H,3,2); x5 x6 x3 1 -------------------------------------------- x4 = | -1.0000 0.0000 -4.0000 1.0000 x1 = | 0.0000 1.0000 -1.0000 -2.0000 x2 = | -1.0000 1.0000 -1.0000 -1.0000 x7 = | -1.0000 1.0000 -1.0000 -5.0000 -------------------------------------------- z = | -1.0000 0.0000 -1.0000 -2.0000 >> % delete the x5 column >> H = delcol(H,'x5'); x6 x3 1 --------------------------------- x4 = | 0.0000 -4.0000 1.0000 x1 = | 1.0000 -1.0000 -2.0000 x2 = | 1.0000 -1.0000 -1.0000 x7 = | 1.0000 -1.0000 -5.0000 --------------------------------- z = | 0.0000 -1.0000 -2.0000 >> % pivot the x1 and x2 rows to the bottom >> H = permrows(H, [1 4 5 2 3]); x6 x3 1 --------------------------------- x4 = | 0.0000 -4.0000 1.0000 x7 = | 1.0000 -1.0000 -5.0000 --------------------------------- z = | 0.0000 -1.0000 -2.0000 x1 = | 1.0000 -1.0000 -2.0000 x2 = | 1.0000 -1.0000 -1.0000 >> % Need to do Phase I of simplex. Introduce artificial row and col >> H = addcol(H,[0 1 0 0 0]','x0',3); x6 x3 x0 1 -------------------------------------------- x4 = | 0.0000 -4.0000 0.0000 1.0000 x7 = | 1.0000 -1.0000 1.0000 -5.0000 -------------------------------------------- z = | 0.0000 -1.0000 0.0000 -2.0000 x1 = | 1.0000 -1.0000 0.0000 -2.0000 x2 = | 1.0000 -1.0000 0.0000 -1.0000 >> H = addrow(H,[0 0 1 0],'z0',6); x6 x3 x0 1 -------------------------------------------- x4 = | 0.0000 -4.0000 0.0000 1.0000 x7 = | 1.0000 -1.0000 1.0000 -5.0000 -------------------------------------------- z = | 0.0000 -1.0000 0.0000 -2.0000 x1 = | 1.0000 -1.0000 0.0000 -2.0000 x2 = | 1.0000 -1.0000 0.0000 -1.0000 z0 = | 0.0000 0.0000 1.0000 0.0000 >> H = ljx(H,2,3); x6 x3 x7 1 -------------------------------------------- x4 = | 0.0000 -4.0000 0.0000 1.0000 x0 = | -1.0000 1.0000 1.0000 5.0000 -------------------------------------------- z = | 0.0000 -1.0000 0.0000 -2.0000 x1 = | 1.0000 -1.0000 0.0000 -2.0000 x2 = | 1.0000 -1.0000 0.0000 -1.0000 z0 = | -1.0000 1.0000 1.0000 5.0000 >> H = ljx(H,2,1); x0 x3 x7 1 -------------------------------------------- x4 = | -0.0000 -4.0000 0.0000 1.0000 x6 = | -1.0000 1.0000 1.0000 5.0000 -------------------------------------------- z = | -0.0000 -1.0000 0.0000 -2.0000 x1 = | -1.0000 0.0000 1.0000 3.0000 x2 = | -1.0000 0.0000 1.0000 4.0000 z0 = | 1.0000 0.0000 0.0000 0.0000 >> % phase I finished; delete row and column >> H = delcol(H,'x0'); x3 x7 1 --------------------------------- x4 = | -4.0000 0.0000 1.0000 x6 = | 1.0000 1.0000 5.0000 --------------------------------- z = | -1.0000 0.0000 -2.0000 x1 = | 0.0000 1.0000 3.0000 x2 = | 0.0000 1.0000 4.0000 z0 = | 0.0000 0.0000 0.0000 >> H = delrow(H,'z0'); x3 x7 1 --------------------------------- x4 = | -4.0000 0.0000 1.0000 x6 = | 1.0000 1.0000 5.0000 --------------------------------- z = | -1.0000 0.0000 -2.0000 x1 = | 0.0000 1.0000 3.0000 x2 = | 0.0000 1.0000 4.0000 >> % continue with Phase II >> H = ljx(H,1,1); x4 x7 1 --------------------------------- x3 = | -0.2500 0.0000 0.2500 x6 = | -0.2500 1.0000 5.2500 --------------------------------- z = | 0.2500 0.0000 -2.2500 x1 = | -0.0000 1.0000 3.0000 x2 = | -0.0000 1.0000 4.0000 >> % solved! Solution is x = (3,4,1/4); >> % The solution is not unique. We can increase x7 as much as we like >> % away from zero, without affecting the value of z and staying feasible. >> % Using a to denote the value of x7, we can say that all points of the >> % form x = (3+a, 4+a, 1/4) are solutions, for all a>=0. >> % >> % 4. We put this problem in a form to which the duality transformation of Section 4.6 can be applied: min x1 + x2 - x3 s.t. -x1 - x2 >= -1 5*x2 + x3 >= 3 x1 + x2 + x3 = 1 x1,x2>=0 We can now write the dual as max -u1 + 3*u2 + u3 s.t. -u1 + u3 <= 1 -u1 + 5*u2 + u3 <= 1 u2 + u3 = -1; u1,u2 >= 0. A feasible point is u = (0,1/5,-6/5) (b) The dual objective at the dual feasible point is 3/5 - 6/5 = -3/5. By weak duality, this is a lower bound on the optimal objective of the primal. (c) An upper bound on the primal objective can be found by finding a point x that is feasible for the primal, and evalauting the primal objective at this point. We see that x=(0,1,-2) is feasible , and the primal objective at this points is 3, giving an upper bound. By strong duality, since we have found feasible points for both primal and dual, then both primal and dual problems have an optimal solution, and their objective values are the same.