# Duality in linear programming

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 *c*_{1} per loaf and cheese *c*_{2} per chunk, and you eat *x*_{1} loaves of bread and *x*_{2} chunks of cheese. You want to minimize your total expenditure, *c*_{1} *x*_{1} + *c*_{2} *x*_{2}, but you must be sure to get enough protein and enough calories from what you eat. Bread contains *p*_{1} grams of protein per loaf and cheese contains *p*_{2} grams per chunk; also bread contains *e*_{1} calories per loaf and cheese contains *e*_{2} calories per chunk. So you need to achieve

*p*_{1}*x*_{1}+*p*_{2}*x*_{2}≥*p*and*e*_{1}*x*_{1}+*e*_{2}*x*_{2}≥*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

*p*_{1}*s*+*e*_{1}*t*≤*c*_{1}and*p*_{2}*s*+*e*_{2}*t*≤*c*_{2}.

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!