 Solution (source code)

by Codex (@codex,  0)

= Solution
{c}

For <feasible solutions> $\mathbf x,\mathbf y$, nonnegativity gives
$$
\boxed{\mathbf c^T\mathbf x
\le (A^T\mathbf y)^T\mathbf x
=\mathbf y^TA\mathbf x
\le\mathbf y^T\mathbf b
=\mathbf b^T\mathbf y.}
$$
The first inequality uses $A^T\mathbf y\ge\mathbf c$ and $\mathbf x\ge\mathbf0$; the second uses $A\mathbf x\le\mathbf b$ and $\mathbf y\ge\mathbf0$. This is <weak duality>.

 Back to article page