Simplex Method
Solve linear programs by walking from vertex to adjacent vertex of the feasible polyhedron, improving the objective at each pivot.
Vertex-hopping
Because a linear program attains its optimum at a vertex of the feasible polyhedron, the simplex method searches only vertices. It starts at a feasible vertex and repeatedly moves to an adjacent vertex that improves the objective, stopping when no adjacent vertex is better, which certifies optimality.
Basic and nonbasic variables
At each vertex, the variables are split into basic (potentially nonzero, one per constraint) and nonbasic (set to zero). A pivot operation swaps one nonbasic variable into the basis and one basic variable out, which corresponds geometrically to sliding along an edge to the next vertex.
The pivot rule
- Pricing: compute reduced costs; a negative reduced cost (for minimization) means an entering variable can improve the objective.
- Ratio test: determine how far the entering variable can increase before a basic variable hits zero, fixing the leaving variable.
- Repeat until all reduced costs are nonnegative, signaling optimality.
Two phases
When no obvious starting vertex exists, phase one minimizes artificial variables to find a feasible vertex, then phase two optimizes the real objective. Degeneracy (multiple constraints tight at one vertex) can cause cycling, prevented by anti-cycling rules such as Bland's rule or lexicographic ordering.
Complexity
In the worst case the simplex method can visit exponentially many vertices (the Klee-Minty examples), yet in practice it is remarkably fast, typically taking a small multiple of the number of constraints in pivots. Its smoothed complexity is polynomial, which explains the gap between worst case and observed behavior.
# Conceptual pivot: choose entering column j (reduced cost < 0),
# leaving row via min ratio b_i / A[i,j] over A[i,j] > 0, then pivot.The revised simplex method, which updates a factorization rather than a full tableau, is the practical workhorse inside industrial LP solvers.