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 3 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

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 duality theorem's four cases, counted over 6,561 small programs. A three-by-three table crossing the status of a linear program — optimal, unbounded or infeasible — with the status of its dual, counting every small program with coefficients from minus one to one. Five of the nine cells are empty.

When one of the two numbers is missing

The duality theorem is usually quoted as an equality: a linear program and its dual reach the same number. That is one of four cases. A program can run away to infinity, or have no feasible point at all, and then its dual is forced into a matching failure. Every small program with coefficients from minus one to one has been classified, and the table has exactly four occupied cells out of nine.

applied · Duality

Named alongside it

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

ConvexityDualityLinear programExistence proofCertificateComplementary slacknessDerivativeFarkas lemmaMatrixMinimaxShadow priceVertex enumeration

All concepts