Duality in LP

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.

Advertisements

0 Responses to “Duality in LP”



  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s





%d bloggers like this: