Dual problem in linear programs

Consider the primal problem: ” Minimize over subject to ” where , and is an matrix. Now the Lagrangian is:

The set of Feasible Lagrange Multipliers is:

and finally, the Dual Problem function is:

So the dual problem is: ” Maximize over subject to ” where .

Note that this is a Linear program in General Form.

If we try to find the dual problem of the dual problem, we should end up with the primal problem.

Lemma

In a Linear program and its Dual Problem (as above) Let be primal feasible, and let be dual feasible

Then and are optimal if and only if Complimentary slackness holds.

Proof

Complimentary slackness is equivalent to:

Suppose and are optimal (feasible) solutions. Due to Strong duality in linear programs:

Then substitute to find Hence Complimentary slackness holds.

Let be primal feasible, and dual feasible and suppose Then substitute to find Due to Weak Duality, this can only happen if and are optimal.