Lp Duality

Fundamental Law of Linear Programming

Apparently, there’s some fundamental law that applies to lp’s. There are three basic points to this rule:

  • If it has no optimal solution, then it is either infeasible or unbounded.
  • If it has a feasible solution, then it has a basic feasible solution.
  • If it is bounded, then it has an optimal basic feasible solution.

First, a definition. If a solution is feasible that means it actually fits the conditions of the primal of the lp. I might be wrong on this one, but that’s what I understand from these slides under the Basic Feasible Solutions section.

Perhaps, to better understand this law, I better go back and learn simplex where they actually go over basic/nonbasic variables and the such. :sigh:

Intro to the primal, dual scheme

Again, I’m basically ripping explanations out of a mixture of U. Wash. slides and Chvatal’s book on LP.

So basically, in standard form we see the primal. Of course the actual coefficients can be expressed in matrix form and thus the primal can be viewed as:

maximize $c^T x$
subject to $Ax \le b$, $0 \le x$

Thus, the dual can be described as kind of the inverse of this, in the following format:

minimize $b^T y$
subject to $A^T y \ge c $, $0 \le y$

Thus, if you take the dual of the dual you actually get the primal.

How do you take the dual?

Good question. These are pretty thorough notes on how to do it so I won’t retype it here.

Basically, just look up at the formulas for primal and dual. Notice how there are some common once in matrix form. Yeah, just do the transformations necessary and bam, you’re done. This took me way too long to realize…

Weak duality theorem

Written on October 4, 2014