ORTOOL线性规划 斯蒂格勒饮食问题

斯蒂格勒饮食问题(The Stigler diet Problem)，给定人类一天所必须摄入的营养 和 每种食物的营养，求出在花费最小的情况下满足人一天的营养需求。

1. 数据说明

①人体每天必须摄入的营养表

营养种类	最低摄入量
卡路里 (千卡)	3
蛋白质 (g)	70
钙 (g)	0.8
铁 (mg)	12
维生素A (KIU)	5
维生素B1 (mg)	1.8
维生素B2 (mg)	2.7
烟酸 (mg)	18
维生素C (mg)	75

②食物营养表

商品	卡路里 (千卡)	蛋白质 (g)	钙 (g)	铁 (mg)	维生素A (KIU)	维生素B1 (mg)	维生素B2 (mg)	烟酸 (mg)	维生素C (mg)
小麦粉（浓缩）	44.7	1411	2	365	0	55.4	33.3	441	0
通心粉	11.6	418	0.7	54	0	3.2	1.9	68	0
小麦谷物（浓缩）	11.8	377	14.4	175	0	14.4	8.8	114	0
玉米片	11.4	252	0.1	56	0	13.5	2.3	68	0
棒子面	36	897	1.7	99	30.9	17.4	7.9	106	0
玉米粥	28.6	680	0.8	80	0	10.6	1.6	110	0
米	21.2	460	0.6	41	0	2	4.8	60	0
燕麦片	25.3	907	5.1	341	0	37.1	8.9	64	0
白面包（浓缩）	15	488	2.5	115	0	13.8	8.5	126	0
全麦面包	12.2	484	2.7	125	0	13.9	6.4	160	0
黑麦面包	12.4	439	1.1	82	0	9.9	3	66	0
磅蛋糕	8	130	0.4	31	18.9	2.8	3	17	0
苏打饼干	12.5	288	0.5	50	0	0	0	0	0
牛奶	6.1	310	10.5	18	16.8	4	16	7	177
炼乳（罐装）	8.4	422	15.1	9	26	3	23.5	11	60
黄油	10.8	9	0.2	3	44.2	0	0.2	2	0
人造黄油	20.6	17	0.6	6	55.8	0.2	0	0	0
蛋	2.9	238	1	52	18.6	2.8	6.5	1	0
奶酪（切达干酪）	7.4	448	16.4	19	28.1	0.8	10.3	4	0
奶油	3.5	49	1.7	3	16.9	0.6	2.5	0	17
花生酱	15.7	661	1	48	0	9.6	8.1	471	0
蛋黄酱	8.6	18	0.2	8	2.7	0.4	0.5	0	0
克里斯科	20.1	0	0	0	0	0	0	0	0
猪油	41.7	0	0	0	0.2	0	0.5	5	0
沙朗牛排	2.9	166	0.1	34	0.2	2.1	2.9	69	0
圆牛排	2.2	214	0.1	32	0.4	2.5	2.4	87	0
烤肋排	3.4	213	0.1	33	0	0	2	0	0
查克烤	3.6	309	0.2	46	0.4	1	4	120	0
盘子	8.5	404	0.2	62	0	0.9	0	0	0
肝脏（牛肉）	2.2	333	0.2	139	169.2	6.4	50.8	316	525
羊腿	3.1	245	0.1	20	0	2.8	3.9	86	0
羊排（肋）	3.3	140	0.1	15	0	1.7	2.7	54	0
猪排	3.5	196	0.2	30	0	17.4	2.7	60	0
猪里脊烤	4.4	249	0.3	37	0	18.2	3.6	79	0
熏肉	10.4	152	0.2	23	0	1.8	1.8	71	0
火腿，烟熏	6.7	212	0.2	31	0	9.9	3.3	50	0
咸猪肉	18.8	164	0.1	26	0	1.4	1.8	0	0
烤鸡	1.8	184	0.1	30	0.1	0.9	1.8	68	46
小牛肉片	1.7	156	0.1	24	0	1.4	2.4	57	0
三文鱼，粉红色（罐装）	5.8	705	6.8	45	3.5	1	4.9	209	0
苹果	5.8	27	0.5	36	7.3	3.6	2.7	5	544
香蕉	4.9	60	0.4	30	17.4	2.5	3.5	28	498
柠檬	1	21	0.5	14	0	0.5	0	4	952
橘子	2.2	40	1.1	18	11.1	3.6	1.3	10	1998
绿豆	2.4	138	3.7	80	69	4.3	5.8	37	862
卷心菜	2.6	125	4	36	7.2	9	4.5	26	5369
萝卜	2.7	73	2.8	43	188.5	6.1	4.3	89	608
芹菜	0.9	51	3	23	0.9	1.4	1.4	9	313
莴苣	0.4	27	1.1	22	112.4	1.8	3.4	11	449
洋葱	5.8	166	3.8	59	16.6	4.7	5.9	21	1184
土豆	14.3	336	1.8	118	6.7	29.4	7.1	198	2522
菠菜	1.1	106	0	138	918.4	5.7	13.8	33	2755
红薯	9.6	138	2.7	54	290.7	8.4	5.4	83	1912
桃子（罐头）	3.7	20	0.4	10	21.5	0.5	1	31	196
梨（罐头）	3	8	0.3	8	0.8	0.8	0.8	5	81
菠萝（罐装）	2.4	16	0.4	8	2	2.8	0.8	7	399
芦笋（罐头）	0.4	33	0.3	12	16.3	1.4	2.1	17	272
绿豆（罐装）	1	54	2	65	53.9	1.6	4.3	32	431
猪肉和豆类（罐头）	7.5	364	4	134	3.5	8.3	7.7	56	0
玉米（罐头）	5.2	136	0.2	16	12	1.6	2.7	42	218
豌豆（罐头）	2.3	136	0.6	45	34.9	4.9	2.5	37	370
西红柿（罐头）	1.3	63	0.7	38	53.2	3.4	2.5	36	1253
番茄汤（罐装）	1.6	71	0.6	43	57.9	3.5	2.4	67	862
桃子，干的	8.5	87	1.7	173	86.8	1.2	4.3	55	57
李子，干的	12.8	99	2.5	154	85.7	3.9	4.3	65	257
葡萄干，干的	13.5	104	2.5	136	4.5	6.3	1.4	24	136
豌豆，干的	20	1367	4.2	345	2.9	28.7	18.4	162	0
利马豆，干的	17.4	1055	3.7	459	5.1	26.9	38.2	93	0
海军豆，干的	26.9	1691	11.4	792	0	38.4	24.6	217	0
咖啡	0	0	0	0	0	4	5.1	50	0
茶	0	0	0	0	0	0	2.3	42	0
可可	8.7	237	3	72	0	2	11.9	40	0
巧克力	8	77	1.3	39	0	0.9	3.4	14	0
糖	34.9	0	0	0	0	0	0	0	0
玉米糖浆	14.7	0	0.5	74	0	0	0	5	0
糖蜜	9	0	10.3	244	0	1.9	7.5	146	0
草莓蜜饯	6.4	11	0.4	7	0.2	0.2	0.4	3	0

