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

Second Exam, Friday, November 12, 2004.

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 six questions, and lasts one hundred and ten minutes.

  1. (20 points)

    The following digraph represents a partially solved minimum cost flow problem with labels on nodes indicating net demand and those on arcs showing unit cost, capacity, and current flow.


    \begin{picture}(300,200)%(-25,-25) \par \put(50,100){\circle{20}} \put(150,150){... ...){(1,15,0)} \put(190,135){(12,$\infty$,10)} \put(190,60){(3,40,0)} \end{picture}

    The given solution is a basic feasible solution for basis $\{(1,2),(1,3),2,4)\}$.

    1. (7 points) Compute all simplex directions available at this basis.
    2. (7 points) Determine whether each of the simplex directions is improving.
    3. (6 points) Regardless of whether they are improving, determine the maximum feasible step $\lambda$ that could be applied to each of the simplex directions, and state the resulting values of the variables and which variables would then be basic.

  2. (20 points) The linear program

    \begin{displaymath} \begin{array}{lrcrcrcrclr} \min & c_1x_1 & + & c_2x_2 \\ ... ... & \multicolumn{7}{r}{x_1,x_2,x_3,x_4} & \geq & 0 \end{array} \end{displaymath}

    has optimal tableau

    \begin{displaymath} \begin{array}{\vert r\vert rrrr\vert} \hline -z & 0 & 0 &... ...1 & 0 & 1 & -2 \\ 10 & 0 & 1 & -2 & 5 \\ \hline \end{array} \end{displaymath}

    1. (10 points) If the right hand side of the second constraint was increased by one unit, how would the optimal value change? For what range (up and down) of values of this right hand side coefficient would the change per unit be the same?
    2. (10 points) Find the values of the cost coefficients $c_1$ and $c_2$.

  3. (10 points)

    Find the dual of the linear program

    \begin{displaymath} \begin{array}{lrcrcrcl} \min & 2x_1 & - &3x_2 & + & x_3 \\ ... ...}{ \leq 0,} & x_2 & \mbox{ free, } & x_3 & \geq & 0 \end{array}\end{displaymath}

  4. (10 points)

    Perform one dual simplex iteration on the tableau


    \begin{displaymath} \begin{array}{\vert r\vert rrrrrr\vert} \hline 3 & 0 & 0 & 8... ...1 & 1 & -1 \\ 11 & 0 & 1 & 3 & 2 & 2 & 3 \\ \hline \end{array}\end{displaymath}

  5. (20 points)

    Let $G=(V,A)$ be the following directed graph, where the label on each edge gives the cost of traversing that edge, the capacity of the edge, and the flow on the edge. This solution is a basic feasible solution.


    \begin{picture}(300,200)%(-25,-25) \par \put(50,150){\circle{20}} \put(50,50){\c... ...90,110){(1,50,30)} \put(190,85){(8,20,0)} \put(255,100){(4,40,30)} \end{picture}

    1. (10 points) What must $c_{14}$ satisfy for the indicated solution to be optimal?
    2. (10 points) Assume the given basic feasible solution is optimal. Suppose the supply at node 1 and the demand at node 5 are each increased by 5 units. Use sensitivity analysis to calculate the increase in the optimal value.

  6. (20 points) Consider the transportation problem represented in the following table:

    \begin{displaymath} \begin{tabular}{r\vert llll\vert} \multicolumn{1}{l}{\quad... ...\ 20 & 9 & 5 & 6 & $2^{20}$\ \\ \cline{2-5} \end{tabular} \end{displaymath}

    There are four sources and four destinations. The supplies and demands are indicated. The cost of each arc is given in the table, and a feasible solution $x$ is indicated by the superscripts.

    1. (10 points) The feasible solution $x$ only uses five arcs. Extend $x$ to give a basic feasible solution.
    2. (10 points) Calculate the reduced costs for your basic feasible solution. Can you conclude that your solution is optimal?


John E. Mitchell
2005-10-24