The Simplex Method: How Linear Programming Runs the World

Right now, somewhere in a server room, an algorithm is deciding which pilot flies which plane on which route tomorrow. Across town, another instance of the same algorithm is telling a hospital which nurses cover which shifts. At a refinery, it's figuring out the cheapest blend of crude oil inputs that produces the right mix of gasoline, diesel, and jet fuel. In a shipping warehouse, it's routing delivery trucks across hundreds of stops to minimize total miles driven.

The algorithm is the simplex method — invented in 1947 by a mathematician named George Dantzig — and it silently powers decisions worth trillions of dollars a year. It is, by most estimates, one of the most economically important algorithms ever written. And the core idea behind it is something you could explain to a reasonably bright teenager.

The Concept

Every real-world decision involves tradeoffs. A farmer with 100 acres can grow wheat or corn. Each crop uses a different amount of fertilizer, generates a different profit per acre, and faces a maximum demand the market will absorb. The farmer wants to maximize profit, subject to the constraints of land, fertilizer, and market demand.

That's a linear programming problem — an optimization problem where both the thing you're trying to maximize (or minimize) and all the constraints are linear relationships: no squares, no square roots, just variables multiplied by constants and added together.

The genius of linear programming is that it's powerful enough to model an enormous range of real decisions — and yet structured enough to have provably efficient algorithms. Dantzig's simplex method is the most famous of these algorithms.

The History

The story begins in two places at once, on opposite sides of the Cold War.

In Leningrad in 1938, a young mathematician named Leonid Kantorovich was approached by engineers at a plywood factory. They needed to allocate different tasks across machines with different capabilities to maximize output — a combinatorially explosive problem. Kantorovich recognized that it could be reduced to a mathematical structure: a linear program. He published his method in 1939 in a pamphlet called Mathematical Methods in the Organization and Planning of Production. In the Soviet planned economy, this work was applied to industrial production — and largely ignored outside the USSR until decades later. In 1975, Kantorovich was awarded the Nobel Prize in Economics for this contribution, the only Soviet economist ever so honored.

Across the Atlantic, George Dantzig arrived at the same idea from the other direction: military logistics. During World War II, the US Army Air Forces faced nightmarish planning problems — how to allocate aircraft, personnel, supplies, and missions across a global theater of war with thousands of interdependent constraints. Dantzig joined the Pentagon after the war specifically to address computational logistics, and in the summer of 1947, he developed the simplex method as a systematic algorithm for solving linear programs at scale.

The method was initially kept close to military circles. When Dantzig met with John von Neumann in 1947 to describe his work, von Neumann — one of the most brilliant mathematicians alive — immediately grasped the underlying mathematical structure and, by some accounts, spent the next hour lecturing Dantzig on duality theory. The simplex method became publicly available in 1951, and it changed the world.

The Geometric Key

To understand why the simplex method works, you need a mental picture.

Imagine a linear programming problem with just two variables: how many units of Product A and Product B to manufacture. Plot those two variables on a graph — Product A on the x-axis, Product B on the y-axis. Your constraints — limits on raw materials, machine time, and labor hours — each rule out part of the plane. Every constraint cuts off a half-plane. What's left after all the cuts is a polygon: the feasible region, the set of all decisions that satisfy every constraint. Maybe it's a triangle. Maybe it's an irregular hexagon.

Your profit function says something like "profit = 3A + 5B." You want the point in the feasible region that makes this as large as possible. Geometrically, you're looking for the point that goes as far as possible in the direction your profit is pulling you.

Here's the observation that makes everything work: the optimal solution is always at a corner.

This is guaranteed by the mathematical structure of linear programs. Because the profit function is linear and the feasible region is a convex polygon, you can always improve your profit by moving along the boundary — and the maximum must occur at a vertex, a corner where two constraint boundaries meet. The interior is never better than the boundary, and the boundary is never better than a corner.

Extend this to three variables and the feasible region becomes a three-dimensional polyhedron. With ten variables, it becomes a ten-dimensional polytope — impossible to visualize, but the mathematics holds exactly the same. The optimal solution always lies at a vertex.

The simplex method exploits this perfectly:

1. Start at any feasible vertex. Pick a corner of the polytope where all constraints are satisfied. 2. Look at all neighboring vertices. These are adjacent corners reachable by moving along a single edge. 3. If any neighbor has a better objective value, move there. Take the best available step. 4. Repeat until no neighbor is better. You've found the optimal solution.

It's like navigating a mountain range in fog: at every position, find the uphill direction and take it. Because the feasible region is convex — shaped like a puffed-out polygon, with no valleys or indentations — there are no false peaks. Every local maximum is the global maximum.

Why It Matters

The applications are so pervasive that the simplex method is nearly invisible — it's mathematical infrastructure that runs beneath large-scale decisions without anyone noticing.

