Where should the next rupee go?
Start with what a feasible region is (topic 01) and why the best point of a linear problem sits at one of its corners (02). Topic 16 is the algorithm that walks from corner to corner to find it, topic 03 shows that every such problem has a mirror problem whose answer is the price of each limit, and topic 17 lets the objective curve, ending at Goemans–Williamson's semidefinite relaxation of Max-Cut, the classical result that QAOA on the quantum side has to beat. Turn six of these shapes over in 3D →
Solve a linear program and you get more than the plan. You get, for free, what each limit is costing you: the amount your objective would improve if you had one more unit of it. That number is the shadow price, and it is the answer to the question the person paying for the model actually had, which is almost never "what should we build" and almost always "where should we spend next".
Two consequences, both counterintuitive, both worth internalising:
A resource with slack is worth exactly zero. Not "a little". Zero. If the best plan is not using all the material you already have, more material cannot change the best plan. Everyone's instinct is to buy more of the expensive thing or the scarce-feeling thing; the correct answer is to buy more of whatever is binding.
Relieving a bottleneck destroys its own value. Buy enough machine-hours and machine-hours stop being the constraint: at which point their shadow price collapses to zero and something else becomes the bottleneck. This is why sensible investment plans alternate between resources instead of doubling down, and why the curve above is concave rather than a straight line.
Every linear program has a twin. Where the primal asks "what should I build?", the dual asks "what are my limits worth?":
PRIMAL DUAL
maximise cᵀx minimise bᵀy
s.t. Ax ≤ b s.t. Aᵀy ≥ c
x ≥ 0 y ≥ 0
Weak duality says any feasible y gives a ceiling on any feasible x: cᵀx ≤ yᵀAx ≤ bᵀy. Strong duality says that at the optimum the two are equal, and that equality is the certificate. A solver can hand you a plan and a set of dual prices, and you can check optimality yourself in one multiplication, without trusting the solver at all.
Worked on the figure's own instance: the duals are y = (3/4, 1/2, 0), giving a dual objective of 24(3/4) + 6(1/2) + 12(0) = 21, exactly the primal optimum. Verified.
Complementary slackness makes the zero rigorous: for each constraint, either it binds or its dual price is zero: never both nonzero. And right-hand-side ranging is the missing half nobody quotes: a shadow price is a one-sided derivative valid only while the same set of constraints stays binding. Report a price without its range and you have told half the truth.
Lagrangian relaxation is what you reach for when a model has a few "hard" constraints sitting on top of an otherwise easy problem. Instead of solving the whole thing at once, move the hard constraints Dx ≤ e into the objective with a penalty:
L(λ) = max cᵀx + λᵀ(e − Dx)
s.t. Ax ≤ b, x ≥ 0
For any λ ≥ 0 this is easier to solve than the original: the hard constraints are gone, only the easy ones (Ax ≤ b) remain, and its value L(λ) is always at least as good as the true optimum, exactly the same weak-duality logic as above, just applied to a hand-picked subset of constraints instead of all of them. Minimising L(λ) over λ ≥ 0 (the Lagrangian dual) gives the tightest bound this decomposition can produce. This is precisely how branch & bound (topic 05) gets a bound sharp enough to prune large integer programs in practice, when solving the full LP relaxation at every node would be too slow. (Everything on this page is linear; the Lagrangian trick above is really the entry point to a much bigger field, for the general convex case, see Boyd & Vandenberghe, Convex Optimization, CUP, 2004, the standard reference.)
Electricity markets, every five minutes Wholesale power markets clear by solving an optimisation: meet demand at every node, respect every transmission line's capacity and every generator's ramp rate, at least cost. The shadow price of the demand constraint at each node is the price you pay for electricity there. It is not set by a committee; it falls out of the dual of the dispatch problem. When a transmission line binds, prices on either side of it separate. That is congestion, and the price gap is literally the line's shadow price. How finely those prices are reported differs by market: the North American ISOs publish a price per node (locational marginal pricing), while Europe, Australia and India clear on the same kind of optimisation but publish prices per zone or region. The duals are doing the pricing either way; only the granularity changes.
Check yourself
In the best plan, one resource is not fully used. What is one more unit of it worth?
A resource with slack is worth exactly zero: if the best plan does not use all you have, more cannot change the best plan. Buy whatever is binding.