= Solution
{c}
The <dual linear program> is
$$
\boxed{D:\quad\text{minimize }g(y)=b^Ty,\qquad
A^Ty\geq c,\quad y\geq0.}
$$
For feasible $x,y$, nonnegativity and the two constraint inequalities imply <weak duality>:
$$
c^Tx\leq y^TAx\leq y^Tb.
$$
If a feasible pair has equal objectives, every primal feasible objective is at most that common value and every dual feasible objective at least it. Thus \b[both feasible solutions are optimal]. Strong duality is not needed for this certificate.
Back to article page
