Math Models of Operations Research
MATP 4700 / DSES 4770

Third Exam, Friday, December 5, 2008.

You may use any result from your notes or a homework that is clearly stated. You may use one sheet of handwritten notes, but no other sources. The exam consists of five questions, and lasts one hundred and ten minutes.

  1. (20 points)

    A pharmaceutical manufacturer must supply 30 batches of its new medication in the next quarter, then 25, 10, and 35 in successive quarters. Each quarter in which the company makes product requires $100,000 setup, plus $3000 per batch produced. There is no limit on production capacity. Batches can be held in inventory, but the cost is a high $5000 per batch per quarter. The company seeks a minimum total cost production plan.

    This problem can be approached by dynamic programming, with states k = 1,…, 5 representing the reaching of quarter k with all earlier demand fulfilled and no inventory on hand.

    1. (15 points)

      Sketch the digraph corresponding to the dynamic program structure. Include costs on all arcs.

    2. (5 points)

      Explain why the feasible production plans correspond exactly to the paths from node k = 1 to node k = 5 in your digraph.

  2. (15 points)

    Solving the linear programming relaxation of a certain integer program results in the following optimal tableau:

    |-----x1--x2--x3-----x4---x5--x6-| |- 8.0|0 0 4 1 1 5 | |-----|--------------------------| | 4.5 |1 0 4 - 3.5 - 1 3 | --3.5--0---1---1----0.5----0---2--

    We decide to solve this problem using branch-and-bound and we branch first on x2.

    1. (5 points) Show that the branch with x2 ≥ 4 is infeasible.
    2. (10 points) Show that the optimal solution to the LP relaxation of the branch with x2 ≤ 3 is integral. What do you conclude?
  3. (10 points.)

    Consider the primal-dual pair of linear programs

    min cT x max bT y subject to Ax = b (P ) subject to AT y + s = c (D ) x ≥ 0 s ≥ 0

    where x, s, and c are n-vectors, b and y are m-vectors, and A is an m × n matrix of rank m.

    Assume ¯x > 0 is feasible in (P) and (y¯ ,¯s ) is feasible in (D) with s¯ > 0. Given a diagonal scaling matrix X with positive diagonal entries, the affine scaling direction requires calculating the projection of Xc onto the nullspace of AX. Let PAX denote the projection matrix and let d denote this projection, so d = PAXXc.

    Show that d = PAXX¯s .

  4. (15 points)

    Use dynamic programming to find the longest path from vertex 1 to vertex t in the following graph, where the edge lengths are given on the graph:

    PICT

    (Hint: If the vertices are ordered 1 - 4 - 5 - 6 - 7 - t then every arc is directed from an earlier vertex to a later vertex. It follows that we can find the longest path to each vertex in succession.)

  5. (20 points)

    Consider the integer program

    max x1 + 2x2 s.t. x1 + 5x2 ≤ 20 (IP ) 4x1 + x2 ≤ 16 x1,x2 ≥ 0, integer

    The optimal solution to the linear programming relaxation of this problem is ¯x = (3-3 19, 3-7 19). The problem is illustrated here:

    PICT

    Solve this problem using branch-and-bound. (Note: It is acceptable to solve the LP relaxations graphically.)

  6. (20 points)

    The point x = (1, 2, 3, 1) is an interior feasible point to the linear program

    min 13x1 + 5x2 + x3 + 7x4 subject to 3x1 + x2 - x3 + x4 = 3 x1 + x3 - x4 = 3 x1, x2, x3, x4 ≥ 0.

    The barrier problem for this linear program for a positive choice of μ is

    min 13x1 + 5x2 + x3 + 7x4 - μ ∑4 lnxi subject to 3x + x - x + x = 3 i=1 1 2 3 4 x1 + x3 - x4 = 3 x1, x2, x3, x4 ≥ 0.

    Show that x = (1, 2, 3, 1) solves the barrier problem when μ = 6. (Hint: the dual problem to min{cT x : Ax = b,x ≥ 0} is max{bT y : AT y ≤ c}.)