George Dantzig and the Simplex Method: Making Linear Programming Computable
George Dantzig’s simplex method turned linear programming from a modeling idea into a practical computational technique, linking postwar planning problems to the emerging world of electronic computation.
Postwar planning created an optimization problem larger than hand rules could manage
George Dantzig’s route to linear programming began with an administrative engineering problem: the U.S. Air Force wanted to mechanize planning for activities, resources and logistics that had been coordinated through large collections of rules and manual calculations. In his oral history, Dantzig described the goal as speeding up planning that had previously been done by hand.[1]
The breakthrough was to represent many such decisions as systems of linear constraints together with an objective to be maximized or minimized.
Dantzig formulated linear programming and the simplex method in 1947
Dantzig recalled developing the linear-programming model in June 1947 and proposing the simplex method in August of that year.[1] INFORMS histories likewise identify the late 1940s as the period in which he created the method and helped propel mathematical programming and operations research forward.[2]
The historical claim should be scoped carefully. Leonid Kantorovich had independently developed important linear optimization ideas earlier in the Soviet Union, but those results were not widely known in the West when Dantzig did his work.[2]
The word programming originally meant planning
In “linear programming,” programming did not initially mean writing software. It referred to constructing a plan—a program of activities—subject to constraints. The later convergence with digital computers made the terminology look more modern than its origin.
The simplex method searches the geometry of feasible solutions
A linear program defines a feasible region bounded by linear constraints. In geometric terms, the simplex method moves among vertices of that region while seeking an improved objective value.[3]
The method does not enumerate every possible combination. Its power comes from exploiting the structure of linear constraints to move from one basic feasible solution to another in a disciplined way.
Algebra and geometry describe the same computation
The tableau and pivot operations taught in algebraic presentations correspond to changing which constraints define the current vertex. This dual view helped make the method both implementable and mathematically analyzable.
Early applications proved that the method was more than an elegant theorem
Dantzig’s oral history recounts large hand calculations for the diet problem, including a system with nine equations and seventy-seven unknowns that required about 120 person-days with desk calculators.[1] Such examples exposed both the value of optimization and the urgent need for automation.
RAND and Project SCOOP became important institutional settings for developing the field, connecting military planning, mathematical modeling and the new generation of computers.[4]
Electronic computers changed the scale at which simplex could operate
INFORMS records that an early stored-program implementation ran on the Standards Eastern Automatic Computer, or SEAC, in 1951 and solved an Air Force deployment model with dozens of equations and variables.[5] Later implementations at RAND and on commercial scientific computers expanded the size of practical problems.
This was an important co-evolution: optimization created demanding workloads for computers, while faster computers made more ambitious optimization models useful.
Algorithm design had to meet numerical engineering
Real simplex implementations needed pivot rules, numerical safeguards, storage schemes and ways to exploit sparse constraint matrices. Turning the mathematical method into dependable software became its own engineering discipline.
The worst case did not erase the method’s practical importance
Later theory showed that simplex variants can require exponentially many pivots on carefully constructed inputs. That result is historically important because it separates worst-case complexity from observed performance on many practical models.
The existence of polynomial-time alternatives such as ellipsoid and interior-point methods broadened linear-programming theory, but simplex remained deeply embedded in optimization software because mature implementations can be highly effective.
Optimization history resists a single measure of “best”
An algorithm can have an unfavorable worst-case bound and still dominate many real workloads because of structure, engineering, warm starts and the kinds of answers practitioners need. Simplex became a classic example of that distinction.
Linear programming became a general language for constrained choice
The model spread far beyond military planning into transportation, manufacturing, scheduling, blending, finance and many other domains. INFORMS describes Dantzig’s work as foundational to the modern optimization discipline.[2][3]
The deeper contribution was representational: diverse operational questions could be translated into a common mathematical form and handed to a general solver.
Why the simplex method belongs in the CodeHistory timeline
The simplex method is part of computing history because it joined a mathematical abstraction to an executable procedure at the moment electronic computation was becoming practical. Dantzig’s 1947 work created both a powerful modeling framework and a route through the resulting search space.[1]
Its legacy is the idea that software can optimize decisions rather than merely calculate predetermined formulas—a major expansion of what organizations came to expect computers to do.
Works Cited
- 01INFORMS — George Dantzig Oral History informs.org
- 02
- 03INFORMS — O.R. Methodologies: Simplex Method informs.org
- 04
- 05
CodeHistory is a living archive. Citations document the evidence used for this edition; later evidence may refine the account.
Submit a research lead