python分配问题_组队、路径分配问题建模案例✕Gurobi应⽤
python3实现
1 前⾔
本⽂以两道经典建模题为例, 进⼀步介绍 Gurobi 与 Python 的交互, 以及其在建模中的应⽤. 阅读本⽂前, 建议读者先配置好 Gurobi 环境，并且对数学建模有⼀定的认识 (吹⽔, 不考虑绝对的严谨性)。
本⽂也可作为建模⼩⽩的“⼊门指南”, 全⽂都是按照我的思维过程进⾏书写, (笔者在建模中承担建模 + 编程 + 模型主框架书写任务, 会将⾃⼰的模型以朴素的语⾔告知队友) ⼩⽩可以放⼼⾷⽤, 感受完成⼀道建模题所需要进⾏的分析⼯作.
2 Problem 1 最佳组队安排问题 (出处不详)
2.1 问题描述
在⼀年⼀度的我国和美国⼤学⽣数学建模竞赛活动中, 任何⼀个参赛院校都会遇到如何选拔最优秀的队员和科学合理地组队问题, 这是⼀个最实际的、⽽且⾸先需要解决的数学模型问题.
现假设有 20 名队员准备参加竞争, 根据队员的能⼒和⽔平要选出 18 名优秀队员分别组成 6 个队, 每个队 3 名队员去参加⽐赛. 选择队员主要考虑的条件依次为有关学科成绩(平均成绩)、智⼒⽔平(反映思维能⼒、分析问题和解决问题的能⼒等)、动⼿能⼒(计算机的使⽤和其他⽅⾯实际操作能⼒)、写作能⼒、外语能⼒、协作能⼒(团结协作能⼒)和其他特长. 每个队员的基本条件量化后如下表所⽰:
假设所有队员接受了同样的培训, 外部环境相同, 竞赛中不考虑其他的随机因素, 竞赛⽔平的发挥只取决于表中所给的各项条件, 并且参赛队员都能正常发挥⾃⼰的⽔平. 现在的问题是:
(1) 如何在20名队员中选拔18名优秀队员参加竞赛;
(2) 给出由18名队员组成6个队的组队⽅案, 使整体竞赛技术⽔平最⾼，并给出每个队的竞赛技术⽔平;
(3) 如果有更多的学⽣报名参加, 你的模型是否仍然可⾏?
2.2 问题分析
建模组队问题是经典的团队分⼯与总效益评估问题. ⼀般来说, 数学建模竞赛中的队员应该⾄少包含三项技能: 擅长⽂字写作与论⽂排版、灵活运⽤的算法思想与编程能⼒、优秀的数学基础与建模能⼒, ⼀般的分配就是三位同学各有专长. 这样的分配对于校⽅⽽⾔更有利于针对不同⼯作的学⽣进⾏集中培训, 避免资源浪费; 对于建模团队⽽⾔, 每位同学发挥⾃⼰的长处, 合作完成⼀篇建模论⽂也是⼤有裨益
的.笔者实践经验认为, 优秀的建模团队应该是每位队员都能独⽴地完成⼀道建模题⽬, 具备独⽴解决问题的基本技能, 在建模⼯作中相互渗透, 队员各有所长, 这有助于团队的协调分⼯、减少沟通成本.
但这样的队员可遇不可求, 退⽽求其次, 能做好⾃⼰的本职⼯作、具有较好的团队合作能⼒即可.
搜索资料容易查到武汉理⼯⼤学2019年美国⼤学⽣数学建模竞赛选拔, 可以作为参考. 建模队员的选拔, 往往根据不同的职位, 有不同的能⼒考察. ⽐如说编程的同学可能需要考虑算法功底、编程软件使⽤、动⼿实践能⼒、项⽬经验、智⼒⽔平等, 这也启发我们, 对于学⽣能⼒的评估, 不能⽤统⼀的评价体系⼀锅端. 我们要解决的第⼀个问题就是怎么选拔出适合从事单项⼯作的同学. 选拔出从事单项⼯作的队员后, 下⼀步要解决的问题就是如何进⾏组队.计算⽅差, 让总体实⼒均衡? 计算平均数, 让总体能⼒均值最⾼? 似乎都可⾏, 但是联想到⾼中的时候开设的⽕箭班 (尖⼦班), 校⽅的考量应该是让优秀的同学冲刺更⾼的奖项 (更好的⼤学), 中间的学⽣尽可能拿奖 (不那么差的学校). 因此就涉及到第三个问题, 如何衡量⼀只队伍获奖的潜⼒.
基于以上分析, 解决该问题的思路为:
评价各个学⽣适合分别从事三项⼯作的得分值 -> 将学⽣进⾏⼯作分队 -> 建⽴获奖潜⼒评估模型 -> 组队安排, 让获奖的总效益最⼤化当然，注意到题⽬说的 “任何⼀个参赛院校都会遇到如何选拔最优秀的队员和科学合理地组队问题”, 以及第三问要求分析更多学⽣时的编排策略，在建模中不应过早地将模
型局限在 20 ⼈选 6 只队伍上. ⽽应该建⽴⼀个普适性较强的模型. 再以20位同学的数据进⾏应⽤, 分析结论.
2.3 基本假设
(1) 学校通过对学⽣三种不同的能⼒评估 (定义为建模能⼒, 编程能⼒, 写作能⼒), 确定学⽣适合进⾏什么⼯作, 再进⼊各项⼯作的编制中;
(2) 学校根据⾼级别奖项优先原则, 在各个能⼒编制选出合适的队员组成⼀对;
(3) 假设所有学⽣在能⼒评估/竞赛中都能正常发挥;
(4) 假设每位同学都对参加选拔的同学的能⼒有⼀定的了解, 为了确保⾃⼰能被选上, 会选择对⾃⼰最有利的⽅向报名.
巴黎恐怖袭击
2.4 模型建⽴
2.4.1 学⽣单项能⼒综合评估
此部分较为简单, 能联想到需要根据不同的能⼒分别选取不同的指标, 建⽴三个评价模型即可. 当然, 作
为建模团队⽽⾔, 建模同学能对写作、编程有⼀定的了解的话可能也是不错的选择, 即除了单独衡量⼀个⽅向外, 还可以结合上其他的能⼒值进⾏综合赋值.
我们假设三种⽅向主要考察以下指标:
建模能⼒评分: 科学成绩
、智⼒⽔平
、其他特长
编程能⼒评分: 智⼒⽔平
、动⼿能⼒
、其他特长
写作能⼒评分: 写作能⼒
、外语⽔平
、其他特长
TOPSIS法(优劣解距离法) 和 RSR(秩和⽐综合评价法) 都是简单⽅便的⽅法. 在评价建模能⼒的时候, 选择科学成绩、智⼒⽔平、其他特长作为评价指标, 使⽤ 熵权法 + TOPSIS ⽅法进⾏评估, 设学⽣
从事
⼯作的能⼒评分为
, 则学⽣的单项能⼒得分矩阵为:
考虑到建模中团队协作能⼒的影响, 定义学⽣
的协作能⼒为
, 则学⽣的综合能⼒得分矩阵为:
也可以考虑某位同学选择建模⽅向, 则主要考虑建模能⼒, 编程能⼒和写作能⼒值折扣记分, (或其他的换算函数), 如:
当然, 也可以对 “其他特长” 进⼀步细化考虑. 毕竟... 学习成绩同样的⼈, 特长越多越好么~
此部分总体思路如下:
2.4.2 团队总能⼒评估
定义团队总能⼒为
. 设学⽣
组成同⼀只建模队伍
, 且学⽣
从事建模⼯作, 学⽣同声翻译设备租赁
从事编程⼯作, 学⽣
从事写作⼯作, 则团队的总能⼒为:
这⾥将团队各成员的单项能⼒得分作为总得分, 并⼈为规定顺序.
# 团队总能⼒评估
def team_score(model, code, write):
"""团队能⼒ = 建模能⼒ * 协作能⼒ + 编程能⼒ * 协作能⼒ + 写作能⼒ * 协作能⼒"""
return power_data.at[model, '建模'] + power_data.at[code, '编程'] + power_data.at[write, '写作']
2.4.3 获奖潜⼒评估英语四级准考证号
获奖概率难以量化, 但我们可以通过抽样仿真来进⾏估计.
假设该校所有报名的学⽣的能⼒得分分布与全体参加竞赛同学的得分分布近似. 这样我们就能通过对所有学⽣进⾏随机组合, 得到全体参加竞赛团队的成绩分布. 结合模型假设: 所有团队在竞赛中都能正常发挥, 那就可以按照团队实⼒的分布来代替他们⽐赛时的得分分布.
接着根据获奖⽐例, 设定三个获奖阈值, 只要团队总能⼒达到阈值⽔平就认为有可能获该奖. 达到
阈值认为有可能获得特等奖, 达到
阈值认为有可能获得⼀等奖, 达到
阈值认为有可能获得⼆等奖.实际论⽂写作的话, 这⾥需要插⼊⼀张流程图.
定义指标变量:
仿真部分具体实现请看代码: (这⾥对整体⽔平 + 20%, 实际上可以多设⼏组, 观察组队变化情况)
# 仿真: 重复实验, 假设该校⽔平与整体⽔平相差 20%
team_scores = []
for i in range(21000):
team = list(power_data.sample(3, replace=True, random_state=i).index)
team_scores.append(team_score(*team) * 1.2)
# 排序, 设 .43% 特等奖, 8.88% ⼀等奖, 37.97% ⼆等奖
team_scores.sort(rever=True)
g0 = team_scores[int(21000 * 0.0043)]
g1 = team_scores[int(21000 * 0.0932)]
g2 = team_scores[int(21000 * 0.3829)]
2.4.4 队员组队分配模型建⽴
假设某次建模⽐赛选拔中需要从
名同学中选拔
只队伍,
与
con应满⾜:
每位学⽣最多只能从事1项⼯作, 这是 0-1 指派问题. 同时, 要满⾜问题 (1) 选拔出优秀的队员, 再满⾜问题 (2) 进⾏组队分配, 这是个多⽬标优化模型.
定义决策变量:
定义第⼀级⽬标函数为全体同学的总能⼒得分最⼤化, 实际意义也很好理解, 优秀的团队应该从优秀的同学中产⽣:
定义第⼆级⽬标函数为获奖效益最⼤化:
10 : 5 : 1 是我瞎掰的, 可以⾃⾏设定. 也可以拆分为第三级、第四级⽬标.
约束条件:
① 每个团队每项⼯组都要有⼈负责
② 每⼀个⼈⾄多在⼀个队伍⾥负责1项⼯作
piaggio③ 每项任务都必须有m个⼈
④ 每个团队都必须有3个⼈
⑤ 获奖情况指标变量约束
实际上，约束 ③ 已经包含了 约束 ④
约束 ⑤ 中, 优化⽬标是全体
,
,
尽可能⼤, 在可能的情况下 每⼀个都会尽量取1, 但取1就必须要满⾜团队的总能⼒得分⼤于各个奖项的得分阈值. 因此, 这样的约束就能⽤来
转化为获奖队伍数量.
2.5 代码及求解20选18的问题太简单了, 类似的改⼀下代码就⾏了
使⽤的编程语⾔：python3.7.1 (Anaconda3)
使⽤的编辑器：Sublime Text 3
使⽤的模块：pandas、statsmodels、scipy
代码⼀: topsis.py ⽂件
neytiri
import pandas as pd
the cret gardenimport numpy as np
虚拟语气倒装def topsis(data, weight=None):
"""TOPSIS评价法"""
# 归⼀化
data = data / np.sqrt((data ** 2).sum())
# 最优最劣⽅案
Z = pd.DataFrame([data.min(), data.max()], index=['负理想解', '正理想解'])
# 距离
weight = entropyWeight(data) if weight is None el np.array(weight)
Result = py()
Result['正理想解'] = np.sqrt(
((data - Z.loc['正理想解']) ** 2 * weight).sum(axis=1))
Result['负理想解'] = np.sqrt(
((data - Z.loc['负理想解']) ** 2 * weight).sum(axis=1))
# 综合得分指数
Result['综合得分指数'] = Result['负理想解'] / (Result['负理想解'] + Result['正理想解']) Result['排序'] = Result.rank(ascending=Fal)['综合得分指数']
return Result, Z, weight
def entropyWeight(data):
"""熵权法"""
data = np.array(data)
# 归⼀化
P = data / data.sum(axis=0)
# 计算熵值
E = np.nansum(-P * np.log(P) / np.log(len(data)), axis=0)
# 计算权系数
return (1 - E) / (1 - E).sum()
代码⼆: main.py⽂件
# -*- coding: utf-8 -*-
# @Author: suranyistretch
# @Date: 2019-03-30 11:32:17
# @Last Modified by: suranyi
# @Last Modified time: 2019-03-30 12:54:51
import numpy as np
import pandas as pd
import gurobipy
import topsis
指出英语
# %% 1.创建测试数据
# 创建 600 名同学
classmates = [f'同学{i}' for i in range(1, 601)]
# 组队队伍数
m = 100
