Simplex Idea

The simplex idea is to search vertices of the feasible polyhedron by moving between adjacent basic feasible solutions.

Geometry

A finite LP optimum can be found at a vertex when it exists. Simplex moves from vertex to neighboring vertex.

Algebra

Vertices correspond to basic feasible solutions. A pivot changes one basis column, so simplex moves to an adjacent BFS.

Improvement

For minimization, simplex chooses a nonbasic variable with negative reduced cost. This gives a direction of cost decrease.

Termination

Simplex stops when all reduced costs are nonnegative, or when an improving direction is unbounded.

Checklist

Explain vertex search, basis pivots, entering variables, leaving variables, and termination.

See Also

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.