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

Question 6: LP Sensitivity Analysis from a Given Final Simplex 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. LP as stated above; final basis $\{x_1,x_2,x_5\}$ (i.e. resource 1 and the requirement are binding, resource 2 has slack).

Find. (a) Optimal solution, max profit, shadow prices of resource 1, resource 2, and the requirement. (b) Range of the $x_2$ objective coefficient that keeps this basis optimal. (c) Profit and new solution if resource 1's availability increases by 5 units (31→36).

Approach. Confirm the primal solution directly from the given equations (nonbasic $x_3=x_4=x_6=0$), then recompute the shadow prices and reduced costs exactly from $y=c_B^\top B^{-1}$ using the basis's own columns (rather than trusting the printed z-row), and use those to do the standard objective-coefficient and RHS ranging.

1. Part (a) — read the primal solution off the tableau (nonbasic $x_3=x_4=x_6=0$): $$x_1=4,\quad x_2=23,\quad x_3=0,\quad z=21(4)+9(23)=\boxed{\$291}$$ Check: resource 1: $2(4)+23=31$ (binding); resource 2: $3(4)+2(23)=58\le60$, slack $x_5=2$ (non-binding); requirement: $4+2(23)=50$ (binding, exactly met).
2. Part (a) — shadow prices via $y=c_B^\top B^{-1}$ on the true basis $B=\{x_1,x_2,x_5\}$ (columns from the original resource-1/resource-2/requirement rows): $$y=(21,9,0)\,B^{-1}=(y_1,y_2,y_3)$$ $$\boxed{y_1(\text{resource 1})=\$11/\text{unit},\quad y_2(\text{resource 2})=\$0/\text{unit (non-binding)},\quad y_3(\text{requirement})=-\$1/\text{unit}}$$ Resource 2's shadow price is 0 because it has 2 units of slack (not binding, so relaxing it further changes nothing). The requirement's shadow price of −1 means tightening the minimum by 1 unit costs $1 of profit (equivalently, relaxing the requirement by 1 unit would gain $1).
3. Part (b) — range of $c_2$ (coefficient of $x_2$) keeping this basis optimal. Using the exact reduced costs $z_j-c_j$ for the nonbasic columns ($x_3$: 6; resource-1 slack: 11; requirement surplus: 1) and their entries in the $x_2$-row of $B^{-1}A_j$, each nonbasic reduced cost must stay $\ge0$ as $c_2=9+\Delta$ shifts: $$\Delta\in[-18,\,1.5]\ \Longrightarrow\ \boxed{c_2\in[-9,\ 10.5]}$$ Cross-checked by re-solving the LP at $c_2=10.4$ (basis unchanged) vs. $c_2=10.6$ (basis changes to $x_1=2,x_2=27$), and similarly at the $-9$ boundary.
4. Part (c) — RHS ranging for resource 1 before applying its $11/unit shadow price. Moving along $B^{-1}$'s resource-1 direction, resource 2's slack $x_5=2$ is the first basic variable to hit zero: $$x_5(t) = 2 - \tfrac43t = 0 \ \Rightarrow\ t_{\max}=\tfrac32\ \text{extra units of resource 1}$$ So the $11/unit marginal value is only valid for the first 1.5 of the requested 5 extra units — beyond that, resource 2 itself becomes binding and adding more of resource 1 buys nothing further.
5. Part (c) — resolve directly at $b_1=36$ (the full +5) rather than naively extrapolating the shadow price over the whole range: $$z_{\text{naive}}=291+5(11)=346\quad(\text{WRONG -- exceeds the }t_{\max}=1.5\text{ validity range})$$ $$\boxed{z_{\text{true}}=\$307.50,\quad x_1=5,\ x_2=22.5,\ x_3=0}$$ $$\boxed{\text{Profit increase}=307.50-291=\$16.50\ (\text{not }5\times11=\$55)}$$ At this new optimum resource 1 usage is $2(5)+22.5=32.5$ (3.5 units of the extra 5 go unused — resource 1 is no longer binding), resource 2 usage is $3(5)+2(22.5)=60$ (now exactly binding), and the requirement $5+2(22.5)=50$ stays exactly met.