Math 340 Assignment #2 Due Wednesday Feb 10, 2016 at the beginning of class. 1. Give an example of a dictionary for which the current basic feasible solution is optimal and yet the coefficients of the non-basic variables in the z row are not all negative. 2. Take your final dictionary to your Quiz 2 after corrections if any are required (if you haven't picked it up remember to do so) and verify the revised simplex formulas. Namely identify B, AN , cB , cN , xB , xN and then compute B 1 and the z row using z = cTB B 1 b + (cTN cTB B 1 AN )xN and then the remaining equations as xB = B 1 b B 1 AN xN . If you move the non basics to the left of the equations, the matrix B 1 can be read off as the coefficients of slack variables. Of course you don't have to change the dictionary and can do this directly but then the columns are either the negative of the coefficients of a slack variable if it is non-basic variable (recall xB = B 1 b B 1 An xN ) and an appropriate column of a single 1 if the slack variable is a basic variable. 3. Theorem 5.5 is taken from page 65-66 of V. Chvatal's book on Linear Programming. Consider the LP: n cx maximize Pn j=1 j j subject to a x j=1 ij j bi xj 0 P (i = 1, 2, . . . m) (5.24) (j = 1, 2, . . . , n) Theorem 5.5. If (5.24) has at least one non-degenerate basic feasible optimal solution, then there is a positive \u000f with the property: If |ti | \u000f for all i = 1, 2, . . . , m, then the problem n maximize j=1 cj xj Pn subject to j=1 aij xj bi + ti xj 0 P (i = 1, 2, . . . m) (5.25) (j = 1, 2, . . . , n) has an optimal solution and its optimal value equals z + Pm i=1 yi ti standing for the with z standing for the optimal value of (5.24) and with y1 , y2 , . . . , ym optimal solution of its dual. Now consider the following LP max 12x1 4x1 x1 2x1 +20x2 +6x2 +(7/2)x2 +4x2 +18x3 +8x3 +2x3 +3x3 600 300 550 x1 , x2 , x3 0 The final dictionary is: x1 x2 x6 z = 75/2 2x3 = 75 = 175 +x3 = 1950 6x3 (7/16)x4 +(1/8)x4 +(3/8)x4 (11/4)x4 Does Theorem 5.5 apply here? +(3/4)x5 (1/2)x5 +(1/2)x5 x5 optimal basis B 1 {x1 , x2 , x6 } x4 x5 x6 x1 7/16 3/4 0 1/2 0 = x2 1/8 x6 3/8 1/2 1 For what value of \u000f (choose the largest possible for this particular data!) is the theorem true? In this case I will offer you an hint about computing \u000f. Hint: If you have been given an inequality 3t1 5t2 5 which must hold for any choices t1 , t2 satisfying \u000f t1 \u000f and \u000f t2 \u000f, then we deduce that \u000f 5/8. 4. Consider our two phase method in the case that the LP is infeasible. We begin with the primal LP max z Ax b . x0 We introduce an artificial variable x0 and obtain the new LP (in Phase 1) max x \u0014 0 \u0015 x [1 | A] 0 b , x x0 0, x 0, where (1) is the vector of -1's and we use [1 | A] to denote the matrix obtained from A by adding one more column (of all -1's) on the left. We assume the maximum value of the objective function in the new LP is strictly negative. (In general this would depend on whether the original LP is infeasible; we assume the original LP is infeasible) a) Derive the dual of the new LP. Verify that an optimal dual solution will verify (certify?) that the inequalities above do not have any feasible solution. Namely explain why y T A 0T , y 0, by <0 2