Diet and nutrition problems

A diet problem is the quintessential cost-minimisation LPP. Each food contains certain amounts of nutrients (vitamins, minerals, proteins, calories). Each food costs a certain amount. The goal: select quantities of each food to satisfy daily nutritional requirements at minimum cost.

Structure

Decision variables: amounts of each food (in grams, units, servings, etc.).

Objective: minimise total cost $Z = c_1 x_1 + c_2 x_2 + \cdots$, where $c_i$ is the cost per unit of food $i$.

Constraints:

• Nutritional minimums: $a_{i1} x_1 + a_{i2} x_2 + \cdots \ge b_i$ for each required nutrient $i$, where $a_{ij}$ is the amount of nutrient $i$ in one unit of food $j$ and $b_i$ is the required total.
• Non-negativity: $x_j \ge 0$.

In Class XII the problem is two-dimensional ($x_1, x_2$), so graphical solution applies.

Standard form

Let $x$ = units of Food A, $y$ = units of Food B. Each food contains nutrient amounts and costs given:

Minimise $Z = c_1 x + c_2 y$ subject to:

• $a_1 x + a_2 y \ge A$
• $b_1 x + b_2 y \ge B$
• $x, y \ge 0$.

The feasible region is unbounded (in the upper-right), but the minimum is attained at a corner , usually at the intersection of two binding constraints (or at an axis intersection if that's feasible).

Worked examples

Example 1. A diet must contain at least $80$ units of vitamin A and $100$ of B. Food F1 contains $4$ A and $2$ B per gram, F2 contains $2$ A and $5$ B per gram. F1 costs ₹$5$ per gram; F2 costs ₹$2$ per gram. Find the optimal diet.

Variables: $x$ grams F1, $y$ grams F2. $Z = 5x + 2y$.

• $4x + 2y \ge 80$ (vit A)
• $2x + 5y \ge 100$ (vit B)
• $x, y \ge 0$.

Constraint lines: $4x + 2y = 80$ at $(20, 0), (0, 40)$. $2x + 5y = 100$ at $(50, 0), (0, 20)$.

Feasible region above both. Corners (with axes):

• $(50, 0)$: check $4(50) = 200 \ge 80$ ✓. Cost: $250$.
• $(0, 40)$: check $5(40) = 200 \ge 100$ ✓. Cost: $80$.
• Intersection: $4x + 2y = 80, 2x + 5y = 100$. Multiply first by 5: $20x + 10y = 400$. Multiply second by 2: $4x + 10y = 200$. Subtract: $16x = 200$, $x = 12.5$. Then $2(12.5) + 5y = 100$, so $5y = 75$, $y = 15$. Cost: $5(12.5) + 2(15) = 62.5 + 30 = 92.5$.

Min $Z = 80$ at $(0, 40)$. Optimal diet: $40$ grams of F2, no F1.

Example 2. A patient is advised to consume at least $12$ units of vitamin C and $20$ of D daily. Pill X has $4$ C, $5$ D, cost ₹$10$/pill. Pill Y has $3$ C, $6$ D, cost ₹$15$/pill.

Variables: $x$ X-pills, $y$ Y-pills. $Z = 10x + 15y$. Constraints: $4x + 3y \ge 12$, $5x + 6y \ge 20$, $x, y \ge 0$.

Lines: $4x + 3y = 12$ at $(3, 0), (0, 4)$. $5x + 6y = 20$ at $(4, 0), (0, 10/3)$.

Corners (on axes): $(4, 0)$ ($y = 0$, larger from first; check $5(4) + 0 = 20 \ge 20$ ✓). $(0, 4)$ ($x = 0$, larger from first; check $5(0) + 6(4) = 24 \ge 20$ ✓). Intersection: $4x + 3y = 12, 5x + 6y = 20$. Multiply first by 2: $8x + 6y = 24$. Subtract second: $3x = 4, x = 4/3, y = (12 - 16/3)/3 = (20/3)/3 = 20/9$. Check non-negative: yes. Cost: $40/3 + 100/3 \cdot 1 \cdot 3/3$... let me recompute: $10(4/3) + 15(20/9) = 40/3 + 300/9 = 120/9 + 300/9 = 420/9 = 46.67$.

Values: $(4, 0): 40$; $(0, 4): 60$; $(4/3, 20/9): 46.67$. Minimum $Z = 40$ at $(4, 0)$.

Example 3. Doctor prescribes a diet with $1500$ calories and $40$ g of protein at minimum. Food P: $300$ cal/serving, $5$ g protein, ₹$8$/serving. Food Q: $150$ cal/serving, $10$ g protein, ₹$3$/serving. Minimise cost.

$x$ servings P, $y$ servings Q. $Z = 8x + 3y$. Constraints: $300x + 150y \ge 1500$ (i.e. $2x + y \ge 10$), $5x + 10y \ge 40$ (i.e. $x + 2y \ge 8$), $x, y \ge 0$.

Lines: $2x + y = 10$ at $(5, 0), (0, 10)$. $x + 2y = 8$ at $(8, 0), (0, 4)$. Intersection: from first $y = 10 - 2x$, sub: $x + 20 - 4x = 8$, $-3x = -12$, $x = 4$, $y = 2$.

Corners: $(0, 10)$ (check $0 + 20 \ge 8$ ✓). $(4, 2)$. $(8, 0)$ (check $16 + 0 \ge 10$ ✓).

Costs: $(0, 10): 30$. $(4, 2): 32 + 6 = 38$. $(8, 0): 64$. Min $Z = 30$ at $(0, 10)$.

Example 4. A pet food must contain at least $30$ g protein, $20$ g fat. Beef supplies $4$ g protein, $2$ g fat per scoop. Grain supplies $2$ g protein, $4$ g fat per scoop. Beef costs ₹$4$/scoop, grain ₹$3$/scoop.

$x$ beef, $y$ grain. $Z = 4x + 3y$. $4x + 2y \ge 30$, $2x + 4y \ge 20$, $x, y \ge 0$.

Simplify: $2x + y \ge 15$, $x + 2y \ge 10$. Lines: $2x + y = 15$ at $(7.5, 0), (0, 15)$. $x + 2y = 10$ at $(10, 0), (0, 5)$.

Intersection of $2x + y = 15, x + 2y = 10$: multiply first by 2: $4x + 2y = 30$. Subtract: $3x = 20, x = 20/3, y = 15 - 40/3 = 5/3$.

Axis corners: $(10, 0)$ ($y = 0$, larger of two; check $20 + 0 \ge 15$ ✓). $(0, 15)$ ($x = 0$, larger of two; check $0 + 30 \ge 10$ ✓).

Costs: $(10, 0): 40$. $(0, 15): 45$. $(20/3, 5/3): 80/3 + 5 = 95/3 \approx 31.67$. Min $Z \approx 31.67$ at $(20/3, 5/3)$.

Example 5. A child's tonic must provide $80$ mg vitamin C and $200$ mg minerals daily. Brand A: $5$ mg C, $20$ mg minerals per spoon, ₹$2$. Brand B: $10$ mg C, $10$ mg minerals per spoon, ₹$3$.

$x$ A, $y$ B. $Z = 2x + 3y$. $5x + 10y \ge 80$ (i.e. $x + 2y \ge 16$), $20x + 10y \ge 200$ (i.e. $2x + y \ge 20$), $x, y \ge 0$.

Intersection: from first $x = 16 - 2y$. Sub second: $32 - 4y + y = 20$, $-3y = -12$, $y = 4, x = 8$.

Axis points: $(16, 0)$ , check $2(16) \ge 20$ ✓. $(0, 20)$ , check $0 + 40 \ge 16$ ✓.

Costs: $(16, 0): 32$. $(0, 20): 60$. $(8, 4): 28$. Min $Z = 28$ at $(8, 4)$.

Example 6. A blood-replacement formula needs $30$ units of iron, $40$ units of vitamin B12. Solution P: $5$ iron, $4$ B12 per ml, ₹$6$/ml. Solution Q: $3$ iron, $8$ B12 per ml, ₹$4$/ml.

$x$ P, $y$ Q. $Z = 6x + 4y$. $5x + 3y \ge 30$, $4x + 8y \ge 40$ (i.e. $x + 2y \ge 10$), $x, y \ge 0$.

Intersection: $5x + 3y = 30, x + 2y = 10$. From second $x = 10 - 2y$. Sub: $50 - 10y + 3y = 30$, $-7y = -20$, $y = 20/7$, $x = 10 - 40/7 = 30/7$.

Axis corners: $(6, 0)$ , $5(6) = 30 \ge 30$ ✓, $6 + 0 \ge 10$ ✗ ($6 < 10$). Infeasible. $(10, 0)$ , $5(10) = 50 \ge 30$ ✓, $10 \ge 10$ ✓. ✓. $(0, 10)$ , $0 + 30 \ge 30$ ✓, $0 + 20 \ge 10$ ✓. ✓. (Also $(0, 5)$ on second only? $0 + 15 < 30$, infeasible.)

Costs: $(10, 0): 60$. $(0, 10): 40$. $(30/7, 20/7): 180/7 + 80/7 = 260/7 \approx 37.14$. Min $Z = 260/7$ at $(30/7, 20/7)$.

Try it yourself

1. A mixture needs at least $300$ g of protein and $200$ g of carbs. Food A: $10$ protein, $20$ carbs per scoop, ₹$5$. Food B: $20$ protein, $10$ carbs per scoop, ₹$8$.
2. Vitamin tablet X: $4$ A, $3$ B, ₹$5$. Tablet Y: $3$ A, $4$ B, ₹$3$. Need $20$ A, $24$ B. Minimise.
3. Lunchbox: $1500$ cal, $80$ g protein. Item A: $300$ cal, $20$ g protein, ₹$10$. Item B: $400$ cal, $10$ g protein, ₹$12$.
4. Dietary supplement: at least $400$ mg calcium, $30$ mg iron. Tablet 1: $50$ Ca, $5$ Fe, ₹$8$. Tablet 2: $100$ Ca, $2$ Fe, ₹$6$.
5. Diet of two foods: $5$ protein and $4$ vitamin C per 100 g of F1 costing ₹$50$. $3$ protein and $5$ vit C per 100g of F2 costing ₹$40$. Need at least $30$ protein, $40$ vit C daily.
6. Two cereals. C1: $200$ cal, $10$ g protein/cup, ₹$4$. C2: $300$ cal, $5$ g protein/cup, ₹$6$. Need $1800$ cal, $50$ g protein. Minimise.
7. Pet food: $40$ g protein, $30$ g fat min. Mix A: $5$ p, $3$ f per oz, ₹$1$. Mix B: $4$ p, $5$ f per oz, ₹$2$. Minimise.
8. Diet of pills. Each pill of type 1: $25$ mg vit C, $4$ mg vit D, costs ₹$2$. Type 2: $15$ mg vit C, $6$ mg vit D, costs ₹$1$. Need $100$ vit C, $40$ vit D.
9. Hospital diet must include at least $20$ g of nutrient I and $20$ g of nutrient II daily. Food P provides $4$ g I, $2$ g II per unit, costs ₹$3$. Food Q: $1$ g I, $4$ g II per unit, costs ₹$2$. Minimise cost.
10. Infant formula. Type X: $10$ proteins, $5$ minerals per scoop, ₹$15$. Type Y: $4$ proteins, $8$ minerals per scoop, ₹$10$. Daily need: $30$ proteins, $30$ minerals.
11. Health bar combinations. Bar A: $200$ cal, $5$ g sugar per piece, ₹$2$. Bar B: $300$ cal, $10$ g sugar, ₹$3$. Need at least $1200$ cal but at most $20$ g sugar. Minimise cost. (Note: this has a $\le$ constraint too.)
12. Two ointments. Ointment P: $3$ active per ml, ₹$5$. Q: $5$ per ml, ₹$8$. Need at least $30$ active over a week of treatment. Minimise cost (only constraint: total volume $\le 10$ ml).
13. Vitamin gummies. A: $4$ vit C, $2$ zinc per gummy, ₹$2$. B: $1$ vit C, $5$ zinc per gummy, ₹$1$. Daily: $20$ vit C, $15$ zinc.
14. A weight-loss meal: max $500$ cal, min $20$ g protein. Food P: $200$ cal, $10$ g protein, ₹$30$. Food Q: $150$ cal, $5$ g protein, ₹$20$. Minimise cost. (Has both $\le$ and $\ge$ constraints!)

Pitfalls and tricks

• Consistent units. Convert everything to a single unit (grams, calories, etc.) before setting up constraints.
• Diet problems usually have $\ge$ constraints for nutritional needs , unbounded region, but minimum exists.
• Axis corners may be feasible. Always check them , sometimes the cheapest diet uses just one food.
• Sketch carefully: too rough a sketch may make you miss a corner.
• Compute $Z$ at the intersection corner carefully , it's often where the minimum lies.