Duality

Remark

Here, we consider a linear optimization problem in standard form, where and we assume .

Given a linear optimization problem , one can instead consider its dual problem. The idea is that minimizing the cost is the same thing as maximizing a lower bound for the cost. We notice that given a we have This means that whenever we get as a lower bound for the cost . All such 's give us a valid lower bound, and we will discover that the largest such lower bound is actually the optimal value, i.e., it gives a perfect lower bound.

Definition: Dual problem

The dual problem to is

Theorem: Weak duality

If and are feasible solutions to and , respectively, thenProof:
Using and we get

Corollary

If and are feasible solutions to and , respectively, and if , then and are optimal.

Using the derivations in the Simplex method we can also prove strong duality.

Theorem: Strong duality

If and are optimal solutions to and , respectively, then Proof:
By weak duality it is sufficient to show that given an optimal solution to there exists a feasible solution to with .

Given the existence of an optimal solution, we can assume is a basic optimal solution given by the Simplex method. Recall then that the reduced costs are nonnegative, , where , meaning This means is a feasible solution to . We also have that