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

p₁ x₁ + p₂ x₂ ≥ p and e₁ x₁ + e₂ x₂ ≥ 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₁ s + e₁ t ≤ c₁ and p₂ s + e₂ t ≤ c₂.

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!