Matpic
mathematics, in pictures
Concept

Feasible region

The set of points satisfying every constraint of a program, which is where any optimum has to be found. It is an intersection of half-planes and so convex, which is why a linear objective attains its optimum at a corner of it.

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

Two polytopes, two optima, one number. The feasible regions of a linear program and of its dual, side by side, each with its optimal vertex, and a number line on which the gap between the two optima closes to nothing.

Two numbers that have to meet

Every linear program has a shadow — a second program built from the same numbers read the other way, whose minimum can never fall below the first's maximum. That much is a one-line calculation; the theorem is that the two numbers are always exactly equal.

applied · Duality 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

The rung below settled that a linear program and its dual reach the same number. This one asks what the dual's variables are, 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

Named alongside it

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

ConvexityDualityLinear programComplementary slacknessDerivativeExistence proofMatrixMinimaxShadow priceVertex enumeration

All concepts