Matpic
mathematics, in pictures
Ladder

Duality — the ladder

2 distinct arguments against one idea, from the one that introduces it to the one that assumes the rest.
  1. 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.

    rung 1 · applied
  2. 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.

    rung 2 · applied

All ladders