Question 4 of 10: 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 2018 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 170 marks across 10 questions and only 100 marks are required, so a candidate would normally answer a subset — all ten are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear programming, the simplex method & sensitivity analysis/duality (ch. 3–4/6), integer programming & branch and bound (ch. 12), queueing theory (ch. 17), decision analysis (ch. 15), computer simulation (ch. 20). Nahmias, Production and Operations Analysis — single-period (newsvendor) and multi-period (dynamic lot-sizing / Wagner–Whitin) inventory models.
Question 4: LP Sensitivity Analysis from a Given Final Simplex Tableau (15 marks)
Check: this paper prints the requirement constraint explicitly as $\ge50$ (a minimum requirement), and with that direction the printed tableau’s primal values ($x_1=4,x_2=23,z=291$) check out exactly against the original constraints (read as $\le50$, the "final" tableau would not be optimal at all). An exact $y=c_B^\top B^{-1}$ recomputation also shows the printed coefficients on $x_3$ and $x_4$ ($\tfrac12,\tfrac23$) do not reproduce (true values 6 and 11) — only the requirement-column coefficient (1) happens to match. All results below use the re-derived values.
Given. LP as stated above; final basis $\{x_1,x_2,x_5\}$ (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.
(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).
(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}$$
$$\boxed{y_1(\text{resource 1})=\$11/\text{unit},\quad y_2(\text{resource 2})=\$0/\text{unit (2 units slack)},\quad y_3(\text{requirement})=-\$1/\text{unit}}$$
The requirement's shadow price of −1 means tightening the minimum by 1 unit costs $1 of profit (equivalently, relaxing it by 1 unit gains $1).
(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 $x_4$: 11; requirement surplus $x_6$: 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).
(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 valid only for the first 1.5 of the requested 5 extra units; beyond that, resource 2 itself becomes binding.
(c) Resolve directly at $b_1=36$ (the full +5) rather than naively extrapolating the shadow price:
$$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}\quad(=1.5\times\$11\text{, i.e. only the first 1.5 extra units earn the shadow price})$$
At this new optimum, resource 1 usage is $2(5)+22.5=32.5$ (3.5 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.
