Linear Programming and the Simplex Method

⚡ Key Takeaways

Linear Programming (LP) optimizes a linear objective function subject to linear equality and inequality constraints. Key result: the optimum, if it exists, occurs at a vertex of the feasible polytope; the Simplex Method (Dantzig, 1947) finds it by walking vertex-to-vertex along edges of improving objective value. Applies to resource allocation, logistics, diet, scheduling, network flow, and game theory. Developed by George Dantzig at the U.S. Air Force; theoretical foundations by Kantorovich, von Neumann, and others.

💡 The Core Insight

The feasible region of an LP is a convex polyhedron. A linear objective attains its extreme value on a vertex (extreme point) of that polyhedron. Since there are finitely many vertices, optimization reduces to searching among them — and the Simplex Method does this intelligently, never moving to a worse vertex, by exploiting the algebraic correspondence between vertices and basic feasible solutions.

DefinitionStandard Form Linear Program

A linear program in standard form is written

1

\quad \max_{x} \; c^Tx \quad \text{subject to} \quad Ax = b,\; x \ge 0

Derivation hint: any inequality $Ax \le b$ becomes equality by adding a nonnegative slack variable $s$ : $Ax + s = b$ , $s \ge 0$ . Symbols:

$x \in \mathbb{R}^n$ — the decision variables (quantities to choose).
$c \in \mathbb{R}^n$ — the cost/profit vector; $c^Tx$ is the objective.
$A \in \mathbb{R}^{m\times n}$ — the constraint matrix ( $m$ constraints, $n$ variables).
$b \in \mathbb{R}^m$ — the right-hand side (resource availabilities).
$x \ge 0$ — componentwise nonnegativity.

The feasible region is $\mathcal{P} = \{x \in \mathbb{R}^n : Ax = b,\; x \ge 0\}$ , a convex polyhedron.

DefinitionBasic Feasible Solution

Assume $A$ has full row rank $m$ with $m < n$ . Partition columns into a basis $B$ (an invertible $m \times m$ submatrix) and nonbasis $N$ . Setting nonbasic variables $x_N = 0$ gives the basic solution

2

\quad x_B = B^{-1}b, \qquad x_N = 0

Derivation hint: $Ax = b$ splits as $Bx_B + Nx_N = b$ ; set $x_N=0$ and invert $B$ . If $x_B = B^{-1}b \ge 0$ , it is a basic feasible solution (BFS). BFSs correspond exactly to vertices of $\mathcal{P}$ .

TheoremFundamental Theorem of Linear Programming

For an LP in standard form with nonempty feasible region $\mathcal{P}$ : 1. If $\mathcal{P} \neq \emptyset$ , there exists at least one basic feasible solution (vertex). 2. If an optimal solution exists, then there exists an optimal solution that is a basic feasible solution. Consequently, optimizing a linear objective reduces to searching a finite set of vertices.

TheoremReduced Costs and Optimality

Given a BFS with basis $B$ , define the reduced cost vector for nonbasic variables

3

\quad \bar{c}_N = c_N - N^T (B^{-1})^T c_B = c_N - N^T y, \quad y = (B^{-1})^T c_B

Derivation hint: substitute $x_B = B^{-1}(b - Nx_N)$ into $c^Tx$ to express the objective in terms of nonbasic variables. For a maximization problem, the current BFS is optimal iff $\bar{c}_N \le 0$ (no nonbasic variable can be increased to improve the objective). The vector $y$ is the vector of dual variables.

ProofThe Simplex Method Improves at Every Step

Setup. Start at a BFS with basis $B$ . The objective written in nonbasic variables is

4

\quad z = c_B^T B^{-1} b + \bar{c}_N^T x_N

Derivation hint: substitute $x_B = B^{-1}b - B^{-1}N x_N$ into $z = c_B^Tx_B + c_N^Tx_N$ .

Step 1 — Pricing. Compute $\bar{c}_N$ via [3]. If all $\bar{c}_j \le 0$ , equation [4] shows increasing any $x_j \ge 0$ cannot raise $z$ , so we are optimal. Stop.

Step 2 — Entering variable. Otherwise choose $j$ with $\bar{c}_j > 0$ . Increasing $x_j$ from $0$ increases $z$ at rate $\bar{c}_j$ .

Step 3 — Ratio test. As $x_j$ increases by $t \ge 0$ , the basic variables change:

5

\quad x_B(t) = B^{-1}b - t\,B^{-1}A_j = \bar{b} - t\,d

