Linear Programming and the Simplex Method

A linear program seeks to maximize or minimize a linear function $c^{T}x$ over a feasible region defined by linear constraints $Ax\le b$, $x\ge 0$. Because both objective and constraints are linear, the feasible region is a convex polyhedron, and the objective increases in straight directions — making the problem tractable yet enormously expressive. LP matters because a vast range of real decisions (what to produce, ship, blend, or schedule) become solvable exactly and at scale. The surprising fact: although the Simplex Method can in pathological cases visit exponentially many vertices, in practice it is so fast and reliable that it powered industrial optimization for decades before polynomial-time interior-point methods even existed.

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.

Formal Statement

Standard Form Linear Program

A linear program in standard form is written

Symbols:

• $x\in {\mathbb{R}}^n$ — the decision variables (quantities to choose).
• $c\in {\mathbb{R}}^n$ — the cost/profit vector; $c^{T}x$ 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.

Basic 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

If $x_B=B^{-1}b\ge 0$, it is a basic feasible solution (BFS). BFSs correspond exactly to vertices of $\mathcal{P}$.

Fundamental Theorem of Linear Programming

For an LP in standard form with nonempty feasible region $\mathcal{P}$:

1. If $\mathcal{P}\ne \varnothing$, 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.

Reduced Costs and Optimality

Given a BFS with basis $B$, define the reduced cost vector for 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.

Why It Holds / Derivation

The Simplex Method Improves at Every Step

To keep $x_B\ge 0$, the maximum step is

Degeneracy and Cycling

When some basic variable equals zero (${\bar{b}}_i=0$), the ratio test may give $t^{\ast }=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.

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.

Building Intuition

Picture the feasible region as a many-faceted gemstone (a convex polytope) sitting in space. The objective $c^{T}x$ defines a direction; imagine pushing a flat plane (a level set $c^{T}x=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.

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

Worked Examples

Carpenter'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$

Ratio test: $96/6=16$, $60/2=30$. Min is $16$ → $s_1$ leaves. New $x_1=16$.

Solving the $2\times 2$ system at the vertex $6x_1+3x_2=96$, $2x_1+4x_2=60$: $x_1=14$, $x_2=4$.

Diet Problem (Minimization)

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

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

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:

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$

Common Misconceptions

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.

Klee–Minty Cube

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

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.

Connections

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.

Real-World Applications

1. Airline crew scheduling & fleet assignment — American Airlines and others save hundreds of millions yearly assigning crews and aircraft via LP/IP.
2. Petroleum refining (blending) — refineries blend crude streams to meet octane and sulfur specs at minimum cost; one of LP's earliest industrial uses (1950s).
3. Diet & nutrition planning — Stigler's 1945 diet problem; still used in agriculture and institutional food service.
4. Supply chain & transportation — minimizing shipping cost from warehouses to demand points (the classic transportation problem).
5. Portfolio optimization — linear approximations to risk/return tradeoffs in finance.
6. Telecommunications & energy networks — routing flow and dispatching power generation (economic dispatch) under capacity limits.
7. Manufacturing production planning — product mix, machine loading, and inventory across multi-period horizons.

Historical Development

• 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.

Subtleties & Limits

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.

See Also