带容量约束的物品分配解决技巧

本文直击PuLP建模中一个高频却易被忽视的痛点：明明约束逻辑合理、数据看似可行，模型却报“Infeasible”——根源往往不在业务逻辑，而在于目标函数缺失或约束索引错误等技术细节；文章以真实案例切入，揭示单个高价物品超出所有类别限额的隐性瓶颈，并手把手演示如何通过引入辅助变量、重构目标函数（如最小化未分配成本）将不可行的纯约束问题转化为稳健可解的优化模型，附带可直接运行的修复代码，助你快速定位并解决分配类建模中的“假不可行”困局。

本文详解为何看似正确的多类别物品分配模型在PuLP中报“Infeasible”，并提供可运行的修复方案——通过引入辅助变量与合理目标函数，将纯可行性问题转化为可解优化问题。

在使用PuLP等线性规划求解器建模“物品→类别”的单一分配问题时，一个常见却令人困惑的现象是：即使约束逻辑正确、数据看起来可行，求解器仍返回 Infeasible（不可行）。根本原因在于：纯约束系统（无目标函数）或目标函数设计不当，可能导致求解器无法启动搜索，或隐含矛盾未被显式暴露。

以您提供的案例为例，5个物品需分配至5个类别，每个类别有价格上限。表面看总物品价格为：

0.0 + 2,616,023.02 + 367,419.34 + 676,545.32 + 228,518.29 = 3,888,505.97

而所有类别限额总和为：

2,754,707.42 + 43,002.21 + 240,301.31 + 500,432.54 + 3,100,233.41 = 6,638,676.89

总限额远超总需求，但单个大额物品（如 3WR21137BHJ81，价格 ≈261.6万）可能无法放入任何满足限额的类别。检查限额：

• META: 43,002.21 → ❌ 太小
• TESLA: 240,301.31 → ❌ 太小
• NETFLIX: 500,432.54 → ✅ 可容纳？但 261.6万 > 50万 → ❌
• APPLE: 2,754,707.42 → ✅（261.6万 < 275.5万）
• GOOGLE: 3,100,233.41 → ✅

→ 看似 APPLE 或 GOOGLE 可容纳该物品。但问题出在：您的原始代码中，第二类约束的索引存在严重错误：

# ❌ 错误写法（原代码）：
for j in range(m):
    model += pulp.lpSum(items[i]["price"] * x[(i, j)] for i in range(n)) <= category_limits[categories[j]]

这里 categories[j] 是字符串（如 "APPLE"），但 category_limits 字典键名拼写为 cateogory_limit（少了一个 r！），且变量名不一致。更关键的是：若字典键名与 categories[j] 不完全匹配（大小写、空格、拼写），category_limits[categories[j]] 将抛出 KeyError；而若静默失败（如用了 .get() 返回 None），约束会变成 <= None，导致模型结构损坏，最终被判定为不可行。

✅ 正确做法是：明确建模 + 添加有意义的目标函数。纯可行性问题（Feasibility Problem）在PuLP中并非首选模式；求解器更擅长优化目标。因此，我们采用「最小化最大负载」策略——即让最“满”的类别尽可能轻，既提升求解鲁棒性，又自然导向可行解（若存在）：

import pandas as pd
import pulp

def assign_items_to_categories(item_prices: pd.Series, cat_limits: pd.Series):
    model = pulp.LpProblem("Assign_Items_to_Categories", sense=pulp.LpMinimize)

    # 二元分配矩阵：rows=categories, cols=items
    assign = pd.DataFrame(
        data=pulp.LpVariable.matrix('assign', cat=pulp.LpBinary,
                                   indices=(cat_limits.index, item_prices.index)),
        index=cat_limits.index,
        columns=item_prices.index
    )

    # 辅助连续变量：表示所有类别中最大的分配总额
    tmax = pulp.LpVariable('tmax', cat=pulp.LpContinuous)

    # 【约束1】每个物品必须分配到且仅到一个类别
    for item in item_prices.index:
        model += pulp.lpSum(assign.loc[:, item]) == 1, f"excl_{item}"

    # 【约束2】每个类别总额 ≤ 其限额
    # 【约束3】每个类别总额 ≤ tmax（推动最小化最大值）
    subtotals = assign @ item_prices  # 向量化计算各品类总额
    for cat in cat_limits.index:
        model += subtotals[cat] <= cat_limits[cat], f"limit_{cat}"
        model += subtotals[cat] <= tmax, f"tmax_{cat}"

    # 【目标】最小化最大类别总额（tmax）
    model.setObjective(tmax)

    model.solve(pulp.PULP_CBC_CMD(msg=1))  # 推荐显式指定求解器
    if model.status != pulp.LpStatusOptimal:
        raise RuntimeError(f"Model unsolved: {pulp.LpStatus[model.status]}")

    # 提取结果
    assignment_df = assign.map(pulp.value).round().astype(int)
    subtotals_series = subtotals.apply(pulp.value)
    return assignment_df, subtotals_series

# 示例数据（修正拼写与结构）
prices = pd.Series(
    data=[0.0, 2616023.02, 367419.34, 676545.32, 228518.29],
    index=['0892ADA75MH1-00', '3WR21137BHJ81', '3137344ABHEX1', '2312312AAWW31-1', '313243A8WTQV1']
)

cat_limits = pd.Series(
    data=[2754707.42, 43002.21, 240301.31, 500432.54, 3100233.41],
    index=['APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE']
)

assign, subtotals = assign_items_to_categories(prices, cat_limits)
print("各品类分配总额：\n", subtotals.round(2))
print("\n分配矩阵（行=品类，列=物品）：\n", assign.T)

? 关键改进点总结：

• ✅ 使用 pd.Series 统一管理数据，避免索引错位与字典键名拼写错误；
• ✅ 引入 tmax 辅助变量，将可行性问题转化为有明确目标的优化问题；
• ✅ 用 pulp.LpVariable.matrix 和 @ 运算符实现向量化建模，大幅提升可读性与健壮性；
• ✅ 显式检查 model.status 并抛出清晰异常，避免静默失败；
• ✅ 所有约束命名（如 f"excl_{item}"）便于调试时定位LP文件中的具体约束。

? 进阶提示：若仍遇不可行，可调用 model.writeLP("debug.lp") 查看生成的 .lp 文件，人工验证约束是否符合预期；或启用 pulp.PULP_CBC_CMD(msg=1) 输出求解日志，观察松弛变量或不可行核心（IIS）。对于大规模问题，还可考虑添加软约束（如允许少量超限并施加惩罚）提升实用性。

该方法不仅修复了原始不可行问题，更构建了一种可扩展、易调试、生产就绪的资源分配建模范式。

好了，本文到此结束，带大家了解了《带容量约束的物品分配解决技巧》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多文章知识！