Question 4 of 10: Simplex Sensitivity Analysis from a Given Final Tableau
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2019 — 17-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 175 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 (ch. 3–4), duality & sensitivity analysis (ch. 6), dynamic programming (ch. 11), network optimization & CPM/PERT project crashing (ch. 9–10), queueing theory incl. finite-source (machine-repair) models (ch. 17), decision analysis & the value of information (ch. 15–16), Markov chains (ch. 16), Monte Carlo simulation (ch. 20). Nahmias, Production and Operations Analysis — deterministic EOQ inventory models with and without planned shortages.
Question 4: Simplex Sensitivity Analysis from a Given Final Tableau (15 marks)
Given.$\max z=x_1+2x_2$ s.t. $x_1+3x_2\le 16$, $x_1+x_2\le 7$, $x_1,x_2\ge0$; final tableau as quoted above, with slacks $x_3,x_4$.
Find. (a) optimal solution; (b) basic/non-basic variables; (c) allowable range of $c_1$ (the $x_1$ objective coefficient); (d) allowable range of $b_1$ (RHS of constraint 1).
Approach. Read (a)–(b) directly off the given tableau (Eq 1, Eq 2 give the basic-variable values; the tableau's basic/non-basic pattern gives the rest). For the sensitivity ranges (c)–(d), rather than trust the z-row sign convention blindly, independently re-solve the LP at perturbed $c_1$ and $b_1$ values and find exactly where the current corner point $(x_1,x_2)=(2.5,4.5)$ stops being optimal/feasible — this is cross-checked against the tableau's own shadow-price row below.
(a) Optimal solution — read the RHS of Eq 1, Eq 2, Eq 0 directly (non-basic $x_3=x_4=0$):
$$\boxed{x_1^*=2.5,\quad x_2^*=4.5,\quad z^*=11.5}$$
Check: $x_1+3x_2=2.5+13.5=16$ and $x_1+x_2=2.5+4.5=7$ — both constraints exactly binding, and $z=x_1+2x_2=2.5+9=11.5$, matching Eq 0. ✓
(b) Basic vs. non-basic.$x_1$ and $x_2$ each appear with coefficient 1 in exactly one equation (Eq 1, Eq 2) and 0 elsewhere — they are basic. $x_3$ and $x_4$ (the slacks) are zero at this solution — they are non-basic (both original constraints are binding, so neither slack is used).
Shadow prices from the tableau. The z-row coefficients of the non-basic slacks give the constraints' shadow (dual) prices directly: $y_1=1/2$ (constraint 1), $y_2=1/2$ (constraint 2) — each extra unit of either RHS is worth $0.50 of $z$. This is confirmed independently below by re-solving at a perturbed RHS.
(c) Range of $c_1$ (currently 1). Re-solving the LP with the $x_1$-coefficient set to $c_1'$ and tracking the vertex that maximizes $c_1'x_1+2x_2$: the corner $(2.5,4.5)$ stays optimal only while $2/3\le c_1'\le 2$ — below $c_1'=2/3$ the optimum jumps to $(0,16/3)$ (maximize $x_2$ alone along $x_1+3x_2=16$), and above $c_1'=2$ it jumps to $(7,0)$ (maximize $x_1$ alone along $x_1+x_2=7$):
$$\boxed{2/3\ \le\ c_1\ \le\ 2}$$
(d) Range of $b_1$ (currently 16, constraint 2's RHS fixed at 7). With both constraints held binding, $x_1=(21-b_1)/2$, $x_2=(b_1-7)/2$; both stay $\ge 0$ (i.e. the same basis, Eq 1/Eq 2, remains feasible) only while:
$$\boxed{7\ \le\ b_1\ \le\ 21}$$
Below $b_1=7$, $x_2$ would go negative (constraint 1 becomes the sole binding one and $x_1$ takes over as the free basic variable along the axis); above $b_1=21$, $x_1$ would go negative. As a check, $dz/db_1=(b_1+7)/2$ differentiated at $b_1=16$ gives exactly $1/2$, matching the tableau's shadow price $y_1$ from step 3.
