 Solution

The dual isweak duality says that any feasible primal $x$ and dual $y$ satisfy $c^{T}x\le b^{T}y$. Indeed,The first inequality uses $x\ge 0$ and $A^{T}y-c\ge 0$, and the second uses $y\ge 0$ and $b-Ax\ge 0$. This proves the theorem. In particular, feasible solutions with equal objective function values are optimal for both problems.