DSES DQE Question on Deterministic OR

John Mitchell

Question: Consider the linear programming problem

min x1 + x2 + x3 + 4x4 + 3x5 s.t. - x1 + x3 + 3x4 - x5 = b1 x1 + x2 - x5 = b2 (P) 2x2 + x3 + 2x4 + x5 = b1 + 2b2 xi ≥ 0, i = 1,...,5.

In what follows, assume that the problem (P) has an optimal solution x¯, where x¯1, ¯x2 and ¯x3 are basic. You do not need to find ¯x.

  1. What is the dual to this linear program?
  2. Use complementary slackness to find an optimal solution ¯y to the dual problem.
  3. Looking purely at the optimal dual solution you found above, can you conclude that no optimal primal solution will have x4 > 0? What about x5?
  4. The optimal dual solution ¯y is not unique: there are other optimal solutions of the form ¯y+λ[-1,-2, 1]T . What is the largest possible value of λ? Do these other optimal solutions imply anything about the values of ¯x1, ¯x2 and ¯x3? Do they imply anything about the values of x4 and x5 in any optimal solution to (P)?

Answer:

  1. max b1y1 + b2y2 + (b1 + 2b2)y3 subject to - y + y ≤ 1 1 2 y2 + 2y3 ≤ 1 y1 + y3 ≤ 1 3y1 + 2y3 ≤ 4 - y1 - y2 + y3 ≤ 3

  2. Since there is an optimal basic feasible solution (bfs) with x1, x2 and x3 basic, there must be an optimal dual solution where the first three constraints hold at equality. Thus, we find an optimal dual solution by solving the equations
    - y1 + y2 = 1 y2 + 2y3 = 1 y1 + y3 = 1

    Solving these equations gives ¯y 1 = 2, y¯ 2 = 3, ¯y 3 = -1. It can be verified that this solution is dual feasible.

  3. Every primal optimal solution is complementary to every dual optimal solution. Thus, any primal optimal solution must be complementary to ¯y . The dual constraint corresponding to x4 is
    3y1 + 2y3 ≤ 4

    This constraint is satisfied at equality by the dual solution ¯y found above. Therefore, primal solutions with x4 > 0 may satisfy complementary slackness with respect to ¯y and so such solutions may be primal optimal.

    However, the dual solution ¯y satisfies the last constraint strictly; thus, no primal optimal solution can have x5 > 0.

  4. Any primal optimal solution is complementary to any dual optimal solution. If we let c denote the primal objective function, A denote the primal constraint matrix, and z denote the dual slacks, then along the given dual set of optimal solutions we have
    ⌊ ⌋ 0 + λ || 0 + 0 || z = c - AT y = || 0 + 0 || || || ⌈ 0 + λ ⌉ 7 - 2λ

    This is dual feasible for 0 ≤ λ ≤ 7∕2, and z1 > 0, z4 > 0, z5 > 0 for 0 < λ < 7∕2. Thus, by complementary slackness, we must have x1 = x4 = x5 = 0 in any primal optimal solution. Therefore, ¯x1 = 0. We can not conclude anything about ¯x2 or ¯x3