Formulating Diet and Blending Problems as LPs

A diet problem asks for the cheapest combination of foods that meets all nutritional requirements.

The formulation has three ingredients:

• Decision variables: let $x_i$ denote the amount of food $i$ in the diet (e.g., servings, ounces, grams).
• Objective: minimize total cost,

$$\min\ \sum_{i=1}^n c_i\, x_i,$$

where $c_i$ is the cost per unit of food $i.$

• Constraints: for each nutrient $j,$ the total amount supplied must meet the daily minimum $b_j{:}$

$$\sum_{i=1}^n a_{ij}\, x_i \geq b_j,$$

where $a_{ij}$ is the amount of nutrient $j$ contained in one unit of food $i.$

• Non-negativity: $x_i \geq 0$ (we cannot consume a negative amount of food).

For example, suppose rice costs \1$per pound and supplies$2$g of protein per pound, while beans cost$$2$per pound and supply$5$g of protein per pound. To meet a$10$g protein minimum at minimum cost, we write

$$\begin{align*}\min\ &\ x_1 + 2 x_2 \\ \text{s.t.}\ &\ 2 x_1 + 5 x_2 \geq 10 \\ &\ x_1,\, x_2 \geq 0.\end{align*}$$