Two Iterations of Revised Simplex
Two Iterations of Revised Simplex
Use this pattern for exam questions asking for two simplex iterations.
Problem
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x_1,x_2,s_1,s_2\ge0.\]Start with basis ${s_1,s_2}$.
Iteration 1
\[B=I, \qquad x_B=(4,5)^T.\]Reduced costs:
\[\bar c=(-3,-2,0,0).\]Choose $x_1$ entering.
\[u=B^{-1}A_1=(1,2)^T.\]Ratio test:
\[4/1=4, \qquad 5/2=2.5.\]So $s_2$ leaves.
New BFS:
\[x_1=2.5, \quad x_2=0, \quad s_1=1.5, \quad s_2=0.\]Iteration 2
New basis:
\[B=\{s_1,x_1\}.\]Reduced costs:
\[\bar c=(0,-0.5,0,1.5).\]Choose $x_2$ entering.
\[u=B^{-1}A_2=(0.5,0.5)^T.\]Ratio test:
\[1.5/0.5=3, \qquad 2.5/0.5=5.\]So $s_1$ leaves.
New BFS:
\[x_1=1, \quad x_2=3, \quad s_1=0, \quad s_2=0.\]Now all reduced costs are nonnegative, so the solution is optimal.
\[z^*=-9.\]Exam checkpoint
For simplex questions in minimization form, negative reduced costs indicate possible improvement. Use $u=B^{-1}A_j$, apply the ratio test only to positive components of $u$, then update the basis.