### Proof of Strong Duality Theorem

Let be

Then is

The theorem states: Suppose B is an optimal basis for the primal . Then is an optimal solution to the dual. Also where * indicates optimal value.

## Proof

###### Step 1

Use the fact that B is an optimal basis for the primal to show that is dual feasible.

Let B be an optimal basis for the primal, and define Thus for the optimal basis B, is the *i*-th element of . 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 in row 0 of the B tableau is given by

But we know that , so for ,

Thus, satisfies each of the 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 in B’s row 0 is , the *i*-th element of . Thus, for . The definition of dual , satisfies all constraints and elements are nonnegative. Thus is dual feasible.

###### Step 2

Show that the optimal primal object function value equals the dual objective function for .

The primal objective function value for basis B is The dual objective function value for the dual feasible solution is

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 is optimal for the dual, and