Theorem 5.2 — Strong Duality Theorem

Consider the standard-form linear program "maximize $c^T x$ subject to $Ax \le b$, $x \ge 0$" with $A \in \mathbb{R}^{m \times n}$, $b \in \mathbb{R}^m$, $c \in \mathbb{R}^n$, and its dual "minimize $b^T y$ subject to $A^T y \ge c$, $y \ge 0$". If the primal has an optimal solution $x^* = (x^*_1, \dots, x^*_n)$, then the dual also has an optimal solution $y^* = (y^*_1, \dots, y^*_m)$ such that

There is no gap between the optimal primal and dual values. Together with weak duality this makes a pair of feasible points with equal objective values a certificate of optimality for both.

Formalization Note Optimality is attainment: $x^*$ is primal feasible with $c^T x \le c^T x^*$ for every primal feasible $x$, and the conclusion asserts a dual feasible $y^*$ with $b^T y^* \le b^T y$ for every dual feasible $y$.