Last time we showed that , also known as the Weak Duality Theorem.
Let’s now take a look at other standard forms for LPs. Last time we worked mostly with
We have already seen that we can switch the objective between minimizing a function or maximizing a function by taking the negative of the original objective. Now we want to show that the following two forms are equally as expressive,
We can transform an inequality constraint of the form into an equality constraint by adding a nonnegative slack variable such that . An equality constraint can easily be transformed into inequality constraints, and .
The nonnegativity constraints can be imposed as follows. For each original variable , we have two variables such that . So constraint would be replaced with and nonnegativity constraints .
Let’s now look at prelationships between a primal LP that we will call and its dual .
Theorem 1. (Strong Duality)
Given a primal LP and its dual , one of the following four possibilities must hold:
1. Infeasible; Unbounded
2. Unbounded; Infeasible
3. Infeasible; Infeasible
4. Bounded & Feasible; Bounded & Feasible with equal optimal values
We can rule out the following three possibilities using Weak Duality,
5. Unbounded; Unbounded
6. Unbounded; Bounded & Feasible
7. Bounded & Feasible; Unbounded
Let’s turn our attention to ruling out
8. Bounded & Feasible; Infeasible
and by duality,
9. Infeasible; Bounded & Feasible
We will need the following lemma
Lemma 1. (Farkas’ Lemma)
For any , exactly one of the following holds:
(1) says that . If is not, then there exists a hyperplane that separates from . We can take this hyperplane to be passing through , with normal . (2) then follows.
We now use Farkas’ Lemma to prove Strong Duality.
Let primal be the following feasible and bounded LP,
and the dual is
and . Now consider the matrix and vector .
Apply Farkas’ Lemma, so either
(1) — this cannot hold since we assumed
(2) . Multiplying the first with , and using , we get . Comparing the two inequalities with and using our assumption that , we conclude that . Hence,
which gives us a feasible dual !
Moreover, this gives us . Since is an arbitrary value greater than , we know that there exists a feasible dual with .