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

Second Exam, Friday, November 11, 2005.

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. (40 points) Consider the linear program:
   
   $$\begin{array}{lrcrcrcrcrclr} \max & 6x_1 & + & x_2 & + & 21x... ... \\ \multicolumn{10}{r}{x_1,\ldots,x_5} & \geq & 0 \end{array}$$
   
   
   1. (20 points) Compute the dual solution corresponding to each of the following basic sets in (P):
      1. $\{x_1,x_2\}$
      2. $\{x_1,x_3\}$
      3. $\{x_2,x_3\}$
      4. $\{x_4,x_5\}$
   2. The dual of a linear program of the form $\max\{c^Tx:Ax=b, x\geq 0\}$ is of the form $\min\{b^Ty : A^Ty \geq c, y \mbox{ free}\}$.
      1. (6 points) Show that exactly two of the dual solutions you calculated in part (a) are feasible in the dual problem to $(P)$.
      2. (7 points) Use the information you determined in part 1(b)i to find the optimal solutions to $(P)$ and its dual. (You may assume that any basic set not considered in part (a) is not optimal.)
      3. (7 points) In this part, we are going to modify the right hand side of $(P)$. This does not change the dual constraints, so it does not change the dual solution corresponding to a particular basis. Specifically, let the right hand side of the first constraint be 45 and that of the second constraint be 27. How does your answer to part 1(b)ii change? (Again, you may assume that any basic set not considered in part (a) is not optimal.)
2. (10 points) A linear program in standard form has optimal tableau:
   
   $$M = \begin{array}{\vert r\vert rrrrrr\vert} \multicolumn{1... ... \frac{1}{2}& 0 & 1 & 0 & 1 & -1 & -1 \\ \hline \end{array}$$
   
   
   An additional constraint is now added:
   
   $$x_4 + x_5 + x_6 \geq \frac{1}{2}.$$
   
   
   Use the dual simplex algorithm to show that the values of $x_1$, $x_2$, and $x_3$ are integral in the optimal solution to the modified problem.

3. (15 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.
   
   
   

   The given feasible solution is not a basic feasible solution. Find a basic feasible solution that is at least as good as the given solution.

   Is your basic feasible solution optimal?

4. (35 points) A transportation problem with three supply nodes and four demand nodes has tableau

   
   

   $$\begin{array}{\vert llll\vert} \hline 6 & 3^{10} & 1^{20} & ... ...& 4 & 7 \\ 3^{20} & 2^{10} & 3 & 5^{20} \\ \hline \end{array}$$
   
   
   The large numbers give the costs of the arcs and the superscripts indicate a flow. This flow is a basic feasible solution.
   1. (7 points) Show that the reduced costs for this basic feasible solution are as follows:
      
      $$\begin{array}{\vert llll\vert} \hline 2 & 0^{10} & 0^{20} & ... ...& 5 & 3 \\ 0^{20} & 0^{10} & 3 & 0^{20} \\ \hline \end{array}$$
      
      

   2. (7 points) Currently, the cost of the arc from supply node 1 to demand node 4 is $c_{14}=8$. What is the smallest value of $c_{14}$ for which the given basic feasible solution is optimal?
   3. (7 points) Now set $c_{14}=4$. Find the optimal solution. (Hint: only one pivot is needed.)
   4. For this part, reset $c_{14}=8$.
      1. (7 points) Assume the supply at node 2 and the demand at node 3 are each increased by 5 units. Use sensitivity analysis to find the change in the optimal value. (You may assume the set of optimal basic variables does not change.)
      2. (7 points) Now consider increasing the supply at node 2 and the demand at node 3 by $t$ units. What is the maximum value for $t$ for which the rate you found in part 4(d)i still holds? Would you expect the rate to be larger or smaller for larger values of $t$?