Simplex Method

Add slacks, then pivot vertex to vertex — enter a profitable variable, leave by the ratio test — until the objective row turns non-positive.

The idea

The simplex method is an algorithm for solving a linear program. Geometrically a finite optimum sits at a vertex of the feasible region, but with many variables the vertices are too numerous to list, so simplex walks to the best one instead: start at a vertex, repeatedly step to a neighboring vertex with a strictly larger objective value, and stop when no neighbor is better.

Proposition (Termination of the simplex method).

If every pivot strictly increases the objective value, then the simplex method halts after finitely many pivots, at a vertex where no neighboring vertex has a larger objective value.

Because every step strictly improves, no vertex is ever revisited, and a polyhedron has finitely many vertices, so the walk must halt; a vertex that no neighbor beats is an optimal vertex.

The walk is carried out algebraically. Each $\le$ constraint receives a slack variable, a nonnegative quantity recording how much room is left before the constraint binds; adding it turns the inequality into an equation, and a slack of $0$ means the constraint is tight. At every stage the variables split in two: the nonbasic ones, held at $0$, and the basic ones, whose values the equations determine. Each such split specifies one vertex of the feasible region.

Algorithm.

Algorithm: Simplex Method Input: maximize a linear objective z subject to ≤ constraints in nonnegative variables Output: a vertex where z is maximal, or the report that z is unbounded 1. add a slack variable to each ≤ constraint, turning it into an equation 2. start at a vertex: original variables nonbasic, held at 0; slacks basic write the objective row: z = constant + a multiple of each nonbasic variable // the split specifies a vertex; the constant is z there 3. if no objective-row coefficient is positive, return the current vertex // no increase can raise z: optimal 4. entering variable = the nonbasic variable with the largest positive objective-row coefficient 5. ratio test: raise the entering variable from 0, other nonbasic variables held at 0, until some basic variable hits 0 // that one is the leaving variable if no equation caps the increase, return "z is unbounded" 6. pivot: the entering and leaving variables trade roles // the walk moves to the adjacent vertex rewrite the equations and the objective row in the new nonbasic variables 7. go to step 3

Ways to work on it

• Walkthrough. Run simplex algebraically on a small LP: slack variables, entering and leaving variables, and the ratio test.
• Practice. Run one simplex pivot: do the ratio test and name the leaving variable.
• Hardest. Read optimality, unboundedness, and termination from the simplex objective row.

Not sure where to start? Take the ten-question placement test.