Two Simplex Iterations Drill Set
Two Simplex Iterations Drill Set
This file gives the exact algebra expected in simplex exam questions.
Problem 1 — revised simplex, two iterations
Solve by revised simplex for the first two iterations:
\[\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 $B_0={s_1,s_2}$.
Iteration 0
\[B_0=I, \qquad x_B=(4,5)^T.\]Reduced costs:
\[\bar c=(-3,-2,0,0).\]Choose $x_1$ entering.
\[u=B^{-1}A_1=\begin{bmatrix}1\\2\end{bmatrix}.\]Ratio test:
\[\frac{4}{1}=4, \qquad \frac{5}{2}=\frac52.\]So $s_2$ leaves and $\theta=5/2$.
New basis:
\[B_1=\{s_1,x_1\}.\]The new BFS is
\[x_1=\frac52, \quad x_2=0, \quad s_1=\frac32, \quad s_2=0.\]Iteration 1
With basis $B_1={s_1,x_1}$,
\[x_B=\left(\frac32,\frac52\right)^T.\]Reduced costs:
\[\bar c=(0,-1/2,0,3/2).\]Choose $x_2$ entering.
\[u=B^{-1}A_2=\begin{bmatrix}1/2\\1/2\end{bmatrix}.\]Ratio test:
\[\frac{3/2}{1/2}=3, \qquad \frac{5/2}{1/2}=5.\]So $s_1$ leaves and $\theta=3$.
New basis:
\[B_2=\{x_2,x_1\}.\]The new BFS is
\[x_1=1, \quad x_2=3, \quad s_1=0, \quad s_2=0.\]Reduced costs at $B_2$ are nonnegative, so this is optimal.
\[z^*=-9.\]Problem 2 — full tableau simplex, two pivots
Use the maximization tableau convention:
\[\max 3x_1+2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x_1+s_3=3,\] \[x_1,x_2,s_1,s_2,s_3\ge0.\]Initial tableau:
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|---|---|---|---|---|---|---|
| $s_1$ | 1 | 1 | 1 | 0 | 0 | 4 |
| $s_2$ | 2 | 1 | 0 | 1 | 0 | 5 |
| $s_3$ | 1 | 0 | 0 | 0 | 1 | 3 |
| $z$ | -3 | -2 | 0 | 0 | 0 | 0 |
Pivot 1
$x_1$ enters. Ratio test: $4/1$, $5/2$, $3/1$. Minimum is $5/2$, so $s_2$ leaves.
After pivot 1:
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|---|---|---|---|---|---|---|
| $s_1$ | 0 | $1/2$ | 1 | $-1/2$ | 0 | $3/2$ |
| $x_1$ | 1 | $1/2$ | 0 | $1/2$ | 0 | $5/2$ |
| $s_3$ | 0 | $-1/2$ | 0 | $-1/2$ | 1 | $1/2$ |
| $z$ | 0 | $-1/2$ | 0 | $3/2$ | 0 | $15/2$ |
Pivot 2
$x_2$ enters. Ratio test uses positive entries in the $x_2$ column:
\[\frac{3/2}{1/2}=3, \qquad \frac{5/2}{1/2}=5.\]So $s_1$ leaves.
After pivot 2:
| basis | $x_1$ | $x_2$ | $s_1$ | $s_2$ | $s_3$ | RHS |
|---|---|---|---|---|---|---|
| $x_2$ | 0 | 1 | 2 | -1 | 0 | 3 |
| $x_1$ | 1 | 0 | -1 | 1 | 0 | 1 |
| $s_3$ | 0 | 0 | 1 | -1 | 1 | 2 |
| $z$ | 0 | 0 | 1 | 1 | 0 | 9 |
Thus
\[x_1=1, \qquad x_2=3, \qquad z=9.\]Practice problems
For each, do exactly two iterations unless optimality or unboundedness occurs earlier.
- $\min -2x_1-5x_2+4x_3$ subject to $2x_1+x_2+x_3=1$, $x_1+4x_2+4x_3-x_4=1$, $x_1+x_2-x_3+x_5=6$, $x\ge0$.
- $\max 2x_1+x_2$ subject to $x_1+2x_2\le2$, $-x_1+2x_2\le2$, $x_2\ge0$.
- $\min -x_1-x_2$ subject to $-x_1+x_2\le2$, $x_1+x_2\ge1$, $x_1\le1$, $x\ge0$.
- $\min 6x_1-7x_2+9x_3$ subject to $3x_1+4x_2+x_3\ge9$, $2x_1+2x_2-5x_3\ge4$, $7x_1+3x_2+4x_3=10$, $x\ge0$.
Exam checkpoint
Practice under exam timing. Write the full pipeline: model, standard form if needed, BFS/reduced costs if asked, simplex iterations if asked, final objective value and interpretation.
Additional two-iteration practice set
Do exactly two iterations unless the method terminates earlier.
5. Revised simplex from slack basis
\[\min -4x_1-x_2\]subject to
\[x_1+x_2+s_1=6,\] \[2x_1+x_2+s_2=8,\] \[x\ge0.\]Start with $B={s_1,s_2}$.
6. Revised simplex with three constraints
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x_1+s_3=3,\] \[x\ge0.\]Start with $B={s_1,s_2,s_3}$.
7. Tableau practice
\[\max 5x_1+4x_2\]subject to
\[6x_1+4x_2\le24,\] \[x_1+2x_2\le6,\] \[x\ge0.\]Start with slack basis.
8. Detect unboundedness
\[\min -x_1-x_2\]subject to
\[x_1-x_2+s_1=1,\] \[x\ge0.\]Start with $B={s_1}$.
9. Given non-slack basis
\[\min -3x_1-2x_2\]subject to
\[x_1+x_2+s_1=4,\] \[2x_1+x_2+s_2=5,\] \[x\ge0.\]Start from $B={s_1,x_1}$.
10. Standard-form equality problem
\[\min 2x_1+3x_2+4x_3+x_4\]subject to
\[2x_1+x_2+x_3=1,\] \[x_1+3x_2+0.5x_4=2,\] \[x\ge0.\]Start from $B={x_3,x_4}$.
11. Candidate basis supplied
For the same problem, start from $B={x_1,x_2}$ and verify whether simplex terminates immediately.
12. Mixed signs after standard form
First convert to standard form, then perform simplex from the natural slack basis if available:
\[\max 2x_1+x_2\]subject to
\[x_1+2x_2\le2,\] \[-x_1+2x_2\le2,\] \[x_1,x_2\ge0.\]