基于Python Pulp的组间元素频次约束优化问题

核心问题分析 #

原代码的问题集中在变量定义偏差和目标函数逻辑错误：

• 变量命名冲突（person变量误用"group"前缀），且无法体现“人员-组”的关联关系，忽略了同一人员在不同组的得分差异
• 约束条件表述错误（比如lpSum(group) ==2不符合“每组2人”的实际要求）
• 目标函数仅简单累加人员的单一得分，未结合人员所在组的实际得分，完全偏离需求

修正后的完整模型 #

步骤1：重新定义决策变量 #

创建二元变量x[(g, p)]，表示人员p是否被分配到组g，精准对应每个人员在不同组的得分差异。

步骤2：明确约束条件 #

• 每个人员最多被分配到1个组（只能被选中1次）：对每个人员p，所有包含p的组g对应的x[(g,p)]之和 ≤1
• 每个被使用的组必须恰好包含2名人员：对每个组g，所有属于g的人员p对应的x[(g,p)]之和只能是0或2（要么不选该组，要么选满2人）
• 可选：若需固定选择组的数量，可额外添加对应约束（比如强制选2个组）

步骤3：正确构建目标函数 #

总得分是所有被选中的(g,p)组合对应的得分之和，即对每个(g,p)，若x[(g,p)]=1，则累加该组合的score值。

完整代码实现 #

import pandas as pd
import pulp

# 示例数据
data = pd.DataFrame({
    'group': ['A', 'A', 'A', 'A', 'B', 'B', 'B', 'B', 'C', 'C', 'C'],
    'person': [1, 2, 3, 4, 1, 2, 5, 6, 1, 4, 7],
    'score': [3, 1, 0.5, 1, 0.7, 0.8, 1.5, 2, 1.5, 2, 1.1]
})

# 创建最大化问题
prob = pulp.LpProblem("group_scores", sense=pulp.LpMaximize)

# 定义决策变量：x[(g,p)] = 1表示人员p被分配到组g
valid_pairs = list(zip(data['group'], data['person']))
x = pulp.LpVariable.dicts("assignment", valid_pairs, cat=pulp.LpBinary)

# 约束1：每个人员最多被分配到1个组
for p in data['person'].unique():
    relevant_pairs = [pair for pair in valid_pairs if pair[1] == p]
    prob += pulp.lpSum([x[pair] for pair in relevant_pairs]) <= 1, f"person_limit_{p}"

# 约束2：每个组要么不选，要么恰好选2人
for g in data['group'].unique():
    group_pairs = [pair for pair in valid_pairs if pair[0] == g]
    prob += pulp.lpSum([x[pair] for pair in group_pairs]).isin([0, 2]), f"group_size_{g}"

# 可选约束：如果需要固定选择的组数量（比如选2个组）
# selected_groups = pulp.LpVariable.dicts("selected_group", data['group'].unique(), cat=pulp.LpBinary)
# for g in data['group'].unique():
#     group_pairs = [pair for pair in valid_pairs if pair[0] == g]
#     prob += pulp.lpSum([x[pair] for pair in group_pairs]) == 2 * selected_groups[g]
# prob += pulp.lpSum(selected_groups.values()) == 2

# 目标函数：最大化所有选中组合的得分之和
prob += pulp.lpSum([x[pair] * data[(data['group'] == pair[0]) & (data['person'] == pair[1])]['score'].values[0] 
                    for pair in valid_pairs]), "total_score"

# 求解问题
prob.solve()

# 整理结果
results = []
for pair in valid_pairs:
    if x[pair].varValue == 1:
        results.append({
            'group': pair[0],
            'person': pair[1],
            'score': data[(data['group'] == pair[0]) & (data['person'] == pair[1])]['score'].values[0]
        })
results_df = pd.DataFrame(results)
print("选中的人员-组分配：")
print(results_df)
print(f"总得分：{pulp.value(prob.objective)}")

关键说明 #

• 决策变量x[(g,p)]精准捕捉了人员与组的关联，解决了同一人员在不同组得分不同的问题
• 约束条件严格贴合需求：人员唯一分配、组人数合规
• 目标函数直接累加所有有效分配的得分，完全匹配“最大化总组得分”的需求

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