The simplex method is a family of algorithms for solving linear programming problems: optimizing a linear objective subject to linear equality and inequality constraints. Developed by George B. Dantzig in 1947, it became a foundational tool of operations research and computational optimization. Its central operation is a change of basis, or pivot, which replaces one set of dependent variables with another. Geometrically, a nondegenerate pivot usually moves between adjacent vertices of a feasible polyhedron.
The method combines a finite algebraic description of candidate solutions with tests for improvement, optimality, and unboundedness. Although some pivot rules require exponentially many iterations on specially constructed problems, carefully engineered implementations are highly effective on many practical models. Primal simplex, dual simplex, and specialized variants remain important in production planning, transportation, scheduling, and integer optimization. Their performance depends not only on the pivot rule but also on sparse linear algebra, numerical tolerances, preprocessing, and the ability to reuse a previously computed basis.
Historical development and scope
George B. Dantzig developed the simplex method in 1947 while working on planning problems for the United States Air Force. Such problems involved allocating limited resources among competing activities whose requirements and contributions could be expressed linearly. Earlier work, including Leonid Kantorovich’s 1939 research on production planning, had already identified important classes of linear allocation problems. Dantzig supplied a general computational procedure that could handle many constraints and variables systematically, making linear programming an operational methodology rather than only a mathematical formulation.
The method’s emergence coincided with the development of electronic computers and the mathematical theory of economic allocation. Connections with game theory, particularly work associated with John von Neumann, helped establish the significance of linear programming duality. Duality showed that the output of an optimization procedure could include not merely a proposed allocation but also a matching system of bounds or prices certifying its optimality. Dantzig’s 1963 book, Linear Programming and Extensions, became a major systematic account of the subject and its applications.
Early descriptions commonly presented the method through a tableau: a rectangular arrangement containing transformed constraint coefficients, right-hand sides, and objective information. A pivot could then be performed by elementary row operations. As problems grew, storing and updating the entire tableau became inefficient. The revised simplex method instead maintained a basis representation and computed the quantities needed for each iteration. Subsequent developments included dual simplex, improved pricing strategies, sparse basis factorizations, and effective handling of variable bounds. These changes transformed the computational scale attainable without changing the underlying basis-exchange principle.
The word simplex refers to a geometric object, a simplex, but the feasible region of a linear program need not itself be a simplex. It may have arbitrarily many faces and vertices or be unbounded. The algorithm is also distinct from the Nelder–Mead simplex method, introduced in 1965 for derivative-free nonlinear optimization. Nelder–Mead moves and reshapes a collection of points forming a simplex; the linear programming simplex method manipulates bases of a constraint matrix. Their shared name does not imply a common optimality theory or computational mechanism.
Standard form and the geometry of basic solutions
A convenient formulation for the primal simplex method is
where is an matrix, , and . The superscript denotes transposition. The objective function is linear, and the feasible set is the intersection of an affine space with nonnegativity constraints. It is therefore a convex set and, more specifically, a polyhedron. Inequality constraints can be converted into equalities using slack or surplus variables; an unrestricted variable can be written as the difference of two nonnegative variables.
Assume that has full row rank , after redundant equations have been removed. Choose linearly independent columns of , forming a square nonsingular matrix . The associated variables are basic, and the remaining variables are nonbasic. With the nonbasic variables set to zero, the equations determine
This is a basic solution. It is a basic feasible solution if . The use of a basis here is algebraic: the selected columns form a basis of the constraint column space. A particular feasible point may correspond to more than one basis.
For the standard-form feasible set, basic feasible solutions are precisely its extreme points, also called vertices. A point is extreme if it cannot be expressed as a nontrivial convex combination of two distinct feasible points. At a basic solution, setting enough coordinates to zero leaves the equality constraints sufficient to determine the remaining coordinates uniquely. If all basic variables are strictly positive, the basic feasible solution is nondegenerate. If one or more are zero, it is degenerate, and several basis descriptions may represent the same vertex.
A central theorem of linear programming states that if a standard-form problem is feasible and its objective is bounded below, an optimal basic feasible solution exists. Thus the search can be restricted to finitely many bases, even though the feasible set generally contains infinitely many points. The method does not enumerate all bases in a fixed order. Instead, objective information guides movement among them. The geometric picture requires care: degeneracy allows a basis change with no movement, and a general linear program written without standard-form nonnegativity restrictions may have no vertices until an appropriate reformulation is made.
Reduced costs and the primal pivot
For a current basis, partition the constraints and objective as
Eliminating the basic variables gives
For a nonbasic variable , its reduced cost is
where is column of . It measures the objective change per unit increase in , with the basic variables adjusted to maintain the equations. For minimization, a negative reduced cost identifies a potentially improving entering variable.
Let enter, and calculate . Increasing from zero to changes the basic variables to . Nonnegativity is maintained precisely while each component with satisfies . The maximum feasible step is therefore
A basic variable attaining this minimum leaves the basis. The algorithm replaces its column in by , producing the next basis. The objective change is , which is strictly negative when and . This is the minimum-ratio test.
Two important termination tests follow directly. If every nonbasic reduced cost is nonnegative, the current feasible solution is optimal: the displayed objective expression shows that every feasible nonnegative can only increase or preserve its value. If a negative-reduced-cost column has for every , no basic variable restricts its increase. The resulting feasible ray decreases the objective indefinitely, certifying unboundedness. Neither conclusion requires inspection of every feasible solution.
The choice among improving columns is called pricing. Dantzig’s original rule selects a most negative reduced cost for minimization. Steepest-edge pricing estimates objective improvement relative to the length of the corresponding feasible direction, rather than relying on reduced cost alone. Devex pricing approximates related weights more cheaply. Partial pricing examines subsets of columns instead of recomputing all reduced costs at every iteration. These strategies can substantially change iteration counts and computational work. A large predicted improvement is not necessarily realized, because the ratio test may permit only a short step—or a zero step at a degenerate vertex.
A worked example
Consider the production model
subject to
Here and are activity levels, the first inequality limits a shared resource, and the other two impose individual capacities. Introduce nonnegative slack variables , and replace maximization by minimization of . The constraints become
The slack columns form an identity matrix, so the initial basis is immediately feasible: , , , with .
The initial reduced costs of and are and . Under the most-negative-reduced-cost rule, enters first. Its transformed column is , so the relevant ratios are and . The minimum is ; hence leaves. The new point has , , , , and . The maximized objective has risen from to . The first pivot reaches the individual capacity limit for , rather than exhausting the shared resource.
The new equations can be expressed as
and the minimized objective is
Thus has reduced cost and enters next. With , increasing reduces from and from , so reaches zero first, at . The resulting solution is , , with original objective value . Geometrically, the algorithm has moved from to , then to , following edges of the feasible polygon.
At the final basis, the nonbasic variables are and , and substitution gives
Both reduced costs are positive, so no feasible point can have a minimized objective below . Equivalently, no feasible production plan yields revenue above . A matching resource-price certificate is obtained by multiplying the three original inequalities by , , and , respectively: their sum gives . This certificate illustrates how the algebra of a final simplex basis also produces a dual explanation of optimality.
Finding an initial feasible basis
An initial feasible basis is easy to obtain when every constraint has the form , all , and . Adding one slack variable per inequality produces an identity basis whose values are the right-hand sides. Equality constraints, lower-bound inequalities, and negative right-hand sides generally prevent this simple construction. Since primal simplex assumes feasibility, it cannot simply begin with an arbitrary nonsingular collection of columns. A separate initialization procedure must either produce a feasible basis or establish that the original constraints are inconsistent.
The standard two-phase method introduces artificial variables. After multiplying rows by where necessary, suppose . An auxiliary problem can be written as
The artificial variables , together with , provide an initial feasible basis. Phase I applies simplex to minimize their sum. Because each artificial variable is nonnegative, an optimal auxiliary value of zero means they can all vanish, giving a feasible point for the original problem. A strictly positive optimal value proves that the original system has no feasible solution.
At the end of a successful Phase I, some artificial variables may remain basic at value zero. They cannot simply be retained as unrestricted substitutes for original variables during Phase II. Where possible, a pivot replaces each with an original or slack variable. If a transformed row contains no suitable replacement coefficient, it identifies a redundant equality that can be removed. The original objective is then restored and recomputed relative to the surviving basis. Phase II proceeds with the ordinary improvement and optimality tests. This separation gives feasibility and optimization distinct, explicit roles.
An alternative is the big- method, which adds a very large penalty for artificial variables to the original objective. Symbolically, an infinitely dominant penalty expresses the desired priority, but an arbitrarily chosen finite numerical can be troublesome: too small a value may not enforce feasibility, while too large a value can aggravate scaling and roundoff problems. Practical solvers also use crash procedures to construct promising starting bases and preprocessing to detect elementary contradictions, such as incompatible variable bounds or an equation with . When a related problem has already been solved, reusing its basis may avoid a fresh Phase I altogether.
Duality, certificates, and dual simplex
For the standard-form minimization problem, the dual is
where is unrestricted in sign. For a basis , define
Then , with zero reduced costs on basic columns. Consequently, nonnegative reduced costs mean that is dual feasible. The primal simplex optimality test therefore checks the existence of a dual feasible solution generated by the current basis. For a primal feasible basic solution, the objective values agree: . Weak duality then proves optimality.
The relation is a concrete instance of Lagrangian duality. For any primal and dual feasible pair,
Equality holds exactly when every product vanishes. These are the complementary slackness conditions: a positive primal variable must have zero reduced cost, while a strictly positive reduced cost forces the corresponding variable to zero at optimum. Simplex makes these relationships explicit through its basis representation. Dual multipliers also support economic interpretations as marginal resource values, provided the sign conventions and the range over which the current basis remains valid are respected.
The dual simplex method, introduced by Carlton Lemke in 1954, reverses the feasibility priorities. It preserves dual feasibility while repairing primal infeasibility. In the present minimization convention, suppose all reduced costs are nonnegative but a basic value is negative. In the dictionary , the chosen infeasible row can be repaired by increasing a nonbasic variable only if . A dual ratio test selects an eligible entering variable so that the resulting reduced costs remain nonnegative. In a simple standard-form version, it minimizes over eligible columns.
Dual simplex is particularly effective after changes that preserve reduced-cost feasibility but disrupt primal feasibility. Changing right-hand sides leaves the reduced costs of a fixed basis unchanged, although basic values may become negative. Adding a violated inequality with a slack variable can likewise produce a useful dual-feasible starting basis. This is important in optimization procedures that repeatedly strengthen a model. Modern implementations generalize the elementary scheme to lower and upper variable bounds, using bound flips, specialized ratio tests, and numerical safeguards. Primal and dual simplex are thus complementary approaches rather than competing descriptions of an identical sequence of pivots.
Degeneracy, cycling, and pivot selection
A basic feasible solution is degenerate when at least one basic variable equals zero. In the ratio test, such a variable can force . The corresponding pivot changes the basis but not the point or objective value. This phenomenon explains why a negative reduced cost does not always produce an immediate improvement: it indicates a favorable algebraic direction, but the current basis may allow no positive step along it. Degeneracy commonly arises from redundant or tightly interacting constraints, network structure, and formulations in which many variables simultaneously lie at bounds.
A sequence of zero-length pivots can cause stalling, during which many bases are visited with little or no objective progress. More severely, some pivot rules can return to a previously visited basis and repeat forever. This is cycling. Since a nondegenerate improving pivot strictly changes the objective in the favorable direction, cycling in the usual primal method requires degeneracy. The finiteness of the set of bases is therefore not, by itself, a proof that an arbitrary pivot rule terminates. A complete finite algorithm needs a rule that prevents repeated bases or otherwise ensures progress.
Bland’s rule, published by Robert Bland in 1977, provides a simple finite rule. Give every variable a fixed index. Choose the eligible entering variable with the smallest index, and among tied candidates in the minimum-ratio test, choose the leaving basic variable with the smallest index. In exact arithmetic, this prevents cycling. Lexicographic pivoting provides another approach: ties are resolved by an ordering equivalent to a hierarchy of infinitesimal perturbations of the right-hand side. The perturbation separates otherwise coincident events without requiring ordinary floating-point numbers to represent actual infinitesimals.
Anti-cycling guarantees and computational efficiency are distinct concerns. Bland’s rule need not be the fastest practical pricing strategy, while more aggressive pricing may require safeguards against long degenerate sequences. Solvers often combine perturbations, alternative pricing strategies, and carefully designed ratio tests. Zero reduced costs must also be interpreted cautiously. A nonbasic variable with zero reduced cost indicates a direction with no immediate objective change, but it yields a distinct alternative optimum only if an appropriate positive feasible step is possible. At a degenerate optimum, several optimal bases may represent the same point. Conversely, an entire edge or higher-dimensional face may consist of distinct optimal solutions, reflecting genuine nonuniqueness rather than merely multiple basis descriptions.
Revised simplex and numerical implementation
The tableau method updates all transformed coefficients after every pivot, using operations closely related to Gaussian elimination. It is clear for small examples but can be expensive when the number of variables is large. The revised simplex method avoids maintaining the entire tableau. Its principal computations are solving
together with reduced-cost calculations . These systems supply the basic values, dual multipliers, and entering direction. The notation is mathematically convenient, but a solver ordinarily does not construct an explicit inverse matrix.
Instead, implementations use numerical linear algebra, typically sparse variants of LU factorization. A basis change replaces just one column, so updating an existing factorization is often cheaper than rebuilding it. Product-form inverse updates and later sparse update schemes exploit this structure. As updates accumulate, however, fill-in and numerical error may increase. Periodic refactorization rebuilds a cleaner representation and can restore computational reliability. The cost of an iteration therefore depends on much more than the number of constraints and variables: sparsity patterns and the evolving basis are crucial.
Real implementations use floating-point arithmetic, so feasibility and optimality tests require tolerances rather than exact comparisons with zero. A tiny computed negative basic value may be roundoff, whereas a larger violation may signal a genuinely infeasible basis. Small pivot elements can amplify numerical error, especially when the basis has a large condition number. Ratio tests used in production software may allow small controlled feasibility deviations to avoid unstable pivots. Scaling rows and columns, checking residuals, and recomputing key quantities contribute to numerical stability, but cannot make poorly conditioned data exact.
Modern solvers also work directly with bounded variables, rather than converting every bound into an extra equation. A nonbasic variable may sit at its lower or upper bound; reduced-cost sign tests depend on which movement is permitted. Presolve can remove fixed variables, tighten bounds, substitute equations, and identify redundant constraints before iterations begin. After solving, postsolve reconstructs a solution to the original model. When mathematical certification is required, rational reconstruction or exact-arithmetic checks can verify primal feasibility, dual feasibility, and objective equality. A floating-point solver status is a numerical conclusion under specified tolerances, whereas an exact primal–dual certificate establishes the corresponding algebraic claim.
Complexity and the limits of geometric intuition
A basic upper bound on the number of possible bases is , since a basis selects of the columns, although many selections may be singular or infeasible. A finite pivot rule could in principle visit a large fraction of them. In 1972, Victor Klee and George Minty constructed distorted cubes on which a standard form of Dantzig’s pivot rule follows an exponentially long path. In dimension , the construction can force traversal of all vertices. It demonstrated that compelling geometric intuition and good empirical performance do not imply a polynomial worst-case bound.
The result concerns a specified pivot rule and family of formulations, not a claim that every simplex execution visits exponentially many vertices. Different rules may behave very differently on the same polyhedron, and adversarial constructions depend on the rule being analyzed. Nevertheless, exponential lower bounds are known for many natural simplex variants. Complexity also has two components: the number of pivots and the arithmetic work needed for each pivot. For rational inputs, exact computation must additionally account for the number of bits required to represent intermediate and output values.
Linear programming itself is polynomial-time solvable. Leonid Khachiyan’s 1979 ellipsoid result established this in the rational bit model, and Narendra Karmarkar’s 1984 work stimulated the development of efficient interior-point methods. Interior-point algorithms usually move through the interior of an appropriate feasible region or relaxation rather than following a sequence of vertex bases. Their polynomial-time analyses therefore do not supply polynomial bounds for ordinary simplex pivot rules. Nor does the existence of a long simplex path imply that the underlying linear program is computationally intractable.
Average-case and smoothed analyses address different questions from worst-case bounds. Smoothed analysis studies performance after small random perturbations of arbitrary input data; work by Daniel Spielman and Shang-Hua Teng established polynomial smoothed bounds for a particular simplex approach under specified perturbation assumptions. Such results help explain why specially constructed hard instances need not represent typical computational behavior, without guaranteeing uniform practical performance. A related unresolved issue is whether linear programming admits a strongly polynomial algorithm: roughly, one whose number of arithmetic operations is polynomial in the numbers of variables and constraints, independent of numerical coefficient sizes, with controlled intermediate encoding lengths. This is stronger than ordinary polynomial-time solvability and is not resolved by the success of either simplex or interior-point implementations.
Applications, reoptimization, and specialized variants
Simplex applies whenever a model has a linear objective and linear constraints. In production planning, variables can represent activity levels, constraints express labor and material availability, and objective coefficients encode costs or revenues. Transportation models assign shipment quantities to routes subject to supply and demand balances. Blending models constrain ingredient proportions and quality measures. In zero-sum games, finite mixed-strategy equilibrium problems can be expressed through linear programs. The validity of each application depends on the modeling assumptions—such as divisibility and linear resource consumption—not on the optimization algorithm alone.
One of simplex’s major practical strengths is reoptimization. A basis is a compact description of a solved model’s local algebraic structure and can remain useful when data change. If only changes, the basis matrix and reduced costs remain fixed, although feasibility must be rechecked. If only objective coefficients change, the current primal point remains feasible, while dual feasibility may fail. Primal or dual simplex can then restore optimality from the existing basis. These relationships underlie sensitivity analysis: within a range where the basis remains optimal, basic variables and objective values respond to data changes through explicit linear or affine expressions.
In integer programming, simplex frequently solves continuous relaxations inside branch-and-bound and cutting-plane algorithms. Branching changes bounds; cuts add inequalities excluding unwanted fractional solutions. Both modifications often leave a basis suitable for rapid dual-simplex reoptimization. The LP solution supplies a bound for the discrete optimization problem, but simplex itself does not enforce integrality. Some structured formulations have integral vertices because of properties of their constraint matrices, allowing a linear programming solution to solve the associated discrete problem without explicit branching.
Column generation exploits reduced costs when the potential number of variables is enormous. A restricted master problem contains only selected columns; its dual multipliers define a pricing subproblem that searches for an omitted variable with improving reduced cost. For a minimization model, proving that no omitted column has negative reduced cost establishes optimality of the full LP relaxation under the usual pricing conditions. The network simplex method uses a different specialization: for minimum-cost flow problems, bases can be represented by spanning-tree structures, allowing pivots and feasibility changes to be implemented through network operations. General-purpose solvers may also combine interior-point optimization with crossover, a procedure that converts an interior solution into a basic solution suitable for basis-based sensitivity analysis and subsequent reoptimization.