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 = cBT B-1b + (cNT - cBT B-1AN )xN and then the remaining equations as xB = B-1b - B-1AN 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-1b - B-1AN 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. Chva´tal's book on Linear Programming. Consider the LP:
maximize j=1∑n cjxj
subject to j=1∑n aijxj ≤ bi (i = 1, 2, . . . m) (5.24)
xj ≥ 0 (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 s with the property: If |ti| ≤ ∈ for all i = 1, 2, . . . , m, then the problem
maximize j=1∑n cjxj
subject to j=1∑n aijxj ≤ bi + ti (i = 1, 2, . . . m) (5.25)
xj ≥ 0 (j = 1, 2, . . . , n)
has an optimal solution and its optimal value equals
z* + i=1∑m yi*ti
with z* standing for the optimal value of (5.24) and with y1*, y2*, . . . , ym* standing for the optimal solution of its dual.
Now consider the following LP
max 12x1 +20x2 +18x3
4x1 +6x2 +8x3 ≤ 600
x1 +(7/2)x2 +2x3 ≤ 300 x1, x2, x3 ≥ 0
2x1 +4x2 +3x3 ≤ 550
The final dictionary is:
x1 = 75/2 -2x3 -(7/16)x4 +(3/4)x5
x2 = 75 +(1/8)x4 -(1/2)x5
x6 = 175 +x3 +(3/8)x4 +(1/2)x5 {x1, x2, x6}
z = 1950 -6x3 -(11/4)x4 -x5
optimal basis
Does Theorem 5.5 apply here?
For what value of s (choose the largest possible for this particular data!) is the theorem true? In this case I will offer you an hint about computing ∈. Hint: If you have been given any choice inequality 3t1 - 5t2 ≤ 5 which must hold for any choices t1, t2 satisfying -∈ ≤ t1 ≤ ∈ and
-∈ ≤ t2 ≤ ∈, then we deduce that ∈ ≤ 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 .
x ≥ 0
We introduce an artificial variable x0 and obtain the new LP (in Phase 1)
max -x0
[-1 |A] [x0x] ≤ b ,
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
yT A ≥ 0T , y ≥ 0 , b · y < 0
will show that there is no feasible solution to the original LP.
b) Verify that for an optimal dual solution (the magic coefficients!) y = (y1, y2, . . . , ym)T we have y1 + y2 + · · · + ym = 1.
5.
a) Extend the standard theorem of the alternative as follows. Let A be an m × n matrix and b be an m × 1 vector. Let u be an n × 1 vector (of upper bounds). Prove that either:
i) there exists an x with Ax ≤ b, x ≤ u
or
ii) there exists vectors y, z with AT y + z = 0, y, z ≥ 0, b · y + u · z < 0
but not both.
You may use the dual introduced in Assignment 1, question 5 to handle free variables.
b) Use a) to show that the following system of equalities with bounded variables given below has no solution. You can guess y, z for the given data:
-x1 -x2 ≤ -6
-x1 +x2 ≤ -8
x1 -2x2 ≤ 3
x1 ≤ 4
x2 ≤ 2