Question 7 of 10: Simplex Sensitivity Analysis From a Final Tableau

Question 7: Simplex Sensitivity Analysis From a Final Tableau (15 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Final optimal tableau above; basic variables $x_1,x_2,x_5$; nonbasic $x_3=x_4=x_6=0$.

Find. (a) optimum + shadow prices; (b) range of $c_2$ preserving the basis; (c) effect of $\Delta b_1=+5$.

Approach. Read the primal solution off the tableau's RHS, but recompute the $z$-row's reduced costs directly from the stated constraints/objective via $\bar c_j=c_B^TB^{-1}A_j-c_j$ rather than trusting the printed $z$-row at face value — the primal rows check out against the original constraints, but (as the check note below documents) the exam's own $z$-row coefficients for $x_3,x_4$ do not reconcile with those same constraints, so this solution derives the marginal values from the verified data instead of repeating the inconsistency.

1. Part (a) — optimal solution and profit. Reading the RHS with all nonbasic variables at zero: $x_1=4$, $x_2=23$, $x_3=0$; slack $x_5=2$ (resource 2 not binding); surplus $x_6=0$ (requirement exactly met). Check: $2(4)+23=31$ ✓, $3(4)+2(23)=58=60-2$ ✓, $4+2(23)=50$ ✓. $$\boxed{x_1=4,\ x_2=23,\ x_3=0,\quad z_{\max}=\$291.}$$
2. Part (a) — marginal (shadow) values, recomputed from $B^{-1}$. With basis $\{x_1,x_2,x_5\}$, $B=\begin{pmatrix}2&1&0\\3&2&1\\1&2&0\end{pmatrix}$ (columns = $x_1,x_2,x_5$ in the resource-1/resource-2/requirement rows). Inverting and forming $y=c_B^TB^{-1}=(21,9,0)B^{-1}$ gives $y=(11,\,0,\,-1)$ — i.e. dual values $11$ for resource 1, $0$ for resource 2, and $-1$ for the requirement (sign negative because it is a $\ge$ floor in a maximization). This $B^{-1}$ is independently confirmed correct because $B^{-1}$ applied to $x_3$'s and $x_4$'s original columns reproduces the tableau's own primal entries for those columns exactly ($\tfrac13,\tfrac13,-\tfrac23$ and $\tfrac23,-\tfrac13,-\tfrac43$): $$\boxed{y_{\text{resource 1}}=\$11/\text{unit},\quad y_{\text{resource 2}}=0\ (\text{slack present, not binding}),\quad \text{marginal cost of requirement}=\$1/\text{unit}.}$$ Resource 2 has slack $x_5=2>0$, so one more unit of it is worthless; the binding requirement constraint costs the firm $1 for every extra unit the contract forces it to supply — confirmed independently by re-solving the LP at requirement $=49$ and $=51$, giving $z=292$ and $z=290$.
3. Part (b) — ranging $c_2$. $x_2$ is basic in row 2 (coefficients of the nonbasic variables $x_3,x_4,x_6$ in that row are $\tfrac13,-\tfrac13,-\tfrac23$ — these primal entries match the given tableau and are unaffected by the $z$-row correction above). As $c_2\to9+\Delta$, the dual vector shifts by $\Delta$ times row 2 of $B^{-1}$, so each reduced cost changes by $\bar c_j^{\text{new}}=\bar c_j-(-\Delta)\cdot(\text{row-2 coeff of }x_j)$, i.e. $\bar c_j+\Delta\cdot(\text{row-2 coeff})\ge0$ using the corrected base values $\bar c_{x_3}=6,\ \bar c_{x_4}=11,\ \bar c_{x_6}=1$: $$x_3:\ 6+\tfrac13\Delta\ge0\Rightarrow\Delta\ge-18;\qquad x_4:\ 11-\tfrac13\Delta\ge0\Rightarrow\Delta\le33;\qquad x_6:\ 1-\tfrac23\Delta\ge0\Rightarrow\Delta\le\tfrac32.$$ The binding pair is $-18\le\Delta\le\tfrac32$, so $$\boxed{-9\le c_2\le10.5}$$ keeps $(x_1,x_2)=(4,23)$ optimal (independently confirmed by re-solving the LP at $c_2=-8.9,\,10.4$ — same basis — versus $c_2=-9.1,\,10.6$, where it changes).
4. Part (c) — how far the shadow price applies. Increasing resource 1's RHS by $\Delta$ shifts the basic values by $\Delta$ times $x_4$'s column (verified primal entries, unaffected by the $z$-row correction): $x_1\to4+\tfrac23\Delta$, $x_2\to23-\tfrac13\Delta$, $x_5\to2-\tfrac43\Delta$. The binding limit is $x_5\ge0$: $2-\tfrac43\Delta\ge0\Rightarrow\Delta\le1.5$. So the corrected $\$11$-per-unit shadow price is valid only for the first 1.5 units of extra resource 1 — beyond that, resource 2 becomes binding and the basis must change. Over that valid range the profit gain is $1.5\times\$11=\$16.5$.
5. Part (c) — the full +5 units. Since the requested increase (5 units) exceeds the 1.5-unit range, re-solving the LP with resource 1's RHS at $31+5=36$ (resource 2 and the requirement become the binding pair) gives the new optimum $$x_1=5,\ x_2=22.5,\ x_3=0,\quad z=21(5)+9(22.5)=105+202.5=\boxed{\$307.5}.$$ The profit increase is $307.5-291=\boxed{\$16.5}$ — exactly the $1.5\times\$11$ found above, because resource 1's usage at this new optimum is only $2(5)+22.5=32.5$ (i.e. only the first 1.5 units of the extra 5 are ever used); resource 1's shadow price is $0$ for any further capacity beyond that point, so the full 5-unit increase and the 1.5-unit allowable increase give the identical profit gain.