本文介绍如何将游泳队 lineup 优化建模为混合整数线性规划（milp）问题，利用 `gekko` 求解器在满足每人最多参赛 m 项、每项最多派 n 人的约束下，最大化全队平均能力评分（rating），克服贪心算法的局部最优缺陷。
在竞技游泳团队排兵布阵中，简单按“个人单项评分（rating）从高到低”贪心填充往往失效——正如示例所示：当 MaxSwimmersPerTeam = 1 且 MaxEntriesPerSwimmer = 1 时，贪心法选 (Swimmer1→Event1, Swimmer2→Event2) 得平均分 825；而全局更优解是 (Swimmer2→Event1, Swimmer1→Event2)，平均分达 845。这本质上是一个带双重容量约束的二分图最大权匹配问题，属于 NP-hard 类别，需借助整数规划建模求解。
✅ 正确建模关键要素
- 决策变量：对每个（泳者, 项目）组合定义二元变量 x[s,e] ∈ {0,1}，表示是否安排该泳者参加该项目；
-
目标函数：最大化总 rating（等价于最大化平均 rating，因事件总数固定）：
model.Maximize(sum(rating[(s,e)] * x[s,e] for s in swimmers for e in events))
-
约束条件：
- 每个项目 e 最多选 N 名泳者：
sum(x[s,e] for s in swimmers) - 每位泳者 s 最多报 M 个项目：
sum(x[s,e] for e in events) - （可选）每个项目至少 1 人（避免空项）：>= 1
- 每个项目 e 最多选 N 名泳者：
⚠️ 注意：原始 gekko 示例中存在两处不严谨之处需修正： ① 目标函数误写为「对每个 event 单独最大化」，实际应全局求和； ② 约束 >=1 和
from gekko import GEKKO
# --- 输入配置 ---
swimmers = ['S1', 'S2', 'S3', 'S4']
events = ['50F', '100F', '200F']
N = 1 # MaxSwimmersPerTeam: 每项最多 N 人
M = 2 # MaxEntriesPerSwimmer: 每人最多 M 项
# rating[(swimmer, event)] = 评分（越高越好）
rating = {
('S1','50F'): 900, ('S1','100F'): 800, ('S1','200F'): 720,
('S2','50F'): 890, ('S2','100F'): 750, ('S2','200F'): 680,
('S3','50F'): 850, ('S3','100F'): 830, ('S3','200F'): 790,
('S4','50F'): 810, ('S4','100F'): 770, ('S4','200F'): 740,
}
# --- 建模 ---
m = GEKKO(remote=False)
x = {}
for s in swimmers:
for e in events:
x[(s,e)] = m.Var(lb=0, ub=1, integer=True)
# 目标：最大化总评分
m.Maximize(m.sum([rating[(s,e)] * x[(s,e)] for s in swimmers for e in events]))
# 约束1：每项最多 N 人
for e in events:
m.Equation(m.sum([x[(s,e)] for s in swimmers]) <= N)
# 约束2：每人最多 M 项
for s in swimmers:
m.Equation(m.sum([x[(s,e)] for e in events]) <= M)
# 求解
m.options.SOLVER = 1 # APOPT 求解器（适合整数问题）
m.solve(disp=False)
# --- 输出结果 ---
print("✅ 最优阵容分配：")
total_rating = 0
count = 0
for s in swimmers:
for e in events:
if x[(s,e)].value[0] > 0.5:
print(f" {s} → {e} (rating={rating[(s,e)]:.0f})")
total_rating += rating[(s,e)]
count += 1
print(f"\n? 总评分：{total_rating:.0f} | 平均评分：{total_rating/count:.1f}")? 实战建议与进阶方向
- 性能权衡：对于 ≤50 泳者 × ≤20 项目的规模，gekko（APOPT）通常在数秒内收敛；超大规模建议切换至 pyomo + gurobi/cplex 或采用列生成（Column Generation）。
- 热启动加速：用贪心解作为初始值（x.var_value = 1），可显著减少分支定界次数。
-
扩展能力：
- 加入接力约束（如 4×100m Free 需 4 人且不可重复）→ 添加 sum(x[s,'Relay']) == 4 及互斥约束；
- 引入疲劳惩罚：若 S1 报 50F 和 100F，则对总分减扣 Δ；
- 多目标优化：在 rating 主目标下，添加最小化总训练负荷为次目标（ε-约束法）。
最终，一个鲁棒的游泳阵容系统不应止步于“谁最快”，而要回答：“在规则与人体极限的夹缝中，如何让团队整体战斗力峰值最高？”——这正是整数规划赋予教练的量化决策力。
