Simplex Starting From a Given BFS

Many exam problems give a candidate vector $\bar x$ and ask what to do next.

Steps

1. Convert the problem to standard form.
2. Lift $\bar x$ by computing slack and surplus variables.
3. Check that $\bar x$ is feasible.
4. Identify a basis associated with $\bar x$.
5. Compute reduced costs.
6. If not optimal, choose an entering variable and perform the requested number of iterations.

Important

If the given point is not a BFS, the simplex method cannot start from it directly. You must either find an initial BFS or use a phase-one method. In this course, exam questions usually give a BFS or ask you to verify that it is not one.

Mini checklist

• Are there exactly $m$ basic columns?
• Is $B$ invertible?
• Is $B^{-1}b\ge0$?
• Are nonbasic variables zero?
• Are reduced costs nonnegative for minimization?

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.