dyas · an OPTIMIZATION duality · measured
THE PRIMAL & THE DUAL
max c·x (resources) ⟺ min b·y (prices) · strong duality: the two optima are EQUAL
Every optimization has a shadow. A primal that maximizes output under limits has a dual that minimizes the value of those limits — a different question, a different variable, a different shape. Yet at the optimum they meet on the same number. Two problems, one value.
◧ primal — maximize
max 3x + 2y
x + y ≤ 4
x + 3y ≤ 6
x, y ≥ 0
optimum: 12 at (4, 0)
dual — minimize ◨
min 4y₁ + 6y₂
y₁ + y₂ ≥ 3
y₁ + 3y₂ ≥ 2
y₁, y₂ ≥ 0
optimum: 12 at (3, 0)
the gap that closes to zero
Weak duality is free: any feasible primal value is ≤ any feasible dual value, so the primal is forever trapped below and the dual above — 12 sits between them like a wall. Strong duality is the theorem: for a feasible linear program the wall is touched from both sides — the gap closes to exactly zero, and the two problems agree. Drag to squeeze them shut.
green · measured
Primal optimum = 12 (vertex (4,0)) and dual optimum = 12 (vertex (3,0)) — enumerated and node-verified, gap 0. Weak duality (primal ≤ dual) holds for every feasible pair shown; the live squeeze never lets the primal cross 12 or the dual fall below it.
amber · the framing
"Resources vs prices / a problem and its shadow" is the standard economic reading (the dual variables are shadow prices), but it is an interpretation laid over the algebra. One concrete LP is shown; the equality is a general theorem, illustrated by this instance.
red · conditions
Strong duality here rests on LP feasibility (Slater/feasible-bounded). It can FAIL with a duality gap for some non-convex or infeasible/unbounded problems — a powerful duality with real hypotheses, not a universal law.