= Solution
{c}
For every primal <feasible solution> $\mathbf x$, <weak duality> gives
$$
\mathbf c^T\mathbf x\le\mathbf b^T\mathbf y^*=\mathbf c^T\mathbf x^*.
$$
Thus no primal <feasible solution> improves on $\mathbf x^*$. Similarly, for every dual <feasible solution> $\mathbf y$,
$$
\mathbf b^T\mathbf y\ge\mathbf c^T\mathbf x^*=\mathbf b^T\mathbf y^*.
$$
Therefore \b[both candidates are optimal], with the same <objective function> value. Equality is a <linear programming optimality certificate> and does not require a separate existence argument.
Back to article page
