Matpic
mathematics, in pictures
Concept

Linear program

The problem of making a weighted sum as large or as small as possible subject to finitely many straight-line inequalities.

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

primal: max 3x₁ + 4x₂dual: min 12y₁ + 10y₂3x₁ + 2x₂ ≤ 12x₁ + 4x₂ ≤ 103y₁ + y₂ ≥ 32y₁ + 4y₂ ≥ 401234501234x₁x₂78/512100(14/5, 9/5)00.511.522.5301234y₁y₂78/53024(4/5, 3/5)05101520253078/51210078/53024they meet at 78/5primal vertex values, from belowdual vertex values, from aboveweak duality checked on all 12 pairs — each of the 4 feasible primal vertices against each of the 3 feasible dual vertices — andcᵀx ≤ bᵀy held every timestrong duality is the equality of the two optima: max 3x₁ + 4x₂ = 78/5 = min 12y₁ + 10y₂, one number reached from below andfrom abovethe dual region is unbounded upward and the drawing cuts it at the box; the enumeration ignores the cut

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 51015202530051015202530b₁max 3x₁ + 4x₂b₁ = 5b₁ = 30slope 2 = y₁slope 4/5 = y₁slope 0 = y₁one row per linear piecethe optimum sits onslope of the optimumdual variable y₁b₁ from 2 to 5b₁ from 5 to 30b₁ from 30 to 32row 1 and x₁ = 0(0, 5/4)22row 1 and row 2(1/5, 49/20)4/54/5row 2 and x₂ = 0(10, 0)00the optimum is piecewise linear in b₁ with 3 pieces, breaking at b₁ = 5 and 30on each piece the slope, taken from the optima at the two ends, equals the dual variable y₁ at the middleof that piece — 2, then 4/5, then 0 — and it changes exactly where a different vertex becomes optimal

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 the row chooser mixes00.20.40.60.81-4-20246weight on row Apayoff to the row choosercol Xcol Ycol Z8/15 → 19/15the most the row chooser can guarantee: 19/15the column chooser mixes00.20.40.60.81-4-20246weight on col Xpayoff to the row chooserrow Arow B7/15 → 19/15the least the column chooser can concede: 19/15both sides name 19/15 = 1.267the value is 19/15 = 1.267, reached by the row chooser mixing 8/15 on A and by the column chooser mixing 7/15 on Xthe lower envelope of 3 lines peaks where two cross; the upper envelope of 2 bottoms out at that heightchecked against every pure reply on both sides, and over 61 mixtures on one side and 91 on the other

The value from both sides

Two choosers move at the same instant, and each asks the cautious question — how much can be guaranteed, whatever the other does. With pure choices the two answers are usually different numbers; allow a probability and they are forced to be the same one.

applied · equilibrium

Named alongside it

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

ConvexityDualityExistence proofFeasible regionMinimaxComplementary slacknessDerivativeDominant strategyMatrixMixed strategyNash equilibriumShadow price

All concepts