The diet problem, one of the earliest applications of LP, was originally used by hospitals to determine the most economical diet for patients. Known in agricultural applications as the feed mix problem, the diet problem involves specifying a food or feed ingredient combination that satisfies stated nutritional requirements at a minimum cost level.
The Whole Food Nutrition Center uses three bulk grains to blend a natural cereal that it sells by the pound. The cost of each bulk grain and the protein, riboflavin, phosphorus, and magnesium units per pound of each are shown in Table 8.5.
On the packaging for each of its products, Whole Food indicates the nutritional content in each bowl of cereal when eaten with 0.5 cup of milk. The USRDA (U.S. Recommended Dietary Allowance) and the more recent DRI (Dietary Reference Intake) were consulted to establish recommended amounts of certain vitamins and minerals for an average adult. Based on these figures and the desired amounts for labeling on the package, Whole Food has determined that each 2-ounce serving of the cereal should contain 3 units of protein, 2 units of riboflavin, 1 unit of phosphorus, and 0.425 unit of magnesium.
In modeling this as an LP, the objective is to minimize cost. There will be four constraints (one each for protein, riboflavin, phosphorus, and magnesium) stipulating that the number of units must be at least the minimum amount specified. Since these requirements are for each 2-ounce serving, the last constraint must say that the total amount of the grains used will be 2 ounces, or 0.125 pound.
In defining the variables, notice that the cost is expressed per pound of the three grains. Thus, in order to calculate the total cost, we must know the number of pounds of the grains used in one serving of the cereal. Also, the numbers in Table 8.5 are expressed in units per pound of grain, so defining variables as the number of pounds of the grains makes it easier to calculate the amounts of protein, riboflavin, phosphorus, and magnesium. We let
GRAIN | COST PER POUND (CENTS) | PROTEIN (UNITS/LB) | RIBOFLAVIN (UNITS/LB) | PHOSPHORUS (UNITS/LB) | MAGNESIUM (UNITS/LB) |
---|---|---|---|---|---|
A | 33 | 22 | 16 | 8 | 5 |
B | 47 | 28 | 14 | 7 | 0 |
C | 38 | 21 | 25 | 9 | 6 |
Objective:
subject to
The solution to this problem requires mixing together 0.025 lb of grain A, 0.050 lb of grain B, and 0.050 lb of grain C. Another way of stating the solution is in terms of the proportion of the 2-ounce serving of each grain—that is, 0.4 ounce of grain A, 0.8 ounce of grain B, and 0.8 ounce of grain C in each serving. The cost per serving is $0.05. Program 8.8 illustrates this solution using Solver in Excel 2016.
Diet and feed mix problems are actually special cases of a more general class of LP problems known as ingredient or blending problems. Blending problems arise when a decision must be made regarding the blending of two or more resources to produce one or more products. Resources, in this case, contain one or more essential ingredients that must be blended so that each final product contains a specific percentage of each ingredient. The following example deals with an application frequently seen in the petroleum industry, the blending of crude oils to produce refinable gasoline.
The Low Knock Oil Company produces two grades of cut-rate gasoline for industrial distribution. The grades, regular and economy, are produced by refining a blend of two types of crude oil, type X100 and type X220. Each crude oil differs not only in cost per barrel but in composition as well. The following table indicates the percentages of crucial ingredients found in each of the crude oils and the cost per barrel for each:
CRUDE OIL TYPE | INGREDIENT A (%) | INGREDIENT B (%) | COST/BARREL ($) |
---|---|---|---|
X100 | 35 | 55 | 30.00 |
X220 | 60 | 25 | 34.80 |
Weekly demand for the regular grade of Low Knock gasoline is at least 25,000 barrels, and demand for the economy is at least 32,000 barrels per week. At least 45% of each barrel of regular must be ingredient A. At most, 50% of each barrel of economy should contain ingredient B. While the gasoline yield from one barrel of crude depends on the type of crude and the type of processing used, we will assume for the sake of this example that one barrel of crude oil will yield one barrel of gasoline.
The Low Knock management must decide how many barrels of each type of crude oil to buy each week for blending to satisfy demand at minimum cost. In modeling this as an LP, the objective is to minimize cost. Each of the two types of gasoline has a demand constraint, and each of the two types of gasoline has a constraint restricting the amount of the ingredients. Thus, there are four constraints. The decision involves the amount of each type of crude to use in each type of gasoline, so these will be the decision variables. Let
This problem can be formulated as follows:
Objective:
subject to
At least 45% of each barrel of regular must be ingredient A:
Thus,
But
So
or
Similarly, at most 50% of each barrel of economy should be ingredient B:
Thus,
But
So
or
Here is the entire LP formulation:
Using Excel, the solution to Low Knock Oil’s formulation was found to be
The cost of this mix is $1,783,600. Refer to Program 8.9 for details.