A small workshop makes two kinds of table. The kitchen table needs 2 hours of carpentry and 1 hour of painting, and yields a margin of 60 euros. The coffee table needs 1 hour of carpentry and 1 hour of painting, and yields 40 euros. Each week there are 100 hours of carpentry and 80 of painting available. How many tables of each type should be made?
This is the typical linear programming (LP) problem: choosing quantities that respect limited resources, while maximising a profit or minimising a cost. The word «programming» has nothing to do with software: it comes from the language of planning, in the sense of a «production programme».
The three ingredients of a model
Every LP model has the same structure.
- Decision variables: the quantities we can choose. Here x = kitchen tables, y = coffee tables.
- Objective function: what we want to maximise or minimise, expressed as a linear combination of the variables. Here: maximise 60x + 40y.
- Constraints: linear inequalities or equalities the variables must satisfy.
The complete model:
maximise 60x + 40y
subject to 2x + y ≤ 100 (carpentry)
x + y ≤ 80 (painting)
x, y ≥ 0
«Linear» means that variables and constants only appear multiplied by numbers and added together: no products of variables, squares, roots or «if… then» conditions. It is a strong restriction, but it allows models with thousands or millions of variables to be solved reliably.
Solving by eye with the graphical method
With two variables the problem can be drawn. Each constraint divides the plane into two halves; the intersection of the allowed halves is the feasible region, a convex polygon. In this example the vertices of the polygon are (0, 0), (50, 0), (20, 60) and (0, 80).
A fundamental result says that, if the problem has an optimum, at least one optimum lies at a vertex of the region. So it is enough to evaluate the objective at the vertices:
| Vertex | 60x + 40y |
|---|---|
| (0, 0) | 0 |
| (50, 0) | 3,000 |
| (20, 60) | 3,600 |
| (0, 80) | 3,200 |
The optimal solution is to make 20 kitchen tables and 60 coffee tables, for a margin of 3,600 euros. Both resources are fully used: 2·20 + 60 = 100 hours of carpentry and 20 + 60 = 80 of painting.
A second example: the diet problem
The diet problem is an LP classic: choosing how much of each food to buy to cover the requirement for certain nutrients at minimum cost. Variables: the quantities of each food. Objective: minimise total cost. Constraints: for each nutrient, the sum of the contents must exceed a minimum threshold.
The same structure describes blending animal feed, fuels or metal alloys: ingredients with different properties are combined to obtain a product with the required characteristics at minimum cost.
Common modelling mistakes
In my work the hard part is almost never the calculation, but the translation. Some recurring mistakes:
- forgetting non-negativity: without x ≥ 0 the solver may propose making −30 tables to «free up» hours;
- inconsistent units: hours in one constraint and minutes in another, euros and thousands of euros in the same objective;
- constraints that are too tight: the model turns out infeasible, that is, without solutions; this is often a sign that a requirement should be treated as a preference rather than an obligation;
- missing constraints: the model turns out unbounded, meaning the profit can grow forever; in reality there is always a limit, such as market demand, that has not been written down;
- hidden non-linearities: volume discounts, fixed set-up costs or «all or nothing» choices are not linear and require integer or binary variables.
What a solver returns
Besides the optimal values of the variables, an LP solver provides valuable information:
- which constraints are binding, that is, satisfied with equality: these are the truly scarce resources;
- the shadow prices: how much the objective would improve with one more unit of each resource;
- the sensitivity ranges: within which values the coefficients can vary without changing the optimal solution.
In the tables example, knowing that one extra hour of carpentry is worth 20 euros of margin and one extra hour of painting is also worth 20 helps decide whether paying for overtime makes sense.
Tools for writing it on a computer
There is no need to implement an algorithm: mature solvers exist, both commercial and free, along with libraries that let you write the model almost as you would on paper. In Python, for example, libraries such as PuLP or SciPy's optimisation functions accept an objective and constraints and return the solution. For small problems, the solver add-in included with spreadsheets is also enough.
In short
- An LP model has decision variables, a linear objective function and linear constraints.
- The feasible region is a convex polygon and the optimum, if it exists, lies at a vertex.
- Production, diet and blending are typical examples of the same structure.
- The most common mistakes are modelling ones: signs, units, missing or overly rigid constraints.
- Binding constraints and shadow prices show which resources are truly scarce and what they are worth.
