讲师中心 微信公众号

工具推荐

视频效率加速
AniShort
AniShort

AI短剧协同制作平台

Laper
Laper

剧本策划到成片协作

立刻MV
立刻MV

低成本歌曲 MV、视频生成

updream

一键生成高质量推广成片

如何用混合整数规划(MIP)优化游泳队阵容分配

风磊姑娘_6590

风磊姑娘_6590

发布时间:2026-01-19 19:00:35

|

981人浏览过

|

来源于php中文网

原创

如何用混合整数规划(MIP)优化游泳队阵容分配

本文介绍如何将游泳队 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
⚠️ 注意:原始 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 主目标下,添加最小化总训练负荷为次目标(ε-约束法)。

最终,一个鲁棒的游泳阵容系统不应止步于“谁最快”,而要回答:“在规则与人体极限的夹缝中,如何让团队整体战斗力峰值最高?”——这正是整数规划赋予教练的量化决策力。

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热门AI工具

更多
蛙蛙写作

一款AI论文写作工具,主要用于超级AI智能写作助手,适合需要提升相关任务效率的用户。

咔片AIPPT

一款在线AI演示文稿制作工具,可根据主题和内容需求辅助生成PPT结构与页面,提高演示材料制作效率。

Seko
Seko Hot

一款AI视频创作工具,主要用于商汤科技推出的创编一体的AI短视频创作Agent,适合需要提升相关任务效率的用户。

小橡皮AI

一款AI工具,主要用于小橡皮一键去AI味,将机器味重的内容改得更有活人感,防止因为 AI 内容被平台打上 AI 标签,以及限流,适合需要提升相关任务效率的用户。

Lovart
Lovart Hot

一款面向视觉设计创作的AI设计平台,可通过智能体和画布工作流辅助制作海报、Logo、网页、PPT及其他视觉内容。

Flowith
Flowith Hot

Flowith是一款基于画布和智能体工作流的 AI 协作工作空间。

DeepSeek

DeepSeek是一款面向对话、写作、编程和推理场景的AI大模型工具。

WorkBuddy

一款AI办公效率工具,主要用于腾讯云推出的AI原生桌面智能体工作台,适合需要提升相关任务效率的用户。

豆包大模型

豆包大模型是一款由字节跳动推出的企业级大语言模型服务平台。

相关专题

更多
页面置换算法
页面置换算法

页面置换算法是操作系统中用来决定在内存中哪些页面应该被换出以便为新的页面提供空间的算法。本专题为大家提供页面置换算法的相关文章,大家可以免费体验。

7416

2023.08.14

Nginx CVE-2026-123007排查与防护指南
Nginx CVE-2026-123007排查与防护指南

Nginx HTTP/2漏洞该怎么修复?本专题围绕CVE-2026-123007,介绍安全版本升级、模块兼容检查和配置恢复方法,以及日志排查、权限设置等后续加固操作,方便你按实际部署情况查找对应教程。

0

2026.11.20

GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

20

2026.11.17

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

60

2026.11.17

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

80

2026.11.17

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

20

2026.11.17

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

80

2026.11.17

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

40

2026.11.17

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

180

2026.11.12

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
关于我们 免责申明 举报中心 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号
PHP中文网订阅号
每天精选资源文章推送

Copyright 2014-2026 https://www.php.cn/ All Rights Reserved | php.cn