Question 6 of 9: LP Sensitivity Analysis from a Given Optimal Tableau

Question 6: LP Sensitivity Analysis from a Given Optimal Tableau (20 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. Original LP: $\max z=5x_1+x_2+2x_3$ s.t. constraint 1 (slack $x_4$) $x_1+x_2+x_3\le6$, constraint 2 (slack $x_5$) $6x_1+x_3\le8$, constraint 3 (slack $x_6$) $x_2+x_3\le2$. Final optimal tableau (basic $x_1,x_3,x_4$; nonbasic $x_2,x_5,x_6=0$): $x_1=1,\ x_3=2,\ x_4=3,\ z=9$, with the reduced-cost/z-row equation as printed above.

Find. (a) Range of $c_1$ keeping the basis optimal. (b) Range of the constraint-2 RHS (currently 8) keeping the basis optimal. (c) Shadow prices and their meaning. (d) Reduced costs of $x_1,x_2,x_3$ and their meaning.

Approach. Recover $B^{-1}$ for the basis $\{x_1,x_3,x_4\}$ from the original constraint columns, use it to independently verify the printed z-row (shadow prices $y=c_B^TB^{-1}$ and reduced costs $c_j-yA_j$), then apply the standard ranging conditions: dual feasibility (all reduced costs $\le0$) for a cost-coefficient range, and primal feasibility ($x_B=B^{-1}b\ge0$) for an RHS range.

1. Recover $B^{-1}$ and verify the given tableau. The basis columns (for $x_1,x_3,x_4$, in the original constraints) are $B=\begin{bmatrix}1&1&1\\6&1&0\\0&1&0\end{bmatrix}$, giving $\det B=6$ and $$B^{-1}=\begin{bmatrix}0&\tfrac16&-\tfrac16\\0&0&1\\1&-\tfrac16&-\tfrac56\end{bmatrix}$$ With $c_B=(5,2,0)$, the shadow prices are $y=c_B^TB^{-1}=(0,\ \tfrac56,\ \tfrac76)$, and the reduced costs of $x_2,x_5,x_6$ come out to $-\tfrac16,-\tfrac56,-\tfrac76$ — exactly the coefficients in the given z-row equation, confirming the printed tableau is internally consistent (unlike some other papers in this series where the printed z-row must be recomputed from scratch).
2. Part (a) — range of $c_1$. Let $c_1=5+\Delta$; recomputing $y$ and the three nonbasic reduced costs symbolically in $c_1$ gives $\text{rc}_{x_2}=c_1/6-1$, $\text{rc}_{x_5}=-c_1/6$, $\text{rc}_{x_6}=c_1/6-2$. Optimality (max problem) needs all three $\le0$: $$c_1/6-1\le0\Rightarrow c_1\le6;\qquad -c_1/6\le0\Rightarrow c_1\ge0;\qquad c_1/6-2\le0\Rightarrow c_1\le12$$ The binding pair is $c_1\ge0$ and $c_1\le6$: $$\boxed{0\le c_1\le6}$$
3. Part (b) — range of the constraint-2 RHS. Let RHS $=8+\delta$, so $b(\delta)=(6,8+\delta,2)^T$. Costs are unchanged, so dual feasibility (optimality) is unaffected; only primal feasibility of $x_B=B^{-1}b(\delta)$ can be violated: $$x_1=1+\delta/6,\qquad x_3=2,\qquad x_4=3-\delta/6$$ Requiring $x_1\ge0$ and $x_4\ge0$ ($x_3=2$ is unaffected): $\delta\ge-6$ and $\delta\le18$, i.e. RHS between $8-6=2$ and $8+18=26$: $$\boxed{2\le \text{RHS}_2\le26}$$
4. Part (c) — shadow prices. From Step 1, $y_1=0$, $y_2=\tfrac56$, $y_3=\tfrac76$: $$\boxed{y_1=0,\quad y_2=\$0.833,\quad y_3=\$1.167\text{ (per unit RHS increase, within each range above)}}$$ Constraint 1 has slack $x_4=3>0$ (not binding), so relaxing it further cannot improve $z$ — its shadow price is correctly zero. Constraints 2 and 3 are both binding, so one more unit of their RHS (within the ranges found by the same method as part (b)) increases the optimal $z$ by $5/6$ and $7/6$ respectively.
5. Part (d) — reduced costs of $x_1,x_2,x_3$. $x_1$ and $x_3$ are basic, so their reduced costs are $0$ by definition; $x_2$ is nonbasic with reduced cost $-\tfrac16$ (from Step 1): $$\boxed{\text{rc}(x_1)=0,\quad \text{rc}(x_3)=0,\quad \text{rc}(x_2)=-\tfrac16}$$ The reduced cost of $x_2$ means $z$ would fall by $1/6$ for every unit $x_2$ is forced into the (currently zero) solution — the opportunity cost of diverting resources to $x_2$ instead of the current optimal product mix.