# Proving Strong Duality with Simplex

Consider the primal program $P$ $\max c^T x$ $Ax \leq b$ $x \geq 0$

and the dual $D$ $\min b^T y$ $A^T y \geq c$ $y \geq 0$

where $\max c^T x \leq \min b^T y$.

We will once again prove strong duality, but this time using the simplex algorithm.

Let $z^* = c^T x^*$ be an optimal, bounded primal solution. Add slack variables $x_{n+1} ... x_m$ such that $\max z = \sum_{i=1}^{n} c_i x_i$ $\sum_{j=1}^{n} a_{ij}x_{j} + x_{n+i} = b_i$ $x_1 ... x_{m+n} \geq 0$

So, at the end of our simplex algorithm, we reach $z = z^* + \sum_{j=1}^{n+m} \bar{c}_j x_j$ $\bar{c}_i \leq 0$

Let $y^*_i = -\bar{c}_{n+i}$

We will show that

(1) $z^* = b^T y^*$
(2) $A^T y^* \geq c$

Proof.

We will first prove (1). $z = z^* + \sum_{j=1}^n \bar{c}_j x_j - \sum_{i=1}^m y^*_i x_{n+i}$ $= z^* + \sum_{j=1}^n \bar{c}_j x_j - \sum_{i=1}^m y^*_i b_i + \sum_{i=1}^m y^*_i (\sum_j a_{ij}x_j)$ $= z^* - \sum_{i=1}^m y^*_i b_i + \sum_{j=1}^n (\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i)x_j$

holds for all $x$. So $x = 0 \implies z = 0 \implies z^* = b^T y^*$.

Now we show (2). We are left with $z = \sum_{j=1}^n (\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i)x_j = \sum_{j=1}^n c_j x_j$

which holds for all $x$. So, $\bar{c}_j + \sum_{i=1}^m a_{ij}y^*_i = c_j$ $\bar{c}_j \leq 0$ $\implies A^T y^* \geq c$

At the optimal solution we get $z = z^* + \sum_{j=1}^n \bar{c}_j x^*_j - \sum_{i=1}^m y^*_i x_{n+i}^*$

with the second and third terms equal to $0$, $\implies x^*_j > 0 \implies \bar{c}_j = 0$ $\implies y^*_i > 0 \implies x^*_{n+i} = b_i - \sum_{j=1}^n a_{ij}x^*_j = 0$

This is what is referred to as “complementary slackness”.