标题：解决线性规划中“模型不可行”问题：正确建模物品到类别的分配约束

标题：解决线性规划中“模型不可行”问题：正确建模物品到类别的分配约束第1张

本文详解为何看似正确的类别分配约束仍导致pulp模型判定为不可行，并通过引入最小化最大类别负载的目标函数，提供可解、鲁棒且易于扩展的整数规划建模方案。

在使用PuLP等工具求解“将N个带价格的物品分配至M个有预算上限的类别”问题时，一个常见误区是：仅添加可行性约束而未设置目标函数，或目标函数设计不当，导致求解器无法找到可行解，甚至误判问题本身不可行。您提供的原始代码正是典型情况——虽然约束逻辑（每个物品恰好分入一类、每类总价格不超限）完全正确，但PuLP默认以最大化目标函数求解，而您的模型未调用 model.setObjective()，此时PuLP会尝试最大化零目标（即 0），这在数学上虽合法，却可能触发求解器内部启发式策略失效，尤其当约束边界紧、数值尺度差异大时（如示例中存在 0.0 与超260万的价格），极易返回 Infeasible 状态。

根本原因在于：无目标函数的纯可行性问题，在实际求解中常需依赖求解器的“可行性泵”或辅助变量技巧；而直接赋予一个合理目标，既能引导搜索方向，又能天然规避数值退化风险。推荐采用「最小化所有类别中最大的已分配金额」（min-max）策略——它不仅确保问题必有解（只要总预算 ≥ 总价格），还能均衡负载、提升解的实用性。

以下为优化后的完整实现（基于 pandas + PuLP，结构清晰、数值稳健）：

import pandas as pd
import pulp

def assign_items_to_categories(
    item_prices: pd.Series,
    cat_limits: pd.Series,
) -> tuple[pd.DataFrame, pd.Series]:
    """
    将物品分配至预算受限的类别，最小化最大类别负载（均衡分配）

    Parameters:
    -----------
    item_prices : pd.Series, index=items, values=price
    cat_limits  : pd.Series, index=categories, values=limit

    Returns:
    --------
    assign : pd.DataFrame, shape (n_categories, n_items), binary assignment
    subtotals : pd.Series, index=categories, actual allocated sum per category
    """
    model = pulp.LpProblem("Assign_Items_to_Categories", sense=pulp.LpMinimize)

    # 决策变量：assign[cat, item] = 1 表示 item 分配给 cat
    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 = 所有类别中最大的已分配金额
    tmax = pulp.LpVariable('tmax', lowBound=0, cat=pulp.LpContinuous)

    # 约束1：每个物品必须且只能分配给一个类别
    for item in item_prices.index:
        model.addConstraint(
            pulp.lpSum(assign.loc[:, item]) == 1,
            name=f'excl_{item}'
        )

    # 约束2：每类总价格 ≤ 其预算上限
    # 约束3：每类总价格 ≤ tmax（使 tmax 成为上界）
    subtotals = assign @ item_prices  # 向量化计算每类总和
    for cat in cat_limits.index:
        model.addConstraint(
            subtotals[cat] <= cat_limits[cat],
            name=f'limit_{cat}'
        )
        model.addConstraint(
            subtotals[cat] <= tmax,
            name=f'tmax_{cat}'
        )

    # 目标：最小化 tmax → 即最小化最重负载类别
    model.setObjective(tmax)

    # 求解（建议启用日志查看过程）
    model.solve(pulp.PULP_CBC_CMD(msg=True))
    if model.status != pulp.LpStatusOptimal:
        raise RuntimeError(f"Model unsolved: {pulp.LpStatus[model.status]}")

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

# 示例数据（修复原代码中的拼写错误：cateogory_limit → category_limit）
if __name__ == "__main__":
    prices = pd.Series(
        data=[0.0, 2_616_023.02, 367_419.34, 676_545.32, 228_518.29],
        index=['0892ADA75MH1-00', '3WR21137BHJ81', '3137344ABHEX1',
               '2312312AAWW31-1', '313243A8WTQV1'],
        name='price'
    )

    category_limits = pd.Series(
        data=[2_754_707.42, 43_002.21, 240_301.31, 500_432.54, 3_100_233.41],
        index=['APPLE', 'META', 'TESLA', 'NETFLIX', 'GOOGLE'],
        name='limit'
    )

    assignment, loads = assign_items_to_categories(prices, category_limits)
    print("各品类实际负载：")
    print(loads.round(2))
    print("\n分配矩阵（行=品类，列=物品）：")
    print(assignment.T)  # 转置以便按物品查看归属

关键改进与注意事项：