Airlines. When you book a flight, the airline has already used linear programming to decide how many seats to offer at each price tier to maximize revenue. Crew scheduling — assigning thousands of pilots and flight attendants to hundreds of daily flights while satisfying FAA rest requirements, union rules, hub constraints, and equipment certifications — is among the most complex linear programs routinely solved. A single major airline's crew scheduling problem can involve millions of variables.

Diet and nutrition. One of the first applications Dantzig tested the simplex method on was the "diet problem," posed by the economist George Stigler in 1945: what is the cheapest combination of foods that meets all nutritional requirements? Stigler had computed a close approximation by hand — a laborious exercise. When the simplex method tackled a version of the full problem in the fall of 1947, using nine nutritional equations and seventy-seven food variables, it demonstrated that systematic computation could find optimal solutions no hand calculation could reach. Today, the multibillion-dollar diet and nutrition industry uses descendants of the same technique.

Oil refining. A petroleum refinery blends multiple grades of crude oil through various processing stages to produce gasoline, diesel, and jet fuel — each with strict chemical property requirements. The linear program that optimizes this blending across dozens of feedstocks and products is solved continuously, and the savings from optimal blending run into hundreds of millions of dollars per year across the industry.

Spreadsheets. The "Solver" add-in in Microsoft Excel quietly runs the simplex method. Anyone who has ever clicked "Solve" to optimize a business model has run code built on a 1947 algorithm.

Telecommunications. Network routing — moving data packets, phone calls, or video streams across a network at minimum cost or maximum throughput — is a linear (or integer) program. The route your video call takes tonight was probably determined by some variant of this math.

The Surprising Paradox

In 1972, computer scientists Victor Klee and Hans Minty constructed a devilish linear program where the simplex method — under certain pivot rules — visits every single vertex before finding the optimum. With n variables, there can be up to 2^n vertices. That's exponential worst-case complexity: a problem with just 50 variables could, in the worst case, require visiting more vertices than there are atoms in the observable universe.

And yet in practice, it runs fast. Problems with tens of thousands of variables get solved in seconds. Problems with millions of variables get solved in minutes. For decades, this was a mathematical mystery.

The theoretical resolution came in 1979, when Soviet mathematician Leonid Khachiyan proved that linear programs can always be solved in polynomial time using a completely different approach called the ellipsoid method — a polynomial-time guarantee that no simplex variant can claim. This was a landmark theoretical result. But in practice, the ellipsoid method was slower than simplex on real problems, and it remained a theoretical achievement rather than a practical workhorse.

The practical explanation came later, from probabilistic analysis: on the random-looking inputs that arise from real logistics networks, production schedules, and resource allocation problems, the simplex method visits only a polynomial number of vertices on average. The adversarial worst case almost never occurs in the wild.

In 1984, mathematician Narendra Karmarkar developed the interior point method, a polynomial-time algorithm that also performs well in practice. Modern solvers often use a combination of simplex and interior point methods, switching strategies depending on problem structure. But simplex remains the workhorse for the majority of practical applications — a nearly eighty-year-old algorithm still winning races.

The Details: What a Pivot Actually Is

In the classroom, the simplex method is often taught with tableaux — big grids of numbers that get transformed at each step. This is the algebraic face of the geometric idea. Each "corner" of the feasible region corresponds to a basic feasible solution: a point where exactly enough constraints hold with equality to pin down a unique location. Moving from one corner to an adjacent one means changing which set of constraints are "active" — this swap is called a pivot.

Different ways of choosing which pivot to make next — different pivot rules — lead to wildly different traversal paths through the polytope, and dramatically different performance. The Bland's rule guarantees termination but can be slow. The steepest edge rule tracks gradient information to make bigger progress per step. Modern commercial solvers use sophisticated adaptive rules, preprocessing techniques, and numerical stability tricks that would be unrecognizable to Dantzig, but that walk in exactly his footsteps.

Takeaways

• Linear programming models optimization with linear constraints — a mathematical structure that captures an enormous range of real decisions, from supply chains to financial portfolios to nutrition planning.
• The simplex method, invented by George Dantzig in 1947, solves these problems by starting at a corner of the feasible region and walking to better corners until no improvement is possible.
• The key structural insight: the optimal solution of any linear program always lies at a vertex of the feasible region — which makes it possible to search a discrete set of corners rather than a continuous infinite space.
• Despite exponential worst-case behavior (the Klee-Minty construction), the simplex method runs efficiently on real-world problems, making it one of the most economically important algorithms in history.
• Linear programming runs invisibly everywhere — in airline scheduling, energy refining, supply chains, diet optimization, and spreadsheet solvers — often beneath decisions worth trillions of dollars without anyone noticing the math behind them.