基于Python的有限资源分配利润最大化及可行组合求解咨询

前置依赖 #

首先安装所需工具库：
pip install pandas pulp

该问题属于带上下界约束的整数背包优化问题，所有浮点型数据可直接取整处理，求解逻辑如下： #

步骤1：数据预处理与可行性校验 #

首先读取数据并做基础校验，确认最小分配总量不超过总资源容量：

import pandas as pd
import pulp

# 读取CSV数据
df = pd.read_csv("data.csv")
# 所有浮点型字段转整型
df = df.round().astype(int)
# 总资源容量
total_capa = 700000

# 可行性前置校验：所有产品最小分配量总和不能超过总容量
sum_min_alloc = df["min_alloc(req*0.2)"].sum()
if sum_min_alloc > total_capa:
    print(f"无可行解：所有产品最小分配总量{sum_min_alloc}超过总资源上限{total_capa}")
    exit()

步骤2：最优解求解 #

使用pulp库自带的CBC整数规划求解器求解最大利润对应的分配方案：

# 定义最大化利润的优化问题
prob = pulp.LpProblem("Resource_Allocation", pulp.LpMaximize)

# 定义决策变量：每个产品的分配量，上下界为对应产品的min_alloc和max_alloc，类型为整数
x = pulp.LpVariable.dicts(
    "alloc",
    df.index,
    lowBound=0,
    cat="Integer"
)
for idx in df.index:
    x[idx].lowBound = df.loc[idx, "min_alloc(req*0.2)"]
    x[idx].upBound = df.loc[idx, "max_alloc(req*0.8)"]

# 目标函数：总利润最大化，假设单位资源投入对应产品的利润固定，即单位利润=总利润/申请资源量
prob += pulp.lpSum(
    [(df.loc[idx, "profit"] / df.loc[idx, "request"]) * x[idx] for idx in df.index]
)

# 约束条件：总分配量不超过资源上限
prob += pulp.lpSum([x[idx] for idx in df.index]) <= total_capa

# 求解（关闭日志输出）
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# 输出最优解结果
if pulp.LpStatus[prob.status] == "Optimal":
    df["optimal_alloc"] = [x[idx].varValue for idx in df.index]
    max_total_profit = round(pulp.value(prob.objective))
    print(f"最优解总利润：{max_total_profit}")
    print("最优分配方案：")
    print(df[["product", "optimal_alloc"]].to_string(index=False))
else:
    print("未找到最优解")
    exit()

步骤3：次优解与TOP N高利润方案输出 #

由于31个产品的全量可行解数量极大，不建议全量枚举，可按需输出前N个利润最高的方案：

# 存储所有解的列表，第一个元素为已经求出的最优解
top_solutions = [
    {
        "profit": max_total_profit,
        "allocation": df["optimal_alloc"].tolist()
    }
]
# 自定义需要输出的高利润方案数量，不要设置过大避免运算时间过长
need_top_n = 100

for i in range(1, need_top_n):
    # 添加约束：排除上一轮已经找到的解
    prob += pulp.lpSum(
        [x[idx] == top_solutions[-1]["allocation"][idx] for idx in df.index]
    ) <= len(df) - 1
    # 重新求解
    prob.solve(pulp.PULP_CBC_CMD(msg=0))
    if pulp.LpStatus[prob.status] != "Optimal":
        break
    # 保存当前解
    current_profit = round(pulp.value(prob.objective))
    current_alloc = [x[idx].varValue for idx in df.index]
    top_solutions.append({
        "profit": current_profit,
        "allocation": current_alloc
    })

# 按利润从高到低输出所有找到的方案
for rank, sol in enumerate(top_solutions, start=1):
    print(f"\n===== 第{rank}优方案 总利润：{sol['profit']} =====")
    temp_df = df[["product"]].copy()
    temp_df["alloc_amount"] = sol["allocation"]
    print(temp_df.to_string(index=False))

可选调整说明 #

• 如果不需要分配量为整数，可将决策变量的cat="Integer"改为cat="Continuous"，求解速度会提升数倍
• 如果产品利润的计算规则和默认假设不同，直接修改目标函数中的利润计算逻辑即可
• 若确实需要全量可行解，可结合分支定界逻辑裁剪无效分支，避免全量枚举带来的性能问题

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