 Linear programming optimality certificate

For the linear program maximizing $c^{T}x$ with $Ax\le b$, $x\ge 0$, a vector $y\ge 0$ with $A^{T}y\ge c$ proves $c^{T}x\le y^{T}b$ for every feasible $x$. If a feasible $x$ attains that bound, it is optimal. This is weak duality written as a directly checkable certificate; adding nonnegative multiples of constraints suffices to verify it. The equivalent reversed-inequality certificate applies to a minimization program.