Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 49 ยท Modelling Decisions

Diet and Blending Models: Minimizing Cost

Model cost-minimization problems with minimum requirements: the classic diet problem and an animal-feed blending model, solved with linprog and milp.

The product-mix model maximizes profit under upper limits. The second great family of OR models turns this around: minimize cost subject to lower limits. You need to satisfy requirements (enough protein, enough strength, enough output), and you want to do it as cheaply as possible. The classic example is the diet problem, one of the first problems ever solved with linear programming. A close cousin is the blending problem, which mixes raw materials into a product with quality targets: animal feed, fuel, fertilizer, steel, paint.

In this lesson you will build both kinds of model and see what changes when constraints point the other way.

A plate of five foods feeding three requirement meters for energy, protein and calcium, with the cheapest daily cost shown
The diet model picks amounts of cheap foods until three requirement meters are full, at the lowest cost.

What you will learn

  • How to write a minimum-requirement (โ‰ฅ) model with a cost objective.
  • How to model blends where a share of the mix must meet a quality limit.
  • What the difference is between continuous and whole-serving solutions.
  • Why such models need extra rules to give realistic answers.

Key terms

Diet problem: choose amounts of foods that meet nutrient needs at minimum cost.

Blending problem: mix ingredients to reach a target quality at minimum cost.

Requirement constraint: a โ‰ฅ constraint that sets a minimum.

Mass balance: a constraint saying that the amounts of the ingredients add up to the total batch.

Composition constraint: a rule on the share of a property in the blend, such as "at least 20% protein".

Educational note. The numbers below are invented for modelling practice. They are not nutrition advice, and nothing here replaces advice from a doctor or dietitian.

The diet problem

A canteen wants the cheapest daily menu that supplies at least 2,000 kcal of energy, 60 g of protein and 1,000 mg of calcium. It can choose from five foods. Each row shows what one serving costs and supplies (example values):

Food Cost ($) Energy (kcal) Protein (g) Calcium (mg)
Oats 0.30 150 5 20
Milk 0.45 120 8 300
Beans 0.60 220 15 80
Rice 0.25 200 4 15
Eggs 0.50 140 12 55

Variables. xโ‚ โ€ฆ xโ‚… = servings per day of oats, milk, beans, rice, eggs.

Objective. Minimize cost 0.30xโ‚ + 0.45xโ‚‚ + 0.60xโ‚ƒ + 0.25xโ‚„ + 0.50xโ‚….

Constraints.

TEXT
150xโ‚ + 120xโ‚‚ + 220xโ‚ƒ + 200xโ‚„ + 140xโ‚… โ‰ฅ 2000   energy
  5xโ‚ +   8xโ‚‚ +  15xโ‚ƒ +   4xโ‚„ +  12xโ‚… โ‰ฅ   60   protein
 20xโ‚ + 300xโ‚‚ +  80xโ‚ƒ +  15xโ‚„ +  55xโ‚… โ‰ฅ 1000   calcium
 0 โ‰ค xโฑผ โ‰ค 8                                      at most 8 servings of any food

The upper bound of 8 servings is our first "realism" rule. Without it the cheapest source of energy (rice) could be used without limit.

linprog only accepts constraints of the form โ‰ค. A โ‰ฅ constraint is turned into โ‰ค by multiplying both sides by -1: -150xโ‚ - 120xโ‚‚ - ... โ‰ค -2000.

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.

The cheapest menu costs about $3.48 and consists of roughly 2.84 servings of milk, 0.39 servings of beans and 7.87 servings of rice. All three requirements are met exactly: they are binding. Notice that the solver ignores oats and eggs: at these prices they supply nutrients less cheaply than the chosen foods.

Whole servings

Fractions of a serving may be fine for a plan averaged over a month, but a canteen serves whole portions. Adding integrality turns the model into an integer program. Solve it with milp:

Python The same diet in whole servings

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 whole-serving plan costs $3.65, a little more than the fractional optimum of $3.48. That difference is the price of integrality: forcing whole numbers can never make the best cost lower. milp accepts lb directly, so no sign flip is needed.

What the model does not know

The model is happy to recommend nearly eight cups of rice. It knows nothing about taste, variety, allergies or culture. A practical diet model adds rules: at most a given amount of each food, minimum variety, limits on fat or salt, and so on. This is a general lesson: an optimizer exploits every gap in your model. When an answer looks absurd, ask which real-world rule is missing.

Blending problems

A feed mill mixes corn, soy meal and oat hulls into 1,000 kg of feed. The mix must contain at least 20% protein and at most 8% fiber. Ingredient data (example values):

