>> % 1. Solve using dual simplex >> A = [3 1 -1; 1 -1 2; 1 2 1]; >> b = [-1 3 2]'; >> p = [1 3 4]'; >> H = totbl(A,b,p); x1 x2 x3 1 -------------------------------------------- x4 = | 3.0000 1.0000 -1.0000 1.0000 x5 = | 1.0000 -1.0000 2.0000 -3.0000 x6 = | 1.0000 2.0000 1.0000 -2.0000 -------------------------------------------- z = | 1.0000 3.0000 4.0000 0.0000 >> H = ljx(H,2,1); x5 x2 x3 1 -------------------------------------------- x4 = | 3.0000 4.0000 -7.0000 10.0000 x1 = | 1.0000 1.0000 -2.0000 3.0000 x6 = | 1.0000 3.0000 -1.0000 1.0000 -------------------------------------------- z = | 1.0000 4.0000 2.0000 3.0000 >> % solution already! x = (3,0,0), objective = 3. 2. The steps (Dx^k, Dy^k, Ds^k) satisfy the following equations: A Dx^k = -(A x^k - b) A' Dy^k + Ds^k = -(A' y^k + s^k - c) Hence we have A x^{k+1} - b = A (x^k + alpha_k Dx^k) - b = (A x^k - b) + alpha_k A Dx^k = (A x^k - b) - alpha_k (A x^k - b) = (1-alpha_k) (A x^k - b) A similar argument shows that A' y^{k+1} + s^{k+1} - c = (1-alpha_k) (A' y^k + s^k - c) 3. (i) The dual is max b'u subject to A'u <= c B'u <= d u >= 0. (ii) Since A >= I and u >= 0, we have A'u >= u. Hence from the first constraint in the dual, and the property c <= 0, we have 0 <= u <= A'u <= c <= 0, which implies that u=0 and c=0. (iii) We are told that the primal has a solution, so by strong duality, the dual has a solution and the optimal primal and dual objectives are equal. Hence, the optimal primal is equal to b'0 = 0. 4. Use the technique from the revised simplex chapter. Set each of the variables x1, x2, x3 at one of its bounds, for example x1=-1, x2 = 0, x3 = -1. Evaluating the left-hand side of the constraints, we have x1 + 3*x2 + 4*x3 = -5 < 10; -x1 + 2*x2 + x3 = 0 > -5; So add artificial variables x4, x5 with x4 >=0, x5 >=0 as follows: x1 + 3*x2 + 4*x3 + x4 = 10 -x1 + 2*x2 + x3 - x5 = -5 and choose the initial basic feasible solution x = (-1,0,-1,15,5) (Note that this is basic, since just two of the variables are away from their bounds.) The phase-I objective is x4 + x5. >> % 5. >> Q = [4 2; 2 2]; p = [-1 -1]'; >> A = [1 2]; b = [2]; >> M = [Q -A'; A 0] M = 4 2 -1 2 2 -2 1 2 0 >> q=[p; -b] q = -1 -1 -2 >> H = lemketbl(M,q); z1 z2 z3 1 -------------------------------------------- w1 = | 4.0000 2.0000 -1.0000 -1.0000 w2 = | 2.0000 2.0000 -2.0000 -1.0000 w3 = | 1.0000 2.0000 0.0000 -2.0000 >> % add artificial column >> H = addcol(H,[1 1 1]','z0',4); z1 z2 z3 z0 1 ------------------------------------------------------- w1 = | 4.0000 2.0000 -1.0000 1.0000 -1.0000 w2 = | 2.0000 2.0000 -2.0000 1.0000 -1.0000 w3 = | 1.0000 2.0000 0.0000 1.0000 -2.0000 >> % special first pivot (Phase I) >> H = ljx(H,3,4); z1 z2 z3 w3 1 ------------------------------------------------------- w1 = | 3.0000 0.0000 -1.0000 1.0000 1.0000 w2 = | 1.0000 0.0000 -2.0000 1.0000 1.0000 z0 = | -1.0000 -2.0000 -0.0000 1.0000 2.0000 >> % w3 became nonbasic; choose z3 as pivot column >> H = ljx(H,2,3); z1 z2 w2 w3 1 ------------------------------------------------------- w1 = | 2.5000 0.0000 0.5000 0.5000 0.5000 z3 = | 0.5000 0.0000 -0.5000 0.5000 0.5000 z0 = | -1.0000 -2.0000 0.0000 1.0000 2.0000 >> % w2 became nonbasic; choose z2 as pivot column >> H = ljx(H,3,2); z1 z0 w2 w3 1 ------------------------------------------------------- w1 = | 2.5000 -0.0000 0.5000 0.5000 0.5000 z3 = | 0.5000 -0.0000 -0.5000 0.5000 0.5000 z2 = | -0.5000 -0.5000 0.0000 0.5000 1.0000 >> % complementary tableau! Solution is z=(0,1,1/2), that is, >> % x = (0,1). Objective is 0. >> diary off