Solution
= Solution
The dual is $\boxed{\min b^Ty\text{ subject to }A^Ty\ge c,\ y\ge0}$. <Weak duality> states that every primal feasible $x$ and dual feasible $y$ satisfy $c^Tx\le b^Ty$. Indeed,
$$
c^Tx\le (A^Ty)^Tx=y^TAx\le y^Tb,
$$
using $x\ge0$ for the first inequality and $y\ge0$ for the second. Thus a feasible dual value is an upper bound on every primal objective value, and a feasible pair with equal values certifies both optima.