非线性约束的优化问题
我是优化问题的新手，正在研究一个简单的最大化问题，我可以在 Excel 中非常简单地解决这个问题。但是，我需要在 Python 中扩展它并需要一些帮助。
我有一份不同食物的菜单，我需要最大限度地提高我的能量输出。例子：
| 宏 | 食物 | 卡路里 | 活力 |
|---|---|---|---|
| 蛋白质 | 鱼 | 100 | 60 |
| 蛋白质 | 羊肉 | 200 | 40 |
| 蛋白质 | 蛋 | 200 | 38 |
| 碳水化合物 | 香蕉 | 200 | 25 |
| 碳水化合物 | 土豆 | 200 | 30 |
| 碳水化合物 | 米 | 200 | 40 |
| 胖的 | 牛油果 | 450 | 50 |
| 胖的 | 奶酪 | 400 | 60 |
| 胖的 | 奶油 | 500 | 55 |
回答
正如您已经提到的，scipy.optimize.minimize无法处理混合整数问题 (MIP)。最多可以做的是尝试通过惩罚方法来解决 MIP，即向目标添加一个惩罚函数，例如1.0/eps * np.sum(x*(1 - x))，其中eps > 0是给定的惩罚参数和xa np.ndarray。
但是，使用 MIP 求解器解决问题要方便得多。由于您的问题具有众所周知的类似背包的结构，因此您甚至可以期待非商业 MIP 求解器（PuLp 默认使用 CBC）来利用您问题的底层结构。在这里，我推荐以下公式：
Binary variables:
x[i] = 1 if fooditem i is chosen, 0 otherwise
Parameters:
a[i][m] = 1 if fooditem i covers macro m, 0 otherwise
c[i] calories for fooditem i
e[i] energy for fooditem i
N total calories limit
Model:
max ? (e[i] * a[i][m] * x[i], ? i ? Fooditems, m ? Macros)
s.t. ? (a[i][m] * x[i], ? i ? Fooditems) <= 1 ? m ? Macros. (1)
? (c[i] * x[i], ? i ? Fooditems) <= N (2)
可以像这样建模和解决：
import pulp
fooditems = {
'Fish': {'macro': 'Protein', 'calorie': 100, 'energy': 60},
'Lamb': {'macro': 'Protein', 'calorie': 200, 'energy': 40},
'Egg': {'macro': 'Protein', 'calorie': 200, 'energy': 38},
'Banana': {'macro': 'Carbs', 'calorie': 200, 'energy': 25},
'Potato': {'macro': 'Carbs', 'calorie': 200, 'energy': 30},
'Rice': {'macro': 'Carbs', 'calorie': 200, 'energy': 40},
'Avocado': {'macro': 'Fat', 'calorie': 450, 'energy': 50},
'Cheese': {'macro': 'Fat', 'calorie': 400, 'energy': 60},
'Cream': {'macro': 'Fat', 'calorie': 500, 'energy': 55},
}
# parameters
macros = list({fooditems[i]['macro'] for i in fooditems})
a = {item: {m: 1 if m == fooditems[item]['macro']
else 0 for m in macros} for item in fooditems}
c = {item: fooditems[item]['calorie'] for item in fooditems}
e = {item: fooditems[item]['energy'] for item in fooditems}
N = 1000
# pulp model
mdl = pulp.LpProblem("bla", pulp.LpMaximize)
# binary variables
x = pulp.LpVariable.dicts("x", fooditems, cat="Binary")
# objective
mdl += pulp.lpSum([e[i] * a[i][m] * x[i] for m in macros for i in fooditems])
# constraints (1)
for m in macros:
mdl += (pulp.lpSum([a[i][m]*x[i] for i in fooditems]) <= 1)
# constraints (2)
mdl += (pulp.lpSum([x[i]*c[i] for i in fooditems]) <= N)
# solve the problem
mdl.solve()
print(f"Status: {pulp.LpStatus[mdl.status]}")
for var in mdl.variables():
print(f"{var.name} = {var.varValue:.0f}")
print(f"energy: {mdl.objective.value()}")
这产生
Status: Optimal
x_Avocado = 0.0
x_Banana = 0.0
x_Cheese = 1.0
x_Cream = 0.0
x_Egg = 0.0
x_Fish = 1.0
x_Lamb = 0.0
x_Potato = 0.0
x_Rice = 1.0
Energy: 160.0