Tag Archives: problems

Learn Duality in Linear Programming

I have just completed a script to help learn about duality in linear programming.

Many real world problems can be formulated as Linear Programming problems. There are often many different ways to formulate a single problem. Some of these alternative formulations can easily be proven to be equal via simple algebra and arithmetic. For example, one person may see a problem as maximizing profit while another may see the same problem as minimizing losses. The relationship between the two alternative formulations can then be shown to be that one simply has the negative objective function value of the other.

Sometimes, though, this relationship between alternative formulations is not as easy to detect. Two alternative formulations that arise regularly in linear programming problems are a primal problem and a dual problem. The dual of a linear programming problem is the problem of finding the best bound on the objective function in terms of the constraints. This dual is formulated so that every feasible solution to the dual is a bound on the primal objective function. The Weak Duality Theorem for Linear Programming says that the optimal solution for a minimization problem is always an upper bound for its dual (which is a corresponding maximization problem). Correspondingly, the optimal solution for a maximization problem is always a lower bound for its dual. This leads to the Strong Duality Theorem for Linear Programming which says that if we can find feasible solutions to the primal and dual problems with matching objective function values, then both of these solutions must be optimal for their respective problems.

This shows an importance of duality. What my script provides is a means of formulating the dual of a given problem to help understand the concept.

The rules for constructing a dual linear program are as follows:

The ith constraint is [<=]Variable yi is [>=] 0
The ith constraint is [>=]Variable yi is is [<=] 0
The ith constraint is =Variable yi is unbounded
Variable xj is [>=] 0The jth constraint is [>=]
Variable xj is [<=] 0The jth constraint is [<=]
Variable xj is unboundedThe jth constraint is =

Other Blogs that have covered this topic:
A Narrow Margin
Optimization and data mining

My Life (as a Number)

A few days ago I went on a nice run that really helped to clear my mind. Afterwards, the song “I Gave You Power” by Nas stayed inside my mind. And I wondered if I could do a similar thing, but more math related. After a quick free-write, what follows is what I came up with.

My Life (as a Number)
– by AfterMath

I’ve been used, abused, and mistreated
Like a tool for you to do what you’ve got to do.
But when you’re through, you’re through
No “how was it for you”
No asking about what I’ve been through
Nah, I don’t get a word from you

Except for those odd days
When you want to whine and moan and complain
About how much you don’t like me
About how much you can’t stand me
About how much you hate me
But you keep coming back to me

And I keep letting you come back to me.
I keep solving your problems for you
And when you get into trouble
I’m the one you turn to.
But I guess that’s what I was created to do
At least now you know what numbers go through.