Simplex Problems
Simplex problems ask you to move from one basic feasible solution to another until optimality or unboundedness is detected.
Starting Point
Simplex starts from a basic feasible solution for:
\[\min c^Tx\]subject to:
\[Ax=b, \qquad x\ge 0.\]One Revised Simplex Iteration
Given basis $B$:
- compute $x_B=B^{-1}b$
- compute reduced costs
- choose entering variable $x_j$ with $\bar c_j<0$
- compute $u=B^{-1}A_j$
- perform the ratio test
- choose leaving variable
- update the basis
Ratio Test
If $u_i>0$, compute:
\[\frac{x_{B(i)}}{u_i}.\]The leaving variable corresponds to the smallest nonnegative ratio:
\[\theta^*=\min_{i:u_i>0}\frac{x_{B(i)}}{u_i}.\]Unboundedness Test
If $\bar c_j<0$ and:
\[u=B^{-1}A_j\le 0,\]then the objective is unbounded below in that direction for a minimization problem.
Update
The entering variable becomes positive:
\[x_j=\theta^*.\]The leaving basic variable becomes zero.
The new basis replaces the leaving column with $A_j$.
Stopping Rule
For minimization, stop when all nonbasic reduced costs are nonnegative:
\[\bar c_j\ge 0.\]Then the current BFS is optimal.
Checklist
In each iteration, show:
- current basis
- $x_B$
- reduced costs
- entering variable
- direction/vector $u$
- ratio test
- leaving variable
- new basis
See Also
Added drill source
Use Two Simplex Iterations Drill Set, Two Iterations of Revised Simplex, and Two Iterations of Full Tableau Simplex.
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.