如何构建最优游泳队阵容？现有贪心算法存短板求方案

问题概述 #

需要构建满足约束条件的游泳队参赛阵容，核心目标是让选中成绩的平均rating最高（等价于总rating最高，因为平均为总rating除以选中数量）。

约束条件 #

• 存在固定的赛事列表，需为每项赛事安排选手
• 每项赛事最多派出 MaxSwimmersPerTeam（记为N）名选手
• 单个选手最多参加 MaxEntriesPerSwimmer（记为M）项赛事
• 已知选手各项目的最佳成绩数据，其中rating字段越高代表成绩越好，可跨赛事比较

示例成绩数据 #

team_1_best_times = [
    {"time_id": 1, "swimmer_id": 1, "event_id": 1, "time": 22.00, "rating": 900.00},
    {"time_id": 2, "swimmer_id": 1, "event_id": 2, "time": 44.00, "rating": 800.00},
    {"time_id": 3, "swimmer_id": 2, "event_id": 1, "time": 22.10, "rating": 890.00},
    {"time_id": 4, "swimmer_id": 2, "event_id": 2, "time": 46.00, "rating": 750.00},
]

贪心算法的局限性 #

当前按rating降序贪心填充的策略存在明显缺陷：
比如当N=1、M=1时，贪心会优先选rating最高的记录（选手1的赛事1，900），剩余只能选选手2的赛事2（750），平均rating为825；但最优分配是选手1的赛事2（800）+选手2的赛事1（890），平均rating可达845，显然更优。

整数规划建模与求解（以Pyomo为例） #

这个问题属于0-1整数规划问题，可以用Pyomo这类运筹学建模工具直接求解，步骤如下：

1. 问题建模 #

• 决策变量：设x[i]为0或1，x[i]=1表示选中第i条成绩记录，x[i]=0则不选
• 目标函数：最大化所有选中记录的rating总和（等价于最大化平均rating）
• 约束条件：
  1. 对每个赛事，选中的选手数量 ≤ N
  2. 对每个选手，选中的赛事数量 ≤ M

2. 代码实现 #

首先安装依赖：

pip install pyomo
conda install -c conda-forge glpk  # 或根据系统配置安装GLPK求解器

实现代码：

from pyomo.environ import ConcreteModel, Var, Objective, ConstraintList, SolverFactory, Binary

# 示例数据
team_1_best_times = [
    {"time_id": 1, "swimmer_id": 1, "event_id": 1, "time": 22.00, "rating": 900.00},
    {"time_id": 2, "swimmer_id": 1, "event_id": 2, "time": 44.00, "rating": 800.00},
    {"time_id": 3, "swimmer_id": 2, "event_id": 1, "time": 22.10, "rating": 890.00},
    {"time_id": 4, "swimmer_id": 2, "event_id": 2, "time": 46.00, "rating": 750.00},
]

# 配置参数
MaxSwimmersPerTeam = 1
MaxEntriesPerSwimmer = 1

# 创建模型实例
model = ConcreteModel()

# 定义0-1决策变量：x[i]表示是否选中第i条记录
model.x = Var(range(len(team_1_best_times)), domain=Binary)

# 目标函数：最大化总rating
def total_rating(model):
    return sum(model.x[i] * team_1_best_times[i]['rating'] for i in range(len(team_1_best_times)))
model.obj = Objective(rule=total_rating, sense='maximize')

# 添加约束条件
model.constraints = ConstraintList()

# 约束1：每项赛事最多派N名选手
event_ids = set(record['event_id'] for record in team_1_best_times)
for event in event_ids:
    model.constraints.add(
        sum(model.x[i] for i in range(len(team_1_best_times)) if team_1_best_times[i]['event_id'] == event) <= MaxSwimmersPerTeam
    )

# 约束2：每个选手最多参加M项赛事
swimmer_ids = set(record['swimmer_id'] for record in team_1_best_times)
for swimmer in swimmer_ids:
    model.constraints.add(
        sum(model.x[i] for i in range(len(team_1_best_times)) if team_1_best_times[i]['swimmer_id'] == swimmer) <= MaxEntriesPerSwimmer
    )

# 调用求解器
solver = SolverFactory('glpk')
result = solver.solve(model)

# 输出结果
print("求解状态：", result.solver.status)
print("最优总rating：", model.obj())
print("选中的参赛记录：")
for i in range(len(team_1_best_times)):
    if model.x[i].value == 1:
        print(f"选手{team_1_best_times[i]['swimmer_id']} - 赛事{team_1_best_times[i]['event_id']}，rating:{team_1_best_times[i]['rating']}")

# 计算平均rating
selected_ratings = [team_1_best_times[i]['rating'] for i in range(len(team_1_best_times)) if model.x[i].value == 1]
avg_rating = sum(selected_ratings) / len(selected_ratings)
print(f"平均rating：{avg_rating:.2f}")

3. 代码说明 #

• 代码中用Binary类型变量确保每个记录只能被选中或不选
• 约束条件分别遍历所有赛事和选手，限制参赛数量
• 求解器采用开源的GLPK，也可以替换为CPLEX、Gurobi等商业求解器（针对大规模数据更高效）

其他工具的适配思路 #

• Gekko：思路与Pyomo一致，通过定义变量、目标函数和约束求解，适合需要动态优化或与其他系统集成的场景
• python-constraint：更适合小型问题，通过定义变量域和约束函数求解，但在大规模数据下效率不如整数规划求解器

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