Name:

MATP6640/DSES6770
Linear Programming
Spring 2008

Midterm Exam, Thursday, April 3, 2008.

Please do all three 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.

Q1       /40
Q2       /30
Q3       /30
Total      /100

Throughout, the standard primal-dual LP pair is

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

where A is m × n and the vectors are dimensioned appropriately.

  1. (40 points)
    1. (20 points) Use complementary slackness to show that y = (10, 5) solves the linear program
      max 11y1 + 8y2 s.t. 5y1 ≤ 50 5y2 ≤ 50 (D4 ) 3y1 + 4y2 ≤ 50 2.5y1 + 4.33y2 ≤ 50

      (Hint: 2.5 × 10 + 4.33 × 5 = 46.65.)

    2. (20 points) The problem in part (1a) is a relaxation of the true problem,
      maxy 11y1 + 8y2 2 2 s.t. w1y1 + w2y2 ≤ 50 ∀w satisfying w1 + w 2 ≤ 25. (D ∞)

      Show that y = (10, 5) is not feasible in the true problem. Give a valid linear constraint that is violated by y = (10, 5) and that could be added to (D4).

    (this page intentionally left blank)

    (this page intentionally left blank)

  2. (30 points)
    Two systems of equations are:
    (I) Ad = 0, cTd = 0, eTd = 1, d ≥ 0 (II) AT v < tc, t and v free
    where e is the n-vector of ones and t is a scalar.
    1. (10 points) Show that exactly one of the two systems has a solution.
    2. (10 points) Assume (P) and (D) are both feasible. Show that if (I) is consistent then (P) has an unbounded set of optimal solutions.
    3. (10 points) Assume (D) is feasible. Show that if (II) is consistent then (D) has a strictly feasible solution.

    (this page intentionally left blank)

  3. (30 points)
    Let (ˆx,ŷ,ŝ) be strictly feasible solutions to (P) and (D). Let ˆμ = xˆT ŝ∕n. Assume the current iterate is reasonably well centered, so ˆ XŜe ≈ˆμe, with the diagonal matrices ˆ X and Ŝ defined in the usual manner. Assume rank(A) = m.

    Assume we add an extra variable w to (P), with corresponding column g, giving the modified problem

    T min c x + hw s.t. Ax + gw = c (Pw ) x, w ≥ 0

    where h is a scalar. The point x = ˆx, w = 0 is feasible for (Pw) but not strictly feasible. It is necessary to increase w to get a strictly feasible point.

    1. (15 points) Ignoring the additional dual constraint gT y ≤ h, how would you try to find a strictly feasible solution to (Pw) while also keeping XSe ≈ˆμe? (Hint: set up conditions to be satisfied by primal directions (Δx, Δw) and dual directions (Δy, Δs).)
    2. (15 points) Now assume you’ve found a strictly feasible primal solution (¯x,¯w) and a new dual solution ¯y with ¯s = c - AT ¯y > 0. If you could pick the scalar h, how would you select it? (Aside: an algorithm could work from an incorrect h and gradually modify it to achieve the correct value.)

    (this page intentionally left blank)