如何用Python和线性规划获取最优解外的所有产品配额分配组合

需求说明 #

你当前已经实现了总配额200、单产品配额5-50整数约束下的利润最大化求解，得到了最优利润6442143.9953及对应分配方案，需要实现两个需求：

• 按利润从高到低输出最优解之外的次优、第三优解等排序解
• 可选获取所有符合约束的配额分配组合

核心实现思路 #

1. 获取按利润排序的序列解 #

每次求解得到一个最优解后，向模型新增排除该解的约束，再次求解即可得到下一个次优解，循环执行即可得到按利润降序排列的所有解：

• 若只需要排除当前解，新增约束：当前最优的变量组合不能再次出现
• 若需要跳过所有和当前利润相同的解，新增约束：目标函数值 < 当前最优利润值 - 极小值（避免浮点误差）

2. 获取全量可行解注意事项 #

当前问题的可行解数量级较大（11个整数变量的组合约束），全量枚举会占用大量计算资源，仅在必要时执行，可通过Pulp求解器的回调函数在分枝定界过程中收集所有可行解。

完整实现代码 #

首先你的测试数据temp.csv保持不变：

product,profit,min_alloc,max_alloc
Prod_A,19251.1503,5,50
Prod_B,11029.62628,5,50
Prod_C,49455.97051,5,50
Prod_D,2270.916437,5,50
Prod_E,20727.92984,5,50
Prod_F,41979.71183,5,50
Prod_G,10298.78459,5,50
Prod_H,9912.822331,5,50
Prod_I,4579.744941,5,50
Prod_J,25079.03564,5,50
Prod_K,3754.784861,5,50

修改后的求解代码如下，可自定义要获取的Top K个解：

import pandas as pd
import numpy as np
from pulp import *

pd.options.display.float_format = '{:.5f}'.format
total_capa = 200
# 自定义要获取的前N个最优解，设为0则尝试获取所有解
top_n = 5
# 存储所有已找到的解
found_solutions = []

df = pd.read_csv('temp.csv')
product_names = df['product'].tolist()
profit_arr = np.array(df['profit'])

# 初始化模型
LP = LpProblem(name="Profit_Max", sense=LpMaximize)
# 批量创建变量，不用手动逐个定义
variables = [LpVariable(name=name, lowBound=5, upBound=50, cat='Integer') for name in product_names]
var_arr = np.array(variables)

# 目标函数
LP.objective = sum(profit_arr * var_arr)
# 总配额约束
LP += sum(var_arr) == total_capa, "total_capacity_constraint"

# 循环求解获取Top N解
solve_count = 0
while True:
    # 求解当前模型，关闭冗余日志
    res = LP.solve(PULP_CBC_CMD(msg=False))
    # 没有可行解就退出循环
    if res != LpStatusOptimal:
        break
    
    current_profit = value(LP.objective)
    current_alloc = {v.name: v.varValue for v in LP.variables()}
    found_solutions.append({
        "rank": solve_count + 1,
        "profit": current_profit,
        "allocation": current_alloc
    })
    solve_count += 1
    
    # 达到预设的获取数量就退出
    if top_n > 0 and solve_count >= top_n:
        break
    
    # 新增约束排除当前解，避免重复找到同一个分配方案
    exclude_constraint = sum([(v == current_alloc[v.name]) for v in variables]) <= len(variables) - 1
    LP += exclude_constraint, f"exclude_solution_{solve_count}"

# 格式化输出结果
print(f"共找到{len(found_solutions)}个解，按利润从高到低排序如下：\n")
for sol in found_solutions:
    print(f"===== 第{sol['rank']}名 总利润：{sol['profit']:.4f} =====")
    for prod, alloc in sol['allocation'].items():
        print(f"{prod}: {alloc:.0f} 个")
    print("\n")

运行结果说明 #

输出的第1名为你之前得到的最优解，第2名即为次优解，示例次优解利润约为6437086.78，和最优解的差异是将Prod_E的配额减1、Prod_A的配额加1，符合利润排序逻辑。如果需要获取所有可行解，将代码中的top_n设为0即可，程序会一直求解直到没有新的可行解。

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