中单位已经和 中一致

表示每花买到表中各食物的营养量

2. 准备数据
   将上述数据变成数组，方便读取

nutrients = [
    ['卡路里 (千卡)', 3],
    ['蛋白质 (g)', 70],
    ['钙 (g)', 0.8],
    ['铁 (mg)', 12],
    ['维生素A (KIU)', 5],
    ['维生素B1 (mg)', 1.8],
    ['维生素B2 (mg)', 2.7],
    ['烟酸 (mg)', 18],
    ['维生素C (mg)', 75],
]
data = [['小麦粉（浓缩）', 44.7, 1411, 2.0, 365, 0.0, 55.4, 33.3, 441, 0],
 ['通心粉', 11.6, 418, 0.7, 54, 0.0, 3.2, 1.9, 68, 0],
 ['小麦谷物（浓缩）', 11.8, 377, 14.4, 175, 0.0, 14.4, 8.8, 114, 0],
 ['玉米片', 11.4, 252, 0.1, 56, 0.0, 13.5, 2.3, 68, 0],
 ['棒子面', 36.0, 897, 1.7, 99, 30.9, 17.4, 7.9, 106, 0],
 ['玉米粥', 28.6, 680, 0.8, 80, 0.0, 10.6, 1.6, 110, 0],
 ['米', 21.2, 460, 0.6, 41, 0.0, 2.0, 4.8, 60, 0],
 ['燕麦片', 25.3, 907, 5.1, 341, 0.0, 37.1, 8.9, 64, 0],
 ['白面包（浓缩）', 15.0, 488, 2.5, 115, 0.0, 13.8, 8.5, 126, 0],
 ['全麦面包', 12.2, 484, 2.7, 125, 0.0, 13.9, 6.4, 160, 0],
 ['黑麦面包', 12.4, 439, 1.1, 82, 0.0, 9.9, 3.0, 66, 0],
 ['磅蛋糕', 8.0, 130, 0.4, 31, 18.9, 2.8, 3.0, 17, 0],
 ['苏打饼干', 12.5, 288, 0.5, 50, 0.0, 0.0, 0.0, 0, 0],
 ['牛奶', 6.1, 310, 10.5, 18, 16.8, 4.0, 16.0, 7, 177],
 ['炼乳（罐装）', 8.4, 422, 15.1, 9, 26.0, 3.0, 23.5, 11, 60],
 ['黄油', 10.8, 9, 0.2, 3, 44.2, 0.0, 0.2, 2, 0],
 ['人造黄油', 20.6, 17, 0.6, 6, 55.8, 0.2, 0.0, 0, 0],
 ['蛋', 2.9, 238, 1.0, 52, 18.6, 2.8, 6.5, 1, 0],
 ['奶酪（切达干酪）', 7.4, 448, 16.4, 19, 28.1, 0.8, 10.3, 4, 0],
 ['奶油', 3.5, 49, 1.7, 3, 16.9, 0.6, 2.5, 0, 17],
 ['花生酱', 15.7, 661, 1.0, 48, 0.0, 9.6, 8.1, 471, 0],
 ['蛋黄酱', 8.6, 18, 0.2, 8, 2.7, 0.4, 0.5, 0, 0],
 ['克里斯科', 20.1, 0, 0.0, 0, 0.0, 0.0, 0.0, 0, 0],
 ['猪油', 41.7, 0, 0.0, 0, 0.2, 0.0, 0.5, 5, 0],
 ['沙朗牛排', 2.9, 166, 0.1, 34, 0.2, 2.1, 2.9, 69, 0],
 ['圆牛排', 2.2, 214, 0.1, 32, 0.4, 2.5, 2.4, 87, 0],
 ['烤肋排', 3.4, 213, 0.1, 33, 0.0, 0.0, 2.0, 0, 0],
 ['查克烤', 3.6, 309, 0.2, 46, 0.4, 1.0, 4.0, 120, 0],
 ['盘子', 8.5, 404, 0.2, 62, 0.0, 0.9, 0.0, 0, 0],
 ['肝脏（牛肉）', 2.2, 333, 0.2, 139, 169.2, 6.4, 50.8, 316, 525],
 ['羊腿', 3.1, 245, 0.1, 20, 0.0, 2.8, 3.9, 86, 0],
 ['羊排（肋）', 3.3, 140, 0.1, 15, 0.0, 1.7, 2.7, 54, 0],
 ['猪排', 3.5, 196, 0.2, 30, 0.0, 17.4, 2.7, 60, 0],
 ['猪里脊烤', 4.4, 249, 0.3, 37, 0.0, 18.2, 3.6, 79, 0],
 ['熏肉', 10.4, 152, 0.2, 23, 0.0, 1.8, 1.8, 71, 0],
 ['火腿，烟熏', 6.7, 212, 0.2, 31, 0.0, 9.9, 3.3, 50, 0],
 ['咸猪肉', 18.8, 164, 0.1, 26, 0.0, 1.4, 1.8, 0, 0],
 ['烤鸡', 1.8, 184, 0.1, 30, 0.1, 0.9, 1.8, 68, 46],
 ['小牛肉片', 1.7, 156, 0.1, 24, 0.0, 1.4, 2.4, 57, 0],
 ['三文鱼，粉红色（罐装）', 5.8, 705, 6.8, 45, 3.5, 1.0, 4.9, 209, 0],
 ['苹果', 5.8, 27, 0.5, 36, 7.3, 3.6, 2.7, 5, 544],
 ['香蕉', 4.9, 60, 0.4, 30, 17.4, 2.5, 3.5, 28, 498],
 ['柠檬', 1.0, 21, 0.5, 14, 0.0, 0.5, 0.0, 4, 952],
 ['橘子', 2.2, 40, 1.1, 18, 11.1, 3.6, 1.3, 10, 1998],
 ['绿豆', 2.4, 138, 3.7, 80, 69.0, 4.3, 5.8, 37, 862],
 ['卷心菜', 2.6, 125, 4.0, 36, 7.2, 9.0, 4.5, 26, 5369],
 ['萝卜', 2.7, 73, 2.8, 43, 188.5, 6.1, 4.3, 89, 608],
 ['芹菜', 0.9, 51, 3.0, 23, 0.9, 1.4, 1.4, 9, 313],
 ['莴苣', 0.4, 27, 1.1, 22, 112.4, 1.8, 3.4, 11, 449],
 ['洋葱', 5.8, 166, 3.8, 59, 16.6, 4.7, 5.9, 21, 1184],
 ['土豆', 14.3, 336, 1.8, 118, 6.7, 29.4, 7.1, 198, 2522],
 ['菠菜', 1.1, 106, 0.0, 138, 918.4, 5.7, 13.8, 33, 2755],
 ['红薯', 9.6, 138, 2.7, 54, 290.7, 8.4, 5.4, 83, 1912],
 ['桃子（罐头）', 3.7, 20, 0.4, 10, 21.5, 0.5, 1.0, 31, 196],
 ['梨（罐头）', 3.0, 8, 0.3, 8, 0.8, 0.8, 0.8, 5, 81],
 ['菠萝（罐装）', 2.4, 16, 0.4, 8, 2.0, 2.8, 0.8, 7, 399],
 ['芦笋（罐头）', 0.4, 33, 0.3, 12, 16.3, 1.4, 2.1, 17, 272],
 ['绿豆（罐装）', 1.0, 54, 2.0, 65, 53.9, 1.6, 4.3, 32, 431],
 ['猪肉和豆类（罐头）', 7.5, 364, 4.0, 134, 3.5, 8.3, 7.7, 56, 0],
 ['玉米（罐头）', 5.2, 136, 0.2, 16, 12.0, 1.6, 2.7, 42, 218],
 ['豌豆（罐头）', 2.3, 136, 0.6, 45, 34.9, 4.9, 2.5, 37, 370],
 ['西红柿（罐头）', 1.3, 63, 0.7, 38, 53.2, 3.4, 2.5, 36, 1253],
 ['番茄汤（罐装）', 1.6, 71, 0.6, 43, 57.9, 3.5, 2.4, 67, 862],
 ['桃子，干的', 8.5, 87, 1.7, 173, 86.8, 1.2, 4.3, 55, 57],
 ['李子，干的', 12.8, 99, 2.5, 154, 85.7, 3.9, 4.3, 65, 257],
 ['葡萄干，干的', 13.5, 104, 2.5, 136, 4.5, 6.3, 1.4, 24, 136],
 ['豌豆，干的', 20.0, 1367, 4.2, 345, 2.9, 28.7, 18.4, 162, 0],
 ['利马豆，干的', 17.4, 1055, 3.7, 459, 5.1, 26.9, 38.2, 93, 0],
 ['海军豆，干的', 26.9, 1691, 11.4, 792, 0.0, 38.4, 24.6, 217, 0],
 ['咖啡', 0.0, 0, 0.0, 0, 0.0, 4.0, 5.1, 50, 0],
 ['茶', 0.0, 0, 0.0, 0, 0.0, 0.0, 2.3, 42, 0],
 ['可可', 8.7, 237, 3.0, 72, 0.0, 2.0, 11.9, 40, 0],
 ['巧克力', 8.0, 77, 1.3, 39, 0.0, 0.9, 3.4, 14, 0],
 ['糖', 34.9, 0, 0.0, 0, 0.0, 0.0, 0.0, 0, 0],
 ['玉米糖浆', 14.7, 0, 0.5, 74, 0.0, 0.0, 0.0, 5, 0],
 ['糖蜜', 9.0, 0, 10.3, 244, 0.0, 1.9, 7.5, 146, 0],
 ['草莓蜜饯', 6.4, 11, 0.4, 7, 0.2, 0.2, 0.4, 3, 0]]

