Skip to content
Tutorials Center
My learning

Topics

Lesson 33 of 38 ยท Applications

Blending and Feed Mix

Model blending problems as linear programs: the diet or feed mix problem, quality constraints written as weighted averages, shadow prices and a gasoline blending example in Python.

Blending problems are the oldest industrial use of linear programming. You have several raw materials with different costs and properties, and you must mix them into a product that meets specifications at the lowest cost. Cattle feed, fertilizer, steel alloys, gasoline, paint, sausages, coffee blends, concrete mixes and investment portfolios all follow the same template.

The skill in blending is not the solver; it is translating quality requirements (a minimum protein level, a maximum sulfur content, an average octane rating) into linear constraints. This lesson shows how, and how to read the shadow prices that come with the solution.

The basic model

Let x_i be the amount of ingredient i in one batch. The cost is sum c_i x_i. Each ingredient has a_ik units of property k per unit of material (for example kilograms of protein per kilogram). The batch must contain total weight B and meet minimum or maximum amounts of each property:

TEXT
minimize    sum_i c_i x_i
subject to  sum_i x_i = B
            sum_i a_ik x_i >= r_k       (minimum of nutrient k)
            sum_i a_ik x_i <= s_k       (maximum of nutrient k)
            x_i >= 0
Python Least-cost animal feed

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 solution uses the cheapest combination that still meets every nutritional limit. Several constraints are binding (satisfied with equality) and others have slack; that matters for the next idea.

Reading the shadow prices

Every constraint in the final solution has a dual value (shadow price): the change in the optimal cost per unit increase of its right-hand side. HiGHS returns them in res.ineqlin.marginals and res.eqlin.marginals. SciPy reports the change in the optimal cost per unit increase of the right-hand side of the <= row exactly as you wrote it. We negated the >= rows, so for those the sign flips: a marginal of -0.86 on the protein row means each extra kilogram of required protein raises the cost by 0.86. Interpret carefully:

  • A constraint with slack has a shadow price of 0: loosening it does not help.
  • A binding constraint has a nonzero price telling you what that requirement costs you. For example, in a 100 kg batch "the protein minimum costs about 0.86 per extra percentage point."
  • The batch-size equality's marginal is the marginal cost per extra kilogram.
Python Which requirements cost money? Shadow prices of the feed 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.

The finite difference matches the dual value. This is the practical meaning of duality, which you studied earlier in the course: dual variables price your resources and requirements. Use them to decide which specification is worth relaxing.

Ratio and percentage constraints

Specifications are often stated as percentages of the mixture: "at most 30% soy" or "protein between 18% and 22%". These look nonlinear because the total is a variable, but they linearize easily. A bound x_soy <= 0.3 * (x_1 + ... + x_n) is the linear constraint:

TEXT
0.7 x_soy - 0.3 x_others <= 0

When the batch size is fixed at B, just use x_soy <= 0.3 B. When the batch size is free (maximizing profit from available material), you must write the constraint homogeneously.

Quality averages. A property such as octane rating of a blend is the weighted average of the ingredients' ratings, weighted by quantity. "Average octane at least 92" means sum q_i x_i / sum x_i >= 92. Multiply both sides by the (positive) total:

TEXT
sum (q_i - 92) x_i >= 0

This is linear, whatever the batch size. The same trick works for "average sulfur at most 0.5%": sum (s_i - 0.5) x_i <= 0.

Python Gasoline blending with quality averages

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 average octane sits exactly at the 91 limit, while sulfur has room to spare (0.094% against 0.10%). All 4,000 barrels of reformate are used, and the cheap, low-octane naphtha is added until octane forces the solver to take some alkylate instead.

Common pitfalls

  • Units. Make sure every a_ik uses the same unit (per kilogram, not per percent of a different base) and that right-hand sides match.
  • Infeasibility. If no mix meets all specs (status 2), check which constraints conflict; relax them one at a time or add "penalty" variables that measure the violation.
  • Many near-equal optima. Blending models often have multiple optimal mixes. Add a secondary goal (fewest ingredients, closest to last month's recipe) if stability matters.
  • Integer requirements. If ingredients come in whole bags or you may use at most k ingredients, you need binary variables (Binary Variables and Logic).
  • Nonlinear blending. Some properties (viscosity, vapor pressure) do not blend linearly; use blending indices that do, or move to nonlinear programming.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you linearize 'the average octane of the blend must be at least 92'?

    Multiplying sum q_i x_i / sum x_i >= 92 by the positive total gives sum (q_i - 92) x_i >= 0.
  2. 2. What does a shadow price of 0 on a requirement tell you?

    A constraint with slack at the optimum has a zero dual value.
  3. 3. How would you write 'at most 30% of the batch of size B is soy'?

    With a fixed batch size B, a percentage bound is a bound on the amount; with a free batch size use 0.7 x_soy - 0.3 x_others <= 0.
  4. 4. Why might a blending LP have several different optimal recipes?

    When two ingredients offer the same value per cost, the optimum can be a whole face of recipes.

Summary

  • A blending LP chooses ingredient amounts to meet specifications at least cost.
  • Percentage and average-quality requirements become linear after multiplying out the (positive) total.
  • Shadow prices show what each specification costs and which ones are worth relaxing.
  • Watch units, infeasibility, ties and properties that do not blend linearly.
  • Whole-bag or limited-ingredient rules require integer variables.

Next: Multi-Period Production Planning