LP Duality

Why it matters

LP duality unifies min + max theorems. Understanding shapes optimization theory.

The architecture

Primal: max c^T x subject to Ax <= b, x >= 0.

Dual: min b^T y subject to A^T y >= c, y >= 0.

How it works end to end

Weak duality: primal feasible x + dual feasible y implies c^T x <= b^T y.

Complementary slackness at optimum.

Farkas lemma foundation.