Solutions to Sample Second Midterm

1.   Note that there was a misprint (now corrected) in the original version of this question: the 3 in the right-hand side of the third constraint should be a 2.

(a).   We have $$\beta = B^{-1} {\bf b} = \pmatrix{t\cr 12-3t\cr 5-2t\cr}$$, so the current basis is optimal as long as $0 \le t \le 5/2$. Within this range, $$z = {\bf c}_{BV}^T \beta = [2,1,0] \pmatrix{t\cr 12-3t\cr 5-2t\cr} = 12 - t$$.

(b).   Small changes in c₁ don't affect the optimal ${\bf x}$, but $$z = {\bf c}_{BV}^T \beta = [c_1, 1, 0] \pmatrix{2\cr 6\cr 1\cr} = 2 c_1 + 6$$. We have $${\bf y}^T = {\bf c}_{BV}^T B^{-1} = [0, 1, c_1-3]$$ and $$\overline{{\bf c}}_N^T = [\overline{c}_2, \overline{c}_4] = [0,1, c_1 - 3] \pmatrix{ 1 & 0\cr 0 & -1\cr 4 & 1\cr} - [-9,-3] = [4 c_1-3, -1+c_1]$$. Note that y₃ is URS because the third constraint is an equality, but we need $4 c_1 - 3 \ge 0$ and $-1 + c_1 \ge 0$, so the range of values in which this is true is $1 \le c_1 < \infty$. If c₁ was slightly less than 1, x₄ would enter the basis. The x₄ column $${\bf d} = B^{-1} \pmatrix{0\cr -1\cr 1\cr} = \pmatrix{1\cr -4\cr -1\cr}$$. The only positive entry is in the x₁ row, so x₁ would leave the basis.

2.(a).   The Dual Simplex Method is appropriate here because the initial tableau is dual-feasible but not primal feasible.

(b).   The initial tableau is

s₂ leaves the basis. The ratios are 1/2 for x₃ and 3/1 for x₄. Having the minimum ratio, x₃ enters the basis.

The basic solution of the primal is x₁ = x₂ = x₄ = 0, x₃ = 11/2, s₁ = 17, s₂ = 0, s₃ = -21/2. The basic solution of the dual is y₁ = 0, y₂ = 1/2, y₃ = 0, e₁ = 5/2, e₂ = 2, e₃ = 0, e₄ = 5/2, with (for both primal and dual) z = -11/2.

3.   The value of the dual variable corresponding to product III is the reduced cost of the primal variable x_III. It represents the increase in the contribution to the profit of one unit of product III that would be necessary in order to make it profitable to produce product III; or, put another way, the reduction in profit for every unit of product III that is produced. It is the difference between the sum of the prices of the resources consumed (according to the shadow prices) and the contribution to the profit for one unit of this product.