Duality and Shadow Prices

Here is a question the workshop owner really asks: "If I could rent one more hour of carpentry, how much extra profit would it earn me — and so what is the most I should pay for it?" Astonishingly, the answer is already hiding inside the linear program we solved. Every LP comes with a shadow twin, its dual, and the dual's solution prices every scarce resource in the model. These prices — shadow prices — are the single most useful thing a manager gets out of linear programming, worth more than the optimal plan itself.

We keep the workshop from the geometry page: x_1 tables at £40, x_2 chairs at £30, optimum (10, 20) for £1000, with both resources fully used.

Every LP has a dual

The original problem — the primal — chooses production levels to maximise profit under resource limits. Its dual flips the whole thing on its head: it chooses a price for each resource to minimise the total value of the resource stock, subject to those prices being high enough that no product looks under-charged. Writing y_1 for the price of a carpentry hour and y_2 for a finishing hour:

Primal (max, choose output)	Dual (min, choose resource prices)
\max\; 40x_1 + 30x_2	\min\; 30y_1 + 40y_2
x_1 + x_2 \le 30 (carpentry)	y_1 + 2y_2 \ge 40 (table)
2x_1 + x_2 \le 40 (finishing)	y_1 + y_2 \ge 30 (chair)
x_1, x_2 \ge 0	y_1, y_2 \ge 0

Read the dual's first constraint aloud: "the resource cost of building one table (y_1 for its carpentry hour, 2y_2 for its two finishing hours) must be at least the £40 profit it earns." The dual insists the prices leave no product looking like a bargain the firm is failing to exploit. The transposition is mechanical: the primal's rows become the dual's columns, its profit coefficients become the dual's right-hand sides, and \le-maximise flips to \ge-minimise.

Weak and strong duality

The two problems are locked together by two theorems that are the backbone of the whole subject:

Weak duality. Any feasible dual value is an upper bound on any feasible primal value: for a max primal, primal \le dual, always. No production plan can out-earn the priced-out value of the resources — so a single feasible dual solution certifies a ceiling on profit and lets a solver prove optimality.
Strong duality. If the primal has an optimum, so does the dual, and their optimal values are equal. The gap closes exactly.

Solving the dual by hand (from y_1 + 2y_2 = 40 and y_1 + y_2 = 30) gives y_2 = 10 and y_1 = 20. Its objective is 30(20) + 40(10) = £1000 — exactly the primal's £1000. Strong duality, confirmed on the nose.

The shadow price: what one more hour is worth

The optimal dual variables y_1 = 20 and y_2 = 10 are the shadow prices of carpentry and finishing. A shadow price is the marginal value of one more unit of a resource — the extra profit the optimum would earn if that resource's limit rose by one, holding everything else fixed.

\text{shadow price of a resource} \;=\; \frac{\partial(\text{optimal profit})}{\partial(\text{its right-hand side})}.

So an extra carpentry hour is worth £20 and an extra finishing hour £10. We can check it directly: grant one more carpentry hour (30 → 31) and re-solving moves the optimum to (9, 22) with profit 40(9) + 30(22) = £1020 — up by exactly £20. This is decision gold: the owner should pay up to £20 (never more) to rent a carpentry hour, and overtime in carpentry buys twice the profit of overtime in finishing. Watch the profit climb as we hand the workshop more carpentry hours — the slope of this line is the shadow price:

Complementary slackness, in words

Why was the carpentry hour worth a positive £20? Because carpentry was completely used up at the optimum — it was binding. This is the intuition behind complementary slackness, the rule that pairs the two problems constraint-by-variable:

If a resource is not fully used (its constraint has slack), its shadow price is zero — a spare hour of something you already have too much of is worth nothing.
If a resource has a positive shadow price, it must be fully used (its constraint is binding).
Symmetrically, if a product is actually made (x_j > 0), its dual constraint holds with equality — the profit it earns exactly equals the resource value it consumes.

In the workshop both resources were binding, so both shadow prices came out positive. Had finishing had 100 idle hours instead of a tight 40, its shadow price would have been exactly £0 — buying more of a resource you are not even exhausting cannot help.

It feels wrong: surely more of any resource is good? But a shadow price measures the value at the margin, right now, for this plan. If finishing hours were sitting idle, an extra finishing hour would just join the pile of unused ones — it changes no decision and earns no extra pound, so its marginal value is genuinely zero. This is exactly why factories chase the bottleneck: only the fully-used, binding resources carry a positive shadow price, so only relieving them increases profit. Spend your improvement budget where the shadow price is highest.

The carpentry shadow price is £20 per hour, but that does not mean 100 extra hours are worth £2000. As you add hours, at some point carpentry stops being the binding constraint — finishing runs out first — and the shadow price drops to something smaller (here, to £0 once carpentry exceeds 40 hours). Look at the graph: the slope is a constant £20 only on the range 20 \le b_1 \le 40; outside it the line bends. A shadow price is a marginal, local rate valid over a limited range of right-hand-side values — how wide that range is, is precisely the question of the next page, sensitivity analysis. Never extrapolate a shadow price to a big change without checking its range.