LP duality and shadow prices

The idea

Every linear program has a twin, its dual. If the original (the primal) decides how much to make from scarce resources, the dual asks: what is one unit of each resource worth? The prices it finds are called shadow prices, and they tell you how much the best profit would rise if you had one more unit of that resource.

The math, with a comment on each formula

The primal problem, with profits c, resource use A and resource limits b: \max_{x}\; c^\top x \quad\text{subject to}\quad Ax \le b,\; x \ge 0. In words: choose how much to make (x) to maximise profit without using more than the limits b.

The dual problem has one price y_i for each resource: \min_{y}\; b^\top y \quad\text{subject to}\quad A^\top y \ge c,\; y \ge 0. In words: set prices on the resources so that each product’s resources are worth at least its profit, and make the total value of the stock b^\top y as small as possible.

Strong duality. If the primal has an optimal solution, so does the dual, and c^\top x^\star = b^\top y^\star . In words: the best profit equals the total value of the resources at the shadow prices. Weak duality (c^\top x \le b^\top y for any feasible pair) is what makes this a certificate: when a plan and a set of prices have equal values, neither can be improved.

Reading a shadow price. If resource i has y_i^\star > 0, it is fully used, and one more unit raises the optimal profit by y_i^\star (as long as the change is small enough that the same resources stay the bottleneck). A resource with spare stock has y_i^\star = 0: buying more of it would not raise the profit. (The reverse need not hold: a fully used resource can still have a zero price when another resource is the real bottleneck.)

Worked example

A company makes products A and B. Each A needs 2 hours of labour and 1 unit of raw material and earns 3; each B needs 1 hour of labour and 2 units of raw material and earns 2. There are 100 labour hours and 80 units of raw material. The kernel solved this model (status optimal):

maximize 3 a + 2 b
subject to
2 a + b <= 100
a + 2 b <= 80
a, b >= 0
# a = units of product A to make (units)
# b = units of product B to make (units)

The best plan makes 40 of A and 20 of B, for a profit of 160.

Feasible region and optimum for L01-01. Blue: constraint lines and feasible region; dashed orange: objective line through the optimum; dot: optimum.

The dual problem (one price per resource) has the optimal value 160, equal to the primal optimum, as strong duality says. Its prices are y_1 = 1.3333 for a labour hour and y_2 = 0.3333 for a unit of raw material; the primal solver reports the same numbers, 1.3333 and 0.3333. Both resources are fully used, so both have a positive price.

Try it

Check the shadow price of labour by giving the company one more labour hour (101 instead of 100):

maximize 3 a + 2 b
subject to
2 a + b <= 101
a + 2 b <= 80
a, b >= 0
# a, b = units of products A and B

The best profit becomes 161.3333, against 160 before: the increase is the labour price 1.3333. Change the 80 and the 101 to other values, and see how long the price stays valid.