I’m trying to get my head around duality. Essentially, every linear program has a dual program. If in the original problem, you’re maximizing, in the second you’re minimizing. Also, you swap the ‘costs’ and the constraints. The costs become constraints and the original constraints go into the objective function.

Economically, duality means that the problem of maximizing profit is the same as the the problem of minimizing costs.

Of course, a system of constraints usually has many feasible solutions. One result of duality is that if one of the problems has a solution than its dual will have a solution, too. A more interesting result about duality is that if the maximizing problem has a solution then the value of its objective function will be less than or equal to the value of the objective function for some solution to the minimizing problem.

This last result, called the weak duality theorem, can be used to show that the optimal solution for the maximizing problem results in a value of its objective function equal to the value of the objective fuction for the minimizing problem at its optimal solution. In this way, you can know if you have an optimal solution by checking if the dual problem gives an equal value of the objective function.

I’m still wrapping my head around all this and I certainly don’t understand the math…. There’s a great presentation I grabbed off a google search.

### Like this:

Like Loading...

*Related*

## 0 Responses to “Duality in LP”