本文介绍如何将游泳队 lineup 问题建模为混合整数线性规划（milp），利用 `gekko` 等优化库求解全局最优阵容，在满足每项赛事最多 n 名队员、每人最多参加 m 项赛事的约束下，最大化平均能力评分（rating）。
在竞技游泳团队管理中，科学分配选手参赛项目是提升整体竞争力的关键。简单按个人单项评分贪心排序（如优先选 rating 最高的组合）常导致次优解——正如示例中：贪心法选得 (900 + 750)/2 = 825 的平均分，而交换人选后可达 (890 + 800)/2 = 845。这种“局部最优≠全局最优”的困境，本质是带多重耦合约束的组合优化问题，需借助数学规划方法建模求解。
核心建模思路
我们将问题抽象为一个二元决策变量系统：对每个（swimmer, event）对定义变量 $ x_{s,e} \in {0,1} $，表示该选手是否被安排参加该项目。目标函数与约束条件如下：
目标函数（最大化总评分）：
$$ \max \sum{s \in S} \sum{e \in E} \text{rating}{s,e} \cdot x{s,e} $$ （注意：最大化总分等价于最大化平均分，因总事件数固定）每人参赛上限约束（MaxEntriesPerSwimmer = M）：
$$ \forall s \in S: \quad \sum{e \in E} x{s,e} \leq M $$每项赛事人数上限约束（MaxSwimmersPerTeam = N）：
$$ \forall e \in E: \quad \sum{s \in S} x{s,e} \leq N $$变量类型约束：所有 $ x_{s,e} $ 为 0–1 整数变量。
✅ 提示：若某选手未游过某项目，直接不定义对应变量或设 rating = -∞（实际代码中可跳过该键值对）。
使用 Gekko 实现完整求解流程
以下是一个生产就绪的简化实现（适配您原始数据结构）：
用于管理博客文章的 Blogger API 命令行工具，可发布、编辑、删除、列出和监控 Blogger 博客。适用于用户需要：(1) 在 Blogger 上发布博客文章...
from gekko import GEKKO
import pandas as pd
# 假设原始数据已加载为列表
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},
]
# 构建映射：(swimmer_id, event_id) → rating
rating_map = {}
swimmers = set()
events = set()
for rec in team_1_best_times:
sid, eid = rec["swimmer_id"], rec["event_id"]
swimmers.add(sid)
events.add(eid)
rating_map[(sid, eid)] = rec["rating"]
# 初始化模型
m = GEKKO(remote=False)
m.options.SOLVER = 1 # APOPT 求解器，支持整数规划
# 定义二元变量：x[sid, eid]
x = {}
for sid in swimmers:
for eid in events:
if (sid, eid) in rating_map:
x[(sid, eid)] = m.Var(lb=0, ub=1, integer=True)
else:
# 未参赛项目，不参与优化
continue
# 目标：最大化总 rating
total_rating = sum(rating_map[(sid, eid)] * x[(sid, eid)]
for (sid, eid) in rating_map.keys())
m.Maximize(total_rating)
# 约束：每人最多参加 M 项（示例设 M=1）
M = 1
for sid in swimmers:
m.Equation(sum(x.get((sid, eid), 0) for eid in events) <= M)
# 约束：每项最多 N 名选手（示例设 N=1）
N = 1
for eid in events:
m.Equation(sum(x.get((sid, eid), 0) for sid in swimmers) <= N)
# 求解
m.solve(disp=False)
# 输出结果
print("✅ 最优阵容（swimmer_id → event_id）:")
for (sid, eid), var in x.items():
if var.value[0] > 0.5:
print(f" Swimmer {sid} → Event {eid} (rating={rating_map[(sid,eid)]:.0f})")
# 计算平均评分
selected_ratings = [rating_map[(sid, eid)] for (sid, eid), var in x.items() if var.value[0] > 0.5]
avg_rating = sum(selected_ratings) / len(selected_ratings) if selected_ratings else 0
print(f"\n? 平均 rating = {avg_rating:.1f}")运行此代码将输出：
✅ 最优阵容（swimmer_id → event_id）: Swimmer 1 → Event 2 (rating=800) Swimmer 2 → Event 1 (rating=890) ? 平均 rating = 845.0
完美复现了“聪明教练”的选择。
注意事项与进阶建议
- 数据预处理关键：确保 rating 具有跨项目可比性（如使用 Z-score 标准化、或基于世界泳联积分公式转换），否则优化结果将失真。
- 扩展性提示：当 |swimmers| × |events| > 10⁴ 时，纯 MILP 可能变慢；此时可结合启发式初始化（如贪心解作为 warm-start）或采用列生成（Column Generation） 或 强化学习调度器。
-
现实约束增强：可轻松加入：
- 体能恢复约束（如 Event2 在 Event1 后 30 分钟内禁止同一人参赛）；
- 接力项目协同约束（如 4×100 Free 需 4 名不同选手且均报过自由泳）；
- 教练偏好权重（对特定组合乘以系数）。
-
替代工具推荐：
- 小规模（<500 变量）：PuLP（语法更直观）、ortools（Google 开源，性能优异）；
- 大规模/非线性：Pyomo + CBC/Gurobi；
- 无需安装求解器：ortools 自带开源求解器，部署友好。
最终，从贪心到规划，不仅是算法升级，更是决策范式的转变——它让排兵布阵从经验驱动走向数据驱动，让每一毫秒潜力都被精准释放。
