5D Library › Insulin-Glucagon Bistability, Visceral Lipolysis Kinetics and Linear-Programming Diet Optimization · 中文
Chapter 6. The Diet Problem, Solved Twice
The oldest linear programme
The problem of this chapter is not new and was not invented by anyone selling a meal plan. Stigler posed it in 1945: given the composition and price of a list of foods and a list of nutrient requirements, what is the cheapest diet that satisfies them all? He solved his own version by educated trial, remarking that there was no systematic method, and the systematic method arrived shortly afterwards. Dantzig’s simplex algorithm turned the question into a mechanical one, and the diet problem became its standard illustration (Stigler 1945; Dantzig 1963). The implementation in p11 uses Bland’s pivoting rule, which guarantees that the algorithm terminates rather than cycling between equally good vertices (Bland 1977).
Evidence
Published. Stigler posed the cost-of-subsistence problem and solved an instance of it by hand before a general method existed (Stigler 1945). Dantzig’s book sets out the simplex method and treats the diet problem as a standard application (Dantzig 1963). Bland proved that his pivoting rule makes the simplex method finite, removing the possibility of cycling (Bland 1977).
What the previous chapters contribute is the constraint list. Energy is held at a target rather than bounded, because the deficit is what Chapter 3 showed does the work. Protein has a floor, because Chapter 3’s trials found lean mass falling in the restricted arm. Carbohydrate has a ceiling, because the switch of Chapter 1 has to stay on the fasted branch. The three electrolytes have floors, because of Chapter 5. And each food has a serving ceiling, because an answer nobody will eat is not an answer.
Calculation
# Chapter 6. p11: The cheapest day that satisfies every constraint. This
# is a linear programme: the quantities of ten foods, in hundred-gram
# units, are chosen to minimise cost while the day's energy is held at a
# target and protein, fat, the three electrolytes and a carbohydrate
# ceiling are respected, with a serving ceiling on each food so that the
# answer is edible. The two-phase simplex method below is written out in
# full and uses Bland's rule, so it cannot cycle. Composition figures
# are rounded from published food tables; prices are illustrative.
FOODS = (
# name, kcal, protein, fat, carb (g), Na, K, Mg (mg), cost, max units
("eggs", 143, 12.6, 9.5, 0.7, 142, 138, 12, 0.60, 2.5),
("chicken thigh", 209, 26.0, 10.9, 0.0, 86, 230, 25, 0.90, 3.0),
("salmon", 208, 20.4, 13.4, 0.0, 50, 363, 29, 2.40, 2.0),
("beef mince", 250, 26.0, 15.0, 0.0, 75, 318, 21, 1.30, 3.0),
("spinach", 23, 2.9, 0.4, 1.4, 79, 558, 79, 0.50, 4.0),
("broccoli", 34, 2.8, 0.4, 4.0, 33, 316, 21, 0.40, 4.0),
("avocado", 160, 2.0, 14.7, 1.8, 7, 485, 29, 0.80, 3.0),
("olive oil", 884, 0.0,100.0, 0.0, 2, 1, 0, 0.70, 1.0),
("pumpkin seeds", 559, 30.2, 49.1, 4.7, 18, 809, 592, 1.80, 0.6),
("lite salt", 0, 0.0, 0.0, 0.0,9700,10500, 0, 0.25, 0.2),
)
TARGET_KCAL = 1800.0
MIN_PROTEIN, MIN_FAT, MAX_CARB = 120.0, 110.0, 50.0
MIN_NA, MIN_K, MIN_MG = 3000.0, 3500.0, 400.0
def simplex(c, rows, verbose=False):
"""min c.x s.t. rows of (coeffs, sense, rhs), x >= 0. Two phases."""
n = len(c)
m = len(rows)
cols = n
extra = [] # (kind, row index)
for i, (_, sense, _) in enumerate(rows):
if sense == "<=":
extra.append(("slack", i))
elif sense == ">=":
extra.append(("surplus", i))
extra.append(("art", i))
else:
extra.append(("art", i))
total = cols + len(extra)
T = [[0.0] * (total + 1) for _ in range(m)]
basis = [-1] * m
for i, (a, _, b) in enumerate(rows):
for j in range(n):
T[i][j] = float(a[j])
T[i][total] = float(b)
for k, (kind, i) in enumerate(extra):
j = cols + k
T[i][j] = -1.0 if kind == "surplus" else 1.0
if kind in ("slack", "art"):
basis[i] = j
art = [cols + k for k, (kind, _) in enumerate(extra) if kind == "art"]
def pivot(obj, allowed):
while True:
# Bland: lowest index with a negative reduced cost
z = [0.0] * (total + 1)
for i in range(m):
cb = obj[basis[i]]
if cb:
for j in range(total + 1):
z[j] += cb * T[i][j]
enter = -1
for j in allowed:
if obj[j] - z[j] < -1e-9:
enter = j
break
if enter < 0:
return z[total]
best, leave = None, -1
for i in range(m):
if T[i][enter] > 1e-9:
r = T[i][total] / T[i][enter]
tie = (abs(r - best) <= 1e-9
if best is not None else False)
if best is None or r < best - 1e-9 or \
(tie and basis[i] < basis[leave]):
best, leave = r, i
if leave < 0:
raise ValueError("unbounded")
p = T[leave][enter]
T[leave] = [v / p for v in T[leave]]
for i in range(m):
if i != leave and abs(T[i][enter]) > 1e-12:
fv = T[i][enter]
T[i] = [T[i][j] - fv * T[leave][j]
for j in range(total + 1)]
basis[leave] = enter
obj1 = [0.0] * total
for j in art:
obj1[j] = 1.0
pivot(obj1, list(range(total)))
if sum(T[i][total] for i in range(m) if basis[i] in art) > 1e-7:
raise ValueError("infeasible")
keep = [j for j in range(total) if j not in art]
obj2 = [0.0] * total
for j in range(n):
obj2[j] = float(c[j])
val = pivot(obj2, keep)
x = [0.0] * n
for i in range(m):
if basis[i] < n:
x[basis[i]] = T[i][total]
return val, x
def build(max_carb=MAX_CARB, min_mg=MIN_MG, target=TARGET_KCAL):
cost = [f[8] for f in FOODS]
rows = []
rows.append(([f[1] for f in FOODS], "=", target))
rows.append(([f[2] for f in FOODS], ">=", MIN_PROTEIN))
rows.append(([f[3] for f in FOODS], ">=", MIN_FAT))
rows.append(([f[4] for f in FOODS], "<=", max_carb))
rows.append(([f[5] for f in FOODS], ">=", MIN_NA))
rows.append(([f[6] for f in FOODS], ">=", MIN_K))
rows.append(([f[7] for f in FOODS], ">=", min_mg))
for i, f in enumerate(FOODS):
a = [0.0] * len(FOODS)
a[i] = 1.0
rows.append((a, "<=", f[9]))
return cost, rows
def totals(x):
out = [0.0] * 7
for xi, f in zip(x, FOODS):
for k in range(7):
out[k] += xi * f[k + 1]
return out
if __name__ == "__main__":
cost, rows = build()
val, x = simplex(cost, rows)
print(" cheapest day that meets every constraint: {:.4f}".format(val))
print(" food hundred-gram units grams")
for xi, f in zip(x, FOODS):
if xi > 1e-6:
print(" {:<17}{:<21.4f}{:.0f}".format(f[0], xi, xi * 100.0))
t = totals(x)
print(" energy {:.1f} kcal, protein {:.1f} g, fat {:.1f} g,"
" carbohydrate {:.1f} g".format(t[0], t[1], t[2], t[3]))
print(" sodium {:.0f} mg, potassium {:.0f} mg, magnesium {:.0f} mg"
.format(t[4], t[5], t[6]))
print(" constraint floor or cap achieved tight")
checks = (("protein", MIN_PROTEIN, t[1], "floor"),
("fat", MIN_FAT, t[2], "floor"),
("carbohydrate", MAX_CARB, t[3], "cap"),
("sodium", MIN_NA, t[4], "floor"),
("potassium", MIN_K, t[5], "floor"),
("magnesium", MIN_MG, t[6], "floor"))
for name, lim, got, kind in checks:
tight = "yes" if abs(got - lim) < 0.5 else "no"
print(" {:<17}{:<15.0f}{:<11.1f}{}".format(name, lim, got, tight))
print(" sensitivity, cost of the cheapest day:")
print(" change cost rise")
for label, kw in (("carbohydrate cap 30 g", {"max_carb": 30.0}),
("carbohydrate cap 20 g", {"max_carb": 20.0}),
("magnesium floor 500 mg", {"min_mg": 500.0}),
("magnesium floor 600 mg", {"min_mg": 600.0}),
("energy target 1500 kcal", {"target": 1500.0}),
("energy target 2100 kcal", {"target": 2100.0})):
c2, r2 = build(**kw)
try:
v2, _ = simplex(c2, r2)
except ValueError:
print(" {:<30}{}".format(label, "no feasible day"))
continue
print(" {:<30}{:<10.4f}{:+.4f}".format(label, v2, v2 - val))
lo, hi = 1400.0, 1800.0
for _ in range(40):
mid = 0.5 * (lo + hi)
c2, r2 = build(target=mid)
try:
simplex(c2, r2)
hi = mid
except ValueError:
lo = mid
print(" lowest energy target the serving ceilings allow:"
" {:.1f} kcal".format(0.5 * (lo + hi)))
c2, r2 = build(target=0.5 * (lo + hi) + 1.0)
v2, _ = simplex(c2, r2)
print(" the cheapest day there costs {:.4f}".format(v2))
# cheapest day that meets every constraint: 8.2888
# food hundred-gram units grams
# eggs 2.5000 250
# chicken thigh 3.0000 300
# spinach 4.0000 400
# broccoli 3.9293 393
# olive oil 0.6673 67
# lite salt 0.2000 20
# energy 1800.0 kcal, protein 132.1 g, fat 126.4 g, carbohydrate 23.1 g
# sodium 3000 mg, potassium 6609 mg, magnesium 504 mg
# constraint floor or cap achieved tight
# protein 120 132.1 no
# fat 110 126.4 no
# carbohydrate 50 23.1 no
# sodium 3000 3000.0 yes
# potassium 3500 6609.3 no
# magnesium 400 503.5 no
# sensitivity, cost of the cheapest day:
# change cost rise
# carbohydrate cap 30 g 8.2888 +0.0000
# carbohydrate cap 20 g 8.3765 +0.0877
# magnesium floor 500 mg 8.2888 +0.0000
# magnesium floor 600 mg 8.4826 +0.1938
# energy target 1500 kcal no feasible day
# energy target 2100 kcal 8.5286 +0.2397
# lowest energy target the serving ceilings allow: 1655.0 kcal
# the cheapest day there costs 8.1785The cheapest day that satisfies every constraint costs 8.2888 and comes out as 250 grams of eggs, 300 of chicken thigh, 400 of spinach, 393 of broccoli, 67 of olive oil and 20 of lite salt. It delivers 1800.0 kcal, 132.1 grams of protein, 126.4 of fat and 23.1 of carbohydrate, with 3000 milligrams of sodium, 6609 of potassium and 504 of magnesium.
Read the tight column. Of the six nutrient constraints, exactly one binds: sodium, at 3000. Protein overshoots its floor by twelve grams, carbohydrate comes in at 23.1 against a ceiling of 50, potassium reaches 6609.3 against a floor of 3500, and magnesium 503.5 against 400. This is the practical lesson of solving the problem rather than arguing about it. The constraint people argue about, carbohydrate, is slack by more than half; the constraint nobody mentions, sodium, is the one holding the solution in place. Lowering the carbohydrate ceiling from 50 to 30 costs nothing at all; lowering it to 20 costs 0.0877. Raising the magnesium floor to 500 costs nothing; raising it to 600 costs 0.1938.
The last two lines matter more than the price. Below an energy target of 1655.0 kcal there is no feasible day at all, because the serving ceilings that keep the answer edible, together with the protein and electrolyte floors, imply a minimum energy. The cheapest day at that floor costs 8.1785. A plan advertised at a thousand calories is not a stricter version of this plan; inside this food list and these ceilings it does not exist.
Twenty-eight days without a repeat
A cheapest day is not a plan, because nobody eats the same cheapest day twenty-eight times. The second problem is combinatorial rather than continuous: build a month of distinct menus under rules about variety.
Calculation
# Chapter 6. p12: Twenty-eight days without repeating a menu. A menu is
# one protein, one vegetable and one fat, each in a fixed portion, so
# there are as many candidate menus as the product of the three lists.
# A menu counts as feasible if its energy falls inside the window and it
# clears the protein and fat floors and the carbohydrate ceiling. The
# plan is then built day by day: the first feasible menu that repeats no
# component used in the previous two days and keeps every component
# inside its own ceiling for the month. The order of candidates rotates
# with the day, which is what spreads the choices out. No randomness.
# The ceilings themselves are not guessed: the program searches for the
# smallest ones, counted together, under which the rule still fills all
# twenty-eight days, and reports what the month then looks like.
PROTEIN = (
("eggs 200 g", 286, 25.2, 19.0, 1.4),
("chicken 280 g", 585, 72.8, 30.5, 0.0),
("salmon 240 g", 499, 49.0, 32.2, 0.0),
("beef 260 g", 650, 67.6, 39.0, 0.0),
("pork loin 260 g", 546, 59.8, 31.2, 0.0),
("prawns 300 g", 297, 60.0, 5.1, 0.9),
)
VEG = (
("spinach 400 g", 92, 11.6, 1.6, 5.6),
("broccoli 350 g", 119, 9.8, 1.4, 14.0),
("courgette 400 g", 68, 4.8, 1.3, 9.2),
("cauliflower 350 g", 88, 6.7, 1.0, 11.6),
("green beans 350 g", 109, 6.3, 0.4, 17.5),
("asparagus 400 g", 80, 8.8, 0.5, 7.6),
("cabbage 400 g", 100, 5.2, 0.4, 16.0),
)
FAT = (
("olive oil 30 g", 265, 0.0, 30.0, 0.0),
("avocado 200 g", 320, 4.0, 29.4, 3.6),
("butter 30 g", 215, 0.3, 24.3, 0.0),
("pumpkin seeds 45 g",252, 13.6, 22.1, 2.1),
("macadamia 40 g", 288, 3.2, 30.3, 2.2),
)
KCAL_LO, KCAL_HI = 700.0, 1100.0
MIN_PROT, MIN_FAT, MAX_CARB = 50.0, 35.0, 25.0
DAYS, SPACING = 28, 2
def totals(p, v, f):
return tuple(PROTEIN[p][k] + VEG[v][k] + FAT[f][k] for k in range(1, 5))
def feasible(p, v, f):
kcal, prot, fat, carb = totals(p, v, f)
return (KCAL_LO <= kcal <= KCAL_HI and prot >= MIN_PROT
and fat >= MIN_FAT and carb <= MAX_CARB)
def plan_month(ok, cap_p, cap_v, cap_f):
plan = []
used_p, used_v, used_f = [0] * len(PROTEIN), [0] * len(VEG), \
[0] * len(FAT)
for day in range(DAYS):
recent = plan[-SPACING:]
chosen = None
for i in range(len(ok)):
p, v, f = ok[(i + day * 7) % len(ok)]
if (p, v, f) in plan:
continue
if any(p == rp or v == rv or f == rf for rp, rv, rf in recent):
continue
if used_p[p] >= cap_p or used_v[v] >= cap_v \
or used_f[f] >= cap_f:
continue
chosen = (p, v, f)
break
if chosen is None:
return plan, used_p, used_v, used_f
plan.append(chosen)
used_p[chosen[0]] += 1
used_v[chosen[1]] += 1
used_f[chosen[2]] += 1
return plan, used_p, used_v, used_f
if __name__ == "__main__":
all_combos = [(p, v, f) for p in range(len(PROTEIN))
for v in range(len(VEG)) for f in range(len(FAT))]
ok = [c for c in all_combos if feasible(*c)]
print(" candidate menus: {} ({} proteins x {} vegetables x {} fats)"
.format(len(all_combos), len(PROTEIN), len(VEG), len(FAT)))
print(" feasible menus: {} ({:.3f} of the candidates)"
.format(len(ok), len(ok) / len(all_combos)))
never = [PROTEIN[p][0] for p in range(len(PROTEIN))
if not any(c[0] == p for c in ok)]
print(" protein portions too small to carry a main meal: {}"
.format(", ".join(never) if never else "none"))
found = None
for total in range(9, 40):
for cp in range(3, min(total, 15)):
for cv in range(3, min(total - cp, 15)):
cf = total - cp - cv
if cf < 3 or cf > 14:
continue
pl, up, uv, uf = plan_month(ok, cp, cv, cf)
if len(pl) == DAYS:
found = (cp, cv, cf, pl, up, uv, uf)
break
if found:
break
if found:
break
cp, cv, cf, plan, used_p, used_v, used_f = found
print(" smallest ceilings that fill {} days: protein {}, vegetable"
" {}, fat {}".format(DAYS, cp, cv, cf))
print(" their sum is {}, against {} days to fill".format(cp + cv + cf,
DAYS))
print(" days planned: {}".format(len(plan)))
print(" day protein vegetable fat kcal")
for i, (p, v, f) in enumerate(plan[:10], 1):
kcal = totals(p, v, f)[0]
print(" {:<5d}{:<15}{:<16}{:<15}{:.0f}"
.format(i, PROTEIN[p][0].split()[0], VEG[v][0].split()[0],
FAT[f][0].split()[0], kcal))
print(" distinct menus in the plan: {}".format(len(set(plan))))
worst = 0
for i in range(1, len(plan)):
for j in range(max(0, i - SPACING), i):
if any(plan[i][k] == plan[j][k] for k in range(3)):
worst += 1
print(" component repeats inside {} days: {}".format(SPACING, worst))
print(" times each protein is used: {}".format(used_p))
print(" times each vegetable is used: {}".format(used_v))
print(" times each fat is used: {}".format(used_f))
kc = [totals(*c)[0] for c in plan]
pr = [totals(*c)[1] for c in plan]
cb = [totals(*c)[3] for c in plan]
print(" energy across the month: {:.0f} to {:.0f} kcal, mean {:.1f}"
.format(min(kc), max(kc), sum(kc) / len(kc)))
print(" protein {:.1f} to {:.1f} g, carbohydrate {:.1f} to {:.1f} g"
.format(min(pr), max(pr), min(cb), max(cb)))
# candidate menus: 210 (6 proteins x 7 vegetables x 5 fats)
# feasible menus: 144 (0.686 of the candidates)
# protein portions too small to carry a main meal: eggs 200 g
# smallest ceilings that fill 28 days: protein 7, vegetable 5, fat 7
# their sum is 19, against 28 days to fill
# days planned: 28
# day protein vegetable fat kcal
# 1 chicken spinach olive 942
# 2 salmon broccoli avocado 938
# 3 beef courgette butter 933
# 4 chicken green pumpkin 946
# 5 salmon spinach olive 856
# 6 beef broccoli avocado 1089
# 7 pork courgette butter 829
# 8 salmon cauliflower olive 852
# 9 beef spinach avocado 1062
# 10 pork broccoli butter 880
# distinct menus in the plan: 28
# component repeats inside 2 days: 0
# times each protein is used: [0, 6, 6, 7, 6, 3]
# times each vegetable is used: [5, 5, 5, 5, 5, 3, 0]
# times each fat is used: [7, 7, 7, 4, 3]
# energy across the month: 704 to 1089 kcal, mean 904.0
# protein 55.3 to 92.7 g, carbohydrate 5.6 to 19.7 gOf the 210 candidate menus, 144 are feasible. One protein portion, the eggs, is never feasible in any combination, because even with the richest vegetable and fat it cannot reach the energy floor for a main meal. That is a result about portion sizes, not about eggs.
The ceilings are not guessed. The program searches for the smallest component ceilings, counted together, under which the rule still fills all twenty-eight days, and finds seven, five and seven, a sum of 19. Under those ceilings the plan reaches 28 distinct menus with 0 component repeats inside two days, energy from 704 to 1089 kcal with a mean of 904.0, protein from 55.3 to 92.7 grams and carbohydrate from 5.6 to 19.7.
Hypothesis · not established
The author’s interpretation (not yet tested): the binding constraint on a real twenty-eight day plan is not nutrition but the number of distinct protein portions a household will buy and cook, and plans fail at the point where that number falls below four rather than where any nutrient floor is missed. What would show it wrong: if, in a cohort following a prescribed month, abandonment were predicted by the nutrient profile of the plan and not by the count of distinct proteins and the shopping frequency it requires, the combinatorial account would be wrong.
Summary
The cheapest compliant day costs 8.2888, and of the six nutrient constraints only sodium binds, while the carbohydrate ceiling is slack by more than half. Below 1655.0 kcal no day satisfies every constraint at all. Of 210 candidate menus 144 are feasible, and the smallest component ceilings that fill the month are seven, five and seven, giving 28 distinct menus with 0 repeats inside two days. Chapter 7 steps back to ask what the classical dietetic literature was warning about, and whether the thermodynamics agrees.
References
Fan, Y. (2026). Insulin-Glucagon Bistability, Visceral Lipolysis Kinetics and Linear-Programming Diet Optimization: Hepatic Glycogen Depletion Times, Triglyceride-Glucose Indices and Micronutrient-Constrained Menus [胰岛素胰高血糖素双稳态、内脏脂解动力学与线性规划配餐] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24090248 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).