 Solution

For the primal equality-form linear program, the dual linear program isIf $x\ge 0$ is primal feasible and $y$ dual feasible, thenThis proves weak duality. Their objective gap is ${\sum }_j{x}_j((A^{T}y{)}_j-c_j)$, a sum of nonnegative terms. The complementary slackness theorem states that a feasible pair is optimal for the two programmes exactly whenThese conditions make the gap zero, which by weak duality certifies optimality; necessity follows from strong duality.