Derivation hint: only column $A_j$ enters, so the perturbation direction is $d = B^{-1}A_j$ . To keep $x_B \ge 0$ , the maximum step is

6

\quad t^* = \min_{i:\, d_i > 0} \frac{\bar{b}_i}{d_i}

Derivation hint: the first basic variable to hit zero determines the binding ratio.

Step 4 — Pivot. The variable achieving the minimum leaves the basis; $x_j$ enters. This yields a new BFS (adjacent vertex) with objective increased by $t^*\bar{c}_j \ge 0$ .

Step 5 — Termination. If $d \le 0$ (no positive component) in Step 3, $x_j$ can increase without bound and $z \to +\infty$ : the LP is unbounded. Otherwise, since there are finitely many bases and (under nondegeneracy) the objective strictly increases, no basis repeats, so the algorithm terminates at an optimum. $\blacksquare$

∎

⚠️ Degeneracy and Cycling

When some basic variable equals zero ( $\bar{b}_i = 0$ ), the ratio test may give $t^* = 0$ : a pivot changes the basis but not the vertex or objective. Repeated zero-step pivots can cycle forever. Anti-cycling rules — Bland's rule (choose smallest-index entering/leaving variable) or the lexicographic method — guarantee termination.

GD

George Dantzig

1914–2005

George Bernard Dantzig formulated the Simplex Method in 1947 while working for the U.S. Air Force on planning and logistics (Project SCOOP). He recognized that the "programming" of interdependent military activities could be cast as linear optimization, and devised the vertex-walking algorithm to solve it. A famous anecdote: as a graduate student he arrived late to a statistics class, copied two problems from the board thinking they were homework, and solved them — only later learning they were two famous unsolved problems. Dantzig also championed LP duality and contributed to large-scale decomposition methods. He is widely regarded as the father of linear programming.

🧠 Intuition

Picture the feasible region as a many-faceted gemstone (a convex polytope) sitting in space. The objective $c^Tx$ defines a direction; imagine pushing a flat plane (a level set $c^Tx = z$ ) in that direction as far as it will go while still touching the gem. The last point of contact is a vertex (or, in ties, an edge or face). The Simplex Method doesn't search the interior — it crawls along the edges of the gem, from corner to corner, always moving so the plane advances. Each pivot is one edge-walk. Because there are finitely many corners and we never go backward, we must reach the highest one.

Figure

Simplex walking along vertices of a 2-D feasible polygon toward the optimum

ExampleCarpenter's Production Mix

A carpenter makes tables ( $x_1$ ) and chairs ( $x_2$ ). Profit: $30/table, $20/chair. Constraints:

Wood: $6x_1 + 3x_2 \le 96$ board-feet
Labor: $2x_1 + 4x_2 \le 60$ hours
$x_1, x_2 \ge 0$

Objective: maximize $z = 30x_1 + 20x_2$ .

Standard form (add slacks $s_1,s_2$ ): $6x_1+3x_2+s_1=96$ , $2x_1+4x_2+s_2=60$ .

Iteration 0. Basis $\{s_1,s_2\}$ , $x=(0,0)$ , $z=0$ . Reduced costs $\bar c_{x_1}=30>0$ , $\bar c_{x_2}=20>0$ . Choose $x_1$ (largest). Ratio test: $96/6=16$ , $60/2=30$ . Min is $16$ → $s_1$ leaves. New $x_1=16$ .

Iteration 1. Pivot on row 1. New objective row gives $\bar c_{x_2}=20-30(\tfrac{3}{6})=5>0$ . Enter $x_2$ . Updated column and RHS: ratio test yields $x_2$ enters, $s_2$ leaves. Solving the $2\times2$ system at the vertex $6x_1+3x_2=96$ , $2x_1+4x_2=60$ : $x_1 = 14$ , $x_2 = 4$ .

Check optimality: all reduced costs $\le 0$ . Profit:

z = 30(14)+20(4) = 420+80

Boxed answer: $\boxed{x_1 = 14 \text{ tables}, \; x_2 = 4 \text{ chairs}, \; z = \$500}$

ExampleDiet Problem (Minimization)

Minimize cost of a diet meeting nutrient minimums using Food A ( $x_1$ , $2/unit) and Food B ( $x_2$ , $3/unit):

Protein: $x_1 + 2x_2 \ge 10$
Vitamins: $3x_1 + x_2 \ge 12$
$x_1, x_2 \ge 0$

