Duality in linear programming

From Spivey's Corner
Jump to: navigation, search

Here's the story I use to remind myself of what primal and dual problems represent in linear programming. Nothing here is at all new, but I find it handy.

Suppose you adopt a diet consisting of bread and cheese. Bread costs c1 per loaf and cheese c2 per chunk, and you eat x1 loaves of bread and x2 chunks of cheese. You want to minimize your total expenditure, c1 x1 + c2 x2, but you must be sure to get enough protein and enough calories from what you eat. Bread contains p1 grams of protein per loaf and cheese contains p2 grams per chunk; also bread contains e1 calories per loaf and cheese contains e2 calories per chunk. So you need to achieve

p1 x1 + p2 x2 >= p and e1 x1 + e2 x2 >= e,

where p and e are your protein and calorie needs.

Now I come along with some marvellous new pills that provide pure protein and pure calories, which I sell at prices s and t. If you feed yourself with my pills alone, it will cost you p s + e t, where s is the cost per gram of protein taken in pill form, and t is the cost per calorie taken as a pill. I want to maximise the amount you pay, but I must be careful to avoid a situation where it would be cheaper for you to replace some of my pills with either bread or cheese. So I must obey the constaints

p1 s + e1 tc1 and p2 s + e2 tc2.

The left-hand side of each of these inequalities represents the cost of supplying the nutrients in a loaf of bread or a hunk of cheese by using pills, and the right hand side represents the cost of the bread or cheese itself.

These two questions are a linear program and its dual. Of course, they have the same answer: I must price my pills so that the cost of your feeding yourself with pills exactly matches the cost of eating real food. I know which I'd prefer.

Bon appetit!