Simplex algorithm

Problem formulation and components

Typical instances are written in matrix form: maximize c^T x subject to Ax ≤ b, x ≥ 0 (or equivalent equality form with slack variables). Key elements are the objective coefficients, constraint matrix, right-hand side values, and basic versus nonbasic variables. A feasible basis corresponds to a vertex of the polyhedron, and a basic feasible solution satisfies all constraints and nonnegativity.

Algorithm outline

1. Find an initial basic feasible solution or determine infeasibility (Phase I). A synthetic objective or auxiliary variables are often introduced.
2. Iteratively improve the current basic feasible solution (Phase II) by selecting an entering variable and a leaving variable, then performing a pivot operation that produces a new basis.
3. Repeat until no entering variable can improve the objective, indicating optimality, or until unboundedness is identified.

Geometric view and pivoting

Geometrically, each pivot moves along an edge of the feasible polyhedron to an adjacent vertex with nondecreasing objective value. Pivot selection rules (for example, largest coefficient, Bland's rule) determine which adjacent vertex is chosen and can affect cycling and performance. Bland's rule prevents cycling by a careful tie-breaking scheme; other rules are designed for speed in practice.

History, complexity and variants

George Dantzig popularized the algorithm in 1947, building on earlier theoretical work such as that by Leonid Kantorovich. Although the simplex method is extremely effective in practice, it has an exponential worst-case running time: adversarial examples exist that force many pivots. Nevertheless, it usually runs quickly on real-world problems. Interior-point methods, introduced later, offer polynomial-time guarantees and are complementary alternatives; revised simplex, dual simplex, and network simplex are common practical variants.

Applications and notable facts

The simplex algorithm is widely used in operations research, logistics, finance, manufacturing, and any area requiring linear optimization. Its practical efficiency, rich geometric interpretation, and extensibility to variants (e.g., integer programming heuristics and sensitivity analysis) explain its continued central role in optimization software and teaching. For further technical details and implementations see textbooks and optimization libraries referenced at further reading.