Ingredient Cost ($/kg) Protein (share) Fiber (share)
Corn 0.22 0.09 0.03
Soy meal 0.45 0.45 0.06
Oat hulls 0.10 0.04 0.30

Variables. c, s, h = kilograms of corn, soy meal and oat hulls.

Objective. Minimize 0.22c + 0.45s + 0.10h.

Constraints.

TEXT
c + s + h = 1000                       mass balance
0.09c + 0.45s + 0.04h โ‰ฅ 0.20 ร— 1000    protein in kg
0.03c + 0.06s + 0.30h โ‰ค 0.08 ร— 1000    fiber in kg
c, s, h โ‰ฅ 0

The trick of blending models is to write the composition rule in kilograms, not percentages. A rule such as "protein share โ‰ฅ 20%" is (0.09c + 0.45s + 0.04h) / (c + s + h) โ‰ฅ 0.20, which is not linear. But because the batch size is fixed at 1,000 kg, the denominator is a constant and the rule becomes the linear inequality above. If the batch size were also a variable, multiply out the fraction: 0.09c + 0.45s + 0.04h โ‰ฅ 0.20(c + s + h).

Python Solve the feed blend

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 quality limits are binding: protein sits exactly at 20% and fiber exactly at 8%. The cost is about $277 per batch.

How cost changes with the requirement

The cost of satisfying a requirement rises with the requirement, but not in a straight line. The curve below recomputes the cheapest diet as the calcium requirement grows from 0 to 1,500 mg.

Python Cheapest diet cost vs calcium requirement

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 flat start shows requirements that are met for free by the cheap foods anyway; the bend upwards shows where calcium starts to cost money. The slope of the curve at any point is the shadow price of calcium, here about $0.0005 per milligram.

Where these models are used

The diet problem was one of the first applications of linear programming: in the 1940s, economists looked for the cheapest way to meet nutrition guidelines and found that the solution, though cheap, was a menu nobody wanted to eat. That history is the best warning about missing constraints. Today, the same structure appears in many industries.

  • Animal feed and fertilizer. Mills blend grains, meals and additives to hit protein, energy and mineral targets at minimum cost; ingredient prices change daily, so the model is re-solved often.
  • Fuel blending. Refineries mix streams to meet octane and vapor-pressure limits.
  • Metals and alloys. Foundries choose scrap and ore mixes that reach a target chemical composition.
  • Food products. Recipes for juices, snacks and sausages meet taste, fat and sugar limits at lowest cost.
  • Marketing and finance. The "choose the cheapest mix that reaches at least a given reach" structure is the same in advertising and in portfolio construction.

In each case the lesson is identical: write the requirements as lower or upper limits on absolute amounts, add the mass balance, and then add the practical rules that keep the answer sensible.

Common misconceptions

"Minimizing cost means choosing the cheapest ingredient." The cheapest ingredient may supply the needed property poorly. The model chooses by cost per unit of requirement met.

"If requirements are met, the solution is realistic." Models need extra rules (limits per ingredient, variety) to avoid extreme but technically correct answers.

"Rounding fractional servings gives the best whole-number plan." Rounding up is feasible but not always cheapest; rounding down may break a requirement. Use integer programming when whole numbers matter.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How do you give a "โ‰ฅ" constraint to linprog?

    linprog takes constraints as A_ub x โ‰ค b_ub, so -aยทx โ‰ค -b expresses aยทx โ‰ฅ b.
  2. 2. In the feed blend, why is the protein rule written as 0.09c + 0.45s + 0.04h โ‰ฅ 200?

    With a fixed batch size the percentage rule becomes a linear constraint in kilograms.
  3. 3. The whole-serving diet costs $3.65 and the fractional one $3.48. Why is the integer cost not lower?

    Integer plans are a subset of all plans, so the best of them cannot be cheaper.
  4. 4. A model recommends eight servings of rice a day. What is the likely reason?

    An optimizer exploits any gap in the model; add real-world rules to prevent extreme answers.
  5. 5. What does a mass-balance constraint do in a blending model?

    c + s + h = 1000 says the three ingredients together make exactly one batch.

Summary

  • Diet and blending models minimize cost subject to lower limits on nutrients or qualities.
  • Turn โ‰ฅ into โ‰ค by multiplying by -1 for linprog, or use lb in milp.
  • Composition rules are written in absolute amounts (kilograms) so they stay linear; add a mass-balance equation.
  • Whole-number requirements cost at least as much as fractional ones.
  • Always ask which real-world rule the model is missing when an answer looks odd.

Next: Binary Variables and Logic