Matpic
mathematics, in pictures
Concept

Linear programming

Maximising a linear expression subject to linear inequalities. Its optimum is always attained at a corner of the region the inequalities cut out, which is what makes it solvable and what makes the corners' arithmetic decide everything about it.

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

The 6 corners, and nothing in between. The 6 permutation matrices of size 3, drawn as grids. A search over every table of shares on a fine grid finds these and only these as corners of the set.

The corners are whole assignments

A table of shares can be written as a lottery over whole assignments, which the anchor's first rung demonstrates on one example. The general statement is that the corners of the set of such tables are exactly the whole assignments, and that single fact is why the whole subject is easy.

applied · Assignment A cheapest assignment, and the proof that it is cheapest. A 4 by 4 cost table with the cheapest assignment marked, and a row price and column price beside each. Every used cell's two prices add to its cost, and the prices total the assignment's cost.

A price for every person and task

The cheapest assignment can be found without comparing it to any other. Attach a number to each person and each task so that no pair's two numbers exceed its cost, and if the numbers add to an assignment's total, that assignment is cheapest — proved, by an argument that never mentions the alternatives.

applied · Assignment The corner that is a half on every edge. A 3-vertex graph beside a table of the 5 corners of its matching relaxation. 4 are whole and one assigns a half to every edge.

Where the corners stop being whole

Everything on this ladder rests on one property — the relaxation of the assignment problem has whole-numbered corners. Add a single edge that closes an odd cycle and the property fails, a corner appears with a half in every coordinate, and the problem changes character completely.

applied · Assignment

Named alongside it

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

AssignmentMatchingIntegralityPolytopeAlgorithmBipartiteCertificateComplementary slacknessComplexityConvexityDualityExtreme point

All concepts