3.声明求解器

# 导入 OR-Tools线性求解器包装器， Glop线性求解器的接口
from ortools.linear_solver import pywraplp
# 实例化Glop解算器并命名它，名称可以随便取
solver = pywraplp.Solver('斯蒂格勒饮食问题求解器', pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)

4.创建变量
注意foods变量就是最终需要线性求解器优化的变量，这里只定义每种食物花费的上下限，线性求解器(pywraplp)得到具体的值

# foods表示每种食物所花费的金额(美元)，下限0.0，上限正无穷
foods = [solver.NumVar(0.0, solver.infinity(), item[0]) for item in data]
print('食物种类为 =', solver.NumVariables())

['out']
食物种类为 = 154

5.定义约束
这里解释一下，相当于函数 y = a1x1 + a2x2+...an*xn

下面代码中其中solver.Constraint(content, solver.infinity()) 表示y(每种必须的营养)的摄入范围为content(最少摄入量)到正无穷

const.SetCoefficient(foods[j], item[i + 1]) 表示设置xi的系数为item[i + 1]，也就是说 食物i*某种营养含量i

最终，每种营养在所有食物的总量都必须高于最小摄入量

# 所有食物营养的总和应满足每种营养的最低要求
# SetCoefficient 表示食物营养总和高于nutrient[1]
constraints = []
for i, (name, content) in enumerate(nutrients):
    # 为每种营养设定上下限 下限为人体每天最少补充量，上限为正无穷
    const = solver.Constraint(content, solver.infinity())
    
    # 这里为该营养 在所有食物设定系数(含量),即 每1美元含量1*食物金额(美元)
    # 所有食物中某种营养的摄入量必须高于最小值
    for j, item in enumerate(data):
        const.SetCoefficient(foods[j], item[i + 1]) 

