Infeasibility

This is a somewhat technical post about he mathematical modeling of an optimal diet, it's not really about food.

A linear programming model is the minimization of the value of a linear function in such a way that the solution still satisfies a collection of linear constrains. In a simple form of the linear formulation of the optimal diet problem we want to

minimize c₁*x₁ + c₂*x₂
such that
p₁*x₁ + p₂*x₂ > 77
x_i > 0 for all i

Where x_i is the quantity of food i (we have two foods to choose from)

c_i is the quantity of carbohydrates contianed in food i (the objective is to minimize this)

p_i is the protein content of food i

and we want to constrain the solution to ensure we have a least the specified level of protein in the diet.

This two variable, one constraint version is pretty easy to solve. Just pick the food that has the highest protein per carb (or lowest carb per protein) and eat as litle of that food as you can and still get enough protein. That's your minimum carbohydrate solution.

I havn't really gotten to the topic of infeasibility yet and the post is starting to get long. So let me just finish off with a specific example and I'll get back to this on another day.

Let's say we have two foods to pick from -- chili and bread. A serving of chili has 18 grams of carbs with 17 grams of protein and a slice of bread has 15 grams of carbs with 3 grams of protein.

Carb per protein for the bread is 15/3 = 5 and for the chili it's 18/17 = 1 (about). The chili is clearly the best choice for this mini-model. Eat enough chili to get the required protein and stop. That's a minimum carb diet that fits the model.

The model is overly simplistic, of course. We'll get to that on another day.