= Solution
{c}
For the primal equality-form <linear program>, the <dual linear program> is
$$
\boxed{\text{minimize }b^Ty\quad\text{subject to }A^Ty\geq c,\quad y\text{ unrestricted in sign}.}
$$
If $x\geq0$ is primal feasible and $y$ dual feasible, then
$$
c^Tx\leq (A^Ty)^Tx=y^TAx=b^Ty.
$$
This proves <weak duality>. Their objective gap is $\sum_j x_j((A^Ty)_j-c_j)$, a sum of nonnegative terms. The <complementary slackness> theorem states that a feasible pair is optimal for the two programmes exactly when
$$
\boxed{x_j((A^Ty)_j-c_j)=0\quad\text{for every }j.}
$$
These conditions make the gap zero, which by weak duality certifies optimality; necessity follows from <strong duality>.
Back to article page
