Concept
Optimize a linear objective over a feasible region defined by linear constraints. Kantorovich’s 1939 production planning and Dantzig’s 1947 planning model and simplex method formed in different institutions; a model may be infeasible, unbounded, or have multiple optima.
Understand it in one breath
Optimize a linear objective over a region cut out by linear constraints. If a finite optimum exists and the feasible region has vertices, at least one optimal vertex exists. An entire edge can also be optimal, and a model may be infeasible or unbounded. Simplex and interior-point methods support resource allocation, flow, and production planning.
At a glance
Scenario | Constraints | Objective | Optimum |
|---|---|---|---|
Factory resource allocation | Materials ≤ 100; labor ≤ 80 | Profit = 5x + 3y → max | One of the vertices |
Blending and mixing | Ingredients, nutrition, and demand | Cost → min | An LP when quantities are continuous |
Network flow | Capacity and flow conservation | Cost → min | Some routing and transport problems |
Linear approximation to power dispatch | Demand and capacity | Operating cost → min | Real systems add nonlinear and integer constraints |
Some linear-classification variants | Linear constraints | Linear loss or cost → min | Can be an LP; a standard SVM is usually a quadratic program |
The simplex algorithm moves among adjacent basic feasible solutions, while interior-point methods travel through the feasible region. Model quality also depends on how faithfully the objective and constraints represent reality.
Key formula
Key moments
Kantorovich — production planning with scarce resources
In Leningrad, linear inequalities and solution methods were applied to production allocation. The work remained little known in the West for years and is not treated as a direct transmission into the later American route.
Dantzig — the planning model and simplex method
In US Air Force planning, Dantzig developed a method that improves an objective by moving among vertices of a feasible polytope. Programming meant organizing plans more than writing code.
Khachiyan — the first polynomial-time LP algorithm
The ellipsoid method showed that linear programming is solvable in polynomial time in theory. Worst-case complexity and practical speed are different comparisons.
Karmarkar — a polynomial-time route through the interior
Karmarkar opened a major era for interior-point methods, but his was not the first polynomial-time LP algorithm and it did not replace simplex in every setting.
Modern applications
Airline and logistics planning, network routing, portfolio optimization, and support-vector machines.
Beyond MathVoyage
Loading…