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

Second Exam, Tuesday, October 20, 2003.

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 minutes.

1.

(20 points; 10 points for each part) Each of the following is a linear program with no optimal solution. State the corresponding dual problem, solve both primal and dual graphically, and verify that whenever primal or dual is unbounded, the other is infeasible.

(a)

$$\begin{array}{lrcrcl} \max & 4x_1 & + & x_2 \\ \mbox{subjec... ...\ &&& 3x_2 & \leq & 12 \\ &&& x_1, x_2 & \geq & 0 \end{array}$$

(b)

$$\begin{array}{lrcrcl} \min & 10x_1 & + & 3x_2 \\ \mbox{subj... ...\\ &&& -x_2 & \geq & 5 \\ &&& x_1, x_2 & \geq & 0 \end{array}$$

2.

(15 points) The optimal solution to the linear programming problem

$$\begin{array}{lrcrcrcl} \max & -4x_1 & + & 3x_2 & + & x_3 \\... ...9 \\ &\multicolumn{5}{r}{x_1, x_2, x_3} & \geq & 0 \end{array}$$

is x₁=0, x₂=5, x₃=0.

(a)

(5 points) Give a dual problem to this linear program.

(b)

(10 points) Use complementary slackness to find an optimal solution to your dual problem.

3.

(15 points) Consider the linear programming minimization problem represented by the following tableau M₀:

$$M_0 = \begin{tabular}{\vert r\vert rrrrrrr\vert} \hline 0 ... ...\ 3 & 0 & -1 & 0 & 1 & -2 & 3 & 1 \\ \hline \end{tabular}$$

(a)

(5 points) Write down a pivot matrix to represent the simplex pivot.

(b)

(10 points) Use the pivot matrix to find the reduced costs and hence show that the resulting tableau is in optimal form. What is the optimal solution?

4.

(15 points) Consider the linear programming problem

$$\begin{array}{lrcrcrcrcl} \min & x_1 & & & - & 3x_3 & + & ... ... & 1 \\ &&& x_i & \geq & 0, && i & = & 1,...,4. \end{array}$$

Use the method of artificial variables to find an initial canonical form for this linear program. You should obtain the basic feasible solution x₁=2, x₂=1, x₃=x₄=0. (If you have a choice for the entering column, choose the first possible column. You should only need two pivots to solve the artificial problem, once you have a canonical form for the artificial problem.)

5.

(15 points) An LP of the form

$$\begin{array}{lrcl} \min & c^Tx \\ \mbox{subject to } & Ax & \leq & b \\ & x & \geq & 0 \end{array}$$

has optimal tableau

$$\begin{array}{\vert r\vert rrrrrrr\vert} \multicolumn{2}{r}{... ... & -1 \\ 8 & 0 & -2 & 1 & 0 & 1 & -2 & 3 \\ \hline \end{array}$$

How much would you be willing to pay for an additional unit of Resource 2? What is the maximum amount of this resource that you are prepared to buy at these prices? If instead someone wished to purchase the resource from you, what is the maximum you would be prepared to sell at this price?

6.

(20 points) Consider the primal-dual pair of linear programming problems

$$\begin{array}{lrcrcrclclrcrcl} \max & 2x_1 &+& 5x_2 &+& 10x_... ...&&&&&&&&&& \multicolumn{3}{r}{y_1, y_2 } & \geq & 0 \end{array}$$

(a)

(10 points) Graph the feasible region for (D). Use this picture and complementary slackness to show that in any optimal solution to (P) we must have x₃=0.

(b)

(10 points) Now set b₁=19 and b₂=9. The primal-dual pair has an optimal solution with x₁=7, x₂=1, x₃=0, y₁=1, and y₂=0. It has become possible to produce an additional product x₄ that uses 3 units of resource 1 and 4 units of resource 2. What price c₄ must be charged for this product for it to be worthwhile to produce it?