Question 5 of 8: LP Sensitivity Analysis from a Given Final Simplex Tableau
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — December 2016 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 160 marks across 8 questions (each worth 20) and only 100 marks are required, so a candidate would normally answer 5 — all eight are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming and the simplex method & sensitivity analysis (ch. 3–4/6), network optimization & PERT/CPM (ch. 9–10), integer programming (ch. 12), Markov chains (ch. 16), decision analysis (ch. 15). Nahmias, Production and Operations Analysis — the single-period (newsvendor) inventory model.
Question 5: LP Sensitivity Analysis from a Given Final Simplex Tableau (20 marks)
Check: the source prints "requirement constraint" for the third row without a visible inequality sign. Read literally as $\le50$, the printed "final" tableau is not optimal at all — an independent LP solve then wants $x_1=15.5,x_3=0$, $z=325.5>291$. Reading it as a minimum requirement, $x_1+2x_2+x_3\ge50$, exactly reproduces the exam's own tableau ($x_1=4,x_2=23,z=291$) — confirmed by direct feasibility/objective check and by an independent LP resolve. This reading is used throughout. Separately to never trust a printed z-row at face value, the printed coefficients on $x_3$ and $x_4$ ($\tfrac12,\tfrac23$) do not reproduce under an exact $B^{-1}$ recomputation (true values 6 and 11) — only the requirement-column coefficient (1) happens to match. All sensitivity results below use the independently re-derived, LP-resolve-confirmed values, not the printed z-row.
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.
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).
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).
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.
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.
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}$$
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.
