Let us go back to the workshop that makes kitchen tables and coffee tables with 100 hours of carpentry and 80 of painting. We found that the optimal plan yields 3,600 euros. Now let us change perspective. A competitor wants to rent all the workshop's hours and asks: what is the minimum price per hour I should offer so that the owner prefers accepting to producing?
This second question is a new linear program, the dual of the first. Duality theory says that the two questions have the same answer, and that the link between the two problems contains valuable economic information.
Building the dual
The starting problem, called the primal:
maximise 60x + 40y
2x + y ≤ 100
x + y ≤ 80
x, y ≥ 0
The competitor offers a euros per hour of carpentry and b euros per hour of painting. They want to spend as little as possible, but every table the owner gives up making must be paid for at least as much as its margin:
minimise 100a + 80b
2a + b ≥ 60 (kitchen table)
a + b ≥ 40 (coffee table)
a, b ≥ 0
The general scheme is mechanical:
- each constraint of the primal becomes a variable of the dual;
- each variable of the primal becomes a constraint of the dual;
- the right-hand sides of the primal become the coefficients of the dual objective, and vice versa;
- the coefficient matrix is transposed;
- a maximum becomes a minimum, and «less than or equal» becomes «greater than or equal».
The dual of the dual is the primal again.
Weak and strong duality
Weak duality: the value of any feasible solution of the (maximisation) primal is less than or equal to the value of any feasible solution of the (minimisation) dual. The reason is simple: no production plan can earn more than the value of the resources it consumes, if these are paid enough to cover every product.
This has an immediate practical use. If an algorithm finds a plan worth 3,500 euros and a dual solution worth 3,700, you know the optimum lies between 3,500 and 3,700, even without having found it. The gap between the two values measures how far you are from the optimum.
Strong duality: if the primal has a finite optimum, so does the dual, and the two values coincide. In the example the dual has its optimum at a = 20, b = 20, with value 100·20 + 80·20 = 3,600: exactly the margin of the optimal plan.
The other combinations follow too: if the primal is unbounded the dual is infeasible, and if the dual is unbounded the primal is infeasible.
Shadow prices
The optimal dual variables have a direct interpretation: they are the shadow prices of the resources. A shadow price tells you how much the optimal value would increase if one more unit of that resource were available, all else being equal.
In the example both are 20: one extra hour of carpentry or painting would bring 20 euros of additional margin. If a carpenter's overtime costs 15 euros an hour, it is worth it; if it costs 25, it is not.
Two important caveats:
- the shadow price is valid only within a certain range: adding many hours of carpentry, sooner or later painting becomes the only bottleneck and the value of a carpentry hour drops;
- a resource with a zero shadow price is not scarce: adding more is useless, because some is already left over.
Complementary slackness
The optimal solutions of the primal and the dual are linked by simple conditions, called complementary slackness:
- if a primal constraint is not binding (some resource is left), the corresponding dual variable is zero;
- if a dual variable is positive, the corresponding constraint is binding;
- likewise, if a product is made (positive primal variable), its dual constraint holds with equality: the value of the resources consumed exactly equals the margin.
| Resource | Hours used | Hours available | Shadow price |
|---|---|---|---|
| Carpentry | 100 | 100 | 20 |
| Painting | 80 | 80 | 20 |
These conditions make it possible to check whether a pair of solutions is optimal without redoing the calculations, and they underpin many algorithms.
Reduced costs
For a product not made at the optimum, the reduced cost tells you how much its margin would have to improve before making it pays off. It is computed as the difference between the value of the resources it would consume (at shadow prices) and its margin. If the workshop were considering a third model needing 1 hour of carpentry and 2 of painting, the resources consumed would be worth 20 + 40 = 60 euros: the new model pays off only if it earns more than 60 euros.
Where duality comes back
Duality is not just theory. The max-flow min-cut theorem is a special case of linear duality. The Hungarian method for assignment essentially works on dual variables. Many large-scale optimisation algorithms exploit the dual to break huge problems into smaller parts, and dual bounds are the standard way to certify the quality of a solution.
In short
- Every linear program has a dual: constraints become variables and vice versa.
- Weak duality: every dual solution provides a bound on the primal's value.
- Strong duality: at the optimum the primal and dual values coincide.
- The optimal dual variables are the shadow prices: the marginal value of each resource.
- Complementary slackness and reduced costs show which resources are scarce and which products would pay off.
