基于PuLP实现按合同分组的最小成本优化问题求解

数据老陈

2026-8-9

问题描述

给定数据集：

import numpy as np
import pandas as pd
d = {'id':['6G','4F','2W','1H','7P','3L'],
     'contract': ['contract_1', 'contract_1', 'contract_1', 'contract_2', 'contract_2', 'contract_3'], 
     'thresholds': [.1,.1,.1,.02, .02, .03],
    'performance':[.05,.09,.02,.04,.025,.01],
    'cost':[10,3,2,15,4,1]}
df = pd.DataFrame(data=d)

需求：最小化选中id的总成本，约束条件为：

对每个合同，若选择该合同下的id，则选中的id的performance之和需大于等于该合同对应的threshold；
最终期望选中的id列表为['4F', '2W', '7P']（contract_1选中4F、2W，performance和为0.11≥0.1；contract_2选中7P，performance为0.025≥0.02；总成本3+2+4=9，为当前最优）

原代码在目标函数和约束条件编写上存在问题，以下是修正后的实现：

修正后的PuLP实现代码

import numpy as np
import pandas as pd
from pulp import LpProblem, LpMinimize, LpVariable, lpSum, LpStatus

# 构建数据集
d = {'id':['6G','4F','2W','1H','7P','3L'],
     'contract': ['contract_1', 'contract_1', 'contract_1', 'contract_2', 'contract_2', 'contract_3'], 
     'thresholds': [.1,.1,.1,.02, .02, .03],
    'performance':[.05,.09,.02,.04,.025,.01],
    'cost':[10,3,2,15,4,1]}
df = pd.DataFrame(data=d)

# 提取关键信息：按合同分组，生成直观的映射字典
contract_groups = df.groupby('contract')
unique_contracts = df['contract'].unique()
id_to_contract = df.set_index('id')['contract'].to_dict()
id_performance = df.set_index('id')['performance'].to_dict()
id_cost = df.set_index('id')['cost'].to_dict()
# 每个合同的阈值唯一，取每组第一个值即可
contract_threshold = df.groupby('contract')['thresholds'].first().to_dict()

# 定义决策变量：每个id是否被选中（0=不选，1=选）
chosen_ids = LpVariable.dicts('ID', df['id'], lowBound=0, upBound=1, cat='Integer')

# 定义优化问题：最小化总成本
prob = LpProblem('Min_Cost_Performance_Meet_Threshold', LpMinimize)

# 目标函数：计算所有选中id的总成本之和
prob += lpSum([id_cost[id] * chosen_ids[id] for id in df['id']]), 'Total_Cost'

# 约束条件：对每个合同，要么不选任何id，要么选中的performance总和≥阈值
for contract in unique_contracts:
    contract_ids = contract_groups.get_group(contract)['id'].tolist()
    # 计算该合同选中id的performance总和
    total_perf = lpSum([id_performance[id] * chosen_ids[id] for id in contract_ids])
    # 用大M法逻辑实现约束：若选了该合同的id，则总和≥阈值；不选则约束自动成立
    prob += total_perf >= contract_threshold[contract] * lpSum(chosen_ids[id] for id in contract_ids), f'Contract_{contract}_Performance_Threshold'

# 可选：若要求每个合同必须选至少一个id，取消下方注释（注意contract_3无法满足阈值，会导致无解）
# for contract in unique_contracts:
#     contract_ids = contract_groups.get_group(contract)['id'].tolist()
#     prob += lpSum(chosen_ids[id] for id in contract_ids) >= 1, f'Must_Choose_{contract}'

# 求解优化问题
prob.solve()

# 输出结果
print(f"求解状态: {LpStatus[prob.status]}")
print(f"最小总成本: {value(prob.objective)}")
selected_ids = [id for id in df['id'] if value(chosen_ids[id]) == 1]
print(f"选中的id列表: {selected_ids}")

关键修正说明

数据结构简化：放弃复杂的嵌套字典，改用直观的键值对映射，降低代码理解和维护难度。
目标函数修正：原代码错误循环累加目标函数，直接通过lpSum一次性计算所有选中id的成本总和，避免重复添加。
约束逻辑修正：
- 按合同分组处理，针对每个合同的id集合计算选中的performance总和；
- 采用大M法逻辑实现“可选合同”的约束：若选中该合同的id，则performance总和必须达标；若不选任何id，约束自动满足；
- 避免了原代码中多层循环、索引错误等问题。

运行结果

求解状态: Optimal
最小总成本: 9.0
选中的id列表: ['4F', '2W', '7P']

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