problem1 b3 = -5 x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | 0.0000 1.0000 1.0000 1.0000 -1.0000 y2 = | 1.0000 -1.0000 3.0000 0.0000 -2.0000 y3 = | -1.0000 -2.0000 -6.0000 -3.0000 5.0000 pivot on (2,1) y2 x2 x3 x4 1 ------------------------------------------------------- y1 = | 0.0000 1.0000 1.0000 1.0000 -1.0000 x1 = | 1.0000 1.0000 -3.0000 -0.0000 2.0000 y3 = | -1.0000 -3.0000 -3.0000 -3.0000 3.0000 pivot on (1,2) y2 y1 x3 x4 1 ------------------------------------------------------- x2 = | -0.0000 1.0000 -1.0000 -1.0000 1.0000 x1 = | 1.0000 1.0000 -4.0000 -1.0000 3.0000 y3 = | -1.0000 -3.0000 0.0000 0.0000 0.0000 blocked! Cannot pivot y3 up to the top. y3 = 0, so the system of equalities is consistent x3, x4 arbitrary => infinite number of solutions linear dependence relation: A(3,:) = -A(2,:) - 3*A(1,:) If b3 = -4 .... x1 x2 x3 x4 1 ------------------------------------------------------- y1 = | 0.0000 1.0000 1.0000 1.0000 -1.0000 y2 = | 1.0000 -1.0000 3.0000 0.0000 -2.0000 y3 = | -1.0000 -2.0000 -6.0000 -3.0000 4.0000 pivot on (2,1) y2 x2 x3 x4 1 ------------------------------------------------------- y1 = | 0.0000 1.0000 1.0000 1.0000 -1.0000 x1 = | 1.0000 1.0000 -3.0000 -0.0000 2.0000 y3 = | -1.0000 -3.0000 -3.0000 -3.0000 2.0000 pivot on (1,2) y2 y1 x3 x4 1 ------------------------------------------------------- x2 = | -0.0000 1.0000 -1.0000 -1.0000 1.0000 x1 = | 1.0000 1.0000 -4.0000 -1.0000 3.0000 y3 = | -1.0000 -3.0000 0.0000 0.0000 -1.0000 blocked! Cannot pivot y3 up to the top. y3 = -1, so the system of equalities is inconsistent and there are no solutions. problem2 x1 x2 x3 1 -------------------------------------------- y1 = | -2.0000 1.0000 3.0000 -1.0000 y2 = | -1.0000 -2.0000 -1.0000 4.0000 y3 = | 1.0000 2.0000 -1.0000 -3.0000 Setting up phase 1: x1 x2 x3 x0 1 ------------------------------------------------------- y1 = | -2.0000 1.0000 3.0000 1.0000 -1.0000 y2 = | -1.0000 -2.0000 -1.0000 0.0000 4.0000 y3 = | 1.0000 2.0000 -1.0000 1.0000 -3.0000 x1 x2 x3 x0 1 ------------------------------------------------------- y1 = | -2.0000 1.0000 3.0000 1.0000 -1.0000 y2 = | -1.0000 -2.0000 -1.0000 0.0000 4.0000 y3 = | 1.0000 2.0000 -1.0000 1.0000 -3.0000 z0 = | 0.0000 0.0000 0.0000 1.0000 0.0000 pivot on (3,4) x1 x2 x3 y3 1 ------------------------------------------------------- y1 = | -3.0000 -1.0000 4.0000 1.0000 2.0000 y2 = | -1.0000 -2.0000 -1.0000 0.0000 4.0000 x0 = | -1.0000 -2.0000 1.0000 1.0000 3.0000 z0 = | -1.0000 -2.0000 1.0000 1.0000 3.0000 pivot on (3,2) x1 x0 x3 y3 1 ------------------------------------------------------- y1 = | -2.5000 0.5000 3.5000 0.5000 0.5000 y2 = | 0.0000 1.0000 -2.0000 -1.0000 1.0000 x2 = | -0.5000 -0.5000 0.5000 0.5000 1.5000 z0 = | 0.0000 1.0000 0.0000 0.0000 0.0000 Done with phase 1, so the current tableau is feasible and we can read off a solution: x1 = 0 x2 = 1.5 x3 = 0 Since the bottom row has zeros, we can pivot on one of those columns, and come up with another feasible point. For example, we can pivot on (1,1): y1 x0 x3 y3 1 ------------------------------------------------------- x1 = | -0.4000 0.2000 1.4000 0.2000 0.2000 y2 = | -0.0000 1.0000 -2.0000 -1.0000 1.0000 x2 = | 0.2000 -0.6000 -0.2000 0.4000 1.4000 z0 = | -0.0000 1.0000 0.0000 0.0000 0.0000 The solution here is: x1 = .2 x2 = 1.4 x3 = 0 Since I can find two solutions, there must be an infinite number of solutions. % Midterm II - Problem 1 % (a) H=totbl(A,b,p,-3); x1 x2 x3 1 -------------------------------------------- x4 = | 1.0000 0.0000 -1.0000 1.0000 x5 = | 0.0000 -1.0000 0.0000 2.0000 x6 = | 1.0000 1.0000 1.0000 1.0000 -------------------------------------------- z = | 1.0000 0.0000 -3.0000 -3.0000 H=ljx(H,3,1); x6 x2 x3 1 -------------------------------------------- x4 = | 1.0000 -1.0000 -2.0000 0.0000 x5 = | 0.0000 -1.0000 0.0000 2.0000 x1 = | 1.0000 -1.0000 -1.0000 -1.0000 -------------------------------------------- z = | 1.0000 -1.0000 -4.0000 -4.0000 % x1 = x6-x2-x3-1; H = delcol(H,'x6');H=delrow(H,'x1'); x2 x3 1 --------------------------------- x4 = | -1.0000 -2.0000 0.0000 x5 = | -1.0000 0.0000 2.0000 --------------------------------- z = | -1.0000 -4.0000 -4.0000 H=ljx(H,1,2); x2 x4 1 --------------------------------- x3 = | -0.5000 -0.5000 0.0000 x5 = | -1.0000 -0.0000 2.0000 --------------------------------- z = | 1.0000 2.0000 -4.0000 % (x1,x2,x3)=(-1,0,0), z=4 % (b) The optimal solution is unique because % 1. the bottom row of the final optimal tableau has positive coefficients % 2. ( x2=x6=0 ) => (x1=-x3-1) => (x1=-1) because x3=0. % Midterm II - Problem 2 % (a) % Dual Formulation max u1 + 2u2 - u3 s.t. u1 + u2 - u3 <= 1 2u1 - u2 <= 1 u2 <= 1 u1, u2, u3 >= 0 % A feasible point: u=(u1,u2,u3)=(0,1,0), w(u)=2 % (b) % A lower bound to the primal problem = 2 from % part (a) & Weak Duality theorem % (c) Any feasible primal point gives upper bound for the (optimal) % objective value: x=(x1,x2,x3)=(1,0,1), z(x) = 2