MATP6640/DSES6770
Linear Programming
Spring 2012

Midterm Exam, Friday, April 20, 2012.

Please do all four problems. Show all work. No books or calculators allowed. You may use any result from class, the homeworks, or the texts, except where stated. You may use one sheet of handwritten notes. The exam lasts 110 minutes.

Throughout, the standard primal-dual LP pair is

T T min c x max bTy s.t. Ax = b (P ) s.t. A y ≤ c (D ) x ≥ 0

where A is m × n and the vectors are dimensioned appropriately. The dual slack variables are defined as s := c - AT y.

  1. (20 points)
    Assume (P) and (D) are both feasible. Let i ∈ {1,…,n}. Show that either xi is unbounded in the set of primal feasible solutions, or the dual slack si is unbounded in the set of dual feasible solutions, but not both.
  2. (35 points)
    Let the LP (P) be
    min - 6x - 6x + 3x + c x 1 2 4 5 5 subject to 2x1 + 2x2 - x4 = 6 2x1 + 3x3 - x4 = 6 2x1 + 2x2 - 2x5 = 6 xi ≥ 0, i = 1,...,5

    1. (5 points) Does there does exist a basic feasible solution with x1, x2, and x3 basic.
    2. (5 points) Find the basic feasible solution with x1, x3, and x5 basic.
    3. (7 points) Find the basic feasible solution with x2, x3, and x4 basic. What would be the corresponding dual solution when using the simplex algorithm?
    4. Now assume the basic feasible solution in part 2c is optimal.
      1. (5 points) What can you say about c5?
      2. (5 points) Assume c5 = 0. Show that the set of primal optimal solutions is unbounded.
      3. (8 points) Assume c5 = 4. Show there exist multiple dual optimal solutions. Which primal variables xi can be positive in an optimal solution? Which dual slacks si can be positive in an optimal solution?
  3. (10 points)
    Every polyhedron P is the feasible region for an LP, for example min{0T x : x ∈P}. Every linear programming problem can be converted to an equivalent one in the standard form (P). Every LP in standard form has an extreme point. Does it follow that every polyhedron has an extreme point? Prove or give a counterexample.
  4. (35 points.)
    The linear program
    min cT x + dTw subject to Ax + Gw = b (P F ) x ≥ 0, w free

    has free variables. Splitting the variables leads to an equivalent linear program of the form (P):

    min cTx + dT u - dT v subject to Ax + Gu - Gv = b (P S) x, u,v ≥ 0

    1. (10 points) Assume (PF) has an optimal solution (x*,w*). Show that (PS) has an unbounded set of optimal solutions.
    2. (10 points) What is the dual problem to (PS)? (Your dual problem should be of the form (D), with free variables and inequality constraints.)
    3. (10 points) What does the result of part 4a imply about the set of feasible solutions to the dual problem to (PS)? Verify this conclusion for your formulation of the dual.
    4. (5 points) Would you advise applying an interior point method to solve the reformulation (PS)? Justify your answer.