约束逻辑正确但PuLP分配模型仍不可行，求优化建议

问题描述 #

现有N个带价格和ID的商品，M个类别，每个类别对分配给它的商品总价有上限要求。需将每个商品仅分配至一个类别，且所有类别总价不超上限。

变量定义 #

• x_ij：0-1决策变量，x_ij=1表示商品i分配至类别j，否则为0；
• p_i：商品i的价格；
• c_j：类别j的价格上限。

约束条件 #

1. 每个商品必须被分配至恰好一个类别；
2. 每个类别分配到的商品总价不得超过其上限。

以下针对代码运行后模型始终不可行的问题，给出排查与优化建议：

问题排查 #

1. 代码拼写错误 #

原代码存在变量名拼写错误与语法问题：

cateogory_limit = 
        {
            "APPLE": 2754707.42,
            "META": 43002.21,
            "TESLA": 240301.31,
            "NETFLIX": 500432.54,
            "GOOGLE": 3100233.41,
        },

• 变量名cateogory_limit应为category_limits（少写一个字母r）；
• 变量定义末尾多余的逗号会导致语法错误，调用函数时参数无法匹配。

2. 示例数据本身不可行 #

观察示例数据的商品价格与类别上限：

• 商品3WR21137BHJ81价格2616023.02，仅能分配给APPLE或GOOGLE；
• 商品2312312AAWW31-1价格676545.32，仅APPLE和GOOGLE上限高于该价格，但APPLE容纳第一个高价商品后剩余额度为138684.4，不足以容纳此商品；
• 商品3137344ABHEX1价格367419.34，同样仅GOOGLE能容纳；
• 多个高价商品叠加后，GOOGLE的上限3100233.41远不足以覆盖总和，导致无可行分配方案。

代码优化建议 #

修正后的完整代码 #

import pulp

def assign_items_to_categories(items, categories, category_limits):
    n = len(items)
    m = len(categories)
    # 明确问题类型（可行性问题设为LpMinimize即可）
    model = pulp.LpProblem("Assign_Items_to_Categories", pulp.LpMinimize)

    # 定义0-1决策变量
    x = pulp.LpVariable.dicts("x", ((i, j) for i in range(n) for j in range(m)), cat='Binary')

    # 约束1：每个商品必须分配至恰好一个类别
    for i in range(n):
        model += pulp.lpSum(x[(i, j)] for j in range(m)) == 1, f"Item_{i}_Must_Assign"
    
    # 约束2：每个类别总价不超过上限
    for j in range(m):
        model += pulp.lpSum(items[i]["price"] * x[(i, j)] for i in range(n)) <= category_limits[categories[j]], f"Category_{categories[j]}_Limit"

    # 可行性问题设置目标函数为0
    model += 0, "Feasibility_Objective"

    # 求解（关闭日志输出）
    model.solve(pulp.PULP_CBC_CMD(msg=0))
    
    # 输出求解状态
    print(f"求解状态: {pulp.LpStatus[model.status]}")

    # 提取结果（仅当求解成功时）
    assignment_result = {category: [] for category in categories}
    if pulp.LpStatus[model.status] == "Optimal":
        for i in range(n):
            for j in range(m):
                if pulp.value(x[(i, j)]) == 1:
                    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']
category_limits = {
    "APPLE": 2754707.42,
    "META": 43002.21,
    "TESLA": 240301.31,
    "NETFLIX": 500432.54,
    "GOOGLE": 3100233.41,
}

# 调用函数
result = assign_items_to_categories(items, categories, category_limits)
print(result)

额外优化点 #

1. 明确问题类型：PuLP需指定最小化/最大化，可行性问题设目标函数为0即可；
2. 添加约束名称：便于后续排查不可行约束的具体来源；
3. 状态判断：提取结果前先判断求解状态，避免无效操作；
4. 日志控制：使用msg=0关闭求解器日志，保持控制台整洁。

数据调整建议 #

若要让示例数据可行，可调整以下内容：

• 提高GOOGLE的上限至4000000.0以上；
• 拆分高价商品（业务允许的前提下）；
• 新增高上限类别。

内容的提问来源于stack exchange，提问作者Christopher Bryan