Linear programming optimal & cheap diet

Assuming we are having a list of 5 example products with it's nutrition facts, price and limitations of quantity we can eat:

	name	quantity	protein	carb	fat	price	min	max
rice	\[p_1\]	100g	8.1g	80g	1g	0.5	2	4
buckwheat groats	\[p_2\]	100g	12g	75g	2.7g	3.0	0	-
red beans	\[p_3\]	30g	6.9g	18g	0.3g	0.36	0	3
mackerel	\[p_4\]	100g	19g	0g	14g	6.15	0	1
fillet chicken	\[p_5\]	100g	21g	0g	3.7g	1.6	2	-

Due to a specific diet we want to consume at least 190g of proteins and 280g carbs. Fat doesn't matter in this case. We also want to do it as cheap as possible.

Linear programming

First, we have to specify our objective function.

We are looking for the cheapest combination of all products, therefore we have to add their quantity multiplied by price together and minimalize it.

\[f = 0.5p_1+3p_2+0.36p_3+6.15p_4+1.6p_5 \to min\]
We also want to ensure that out target is included (proteins and carbs):
First row represents proteins in each product, second carbs, third fat.
 \begin{cases} 8.1p_{p_1} + 12p_{p_2} + 6.9p_{p_3} + 19p_{p_4}+ 21p_{p_5}\geqslant 190 \\ 80p_{c_1} + 75p_{c_2} + 18p_{c_3} + 0p_{c_4}+ 0p_{c_5} \geqslant 280 \\ 1p_{f_1} + 2.7p_{f_2} + 0.3p_{f_3} + 14p_{f_4}+ 3.7p_{f_5} \geqslant 0 \end{cases}
To make use of this equations we have to replace the greater than-equal siqn with less than-equal (multiply both sides by -1):

\begin{cases}  -8.1p_{p_1} - 12p_{p_2} - 6.9p_{p_3} - 19p_{p_4}- 21p_{p_5}\leqslant -190 \\ -80p_{c_1} - 75p_{c_2} - 18p_{c_3} - 0p_{c_4}- 0p_{c_5} \leqslant -280 \\ -1p_{f_1} - 2.7p_{f_2} - 0.3p_{f_3} - 14p_{f_4}- 3.7p_{f_5} \leqslant 0 \end{cases}

Remeber about min/max limitations per each product:

\begin{cases} 2 \leqslant p_1 \leqslant 4\\0 \leqslant p_2 \leqslant \infty \\0 \leqslant p_3 \leqslant 3 \\0 \leqslant p_4 \leqslant 1 \\2 \leqslant p_5 \leqslant \infty\end{cases}

Solve it

We will use Matlab's built-in function for solving such problems - linprog().
Will will have to provide arguments such as:

• linear objective function vector (f)
• matrix for linear inequality constraints (A)
• vector for linear inequality constraints (b)
• vector of lower bounds (lb)
• vector of upper bounds (ub)

Based on the equations above:

 \[A = \begin{bmatrix} -8.1 & -12 & -6.9 & -19 & -21 \\ -80 & -75 & -18 & 0 & 0 \\-1 & -2.7 & -0.3 & -14 & -3.7 \end{bmatrix} b = \begin{bmatrix} -190 \\ -280 \\0 \end{bmatrix}\]

\[f = \begin{bmatrix} 0.5 \\ 3 \\0.36 \\ 6.15 \\1.6 \end{bmatrix} lb = \begin{bmatrix} 2 \\ 0 \\0 \\ 0 \\2 \end{bmatrix} ub = \begin{bmatrix} 4 \\ \infty \\3 \\ 1 \\\infty \end{bmatrix}\]

Finally - Matlab script:

f = [0.5 3 0.36 6.15 1.6]';
A = [-8.1   -12     -6.9    -19     -21;
     -80    -75     -18     0       0;
     -1     -2.7    -0.3    -14     -3.7];
b = [-190 -280 0]';
lb = [2 0 0 0 2]';
ub = [4 inf 3 1 inf]';

[x, fval] = linprog(f,A,b,[],[],lb,ub);

products_quantities = x
total_price = fval
nutritions = -A*x

And produced outcome:

products_quantities =

    4.0000
    0.0000
    3.0000
    0.0000
    6.5190

total_price =

   13.5105

nutritions =

  190.0000
  374.0000
   29.0205

That means that the most optimal option is to consume 400g of rice, 90g of beans and 650g of fillet chicken. We will pay about 13.5 for this meal and it will provide us 190g of proteins, 374g carbs and 29g of fat.