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$:

  1. compute $x_B=B^{-1}b$
  2. compute reduced costs
  3. choose entering variable $x_j$ with $\bar c_j<0$
  4. compute $u=B^{-1}A_j$
  5. perform the ratio test
  6. choose leaving variable
  7. 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.