Blending models

In the production planning models that we have considered so far, there is a very precise way of producing each item type. When producing a car, you typically need an engine and four wheels. Factors cannot be substituted; there is no way to convince a customer to buy a car with 20 wheels and no engine. This is typical of discrete manufacturing, but there are situations allowing several ways to produce an item by blending ingredients, provided we satisfy the constraints that define an acceptable mix. This happens in the oil industry, where different chemical components are blended to obtain gasoline meeting some economical and regulatory constraints, as well as in certain food industries. In fact, the prototypical blending problem is the diet problem.

Example 12.11 (The diet problem) When specifying a diet, we want to make sure that we take a minimum amount of certain nutrients, like proteins and vitamins. On the other hand, we want to place an upper bound on other elements, like fat and sodium. We obtain such elements by eating different foods, that have different prices. Now suppose that we want to find the minimum cost diet, such that all of the elements stay within their prescribed bounds. This is a very crude approach, of course, as a diet has many more features that we should pay attention to, and we are disregarding the need for some day-to-day variation. Yet, it is a good starting point.

To formalize the problem, we define first the basic sets we are dealing with: the set I of elements or nutrients, indexed by i, and the set J of food types, indexed by j. The information we need is

• The cost c_j of each food type j ∈ J.
• The content a_ij of each nutrient i ∈ I contained in a unit amount (measured in weight or volume) of food type j ∈ J.
• The lower and upper bounds, l_i and u_i, on the daily assumption of each element; if one of the two bounds is missing, we may just set it to 0 or +∞, respectively.

To specify a diet, we use as decision variable the amount x_i of each food j ∈ J that is consumed per day.²⁰ Then, the model is rather easy to write down:

The model is pretty self-explanatory, but once again we invite the reader to observe the use of indices in constraint (12.28). The coefficients a_ij have a double subscript, and one is covered by the sum, while the other one is covered by the enumeration of constraints.

In the diet problem, the lower and upper bounds are given in absolute terms, since we specify the minimum and maximum amounts of proteins that one should consume per day. In other settings, blending constraints are more naturally expressed in percentage terms. To see a trivial example, imagine that you have to prepare a cocktail for your next party, blending three liquors, L_a, L_b, and L_c. The alcoholic content of each of the three ingredients is d_a = 20°, d_b = 32°, and d_c = 55°. You want to keep the damage that your guests will inflict on your home to an acceptable level, so the alcoholic content of your brew should be in the range between lower bound L = 25° and upper bound U = 30°. If we assume that the alcoholic content of the mixture depends linearly on the percentage of each ingredient, we have the following constraint:

where variables z_a, z_b, and z_c are the percentage of each element in the cocktail. However, this is not very operational: If you have a given number of half-empty bottles of each ingredient, you would like to get a recipe giving you exactly how much of each liquor you should use. If we denote by x_a, x_b and x_c the actual volume used of each liquor, respectively, the constraint above can be written as

This form is not very pleasing however, as it is nonlinear, but it is very easy to get an equivalent linear expression. The amount of cocktail we mix, assuming there is no loss in volume, is

and the constraint above can be written as

The introduction of decision variable y is not strictly necessary, but it helps to improve model readability.

Example 12.12 (Optimal mix in a process industry) Let us write an optimal mix model suited for process industries, whereby the blend of raw materials to produce end items features some recipe flexibility. We disregard capacity constraints, but we assume that raw materials are available in limited amounts, and we must make the best of them. Limited availability of raw materials may be due to budget limitations in purchasing, limited availability on the market, or limited stocking capacity. We have a set I of raw materials, indexed by i, and a set J of end products, indexed by j. Let us denote by R_j the subset of raw materials that we may use in blending end product j. In this simple example we go to the opposite extreme with respect to discrete manufacturing with fixed and very rigid bills of materials, as we assume that we may use any raw material in the proper subset to blend an end product. Real-life problems fall somewhere between these extremes. The only constraint we enforce on the mix of raw materials relates to a quality measure. Each raw material has some feature, which is measured by a score q_i (the larger, the better). When we mix ingredients, the quality score of the resulting blend is a linear combination, an average, if you prefer, of the scores of the inputs, with weights proportional to the percentage of each raw material used. The quality score of each end product must fall between lower and upper bounds L_j and U_j. The economic side of the coin is represented by the unit cost c_i of raw materials and the selling price p_j of end items. Demand for end items is bounded by d_j, and raw-material availability is represented by inventory level I_i.

Assuming that we want to maximize profit, which decision variables should we introduce? On the commercial side, we must decide the amount of each end product that we blend and sell. Let us denote this amount by y_j. On the blending side, we must decide how much of each raw material i we use in blending end product j. Let us denote this variable by x_ij, which is defined only for i ∈ R_j. We may accomplish our aim by solving the following LP:

Equation (12.29) is profit, expressed as revenue from sales, minus cost of raw materials; note that in the second term we have a double sum, where we first sum with respect to end products, and then with respect to each raw material that may be used to blend that end product. Equation (12.30) is essentially a balance constraint related to conservation of mass; when complex chemical reactions are involved, a more careful modeling may be needed to account for nonlinearities. Equation (12.31) ensures that quality stipulations are met. Finally, Eq. (12.32) ensures that we do not use more raw materials than available. The sum in Eq. (12.32) might look odd at first sight; the notation j : i ∈ R_j specifies the indices of end products for which raw material i is part of the recipe R_j; formally, it denotes the subset of j ∈ J such that i is in R_j. Note that index i is fixed by constraint enumeration, since we have one such constraint for each ingredient, and that by doing so we sum only over defined variables x_ij. In practice, this is essentially an inversion of the mapping represented by R_j, which maps end item j into the set R_j of raw materials; given a raw material i, we want to sum over the set of end items that use it.²¹

Clearly, this is an oversimplified model. One questionable point concerns the cost of raw materials. From the perspective of a static model like this one, one could argue that this cost is sunk, and we should not consider it, as there is no value in keeping unused raw materials. In a realistic model, we would probably consider time and purchasing decisions; in many settings, the timing of purchase is important as some raw materials feature quite significant price swings.