Question 2 of 8: Two Iterations of the Revised Simplex Method
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
National Exams — May 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 revised simplex method (ch. 3–5), network optimization models (ch. 9), integer programming (ch. 12), decision analysis (ch. 16), and queueing theory (ch. 17).
Question 2: Two Iterations of the Revised Simplex Method (20 marks)
Given.$\text{Max } Z=2x_1-x_2+x_3$ subject to $3x_1+x_2+x_3\le 60$, $x_1-x_2+2x_3\le 10$, $x_1+x_2-x_3\le 20$, all $x_i\ge 0$.
Find. The basis, $B^{-1}$, simplex multipliers $y$, reduced costs, entering/leaving variables and basic solution produced by exactly two iterations of the Revised Simplex method.
Approach. Add slacks to get the initial identity basis, then at each iteration compute $y=c_B^{\mathsf T}B^{-1}$, price out the nonbasic columns to find the entering variable, run the min-ratio test on $B^{-1}a_{\text{enter}}$ for the leaving variable, and update $B^{-1}$ by the product-form (elementary row) pivot.
Standard form and initial basis. Add slacks $s_1,s_2,s_3\ge0$:
$$3x_1+x_2+x_3+s_1=60,\quad x_1-x_2+2x_3+s_2=10,\quad x_1+x_2-x_3+s_3=20.$$
The initial basis is $B_0=[a_{s_1},a_{s_2},a_{s_3}]=I_3$, so $B_0^{-1}=I_3$, $x_{B_0}=B_0^{-1}b=(60,10,20)^{\mathsf T}$, $c_{B_0}=(0,0,0)$, hence $y_0=c_{B_0}B_0^{-1}=(0,0,0)$. Pricing out the nonbasic columns, $c_j-y_0a_j$ gives reduced costs $(2,-1,1)$ for $(x_1,x_2,x_3)$: $x_1$ has the largest positive reduced cost, so $x_1$ enters.
Iteration 1 — ratio test and pivot.$d=B_0^{-1}a_{x_1}=(3,1,1)^{\mathsf T}$; the min-ratio test compares $60/3=20$, $10/1=10$, $20/1=20$ — the minimum is row 2, so $s_2$ leaves. Updating by the pivot row (row 2, pivot element 1) gives the new basis $B_1=[a_{s_1},a_{x_1},a_{s_3}]$ with
$$B_1^{-1}=\begin{bmatrix}1&-3&0\\0&1&0\\0&-1&1\end{bmatrix},\qquad x_{B_1}=B_1^{-1}b=\begin{bmatrix}30\\10\\10\end{bmatrix}\ \Rightarrow\ s_1=30,\ x_1=10,\ s_3=10.$$
Objective so far: $Z_1=c_{B_1}\cdot x_{B_1}=2(10)=\boxed{20}$.
Iteration 1 — price out for iteration 2.$y_1=c_{B_1}B_1^{-1}=(0,2,0)$. Reduced costs for the nonbasic columns: $c_{x_2}-y_1a_{x_2}=-1-(2)(-1)=1$, $c_{x_3}-y_1a_{x_3}=1-(2)(2)=-3$, $c_{s_2}-y_1a_{s_2}=0-(2)(1)=-2$. Only $x_2$ is positive, so $x_2$ enters.
Iteration 2 — ratio test and pivot.$d=B_1^{-1}a_{x_2}=(4,-1,2)^{\mathsf T}$. Only rows with positive $d_i$ compete: row 1, $30/4=7.5$, and row 3, $10/2=5$ (row 2's $d_2=-1<0$ is excluded — increasing $x_2$ only helps $x_1$ there). The minimum is row 3, so $s_3$ leaves. The new basis $B_2=[a_{s_1},a_{x_1},a_{x_2}]$ gives
$$B_2^{-1}=\begin{bmatrix}1&-1&-2\\0&0.5&0.5\\0&-0.5&0.5\end{bmatrix},\qquad x_{B_2}=B_2^{-1}b=\begin{bmatrix}10\\15\\5\end{bmatrix}\ \Rightarrow\ s_1=10,\ x_1=15,\ x_2=5,\ x_3=0.$$
Objective after iteration 2: $Z_2=2(15)-1(5)=\boxed{25}$.
Optimality check.$y_2=c_{B_2}B_2^{-1}=(0,1.5,0.5)$; reduced costs for the remaining nonbasic columns are $c_{x_3}-y_2a_{x_3}=-1.5$, $c_{s_2}-y_2a_{s_2}=-1.5$, $c_{s_3}-y_2a_{s_3}=-0.5$ — all $\le 0$, so the tableau is already optimal after exactly the two requested iterations (the question only asks to perform two iterations, and here they happen to reach the optimum).
