MATP6640/DSES6770 Linear Programming, Homework 2.

Due: Friday, February 17, 2012.

  1. Consider the dual pair min{cTx : Ax = b, x ≥ 0} and max{bTy : ATy ≤ c}.
    1. Prove that if one problem has a nondegenerate and unique optimal solution then so does the other.
    2. Suppose that we have a nondegenerate optimal basis for the primal and that one of the reduced costs for the optimal basis is zero. What does the result of question 1a imply? Must there exist another optimal basis?
  2. Let A be an m × n matrix and let b be a vector in IRm. We consider the problem of minimizing ||Ax - b||∞ over all x ∈ IRn. Let v be the value of the optimal cost.
    1. Let y ∈ IRm satisfy ∑ i=1m|yi| = 1 and ATy = 0. Show that bTy ≤ v.
    2. Show that the optimal value of the following LP is v:
      max bTy subject to ∑ ATy = 0 mi=1 |yi| = 1

  3. Consider the linear programming problem
    min x1 - 3x2 + x3 + x4 + x5 s.t. x1 + x3 - 2x5 = 10 - 3x2 + x3 + x4 + 2x5 = 7 x1 + x2 - 3x5 = 6 xi ≥ 0, i = 1,...,5.

    Show that this problem has unbounded objective function value by using the revised simplex algorithm starting from the basic feasible solution x = [6,0,4,3,0]T. Use the eta factorization of the inverse, so you should first factorize the initial basis B as LB = U, where L is lower triangular and U is upper triangular. On subsequent iterations, update the basis matrix by using eta matrices. What is the ray that you find? (Hint: you should find the ray on the second iteration.)

  4. Use AMPL or another linear programming package to solve the linear programming problem
    min x1 + 3x2 + x3 - 4x5 s.t. x1 + x3 - 2x5 = 10 - 3x2 + x3 + x4 + 2x5 = 7 x1 + x2 - 3x5 = 6 xi ≥ 0, i = 1,...,5.

    (See the course webpage for more information on AMPL.)

  5. The dual to the linear program in question 3 is infeasible. Taking nonnegative linear combinations of the dual constraints gives further valid dual constraints. Show how the ray you found for the linear programming problem in question 3 can be used to construct a linear combination of the dual constraints that is clearly infeasible.
    John Mitchell
    Amos Eaton 325
    x6915.
    mitchj at rpi dot edu
    Office hours: Tuesday: 12 noon – 2pm, Wednesday: 2pm – 4pm.