Math 340

Second Midterm

March 6, 1996

Instructions: Non-programmable calculators are allowed, no other aids. Show your work.

[ 16 points ] 1  Consider the problem

The optimal solution has

$${{\bf B}}^{-1} = \bordermatrix{&\cr x_1 & 0 & 0 & 1 \cr x_3 & 0 & 1 & -3 \cr s_1 & 1 & -1 & -2 \cr}$$

• (a) Suppose the 3 in the right-hand side of the third constraint were replaced by a parameter t. For what range of values of t would the basis above give the optimal solution of the problem? Within this range, how does the optimal value $\alpha$ of the objective depend on t?
• (b) How would small changes in c₁ (the coefficient of x₁ in the objective) affect the optimal ${\bf x}$ and the optimal value $\alpha$ of the objective? For what range of values of c₁ would this be true? What happens when c₁ is slightly outside this range? (if a pivot is necessary, just say which variables enter and leave the basis)

[ 10 points ] 2  Consider the problem

• (a) Why is the Dual Simplex Method appropriate for this problem?
• (b) Perform ONE pivot, using the Dual Simplex Method (either revised or not), and indicate the basic solutions of the primal and dual problems resulting from this pivot.

[ 4 points ] 3  A factory can produce three products (I, II and III). In deciding how much of each product to produce, we formulate and solve a linear programming problem to maximize profits subject to constraints on availability of certain resources. The optimal solution, which is not degenerate, tells us not to produce any of product III. Explain the practical or economic significance of the value of the dual variable corresponding to this product.

[ 30 ] Total marks