Matrix Multiplication of macronutrients to meet a target

Question

I'm trying to adjust recipes to meet specific macro-nutrient targets. Consider a recipe with a bunch of ingredients, each of which is composed of macro-nutrients (fat, carbohydrate, protein, etc.).

For example, a beef chilli recipe might be:

    Ingredient    | Weight (g) | Carbohydrate (g) | Fat (g) | Protein (g)
+-----------------+------------+------------------+---------+-------------+
  Beef Mince      |      150.0 |              0.0 |     6.0 |        37.5
  Carrot          |       50.0 |              3.5 |     0.5 |         0.0
  Chilli          |        5.0 |              0.8 |     0.7 |         0.7
  Cumin           |        3.0 |              0.8 |     0.5 |         0.7
  Garlic          |       10.0 |              1.7 |     0.8 |         0.1
  Kidney Beans    |       30.0 |              3.9 |     2.1 |         0.3
  Onion           |       30.0 |              3.3 |     0.6 |         3.0
  Rice            |       60.0 |             16.2 |     2.4 |         0.6
  Tinned Tomatoes |      150.0 |              6.0 |     1.5 |         0.0
+-----------------+------------+------------------+---------+-------------+
                                      36.2g       |  15.1g  |    42.9g
                               +------------------+---------+-------------+

And I want to change the weight of the ingredients to meet a given target, in this case 122g of Carbohydrate, 23g of Fat, 45g of Protein.

I'm not having any luck taking each individual ingredients and adjusting to meet the target because they obviously affect all 3 macro-nutrients. It's been a while since I did any matrix multiplication, but it feels like this might be helpful trying to solve the problem.

Is this a well-documented algorithm? Do you have any advice? My Google-foo is failing me.

Answer 1

Your system of linear equations is underdetermined. It has more unknowns than equations.

I tried to solve it using the Moore-Penrose pseudoinverse along the lines of a related post. My calculations might be flawed, but I got partly negative weights. Not really practical for a recipe!

My second attempt was the Excel solver which resulted in:

The solver seeks the minimum of a target cell by varying variable cells. In this case the target is the sum of squared errors between achieved mix and desired mix. The variables are the weights of the nine ingredients.

Other than a normal solver for linear equations, the Excel solver can restrict the variables to non-negative values which comes in handy for your case.

---

Update:

You can view and solve this task as Linear Program, as set of linear (in)equalities.

A GLPK model:

# weights of the nine ingredients
var x1, >= 0;
var x2, >= 0;
var x3, >= 0;
var x4, >= 0;
var x5, >= 0;
var x6, >= 0;
var x7, >= 0;
var x8, >= 0;
var x9, >= 0;

# dummy objective
maximize obj: 0;
# Carbohydrate target
s.t. c1: (0.0 / 150) * x1 + 
         (3.5 /  50) * x2 + 
         (0.8 /   5) * x3 + 
         (0.8 /   3) * x4 + 
         (1.7 /  10) * x5 + 
         (3.9 /  30) * x6 + 
         (3.3 /  30) * x7 + 
         (16.2 / 60) * x8 + 
         (6 /   150) * x9 == 122;
# Fat target
s.t. c2: (6   / 150) * x1 + 
         (0.5 /  50) * x2 + 
         (0.7 /   5) * x3 + 
         (0.5 /   3) * x4 + 
         (0.8 /  10) * x5 + 
         (2.1 /  30) * x6 + 
         (0.6 /  30) * x7 + 
         (2.4 /  60) * x8 + 
         (1.5 / 150) * x9 == 23;
# Protein target
s.t. c3: (37.5/ 150) * x1 + 
         (0.0 /  50) * x2 + 
         (0.7 /   5) * x3 + 
         (0.7 /   3) * x4 + 
         (0.1 /  10) * x5 + 
         (0.3 /  30) * x6 + 
         (3.0 /  30) * x7 + 
         (0.6 /  60) * x8 + 
         (0.0 / 150) * x9 == 45;
solve;
display x1, x2, x3, x4, x5, x6, x7, x8, x9;
end;

The solution

x1.val = 110.814249363868
x2.val = 0
x3.val = 0
x4.val = 0
x5.val = 0
x6.val = 0
x7.val = 133.206106870229
x8.val = 397.582697201018
x9.val = 0

There are various wrappers available for GLPK to call it from within your own programs.