Consider a generic linear program:
Note that we can write any linear program in this form. Suppose the was absent. Then we could write where and this would make it an LP of the above form. Here are a few other forms of the LP that are equivalent:
We can write the first form by introducing a slack variable, i.e. if and only if there exists such that . To write the second form in the first form we observe that if and only if and .
Suppose we are given a linear program in the first form, i.e.
We wish to find an upper bound for the maximum. Notice that for any such that , is a valid upper bound for the maximum. Thus the best upper bound we can find is given by another LP called the dual of the first LP.
The first LP is often called the primal and the second program is called the dual. Note that the dual of the dual is the primal program. Let be the primal optimal value and the dual optimal value. Then weak LP duality tells us that .
Strong LP Duality: For a primal and dual pair of LP programs, . In other words
To prove this we will introduce the following simple lemma.
Farkas Lemma: Let and . Then exactly one of the following is true:
- such that
- such that and
Let be the columns of . Then the first condition is equivalent to saying that the vector belongs to the cone generated by the columns of . Notice that the cone generated by the set of vectors is given by . The second condition merely says that if (i.e. the first condition does not hold) then one can find a hyperplane going through the origin such that separates from the cone. The hyperplane is given by . Since for every it follows that for every element satisfies . However thus separating it.