Two theorems that change how you think about LP.
Chapter: 0 — LP theory · lesson id lp-duality-theorems · theory lesson
We constructed the dual by hunting for a lower bound on the primal. So a bound is what we should get first. That is $weak\ duality$: the dual value is always a lower bound on the primal value. Then comes the surprise: when both LPs have finite optima, the bound is tight. That is $strong\ duality$. These two theorems are the foundation of LP sensitivity analysis, the simplex method's correctness, and the algorithms behind every commercial solver.
Theorem (Weak Duality). For any primal-feasible $x$ and any dual-feasible $y$, $c^{\top} x \geq b^{\top} y$. In particular, the primal optimal value is at least the dual optimal value: $p^{} \geq d^{}$.
Proof, step by step (Weak Duality).
Corollary (Two-line bound certificate). If you have a primal-feasible $x$ and a dual-feasible $y$ with $c^{\top} x = b^{\top} y$, then $x$ is primal-optimal and $y$ is dual-optimal.
This is a $certificate$ of optimality: anyone can verify your two vectors in linear time, no algorithm needed. Modern solvers exploit this by computing both primal and dual variables together and stopping when the gap is closed.
Quick check. A primal LP has feasible solution $\bar{x}$ with $c^{\top} \bar{x} = 10$. A dual feasible solution $\bar{y}$ has $b^{\top} \bar{y} = 7$. Which of the following can you conclude?
Theorem (Strong Duality). If the primal LP has a finite optimal value $p^{}$, then the dual LP also has a finite optimal value $d^{}$, and $p^{} = d^{}$.
The hypothesis matters. There is a subtle case where the primal is infeasible $and$ the dual is unbounded (and vice versa), and one even-more-subtle case where both are infeasible. The full picture is the $strong\ duality\ theorem$ in its complete form. The version above is what you reach for 95% of the time.
Proving strong duality from scratch requires either the simplex method's termination argument (which itself relies on some non-trivial linear algebra) or a separation theorem from convex analysis. We will not reproduce a full proof here — both routes take several pages of careful work. What we $can$ do is unpack what strong duality $means$, geometrically and economically.
Imagine the primal feasible region as a polytope. The objective $c^{\top} x$ sweeps across it as a family of parallel hyperplanes; the optimum is where the lowest such hyperplane still touches. The dual variables $y$ are the $support$ data of that hyperplane — the coefficients that show $c$ can be written as a non-negative combination of the binding constraint normals. Strong duality says: not only does such a non-negative combination exist (a separation-theorem fact about convex sets), the dual LP $finds$ it.
A polytope and a supporting hyperplane meeting at a vertex is what strong duality looks like, dimension by dimension. Weak duality is "the hyperplane is below the polytope". Strong duality is "the hyperplane touches the polytope".
Theorem (Complementary Slackness). Let $x^{}$ be primal-optimal and $y^{}$ be dual-optimal. Then for every $i$ and $j$: (a) if $y_{i}^{} > 0$, the $i$-th primal constraint is active: $A_{i} x^{} = b_{i}$; (b) if the $i$-th primal constraint is slack ($A_{i} x^{} > b_{i}$), then $y_{i}^{} = 0$; (c) if $x_{j}^{} > 0$, the $j$-th dual constraint is active: $A_{\cdot j}^{\top} y^{} = c_{j}$; (d) if the $j$-th dual constraint is slack, then $x_{j}^{*} = 0$.
Complementary slackness drops out of the weak-duality proof: when both inequalities in the chain $b^{\top} y \leq y^{\top} A x \leq c^{\top} x$ are equalities at $(x^{}, y^{})$, each individual term-by-term product must collapse. The result is one of the most useful theorems in OR: it tells you which constraints to look at when you ask "what shadow price does this resource have?".
Quick check. In a factory LP, the dual variable for the "labour hours" constraint comes out to $y_{\text{lab}}^{*} = $7$ per hour. What does this mean economically?
Recap.
Read this through MCP: read with path: "lessons/lp-duality-theorems", or resource hlpl://lessons/lp-duality-theorems.