Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 38 ยท Modelling

Diet and Blending Problems

Model the diet problem and blending (mixing) problems as minimum-cost linear programs with nutrient requirements, ratio constraints and proportion variables.

Product mix problems maximize profit under upper limits. The second great family flips this: minimize cost subject to lower requirements. The diet problem (Stigler's classic) and its industrial cousins, blending for fuel, feed, alloys, fertilizer and coffee, are all of this type. They also introduce an important modelling skill: ratio and proportion constraints.

The diet problem

Choose how much of each food to buy so that daily nutrient requirements are met at minimum cost. Let x_j be the amount (in servings) of food j. For each nutrient i, with a_ij the amount of nutrient i per serving of food j:

TEXT
minimize    sum_j cost_j * x_j
subject to  sum_j a_ij * x_j >= minimum_i      (each nutrient)
            sum_j a_ij * x_j <= maximum_i      (optional upper limit)
            x_j >= 0, x_j <= servings_max_j

Here is a small made-up data set with four foods and three nutrients.

Food Cost per serving Calories Protein (g) Fiber (g)
Oats 0.30 150 5 4
Lentils 0.45 230 18 15
Milk 0.50 120 8 0
Apples 0.60 95 0 4

Requirements: calories between 1800 and 2400, protein at least 60 g, fiber at least 30 g, and at most 6 servings of any one food.

Python Solve the diet problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Look at the answer critically: the cheapest feasible diet is probably monotonous and not very appetizing. The LP did exactly what we asked. If a real person would not eat it, the model is missing constraints (variety limits, taste preferences). This is a standard lesson in OR: the optimizer exploits every loophole in the model.

A model is only as good as its constraints. The result "eat 6 servings of lentils" is optimal for the stated problem and may still be useless. Add realistic bounds, then re-solve.

Blending problems

In a blending problem you mix raw materials into a product whose quality (an average property) must meet a specification. The trick: quality is an average, which is a ratio, and ratios are not linear. The fix is to multiply through by the total, which is linear.

Example: a refinery blends three components into 1000 barrels of fuel. Octane must be at least 90 on average and sulfur at most 0.05%.

Component Cost per barrel Octane Sulfur % Available
A 60 98 0.08 500
B 48 88 0.04 700
C 40 84 0.02 600

Let x_A, x_B, x_C be barrels. The octane requirement is

(98 x_A + 88 x_B + 84 x_C) / 1000 >= 90, which is linear after multiplying by 1000 (the total is fixed here).

If the batch size were itself a variable, write the ratio as 98 x_A + 88 x_B + 84 x_C >= 90 (x_A + x_B + x_C), i.e. 8 x_A - 2 x_B - 6 x_C >= 0. Moving everything to one side makes any "average at least a target" constraint linear.

Python Fuel blending

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The ratio form sum((target - property_j) x_j) <= 0 is worth memorizing.

Proportion variables

An alternative formulation lets the variables be fractions of the blend: p_A + p_B + p_C = 1, and the quality constraints are then plain averages, 98 p_A + 88 p_B + 84 p_C >= 90. The result is scaled by the batch size afterwards. Fractions are convenient when the batch size is not fixed.

Python Same blend with proportion variables

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both formulations give the same plan, as they must: the availability limits 500/700/600 become proportion caps 0.5/0.7/0.6 when the batch is 1000 barrels.

When the problem is a mix of ideas

Real models mix the types. A feed company minimizes cost (diet-like) while meeting nutrient minimums (diet-like) and averaging specifications (blend-like) and using limited ingredient stocks (product-mix-like). Everything is still linear, so one linprog call solves it.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the diet problem, what is the objective?

    We minimize cost subject to lower (and optional upper) nutrient requirements.
  2. 2. Average octane of a blend must be at least 90. Which linear constraint expresses it when the total is a variable?

    Multiply the average constraint by the total and move everything to one side: sum(octane_j x_j) >= 90 sum(x_j).
  3. 3. The optimal diet is boring and unrealistic. What should you do?

    The solver is optimal for the model you wrote; improve the model rather than the solver.
  4. 4. With proportion variables p_j for a blend, which equation must hold?

    The proportions of a mix add up to the whole, i.e. 1.

Summary

  • Diet problems minimize cost subject to lower (and upper) nutrient requirements.
  • Average-quality constraints become linear after multiplying out the total.
  • Proportion variables (sum = 1) are an equivalent, convenient formulation.
  • Optimizers exploit loopholes: add realistic limits and re-solve.
  • Cost minimization, blending and product mix combine naturally.

Next: Transportation and Assignment Models