Simplex Method

The simplex method is the linear-programming algorithm developed by George B. Dantzig in 1947, foundational to operations research. Core idea: the feasible region of an LP in standard form max c^T x s.t. Ax = b, x ≥ 0 is a convex polytope, and a linear objective attains its optimum at a vertex; each vertex corresponds to a basic feasible solution (BFS) in which m basic variables are positive and the n-m non-basic variables are zero. The algorithm proceeds: (1) find an initial BFS (via big-M or two-phase method); (2) compute reduced costs c_j - c_B^T B^(-1) A_j; if all are ≥ 0 for non-basic variables the current BFS is optimal; (3) select an entering variable with negative reduced cost (Dantzig's rule chooses the most negative), determine the leaving variable by the minimum-ratio test, pivot, and return to step (2). Geometrically, the method walks from a vertex of the polytope to an adjacent vertex. Complexity: Klee and Minty (1972) showed via the Klee-Minty cube that the worst case can require 2^n iterations (exponential); however average-case and smoothed analysis (Spielman and Teng 2004) prove the simplex is polynomial-time on average, explaining its outstanding practical speed. Variants: (a) revised simplex uses sparse-matrix factorization for large problems; (b) dual simplex (Lemke 1954) proceeds via dual feasibility; (c) network simplex solves transportation and assignment problems on tree structures in seconds. Cycling — an infinite loop at a degenerate vertex — is prevented by Bland's rule (1977) or lexicographic pivoting. In modern LP solvers the simplex is offered alongside interior-point methods and dominates in warm-start contexts, particularly within MILP branch-and-cut.