Solution
= Solution
{c}
The dual is
$$
\boxed{\text{minimize }b^Ty
\quad\text{subject to }A^Ty\geq c,\quad y\geq0.}
$$
<weak duality> says that any feasible primal $x$ and dual $y$ satisfy $c^Tx\leq b^Ty$. Indeed,
$$
c^Tx\leq(A^Ty)^Tx=y^TAx\leq y^Tb.
$$
The first inequality uses $x\geq0$ and $A^Ty-c\geq0$, and the second uses $y\geq0$ and $b-Ax\geq0$. This proves the theorem. In particular, feasible solutions with equal <objective function> values are optimal for both problems.