Question 2 of 10: Simplex Method and Coupled Coefficient/RHS Sensitivity

Question 2: Simplex Method and Coupled Coefficient/RHS Sensitivity (20 marks: a–10, b–10)

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. $\max Z=-3x_1+8x_2$ subject to $4x_1+2x_2\le12$, $2x_1+3x_2\le6$, $x_1,x_2\ge0$.

Find. (a) the optimal $(x_1,x_2,Z)$ by the Simplex Method; (b) the range of the linked change (% increase $\beta$ in $c_2=8$, paired with a $2\beta\%$ decrease in $b_1=12$) over which the current optimal basis stays optimal, and the resulting solution/objective as functions of $\beta$.

Approach. Add slacks and pivot once (the negative $x_1$ coefficient already signals it won't enter), confirm optimality from the $Z$-row signs, then use $B^{-1}$-based ranging on the final basis to track how the entering-variable test responds as $c_2$ and $b_1$ move together.

1. Standard form. Introduce slacks $s_1,s_2\ge0$: $4x_1+2x_2+s_1=12$, $2x_1+3x_2+s_2=6$. Writing the objective row as $Z+3x_1-8x_2=0$ (from $Z=-3x_1+8x_2$), the most negative coefficient is $x_2$'s ($-8$) — $x_1$'s coefficient is already positive ($+3$), so $x_1$ can never be an improving entering variable and is skipped.
2. Single pivot — $x_2$ enters. Ratio test: $12/2=6$ (row 1) vs $6/3=2$ (row 2) → row 2 leaves ($s_2$ exits). Pivoting on the row-2/$x_2$ entry ($x_2=2-\tfrac23x_1-\tfrac13s_2$) and substituting into row 1 and the $Z$-row gives $$\tfrac83x_1+s_1-\tfrac23s_2=8,\qquad Z+\tfrac{25}{3}x_1+\tfrac83s_2=16.$$ Both $Z$-row coefficients are now $\ge0$ → optimal after a single pivot.
3. Read off the optimum. Nonbasic $x_1=s_2=0$; basic $x_2=2$, $s_1=8$: $$\boxed{x_1=0,\quad x_2=2,\quad Z^\*=16.}$$ Check: $4(0)+2(2)=4\le12$ (slack 8) ✓; $2(0)+3(2)=6\le6$ (binding) ✓.
4. Part (b) — set up the linked change. Let $\beta$ = % increase applied to $c_2=8$, so $c_2=8(1+\beta/100)$, paired with a $2\beta\%$ decrease in $b_1=12$: $b_1=12(1-2\beta/100)$ ($c_1=-3$ and $b_2=6$ stay fixed). The current basis is $\{x_2,s_1\}$ with basis matrix (columns for $x_2,s_1$ from the two constraints) $B=\begin{pmatrix}2&1\\3&0\end{pmatrix}$, $B^{-1}=\begin{pmatrix}0&\tfrac13\\1&-\tfrac23\end{pmatrix}$.
5. RHS feasibility (drives the upper limit on $\beta$). Basic values as $b_1$ varies (with $c_2$ not entering this calculation): $\begin{pmatrix}x_2\\s_1\end{pmatrix}=B^{-1}\begin{pmatrix}b_1\\6\end{pmatrix}=\begin{pmatrix}2\\b_1-4\end{pmatrix}$. Feasibility needs $s_1=b_1-4\ge0\Rightarrow b_1\ge4$. Substituting $b_1=12(1-2\beta/100)\ge4$ gives $$\boxed{\beta\le100/3\approx33.3\%.}$$
6. Reduced-cost feasibility (checks the other direction). With $c_2$ entering the objective row, the nonbasic reduced costs are $r_{x_1}=-3-\tfrac23c_2$ and $r_{s_2}=-\tfrac13c_2$; both must stay $\le0$ for a max problem. At $c_2=8$ these are $-\tfrac{25}{3}$ and $-\tfrac83$, and increasing $c_2$ only makes both more negative — so this direction never binds as $\beta$ grows; the RHS condition in Step 5 is the sole limit.
7. Solution and objective as functions of $\beta$. Over the valid range $0\le\beta\le100/3\%$, $x_2=2$ is unchanged by $b_1$ (constraint 1 stays slack or just touches zero) and by $c_2$ (it is still the same vertex), so $(x_1,x_2)=(0,2)$ throughout; only $Z$ tracks the changing coefficient: $$\boxed{Z(\beta)=c_2\cdot x_2=8\Big(1+\tfrac{\beta}{100}\Big)\times2=16\Big(1+\tfrac{\beta}{100}\Big)=16+0.16\beta.}$$ At the limit $\beta=100/3\%$: $Z=16(1+1/3)=64/3\approx21.33$.