Question 2 of 9: Simplex Method and Sensitivity Analysis
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 2013 — 98-Ind-A1 Operations Research. Three-hour, open-book exam (any non-communicating calculator permitted); the paper totals 180 marks across 9 questions and only 100 marks are required, so a candidate would normally answer a subset — all nine are solved below for completeness.
Reference texts: Hillier & Lieberman, Introduction to Operations Research (11th ed., McGraw-Hill) — linear/integer programming, network optimization, dynamic programming, decision analysis and queueing theory; Niebel & Freivalds, Niebel's Methods, Standards, and Work Design (13th ed.) — job-shop sequencing context.
Given. $\max Z=2x_1+3x_2$ subject to $x_1+2x_2\le6$, $2x_1+x_2\le8$, $x_1,x_2\ge0$.
Find. (a) the optimal $(x_1,x_2,Z)$ by the Simplex Method; (b) the range of the $x_2$ coefficient ($=3$) over which the optimal basis (and hence this vertex) stays optimal.
Approach. Add slacks and pivot the standard Simplex tableau to optimality; then read the objective-row coefficients of the two final nonbasic slacks as linear functions of the varying coefficient and solve for the interval where both stay non-negative (equivalently, use $B^{-1}$ sensitivity analysis).
Iteration 1 — $x_2$ enters. The most negative reduced cost in $Z-2x_1-3x_2=0$ is $x_2$'s. Minimum ratio test: $6/2=3$ (row 1) vs $8/1=8$ (row 2) → row 1 leaves ($s_1$ exits). Pivoting on the row-1/$x_2$ entry gives $x_2=3-\tfrac12x_1-\tfrac12s_1$ and updates row 2 to $\tfrac32x_1-\tfrac12s_1+s_2=5$, with $Z=9+\tfrac12x_1-\tfrac32s_1$.
Iteration 2 — $x_1$ enters. $Z$'s row still has a positive $x_1$ coefficient (improving direction for a max problem). Ratio test: $3/(1/2)=6$ (row 1) vs $5/(3/2)=10/3$ (row 2) → row 2 leaves ($s_2$ exits). Pivoting on the row-2/$x_1$ entry gives $x_1=\tfrac{10}{3}-\tfrac13s_1+\tfrac23s_2$ and updates row 1 to $x_2+\tfrac23s_1-\tfrac13s_2=\tfrac43$, with
$$Z + \tfrac43s_1+\tfrac13s_2 = \tfrac{32}{3}.$$
Both slack coefficients in the $Z$-row are now $\ge0$ → optimal.
Read off the optimum. $s_1=s_2=0$ (both original constraints bind), so
$$\boxed{x_1=\tfrac{10}{3}\approx3.333,\quad x_2=\tfrac43\approx1.333,\quad Z^\*=\tfrac{32}{3}\approx10.667.}$$
Check: $x_1+2x_2=\tfrac{10}{3}+\tfrac83=6$ ✓; $2x_1+x_2=\tfrac{20}{3}+\tfrac43=8$ ✓.
Part (b) — sensitivity of $c_2$. Let $c_2=3+\Delta$ with $c_1=2$ fixed. The optimal basis is $\{x_1,x_2\}$ with basis matrix $B=\begin{pmatrix}1&2\\2&1\end{pmatrix}$, $B^{-1}=\tfrac1{-3}\begin{pmatrix}1&-2\\-2&1\end{pmatrix}$. The basis stays optimal while both nonbasic reduced costs $z_j-c_j\ge0$:
for $s_1$ (column $(1,0)^T$): $z_{s_1}-c_{s_1}=\tfrac23c_2-\tfrac23\ge0\Rightarrow c_2\ge1$;
for $s_2$ (column $(0,1)^T$): $z_{s_2}-c_{s_2}=\tfrac43-\tfrac13c_2\ge0\Rightarrow c_2\le4$.
$$\boxed{1\le c_2\le4}$$
(equivalently, geometrically: the vertex stays optimal while the objective slope $-c_1/c_2$ stays between the two binding constraints' slopes $-2$ and $-\tfrac12$, i.e. $0.5\le 2/c_2\le2$ — the same interval).
