NOTE: Since this math post is centered around economics, I will adopt a few conventions that are usually not okay in pure math. For example, I might write something like $\frac{123}{345}=0.357$ for expediency’s sake, even though this is not strictly mathematically tue.
In this post, I will develop a solution method for an interesting optimization problem in economics called the diet problem. The general form of the problem is as follows.
As a living human being, you have various nutritional quotas that you must satisfy to survive, and in order to do so you must eat different types of food with varying quantities of each nutrient. Given a list of nutrients, the required quantities of each respective nutrient, a list of foods, the costs of each food, and the nutritional contents of each food, how can you decide upon a quantity of each food to purchase that both satisfies your needs and costs as little as possible? Note that food is purchased continuously (you may purchase non-integer quantities of the foods, but not negative quantities).
An example diet problem might look like this. There are three nutrients $N_1, N_2, N_3$, and you need quantities $1,2,$ and $3$ units of these respective nutrients. There are four different foods $F_1, F_2, F_3, F_4$ that cost $5,4,3,$ and $2$ dollars per unit respectively. The table below shows the nutritional information of each food:
If you’re up for the challenge, go ahead and try to solve the problem above before I offer a solution below.
First of all, there are a few things we can do right off the bat to make this problem a little bit easier to digest. The numbers displayed in the table measure the amount of each nutrient contained in each unit of food, but there are even more numbers outside of the table that make the problem even messier (the costs of each food and the amounts of each nutrient required). However, suppose that we convert the numbers in the table from the quantity of each nutrient supplied per unit of food to the proportion of the required amount of each nutrient supplied per unit of food. For example, in my example problem, the $2$ in the second row and first column would be changed to $1.5$, since $3$ units of $N_2$ are supplied by $F_1$ and $2$ units of $N_2$ are required, and $3/2=1.5$. If we convert all the numbers in the table above, we end up with the following new table:
Now these numbers represent the proportion of the required amount of each nutrient that $1$ unit of each food would supply, and we don’t have to worry about the numbers $1,2,$ and $3$ (the nutrient quotas) anymore. We can do something similar for the food costs $5,4,3,$ and $2$. If we convert each number in the table to represent the proportion of each nutrient supplied by one dollar (rather than one unit) of each food, then we can divide the numbers in columns $1,2,3,$ and $4$ by the costs $5,4,3,$ and $2$ respectively, and we will no longer have to deal with those numbers. Doing this yields the following table:
Now we have encapsulated all of the information necessary for the problem into a single compact table, with no extraneous data necessary. From now on, all of the diet problems I present will be in this concise form to avoid unnecessary arithmetic.
As overwhelming as the data table may seem, it actually provides us with enough information to easily solve the problem right now, using only some basic reasoning and no fancy math (the fancy math will come later). Notice that every number in the bottom row is less than or equal to the corresponding number in the row above it. In the context of the problem, this means that every food satisfies a greater proportion of our $N_2$ quota than of our $N_3$ quota, which implies that as long as we satisfy our $N_3$ quota, our $N_2$ quota is guaranteed to be satisfied. Thus, we may ignore $N_2$ entirely, eliminating a row of the table and reducing the problem substantially:
By the same reasoning, we may also eliminate $N_1$, since it is more abundant than $N_3$ in any food:
At this point, it is obvious that we should simply buy $1.5$ dollars of $F_3$, since it contains the most $N_3$ on the dollar (and we know that both $N_1$ and $N_2$ will also be satisfied by the argument made earlier). This is the answer to our example problem!
That was certainly much easier than expected. However, not all diet problems work out so nicely. Consider the problem represented by the following table:
In this case, there is no obvious way to eliminate foods or nutrients. This is where we have to bring out the fancy math. Suppose we purchase quantities $x_1$ and $x_2$ of foods $F_1$ and $F_2$ respectively. Then our nutritional needs can be restated as the following constraints: Before we formulate a rigorous solution to the problem, our intuition can suggest a viable method of attack. Intuitively, it seems true that any cost-minimizing solution would contain the minimum required amounts of both nutrients, since any excess would suggest that more money has been spent than is required (of course, this was not true of the previous example, since some nutrients always appeared in greater quantities than others... but right now we’re tackling this problem non-rigorously, and we’ll come back later and prove whatever conclusions we reach).
If we make this assumption, then we may replace the above inequalities with equalities: This system of equations is easily solved by hand, but because we will encounter more complicated systems of equations later in this post, we will solve it using matrices:
This suggests that $x_1 = 2.857$ and $x_2 = 1.429$, with a total cost of $x_1+x_2=4.286$. But how do we know that this is really the optimal solution?
Here is a rigorous method of proof that the above solution is optimal. Let’s return to our two initial inequalities: Multiply the first inequality by $2.857$ and the second by $1.429$, yielding the following two inequalities: Then add them: Ah-ha! The quantity $x_1+x_2$ represents the total cost, and we have just proven, given only that we satisfy our nutritional needs, that the total cost must necessarily be greater than or equal to $4.286$. This shows that our previously determined solution of $x_1=2.857$ and $x_2=1.429$ is indeed optimal.
Any diet problem with a $2\times 2$ table can be solved either using the above method or by eliminating foods or nutrients as we did with the first example problem. So now let’s try something a little bit more complicated:
This time, we have the following two inequalities:
To rigorously find a solution, we want to manipulate these inequalities to obtain an inequality in the form
and we will have to do this by creating some linear combination of (i) and (ii). But we have a little problem - if we add $a$ times (i) with $b$ times (ii), in order to obtain the expression $x_1+x_2+x_3$ on the left side, we will need
but this system of three equations and only two variables has no solution. Now what?
Well, since we have two variables, any two of these equations will have a solution $(a,b)$. So let’s find the solution of each pair of them and see what we get. If we solve the first and second equations as a system, we get $a=1.818$ and $b=2.727$, and we will end up with the inequality
Wait a minute. By adding $0.091x_3$ to both sides, we may obtain the equivalent inequality
This means that if we let $x_3=0$, we might be able to achieve a minimum cost of $4.545$. If we assume $x_3=0$, the table becomes $2\times 2$ and we can assume equality rather than inequality (as we did in the previous problem) and obtain the following system of equations:
We may solve this again using matrices:
giving us the solution $x_1=2.727$ and $x_2=1.818$, and a total cost of $4.545$... and we have already shown that the cost of fulfilling our nutritional needs is always at least $4.545$. This is sufficient to show that our solution of $x_1=2.727$, $x_2=1.818$, and $x_3=0$ at a cost of $4.545$ is optimal.
Now, instead of a $2\times 3$ table, let’s try a $3\times 2$ table:
Once again, I chose this table because it cannot be simplified by eliminating any foods or nutrients as we did before, forcing us to come up with a more creative solution. This time, we have a system of three inequalities in two variables, rather than two inequalities in three variables:
A linear combination of any two of these inequalities can be found that results in the expression $x_1+x_2$ on the left side. If we consider only (i) and (ii), we get
Considering (i) and (iii) would yield a situation in which $F_2$ is always a better deal than $F_1$, and the minimum cost in that case would be
Finally, combining (ii) and (iii) would produce the following inequality:
Thus, the maximum of these lower bounds is $2.778$, meaning that no matter what, our cost will end up being at least $2.778$. From here, it is easy to calculate (using matrices, which I will omit this time) that expenses of $x_1 = 1.111$, $x_2 = 1.667$ and $x_3 = 0$ yield a total (optimal) price of $2.778$ and cover all of our needs.
Let’s do one more problem before I conclude this post. I’ll make it a $3\times 3$ table this time:
Again, there are no foods or nutrients that we may immediately eliminate, because no one column is greater than another in each of its entries, and no one row is greater than another in each of its entries. Here are the three inequalities implied by this table:
To solve this system (when the inequalities are replaced with equalities), we may use matrices again:
Which yields the solution $x_1=0.145$, $x_2=2.029$, $x_3=1.159$, with total cost $x_1+x_2+x_3=3.333$. To show that this is optimal, we must use a linear combination of the above inequalities multiplied by constant factors $a=1.667$, $b=1.667$, and $c=0$ (which I obtained using matrices, as usual), which yields the following inequality:
and we are done!
Use this method with caution. It will only work if no foods or nutrients can be eliminated, and it is not always obvious when this is possible. For instance, consider the following similar problem:
If we attempt to list out a system of inequalities, assume that they are equalities, and then solve the system with a matrix, we get the following answer:
Uh-oh, $x_1$ is negative. Why did that happen? None of the foods or nutrients can be obviously eliminated, since no row is greater than any other row in each of its entries, and the same is true for the columns.
The problem is that $F_2$ can actually be eliminated, although it isn’t immediately obvious at first glance. Consider this: buying $1$ dollar of $F_2$ supplies $0.2$ units of $N_1$, $0.4$ units of $N_2$, and $0.1$ units of $N_3$. But buying $0.5$ dollars of both $F_1$ and $F_3$ costs the same amount, but supplies $0.25, 0.4$, and $0.65$ units of $N_1, N_2$, and $N_3$ respectively - which is more than (or the same as) $F_2$ with respect to every nutrient. Thus, any dollar spent on $F_2$ is an inefficient use of money, since spending the same amount on $F_1$ and $F_3$ could result in greater amounts of nutrients. This allows us to eliminate the middle row of the table, leaving the following:
I won’t finish the rest of the problem, because it is very much the same as the ones we have already done so far.
That concludes this blog post! By working out numerous example problems above, I have demonstrated a general strategy for solving the diet problem. However, it would be interesting to come up with an algorithm to solve the problem without doing any work by hand. It would be even better to write a program (in Python, say) that would calculate the optimal values of $x_i$ given a table of nutritional information for an array of foods. Perhaps this will be the topic of a future blog post.