斯蒂格勒饮食问题(The Stigler diet Problem),给定人类一天所必须摄入的营养 和 每种食物的营养,求出在花费最小的情况下满足人一天的营养需求。
- 数据说明
①人体每天必须摄入的营养表
营养种类 | 最低摄入量 |
---|---|
卡路里 (千卡) | 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 |
中单位已经和 中一致
表示每花买到表中各食物的营养量
- 准备数据
将上述数据变成数组,方便读取
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)