print('约束总量为 =', solver.NumConstraints())

6.创建目标函数

objective = solver.Objective()
for food in foods:
    # 也是添加系数，1*食物i+1*食物2+...+1*食物n=总金额
    objective.SetCoefficient(food, 1)
objective.SetMinimization()

7.输出结果

# 检查问题是否有最佳解决方案
if status != solver.OPTIMAL:
    print('问题没有最优解！')
    if status == solver.FEASIBLE:
        print('找到了一个潜在的次优解决方案。')
    else:
        print('解算器无法解决问题。')
        exit(1)

# 显示每种食物的购买金额（以美元为单位）
# 食品每年的花费
nutrients_result = [0] * len(nutrients)
for i, food in enumerate(foods):
    # 如果该食物花费大于0
    if food.solution_value() > 0.0:
        print(f'{data[i][0]}: ${365. * food.solution_value()}')
        for j, _ in enumerate(nutrients):
            nutrients_result[j] += data[i][j + 1] * food.solution_value()
print(f'\n最优年价格: ${365. * objective.Value()}')
              
              

print('\n每日营养摄入:')
for i, nutrient in enumerate(nutrients):
    print(f'{nutrient[0]}: {nutrients_result[i]} (min {nutrient[1]})')

['out']
小麦粉（浓缩）: $10.774457511918223
肝脏（牛肉）: $0.6907834111074193
卷心菜: $4.093268864842877
菠菜: $1.8277960703546996
海军豆，干的: $22.275425687243036

最优年价格: $39.66173154546625

每日营养摄入:
卡路里 (千卡): 3.000000000000001 (min 3)
蛋白质 (g): 147.41353494220908 (min 70)
钙 (g): 0.8000000000000002 (min 0.8)
铁 (mg): 60.4669221017366 (min 12)
维生素A (KIU): 5.0 (min 5)
维生素B1 (mg): 4.1204388048386225 (min 1.8)
维生素B2 (mg): 2.7000000000000006 (min 2.7)
烟酸 (mg): 27.31598070028833 (min 18)
维生素C (mg): 75.0 (min 75)