我有以下问题想要解决：
我们有 N 个带有价格和 ID 的商品，以及 M 个类别，其中每个类别 对该类别的商品价格总和有总余额/限制。 最后，我们希望每个项目只分配给一个类别， 并且每个类别不超过其总余额/限制。
让：
限制如下：
每个项目必须准确地分配到一个类别。
分配给每个类别的商品总价不得超过类别限制。
我使用 PuLP python 模块创建了线性编程代码：
def assign_items_to_categories(items, categories, category_limits):
n = len(items)
m = len(categories)
model = pulp.LpProblem("Assign_Items_to_Categories")
# Define decision variables
x = pulp.LpVariable.dicts("x", ((i, j) for i in range(n) for j in range(m)), cat='Binary')
# Constraints
# 1st constraint
for i in range(n):
model += pulp.lpSum(x[(i, j)] for j in range(m)) == 1
# 2nd constraint
for j in range(m):
model += pulp.lpSum(items[i]["price"] * x[(i, j)] for i in range(n)) <= category_limits[categories[j]]
# Solve the problem
model.solve()
model.writeLP('model.lp')
# Extract the solution
assignment_result = {category: [] for category in categories}
for i in range(n):
for j in range(m):
if pulp.value(x[(i, j)]) == 1:
valid = True
assignment_result[categories[j]].append(items[i])
return assignment_result
items = [{
"id": "0892ADA75MH1-00",
"price": 0.0
},
{
"id": "3WR21137BHJ81",
"price": 2616023.02
},
{
"id": "3137344ABHEX1",
"price": 367419.34
},
{
"id": "2312312AAWW31-1",
"price": 676545.32
},
{
"id": "313243A8WTQV1",
"price": 228518.29
}]
categories = ['APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE']
cateogory_limit =
{
"APPLE": 2754707.42,
"META": 43002.21,
"TESLA": 240301.31,
"NETFLIX": 500432.54,
"GOOGLE": 3100233.41,
},
然而，结果总是表明该问题不可行。我相信我编码的约束反映了说明中提到的约束。任何改进此代码的建议都会非常有帮助！
编辑：我添加了一些示例数据以供更好的参考。
最小化类别分配之间差异的一个粗略但快速的目标是最小化最大类别小计。对于极少数的项目，它的效果不是很好；对于许多项目来说，它工作得很好：
import pandas as pd
import pulp
def assign_items_to_categories(
item_prices: pd.Series,
cat_limits: pd.Series,
):
model = pulp.LpProblem(name="Assign_Items_to_Categories", sense=pulp.LpMinimize)
assign = pd.DataFrame(
data=pulp.LpVariable.matrix(
name='assign', cat=pulp.LpBinary,
indices=(cat_limits.index, item_prices.index),
),
index=cat_limits.index,
columns=item_prices.index,
)
tmax = pulp.LpVariable(name='tmax', cat=pulp.LpContinuous)
# Each item must be assigned to exactly one category.
for item, row in assign.items():
model.addConstraint(
name=f'excl_{item}',
constraint=pulp.lpSum(row) == 1,
)
subtotals = assign @ item_prices
for cat, subtotal in subtotals.items():
# The total price sum of items assigned to each category must not exceed the category limit.
model.addConstraint(
name=f'limit_{cat}', constraint=subtotal <= cat_limits[cat])
model.addConstraint(
name=f'tmax_{cat}', constraint=subtotal <= tmax)
model.setObjective(tmax)
model.solve()
if model.status != pulp.LpStatusOptimal:
raise ValueError(model.status)
assign = assign.map(pulp.value)
subtotals = subtotals.apply(pulp.value)
return assign, subtotals
def main() -> None:
prices = pd.Series(
index=pd.Index(
name='item',
data=('0892ADA75MH1-00', '3WR21137BHJ81', '3137344ABHEX1',
'2312312AAWW31-1', '313243A8WTQV1'),
),
name='price',
data=(0.0, 2_616_023.02, 367_419.34, 676_545.32, 228_518.29),
)
cat_limits = pd.Series(
index=pd.Index(
name='category',
data=('APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE'),
),
data=(2_754_707.42, 43_002.21, 240_301.31, 500_432.54, 3_100_233.41),
)
assign, subtotals = assign_items_to_categories(item_prices=prices, cat_limits=cat_limits)
print(subtotals)
print(assign.T)
if __name__ == '__main__':
main()
Result - Optimal solution found
Objective value: 2616023.02000000
Enumerated nodes: 0
Total iterations: 0
Time (CPU seconds): 0.02
Time (Wallclock seconds): 0.02
Option for printingOptions changed from normal to all
Total time (CPU seconds): 0.02 (Wallclock seconds): 0.02
category
APPLE 676545.32
META 0.00
TESLA 228518.29
NETFLIX 367419.34
GOOGLE 2616023.02
dtype: float64
category APPLE META TESLA NETFLIX GOOGLE
item
0892ADA75MH1-00 0.0 0.0 1.0 0.0 0.0
3WR21137BHJ81 0.0 0.0 0.0 0.0 1.0
3137344ABHEX1 0.0 0.0 0.0 1.0 0.0
2312312AAWW31-1 1.0 0.0 0.0 0.0 0.0
313243A8WTQV1 0.0 0.0 1.0 0.0 0.0