Duality of linear programs

(Weak duality.) Let $x$ be any primal-feasible point ($Ax\le b$, $x\ge 0$) and $y$ any dual-feasible point ($A^{\mathsf{T}}y\ge c$, $y\ge 0$). Since $x\ge 0$ and $A^{\mathsf{T}}y\ge c$, multiplying the inequality by the nonnegative vector $x$ preserves it: $c^{\mathsf{T}}x\le \left(A^{\mathsf{T}}y\right)^{\mathsf{T}}x=y^{\mathsf{T}}Ax$. Since $y\ge 0$ and $Ax\le b$, the same argument gives $y^{\mathsf{T}}Ax\le y^{\mathsf{T}}b=b^{\mathsf{T}}y$. Chaining the two inequalities, $c^{\mathsf{T}}x\le b^{\mathsf{T}}y$ for every feasible pair, which is weak duality.

(Strong duality.) Run the simplex method on the primal until it terminates at an optimal basic feasible solution $x^{*}$ with optimal basis matrix $B$, so that $x^{*}_B=B^{-1}b$ and the reduced costs of every non-basic variable are non-negative — this termination condition is equivalent to defining $y^{*\mathsf{T}}=c_B^{\mathsf{T}}B^{-1}$, which one can check satisfies $A^{\mathsf{T}}y^{*}\ge c$ and $y^{*}\ge 0$, i.e. $y^{*}$ is dual-feasible.

Substituting, the primal optimal value is $c^{\mathsf{T}}x^{*}=c_B^{\mathsf{T}}x^{*}_B=c_B^{\mathsf{T}}B^{-1}b=y^{*\mathsf{T}}b=b^{\mathsf{T}}y^{*}$. Combined with weak duality ($c^{\mathsf{T}}x^{*}\le b^{\mathsf{T}}y^{*}$ always), equality here forces $y^{*}$ to be dual-optimal as well, so $c^{\mathsf{T}}x^{*}=b^{\mathsf{T}}y^{*}$, proving strong duality.