Concept

Shadow price

The rate at which the best value of an optimisation problem improves when one constraint is relaxed by a unit. It is the dual variable of that constraint, and it is zero for any constraint that is not binding at the optimum.

Named by 2 essays across one field — each of them below, with the objects they name alongside it.

What one more unit of constraint 1 is worth. The optimum of a linear program plotted against one of its right-hand sides, as an exact piecewise linear graph, with the breakpoints marked and each piece's slope named as a dual variable.

What a constraint is worth

A linear program and its dual reach the same number. What the dual's variables are is a separate question, and the answer converts a solution into a rate for every constraint — piecewise constant, zero on the constraints that are not doing any work.

applied · Duality

The optimum as the lowest of 3 lines, one per dual vertex. The optimal value of a linear program plotted against one right-hand side, drawn over a family of straight lines, one for each vertex of the dual feasible region. The optimum follows the lowest line throughout.

The lines the optimum lies under

Change the resources a linear program is given and its best value changes too, tracing a graph. Every solution of the dual is a straight line lying above that graph, and the graph is exactly the lowest of those lines — a bent roof of finitely many planks. Require the answer to be in whole numbers and the roof stays where it was while the graph falls away beneath it in steps, and the space between is the part of the problem no price can see.

applied · Duality

Named alongside it

The objects these essays reach for when they reach for this one.

Convexity Duality Linear program Complementary slackness Concave function Derivative Feasible region Integer program Knapsack Lagrangian relaxation

All concepts