Consider the primal program
and the dual
We will once again prove strong duality, but this time using the simplex algorithm.
Let be an optimal, bounded primal solution. Add slack variables such that
So, at the end of our simplex algorithm, we reach
We will show that
We will first prove (1).
holds for all . So .
Now we show (2). We are left with
which holds for all . So,
At the optimal solution we get
with the second and third terms equal to ,
This is what is referred to as “complementary slackness”.