Diet problems
Diet Problems
Diet problems choose quantities of foods or ingredients to satisfy nutritional requirements at minimum cost.
They are classic linear programming models.
Basic Structure
A diet problem has:
- foods or ingredients
- nutrients or requirements
- nutrient content per unit of food
- cost per unit of food
- minimum or exact nutritional requirements
- nonnegative food quantities
Decision Variables
If there are $n$ foods, define:
\[x_j=\text{quantity of food }j\]for:
\[j=1,\ldots,n\]The unit must be clear.
Examples:
- kilograms
- grams
- servings
- portions of $100$ grams
Objective Function
If food $j$ costs $c_j$ per unit, total cost is:
\[c_1x_1+c_2x_2+\cdots+c_nx_n\]The objective is:
\[\min \sum_{j=1}^n c_jx_j\]Nutrient Constraints
If food $j$ contains $a_{ij}$ units of nutrient $i$, and the required amount of nutrient $i$ is $b_i$, then:
\[a_{i1}x_1+a_{i2}x_2+\cdots+a_{in}x_n\ge b_i\]for each nutrient $i$.
Use $\ge$ when the requirement is “at least”.
Use $=$ if the problem asks for exact nutritional content.
General Diet LP
The standard model is:
\[\min \sum_{j=1}^n c_jx_j\]subject to:
\[\sum_{j=1}^n a_{ij}x_j\ge b_i, \qquad i=1,\ldots,m\] \[x_j\ge 0, \qquad j=1,\ldots,n\]Matrix Form
Let:
- $A$ be the nutrient-content matrix
- $b$ be the requirement vector
- $c$ be the food-cost vector
Then:
\[\min c^Tx\]subject to:
\[Ax\ge b\] \[x\ge 0\]Example: Food Quantities
Suppose the foods are:
- pasta
- meat
- vegetables
- cheese
Let:
\[x_1=\text{hundreds of grams of pasta}\] \[x_2=\text{hundreds of grams of meat}\] \[x_3=\text{hundreds of grams of vegetables}\] \[x_4=\text{hundreds of grams of cheese}\]Suppose the daily minimums are:
- at least $70$ g protein
- at least $50$ g fats
- at least $250$ g sugar
The nutrient table per $100$ g is:
| Food | Protein | Fats | Sugar |
|---|---|---|---|
| Pasta | 9.9 | 1.2 | 75.3 |
| Meat | 20.8 | 1.1 | 0 |
| Vegetables | 2 | 0.2 | 4 |
| Cheese | 22 | 26 | 0 |
Then the nutrient constraints are:
\[9.9x_1+20.8x_2+2x_3+22x_4\ge 70\] \[1.2x_1+1.1x_2+0.2x_3+26x_4\ge 50\] \[75.3x_1+4x_3\ge 250\]Cost Function
If costs per kilogram are:
- pasta: $1$
- meat: $9$
- vegetables: $0.80$
- cheese: $12$
and variables are in $100$ g units, then the costs per variable unit are:
\[0.10,\quad 0.90,\quad 0.08,\quad 1.20\]So the objective is:
\[\min 0.10x_1+0.90x_2+0.08x_3+1.20x_4\]Upper Bounds
Diet problems can also include upper limits.
Example:
no more than half a kilogram of vegetables per day
Since:
\[x_3=\text{hundreds of grams of vegetables}\]half a kilogram is $500$ g, so:
\[x_3\le 5\]Exact vs Minimum Diet
Some theoretical diet models use:
\[Ax=b\]This means the nutrient profile must be exactly equal to the requirement.
Practical diet models usually use:
\[Ax\ge b\]because nutrients must be at least the required amount.
Common Mistakes
Avoid these mistakes:
- forgetting to convert kilograms to $100$ g units
- using $\le$ for minimum nutrient requirements
- forgetting upper limits such as maximum vegetables
- omitting foods with zero nutrient content from a constraint incorrectly
- mixing cost per kg with variables measured in grams
- forgetting nonnegativity
Key Takeaway
A diet LP chooses food quantities to satisfy nutrient requirements at the lowest possible cost.
Exam checkpoint
For formulation questions, show variables, objective, constraints, sign restrictions, and units. Do not solve unless the question asks for a solution.