Objective: minimize $z = 2x_1 + 3x_2$ . Convert $\ge$ to $\le$ for Simplex by subtracting surplus variables (or use the dual / Big-M). Geometrically the optimum lies at the intersection of the two binding constraints:

x_1 + 2x_2 = 10, \qquad 3x_1 + x_2 = 12

Solving: from the second, $x_2 = 12 - 3x_1$ . Substitute: $x_1 + 2(12-3x_1)=10 \Rightarrow x_1 - 6x_1 + 24 = 10 \Rightarrow -5x_1 = -14 \Rightarrow x_1 = 2.8$ . Then $x_2 = 12 - 8.4 = 3.6$ . Cost: $z = 2(2.8) + 3(3.6) = 5.6 + 10.8$

Boxed answer: $\boxed{x_1 = 2.8, \; x_2 = 3.6, \; z = \$16.40}$ (both constraints binding; check other vertices give higher cost).

⚠️ Pitfalls

"The optimum is unique." Not necessarily — if the objective is parallel to a binding constraint, an entire edge or face is optimal (alternative optima).
"Simplex is polynomial-time." No. Klee–Minty (1972) constructed cubes where Simplex with Dantzig's pivot rule visits all $2^n$ vertices. Worst-case behavior is exponential, though typical behavior is excellent.
"More constraints means harder." Adding redundant constraints doesn't change the optimum; complexity scales with the geometry, not raw count.
"Integer answers come for free." LP allows fractional $x$ . Requiring integers makes it Integer Programming, which is NP-hard.

CounterexampleKlee–Minty Cube

Consider the LP over the perturbed unit cube in $\mathbb{R}^n$ :

7

\quad \max\; x_n \quad \text{s.t.}\quad 0 \le x_1 \le 1,\; \varepsilon x_{k-1} \le x_k \le 1 - \varepsilon x_{k-1}\;(2\le k\le n)

Derivation hint: the small $\varepsilon$ -skew distorts a cube so the objective direction threads through every one of the $2^n$ corners. Starting at the origin, Simplex with the steepest-ascent (Dantzig) pivot rule visits all $2^n$ vertices before reaching the optimum. This proves the method has exponential worst-case complexity, motivating polynomial alternatives like the ellipsoid and interior-point methods.

connection

LP sits at a crossroads of several fields. The Simplex Method is fundamentally an exercise in Convex Geometry — walking the vertices of a polytope. Every LP has a paired dual LP, and Linear Programming Duality gives the powerful strong duality theorem: primal and dual optima coincide, and the dual variables $y$ are exactly the shadow prices (marginal values of resources). LP generalizes to Convex Optimization and specializes to Network Flow Problems (where Simplex becomes the highly efficient network Simplex). Game theory connects deeply: von Neumann's minimax theorem for Zero-Sum Games is equivalent to LP duality. Modern competitors are Interior-Point Methods, which traverse the polytope's interior rather than its edges.

🔬 Where this appears

⏳ History

- 1939 — Leonid Kantorovich formulates LP-type problems for Soviet production planning; later shares the 1975 Nobel in Economics.

- 1941 — Frank Hitchcock poses the transportation problem.

- 1945 — George Stigler poses and approximately solves the diet problem by hand.

- 1947 — George Dantzig develops the Simplex Method for U.S. Air Force planning (Project SCOOP).

- 1947 — John von Neumann conjectures and outlines LP duality in a conversation with Dantzig.

- 1951 — Tjalling Koopmans advances activity analysis; shares 1975 Nobel with Kantorovich.

- 1972 — Klee & Minty publish the cube showing Simplex's exponential worst case.

- 1979 — Leonid Khachiyan proves LP solvable in polynomial time via the ellipsoid method.

- 1984 — Narendra Karmarkar introduces a practical polynomial-time interior-point method, sparking the modern era.

open-problem

A famous gap remains between LP theory and practice. Is there a pivot rule for the Simplex Method that runs in polynomial time? Despite decades of effort, no such rule is known, and many natural rules (Dantzig, steepest-edge, Bland) have superpolynomial or exponential worst cases (the Hirsch conjecture on polytope diameters, long thought to bound this, was disproved by Santos in 2010). Relatedly, whether LP can be solved in strongly polynomial time — a number of arithmetic operations bounded by a polynomial in $m,n$ alone, independent of the bit-size of the data — is one of Smale's 18 open problems for the 21st century. Interior-point methods are weakly polynomial; a strongly polynomial algorithm remains undiscovered.

Linear Programming and the Simplex Method

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also