Developed by Leonid V. Kantorovich (Mathematical Methods of Organizing and Planning Production, 1939) and George B. Dantzig, whose simplex algorithm (Maximization of a Linear Function of Variables Subject to Linear Inequalities, 1951) solves it.
Writes an allocation problem as a linear objective under linear constraints and solves for the best mix, along with what loosening each constraint is worth.
The best product mix sits at a corner of what the machines allow
A cabinet shop makes standard and deluxe cabinets on a cutting machine (40 hours a week) and a finishing line (60 hours). The shaded part of the chart is beyond the hours; the white part is every mix the shop can make. Move the mix and watch the margin: it is highest where both machines run full, at the corner of 16 standard and 12 deluxe. Raise the deluxe margin past $200 and the best corner moves to all deluxe. Illustrative.
This mixNot possible: this mix needs more hours than a machine has, so the shop cannot make it.Possible: the machines can make this mix; compare its margin with the best corner.
An example
A cabinet shop made two products: a standard cabinet with a $100 margin and a deluxe one with $150. Every cabinet passed through a cutting machine, available 40 hours a week, and a finishing line, available 60. A standard cabinet took one hour of cutting and three of finishing; a deluxe took two of cutting and one of finishing. The owner had been running ten of each, a habit from the shop's early days, for $2,500 a week.
His daughter, back from a business degree, wrote the week as a small linear program: two quantities to choose, one margin to maximize, two limits on hours. The best mix sat where both machines ran full, 16 standard and 12 deluxe, for $3,400. The same solution showed that an extra cutting hour was worth $70 and an extra finishing hour only $10, so when a used cutting machine came up for sale, the shop knew what a second shift on it would pay.
Why it works
Many allocation problems feel like judgment calls because every choice affects every other through shared limits. Writing them as a linear program makes the interaction explicit: the quantities to choose, the objective, and each limit as a straight-line constraint. The set of feasible choices is then a region with straight edges, and a linear objective is always best at one of its corners. The simplex method walks from corner to corner, improving each time, until no neighbor is better.
The second payoff is the shadow price: how much the objective would improve if one limit were loosened by a unit. It says which constraint is worth relaxing and by how much, and it shows which ones do not bind at all. That turns a production plan into an investment case, and it shows where buying more of a limited resource would be money thrown away.
The thinking behind it
Leonid V. Kantorovich Leonid V. Kantorovich, a Soviet mathematician, developed linear programming in 1939 for planning production, in Mathematical Methods of Organizing and Planning Production, published by Leningrad State University and translated into English in Management Science in 1960. He is regarded as a founder of the field, and he shared the 1975 Nobel Memorial Prize in Economic Sciences for contributions to the theory of the optimal allocation of resources.
George B. Dantzig George B. Dantzig, an American mathematical scientist, devised the simplex method in 1947 while working on Air Force planning and published it as Maximization of a Linear Function of Variables Subject to Linear Inequalities (1951), in a volume edited by Tjalling C. Koopmans. His Linear Programming and Extensions (1963) became the standard account. He is counted, with Kantorovich and John von Neumann, among the founders of linear programming.
How to run it
- Define the decision variables. Name each quantity to choose, with its unit: cabinets a week, hours per team, dollars per channel.
- Write the objective. State what to maximize or minimize as a sum of each variable times its margin or cost.
- Write each limit as a linear constraint. Hours, budget, storage, and minimum orders each become one line saying the total used stays within what is available.
- Check that the relations are close to linear. If a margin falls with volume or a setup cost applies, note it before trusting the answer.
- Solve with a standard solver. A spreadsheet solver handles a few dozen variables; larger problems need a dedicated one.
- Read the optimum and the shadow prices. See which constraints run full, and what one more unit of each would be worth.
- Sanity-check before acting. Ask whether the mix is sellable and the shop floor can run it, then adjust the constraints and solve again.
Where it goes wrong
The common failure is a model that leaves out a real limit. The solver then recommends a mix the business cannot sell or staff, such as all deluxe cabinets when the market takes only eight a week. Add demand limits and minimum runs as constraints, and rerun.
A second failure is forcing a curved problem into straight lines. Volume discounts, overtime premiums, and setup times bend the relations, and the corner the solver finds may not be the best real plan. Model the bends with separate variables or use a nonlinear method. The third is reading shadow prices too far. They hold only for small changes; a large expansion of one machine can move the best corner and change every price.
When to use something else
- Theory of Constraints. When one bottleneck limits the whole flow and the work is managing it day to day.
- Marginal Analysis. When there is one decision to scale, such as how many people to hire, and no web of shared limits.
- Constraint Satisfaction. When the task is finding any plan that meets every rule, such as a timetable, with no margin to maximize.
Where it sits in SOLVE eX
Go to the source
- Mathematical Methods of Organizing and Planning Production, 1939
- Maximization of a Linear Function of Variables Subject to Linear Inequalities, Activity Analysis of Production and Allocation, edited by Tjalling C. Koopmans, Wiley; the method dates from 1947, 1951