数学规划模型-3省公开课一等奖全国示范课微课金奖PPT课件.pptx

该【数学规划模型-3省公开课一等奖全国示范课微课金奖PPT课件 】是由【guwutang】上传分享，文档一共【14】页，该文档可以免费在线阅读，需要了解更多关于【数学规划模型-3省公开课一等奖全国示范课微课金奖PPT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章 数学规划模型
接力队选拔和选课策略（0-1规划，多目标）
y
第1页
分配问题
接力队选拔和选课策略
若干项任务分给一些候选人来完成，每人专长不一样，完成每项任务取得效益或需要资源就不一样，怎样分配任务使取得总效益最大，或付出总资源最少。
若干种策略供选择，不一样策略得到收益或付出成本不一样，各个策略之间有相互制约关系，怎样在满足一定条件下作出决择，使得收益最大或成本最小。
第2页
丁蛙泳成绩退步到1’15”2；戊自由泳成绩进步到57”5, 组成接力队方案是否应该调整？
怎样选拔队员组成4100米混合泳接力队?
例1 混合泳接力队选拔
甲
乙
丙
丁
戊
蝶泳
1’06”8
57”2
1’18”
1’10”
1’07”4
仰泳
1’15”6
1’06”
1’07”8
1’14”2
1’11”
蛙泳
1’27”
1’06”4
1’24”6
1’09”6
1’23”8
自由泳
58”6
53”
59”4
57”2
1’02”4
5名候选人百米成绩
穷举法：组成接力队方案共有5!=120种。
第3页
目标函数
若选择队员i参加泳姿j 比赛，记xij=1, 不然记xij=0
0-1规划模型
cij(秒)~队员i 第j 种泳姿百米成绩
约束条件
每人最多入选泳姿之一
cij
i=1
i=2
i=3
i=4
i=5
j=1


78
70

j=2

66


71
j=3
87




j=4

53



每种泳姿有且只有1人
第4页
模型求解
最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0;
(秒)=4’13”2
输入LINGO求解
甲
乙
丙
丁
戊
蝶泳
1’06”8
57”2
1’18”
1’10”
1’07”4
仰泳
1’15”6
1’06”
1’07”8
1’14”2
1’11”
蛙泳
1’27”
1’06”4
1’24”6
1’09”6
1’23”8
自由泳
58”6
53”
59”4
57”2
1’02”4
甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳.
第5页
丁蛙泳c43 =，戊自由泳c54=  , 方案是否调整？
敏感性分析？
乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳、戊~ 自由泳
IP规划普通没有与LP规划相类似理论，LINDO输出敏感性分析结果通常是没有意义。
最优解：x21 = x32 = x43 = x51 = 1, 成绩为4’17”7
c43, c54 新数据重新输入模型，用LINDO求解
指派(Assignment)问题：每项任务有且只有一人负担，每人只能负担一项，效益不一样，怎样分配使总效益最大.
讨论
甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳.
原方案
第6页
为了选修课程门数最少，应学习哪些课程 ？
例2 选课策略
要求最少选两门数学课、三门运筹学课和两门计算机课
课号
课名
学分
所属类别
先修课要求
1
微积分
5
数学
2
线性代数
4
数学
3
最优化方法
4
数学；运筹学
微积分；线性代数
4
数据结构
3
数学；计算机
计算机编程
5
应用统计
4
数学；运筹学
微积分；线性代数
6
计算机模拟
3
计算机；运筹学
计算机编程
7
计算机编程
2
计算机
8
预测理论
2
运筹学
应用统计
9
数学试验
3
运筹学；计算机
微积分；线性代数
选修课程最少，且学分尽可能多，应学习哪些课程 ？
第7页
0-1规划模型
决议变量
目标函数
xi=1 ~选修课号i 课程（xi=0 ~不选）
选修课程总数最少
约束条件
最少2门数学课，3门运筹学课，
2门计算机课。
课号
课名
所属类别
1
微积分
数学
2
线性代数
数学
3
最优化方法
数学；运筹学
4
数据结构
数学；计算机
5
应用统计
数学；运筹学
6
计算机模拟
计算机；运筹学
7
计算机编程
计算机
8
预测理论
运筹学
9
数学试验
运筹学；计算机
第8页
先修课程要求
最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21
0-1规划模型
约束条件
x3=1必有x1 = x2 =1
模型求解（LINGO）
  
 

课号
课名
先修课要求
1
微积分
2
线性代数
3
最优化方法
微积分；线性代数
4
数据结构
计算机编程
5
应用统计
微积分；线性代数
6
计算机模拟
计算机编程
7
计算机编程
8
预测理论
应用统计
9
数学试验
微积分；线性代数
第9页
学分最多
多目标优化处理方法：化成单目标优化。
两目标(多目标)规划
讨论：选修课程最少，学分尽可能多，应学习哪些课程？
课程最少
以学分最多为目标，不论课程多少。
以课程最少为目标，不论学分多少。
最优解如上，6门课程，总学分21 。
最优解显然是选修全部9门课程 。
第10页