5D Library › 胰岛素胰高血糖素双稳态、内脏脂解动力学与线性规划配餐 · English
第六章 配餐问题,解两遍
最老的那个线性规划
本章的问题不是新的,也不是哪个卖食谱的人发明的。Stigler 在 1945 年提出它:给定一张食物清单的成分与价格,以及一张营养需求清单,满足全部需求的最便宜饮食是什么?他用有根据的试错解了自己那一版,并说当时没有系统方法;系统方法随后就到了。Dantzig 的单纯形算法把这个问题变成机械的,而配餐问题成了它的标准例证 (Stigler 1945; Dantzig 1963)。p11 的实现用 Bland 的转轴规则,它保证算法会终止,而不会在同样好的若干顶点之间循环 (Bland 1977)。
证据
已发表。 Stigler 提出了生存成本问题,并在一般方法出现之前手算解出了它的一个实例 (Stigler 1945)。Dantzig 的书陈述单纯形法,并把配餐问题当作标准应用处理 (Dantzig 1963)。Bland 证明他的转轴规则使单纯形法有限终止,排除了循环的可能 (Bland 1977)。
前几章贡献的是那张约束清单。能量被固定在一个目标上而不是给一个区间,因为第三章显示真正做工的是热量缺口。蛋白质有一条下界,因为第三章那些试验发现限时那一组的去脂体重在下降。碳水化合物有一个上限,因为第一章那个开关必须停在空腹分支上。三种电解质各有一条下界,这是第五章的缘故。而每种食物都有一个份量上限,因为没人会吃的答案不是答案。
推导
# 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.1785满足全部约束的最便宜一天花 8.2888,解出来是 250 克蛋、300 克鸡腿肉、400 克菠菜、393 克西兰花、67 克橄榄油与 20 克低钠盐。它交付 1800.0 kcal、132.1 克蛋白质、126.4 克脂肪与 23.1 克碳水化合物,钠 3000 毫克、钾 6609 毫克、镁 504 毫克。
读那一列「紧」。六条营养约束里,恰好有一条是紧的:钠,在 3000 处。蛋白质超出下界十二克,碳水化合物为 23.1,而上限是 50,钾达到 6609.3,下界是 3500,镁为 503.5,下界是 400。这就是把问题解出来而不是围着它争论的实际收获。人们争论的那条约束,碳水化合物,松了一半以上;没人提起的那条约束,钠,才是把这个解按在原位的那一条。把碳水上限从 50 降到 30,一分钱也不多花;降到 20,花 0.0877。把镁下界提到 500,不多花;提到 600,花 0.1938。
最后两行比价格更要紧。在能量目标 1655.0 kcal 以下,根本没有一个可行的一天,因为那些让答案还能吃下去的份量上限,加上蛋白质与电解质的下界,隐含了一个最低能量。在那条地板上,最便宜的一天花 8.1785。一份标榜一千大卡的方案并不是这套方案更严格的版本;在这张食物清单与这些上限之内,它并不存在。
二十八天不重样
最便宜的一天不是一份方案,因为没有人会把同一个最便宜的一天吃二十八遍。第二个问题是组合的而不是连续的:在关于变化的规则之下,排出一个月不重样的菜单。
推导
# 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 g210 个候选菜单里有 144 个可行。有一份蛋白质份量,也就是那份蛋,在任何组合里都不可行,因为即便配上最厚的蔬菜与脂肪,它也达不到一顿正餐的能量下界。这是一个关于份量大小的结果,不是关于蛋的结果。
那些上限不是猜的。程序去搜索合计最小的组件上限,要求这条规则仍能把二十八天全部排满,找到的是七、五与七,合计 19。在这些上限下,方案达到 28 张不重样的菜单,两天之内的组件重复为 0,能量从 704 到 1089 kcal、均值 904.0,蛋白质从 55.3 到 92.7 克,碳水化合物从 5.6 到 19.7 克。
假说 · 尚未验证
作者的诠释(尚未验证): 一份真实的二十八天方案的紧约束不是营养,而是一个家庭愿意买并愿意做的不同蛋白质份量的数目;方案失败的地方是这个数目掉到四以下,而不是哪条营养下界没达到。什么会证明它错: 在一个遵循既定月度方案的队列里,如果放弃能由方案的营养谱预测,而不能由不同蛋白质的数目与它所要求的采购频率预测,那么这套组合解释就是错的。
小结
最便宜的合规一天花 8.2888,而六条营养约束里只有钠是紧的,碳水化合物上限松了一半以上。在 1655.0 kcal 以下,没有一天能同时满足全部约束。210 个候选菜单里有 144 个可行,而排满整月的最小组件上限是七、五与七,给出 28 张不重样的菜单与两天之内 0 次组件重复。第七章后退一步,问古典食疗文献到底在警告什么,以及热力学是否同意。
参考文献
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).