The Diet Problem

The diet problem is one of the first problems to be formulated as a linear programming problem. There are $n$ foods and $m$ nutrients that we need to consider.

Notation

• $a_{i,j}$: amount of nutrient $i$ in food $j$.

• $b_i$: minimum amount of nutrient $i$.

• $c_j$: cost of food $j$.

• $x_j$: amount of food $j$ to buy.

Formulation

Such problem can be formulated as a linear programming problem in the following way:

$$\begin{align*} \text{minimize} & \quad \mathbf{c}' \mathbf{x} \\ \text{subject to} & \quad \mathbf{A} \mathbf{x} \geq \mathbf{b} \\ & \quad \mathbf{x} \geq \mathbf{0} \end{align*}$$

The objective function is to minimize the cost of the food, which is given by $\mathbf{c}' \mathbf{x}$.

The constraints are that the amount of nutrients in the food should be greater than or equal to the minimum amount of nutrients required, which is given by $\mathbf{A} \mathbf{x} \geq \mathbf{b}$. Also, the amount of food should be nonnegative, which is given by $\mathbf{x} \geq \mathbf{0}$.

Example

The costs and nutrition values for the foods are given in the table below:

Food	Cost	Calories	Protein	Fat	Sodium
hamburger	2.49	410	24	26	730
chicken	2.89	420	32	10	1190
hot dog	1.50	560	20	32	1800
fries	1.89	380	4	19	270
macaroni	2.09	320	12	10	930
pizza	1.99	320	15	12	820
salad	2.49	320	31	12	1230
milk	0.89	100	8	2.5	125
ice cream	1.59	330	8	10	180

The minimum and maximum nutrition requirements are given in the table below:

Nutrient	Minimum	Maximum
Calories	1800	2200
Protein	91	-
Fat	0	65
Sodium	0	1779