Simplex Method — Mathematics Knowledge System

Overview

The simplex method is an iterative algorithm for solving linear programs by traversing the vertices (extreme points) of the feasible polytope, moving along edges to improve the objective at each step. Invented by George Dantzig in 1947, it remains the most widely used LP algorithm in practice despite having exponential worst-case complexity — its average-case performance on practical problems is excellent.

Intuition

Think of the feasible polytope as a multifaceted gem. The simplex method starts at any corner (vertex), looks at neighbouring corners connected by an edge, and moves to whichever neighbour improves the objective. It keeps moving until no improvement is possible — that vertex is optimal.

Formal Definition

Definition

The algorithm works on the standard form LP: min cᵀx, Ax=b, x≥0. A basis B is a set of m linearly independent columns of A; the basic feasible solution (BFS) is xB = B⁻¹b ≥ 0, xN = 0.

\bar{c}_N = c_N - c_B^T B^{-1} N \quad \text{(reduced costs of non-basic variables)}

Reduced costs

\text{Optimality: } \bar{c}_N \ge 0 \implies \text{current BFS is optimal}

Optimality criterion

\text{Pivot: enter column } j: \bar{c}_j < 0,\quad \text{leave row } i = \arg\min_{d_{ij}>0} \frac{x_{B_i}}{d_{ij}}

Minimum ratio test (leave rule)

d = B^{-1} a_j \quad \text{(representation of entering column in current basis)}

Direction vector

Notation

Notation	Meaning
$B$	Basis matrix (m×m invertible submatrix of A)
$x_B,\; x_N$	Basic and non-basic variables
$\bar{c}_N$	Reduced cost vector for non-basic variables
$d = B^{-1}a_j$	Step direction when entering column j

Properties

Finite termination (non-degenerate case)

\text{If no BFS is degenerate (all basic variables positive), the simplex method terminates in finitely many steps}

Bland's rule prevents cycling

\text{Choose entering and leaving variables with smallest index among eligible candidates; then cycling is impossible}

Complexity

\text{Worst-case exponential (Klee-Minty); average-case polynomial under smoothed analysis}

Worked Examples

1
Introduce slacks s₁,s₂: min -x₁-2x₂, s.t. x₁+x₂+s₁=4, x₁+s₂=3, all ≥ 0.
$\text{Standard form: slack variables } s_1, s_2$
2
Initial BFS: x₁=x₂=0, s₁=4, s₂=3. Objective = 0. Basis B = {s₁,s₂}.
$x_B = (s_1, s_2) = (4,3),\quad c^Tx = 0$
3
Reduced costs: c̄₁ = -1, c̄₂ = -2. Most negative is x₂ (index 2): enters.
$\bar{c}_2 = -2 < 0 \implies x_2 \text{ enters}$
4
Minimum ratio test: s₁ row gives 4/1=4; s₂ has no x₂ coefficient (0), so only s₁ can leave.
$\min(4/1) = 4 \implies s_1 \text{ leaves}$
5
New BFS: x₂=4, x₁=0, s₁=0, s₂=3. Objective = -8.
$c^T x = -2 \cdot 4 = -8$

✓ Answer

After one pivot, x₂ enters the basis, objective improves from 0 to -8.

Practice Problems

Mediumfree response

Explain why Bland's rule guarantees finite termination of the simplex method.

Common Mistakes

Common Mistake

Thinking the simplex method always terminates quickly

The worst-case complexity is exponential. The Klee-Minty cube shows it can visit 2ⁿ vertices. However, in practice and under smoothed analysis, average performance is polynomial.

Quiz

In the simplex method, the minimum ratio test determines:

Which variable enters the basisWhich variable leaves the basisWhether the current BFS is optimalThe step size along the objective direction

Historical Background

Dantzig developed the simplex method in 1947, inspired by his work on optimising logistics for the US military. The method's name comes from Dantzig's advisor John von Neumann's suggestion, as the algorithm moves along the boundary of the feasible simplex. Despite Khachian's 1979 polynomial-time ellipsoid method and Karmarkar's 1984 interior-point method, the revised simplex method (with proper pivoting rules) remains the algorithm of choice for large-scale LP.

1947
Dantzig invents the simplex method
George Dantzig
1954
Bland's pivoting rule introduced to prevent cycling
Robert Bland
1977
Klee-Minty example shows exponential worst-case for naive simplex
Victor Klee, George Minty

Summary

The simplex method moves between adjacent vertices of the feasible polytope, improving the objective at each step.
A pivot selects an entering variable (negative reduced cost) and leaving variable (minimum ratio test).
Bland's rule or perturbation techniques prevent cycling in degenerate cases.
Worst-case exponential but excellent average-case performance; widely used in practice.

References

BookDantzig, G.B. — Linear Programming and Extensions (1963), Princeton University Press
WebsiteWikipedia — Simplex algorithm
WebsiteMathWorld — Simplex Method