### Proof of Strong Duality Theorem

Let $(P)$ be

$\begin{array}{rcl} \max z&=&\mathbf c^T\mathbf{x}\\\mbox{subject to }A\mathbf{x} &\leq&\mathbf{b}\\\mathbf x &\geq& 0\end{array}$

Then $(D)$ is

$\begin{array}{rcl}\min w&=&\mathbf b^T\mathbf y\\\mbox{subject to } A^T \mathbf{y}&\geq&\mathbf c\\\mathbf y &\geq&0\end{array}$

The theorem states: Suppose B is an optimal basis for the primal $(P)$.  Then $\mathbf c_B B^{-1}$ is an optimal solution to the dual.  Also $z^*=w^*$ where * indicates optimal value.

## Proof

###### Step 1

Use the fact that B is an optimal basis for the primal to show that $\mathbf c_B B^{-1}$ is dual feasible.

Let B be an optimal basis for the primal, and define $\mathbf c_B B^{-1}=[y_1,y_2,\cdots,y_m]$  Thus for the optimal basis B, $y_i$ is the i-th element of $\mathbf c_B B^{-1}$.  B is optimal for the primal, so the coefficient of each variable in row 0 of B’s primal tableau must be nonnegative.  The coefficient of $x_j$ in row 0 of the B tableau $(\bar c_j)$ is given by

$\begin{array}{rcl}\bar c_j &=& \mathbf c_B B^{-1}\\\mathbf a_j-c_j&=&[ \begin{matrix}y_1&y_2&\cdots&y_m\end{matrix}]\left[\begin{matrix}a_{1j}\\a_{2j}\\\vdots\\a_{mj}\end{matrix}\right]-c_j\\&=&y_1a_{1j}+y_2a_{2j}+\cdots+y_ma_{mj}-c_j\end{array}$

But we know that $\bar c_j\geq0$, so for $j=1,2,\cdots n$,

$y_1a_{1j}+y_2a_{2j}+\cdots+y_ma_{mj}-c_j\geq0$

Thus, $\mathbf c_B B^{-1}$ satisfies each of the $n$ dual constraints.

Because B is an optimal basis for the primal, we know that each slack variable has a nonnegative coefficient in the B primal tableau.  The coefficient of $s_i$ in B’s row 0 is $y_i$, the i-th element of $\mathbf c_B B^{-1}$.  Thus, $y_i \geq0$ for $i=1,2,\cdots,m$.  The definition of dual $(D)$, $\mathbf c_B B^{-1}$ satisfies all $n$ constraints and elements are nonnegative.  Thus $\mathbf c_B B^{-1}$ is dual feasible.

###### Step 2

Show that the optimal primal object function value equals the dual objective function for $\mathbf c_B B^{-1}$.

The primal objective function value for basis B is $\mathbf c_B B^{-1}\mathbf b$  The dual objective function value for the dual feasible solution $\mathbf c_B B^{-1}$ is

$b_1y_1+b_2y_2+\cdots+b_my_m=[\begin{matrix}y_1&y_2&\cdots&y_m\end{matrix}]\left[\begin{matrix}b_1\\b_2\\\vdots\\b_m\end{matrix}\right]=\mathbf c_B B^{-1}\mathbf b$

Thus, step 2 is shown as required.

###### Step 3

Given that we have found a primal feasible solution and a dual feasible solution that have equal objective values, we can conclude that $\mathbf c_B B^{-1}$ is optimal for the dual, and $z^*=w^*$

$\Box$