Math Models of Operations Research, MATP 4700/ DSES 4770.

Third Exam, Friday, December 9, 2005.

  1. (40 points) Consider the standard form LP

    \begin{displaymath} \begin{array}{lrcrcrcl} \min & 10x_1 & + & x_2 \\ \mbox{s.t... ... \\ & \multicolumn{5}{r}{x_1, x_2, x_3} & \geq & 0 \end{array}\end{displaymath}

    1. (7 points) Show that $x^{(0)}=(4,3,1)$ is an appropriate point to start the affine scaling algorithm.
    2. (6 points) Derive the associated scaled standard form corresponding to the solution $x^{(0)}$.
    3. (7 points) The move direction for the affine scaling algorithm is $\Delta x = 7.669(-1,1,1)$. Show that this direction is improving and feasible at $x^{(0)}$.
    4. (6 points) Compute the maximum possible steplength $\lambda_{\max}$ in the direction $\Delta x$.
    5. (7 points) For this problem, why must a log barrier method give a direction from $x^{(0)}$ that is a multiple of $\Delta x$?
    6. (7 points) The logarithmic barrier subproblem is

      \begin{displaymath} \begin{array}{lrcrcrcl} \min & 10x_1 & + & x_2 & - & \multic... ... \\ & \multicolumn{5}{r}{x_1, x_2, x_3} & \geq & 0 \end{array}\end{displaymath}

    What equations would you solve to verify that $\bar{x}=(1,6,4)$ solves the barrier subproblem for $\mu=\frac{108}{7}$? (Note: you do not need to actually solve the equations.)

  2. (10 points) Express the following fixed charge problem as an equivalent integer programming problem:

    \begin{displaymath} \begin{array}{lll} \begin{array}{lrcrcl} \min & c_1(x_1) ... ... \mbox{otherwise} \end{array} \right. \end{array} \end{array} \end{displaymath}

  3. (20 points)

    Consider the integer program

    \begin{displaymath} \begin{array}{lrcrclr} \max & x_1 & + & 2x_2 \\ \mbox{s.t.}... ...icolumn{3}{r}{x_1, x_2} & \geq & 0, \mbox{ integer} \end{array}\end{displaymath}

    The optimal solution to the linear programming relaxation of this problem is $\bar{x}=(3\frac{3}{19},3\frac{7}{19})$. The problem is illustrated below.
    1. (6 points) Show that the constraint $x_1+3x_2 \leq 12$ is a valid constraint (that is, the constraint is satisfied by all feasible solutions to $(IP)$).
    2. (6 points) Solve graphically the LP relaxation with the extra constraint $x_1+3x_2 \leq 12$.
    3. (8 points) Find a valid constraint that is violated by the point you found in part (b). Add the constraint to the LP relaxation and graphically solve it again.


    \begin{picture}(250,250)(-25,-25) \put(-25,0){\vector(1,0){250}} \put(0,-25){\ve... ...)\{$2 frac\{1\}\{3\}$\} \put(215,-15){$x_1$} \put(-12,215){$x_2$} \end{picture}

  4. (15 points)

    Use Dijkstra's algorithm to find the shortest path from vertex 1 to vertex $t$ in the following graph, where the edge lengths are given on the graph:


    \begin{picture}(350,200) %labelled vertices % put(20,190)\{ circle\{20\}\} % put... ...260,65){9} \put(260,100){\vector(1,0){50}} %(7,t) \put(280,105){3} \end{picture}

  5. (15 points)

    Burgess Fuel is planning its purchases of heating oil for the next four months. The forecasted demands and purchase costs per gallon are contained in the table:

      month 1 month 2 month 3  
    demand 7000 8000 3000  
    price per gallon $2 $3 $4  
    If they purchase a gallon of oil for use in a later month, they pay an inventory cost of $1.20 per gallon per month in storage. Each order incurs a fixed delivery cost of $2000, regardless of the amount ordered. Burgess Fuel currently has no fuel on hand. This problem can be approached by dynamic programming, with states $k=1,\ldots,4$ representing the reaching of month $k$ with all earlier demand fulfilled and no inventory on hand. Sketch the digraph corresponding to the dynamic program structure. Include costs on all arcs. Explain why the feasible production plans correspond exactly to the paths from node $k=1$ to node $k=4$ in your digraph. (Note: you do not need to find the optimal solution.)


John Mitchell
2008-11-26