Consider the primal program

and the dual

where .

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

Let

We will show that

(1)

(2)

*Proof.*

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”.

Advertisements