分派问题1.4 接力队选拔和选课策略若干项任务分给一些候选人来完成，每人的专长不同， 完成每项任务取得的效益或需要的资源就不同，如何分 派任务使获得的总效益最大，或付出的总资源最少。若干种策略供选择，不同的策略得到的收益或付出的 成本不同，各个策略之间有相互制约关系，如何在满 足一定条件下作出决择，使得收益最大或成本最小。数学模型丁的蛙泳成绩退步到115”2；戊的自由泳成绩进步到 57”5, 组成接力队的方案是否应该调整？如何选拔队员组成4100米混合泳接力队?例1 混合泳接力队的选拔 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”45名候选人的百米成绩穷举法：组成接力队的方案共有5!=120种。【问题】数学模型目标 函数若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)队员i 第j 种泳姿的百米成绩约束 条件每人最多入选泳姿之一 ciji=1i=2i=3i=4i=5j=166.857.2787067.4j=275.66667.874.271j=38766.484.669.683.8j=458.65359.457.262.4每种泳姿有且只有1人 【问题分析】 数 学 模 型【模型求解】 最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0;成绩为253.2(秒)=413”2 MIN 66.8x11+75.6x12+87x13+58.6x14+ +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TOx11+x12+x13+x14 =1 x41+x42+x43+x44 =1x11+x21+x31+x41+x51 =1 x14+x24+x34+x44+x54 =1 END INT 20 输入LINDO求解 甲乙丙丁戊蝶泳106”857”2118”110”107”4仰泳115”6106”107”8114”2111”蛙泳127”106”4124”6109”6123”8自由泳58”653”59”457”2102”4甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.数学模型丁蛙泳c43 =69.675.2，戊自由泳c54=62.4 57.5, 方案是否调整？ 敏感性分析？乙 蝶泳、丙 仰泳、丁 蛙泳、戊 自由泳IP规划一般没有与LP规划相类似的理论，LINDO输出的敏感性分析结果通常是没有意义的。最优解：x21 = x32 = x43 = x51 = 1, 成绩为417”7 c43, c54 的新数据重新输入模型，用LINDO求解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能 承担一项，效益不同，怎样分派使总效益最大. 讨论甲 自由泳、乙 蝶泳、丙 仰泳、丁 蛙泳.原 方 案数学模型为了选修课程门数最少，应学习哪些课程 ？ 例2 选课策略要求至少选两门数学课、三门运筹学课和两门计算机课 课号课名学分所属类别先修课要求1微积分5数学 2线性代数4数学 3最优化方法4数学；运筹学微积分；线性代数 4数据结构3数学；计算机计算机编程 5应用统计4数学；运筹学微积分；线性代数 6计算机模拟3计算机；运筹学计算机编程 7计算机编程2计算机 8预测理论2运筹学应用统计 9数学实验3运筹学；计算机微积分；线性代数选修课程最少，且学分尽量多，应学习哪些课程 ？ 【问题】数学模型0-1规划模型 决策变量 目标函数 xi=1 选修课号i 的课程 （xi=0 不选） 选修课程总数最少 约束条件最少2门数学课，3门运筹学课， 2门计算机课。 课号课名所属类别1微积分数学2线性代数数学3最优化方法数学；运筹学4数据结构数学；计算机5应用统计数学；运筹学6计算机模拟计算机；运筹学7计算机编程计算机8预测理论运筹学9数学实验运筹学；计算机【问题分析】 数学模型先修课程要求最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21 约束条件x3=1必有x1 = x2 =1 课号课名先修课要求1微积分 2线性代数 3最优化方法微积分；线性代数 4数据结构计算机编程 5应用统计微积分；线性代数 6计算机模拟计算机编程 7计算机编程 8预测理论应用统计 9数学实验微积分；线性代数【模型求解】 （LINDO）数 学 模 型学分最多多目标优化的处理方法：化成单目标优化。两目标(多目标)规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？ 课程最少 以学分最多为目标，不管课程多少。 以课程最少为目标，不管学分多少。最优解如上，6门课程， 总学分21 。最优解显然是选修所有9 门课程 。【问题分析】 数 学 模 型【模型求解】多目标规划 在课程最少的前提下以学分最多为目标。最优解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它为0；总学分由21增 至22。注意：最优解不唯一！课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3 LINDO无法告诉优化问题 的解是否唯一。可将x9 =1 易为x6 =1增加约束 ，以学分最多为目标求解。数学模型 对学分数和课程数加权形成一个目标，如三七开。 最优解： x1 = x2 = x3 = x4 = x5 = x6 = x7 = x9 =1， 其它为0；总学分28。课号课名学分1微积分52线性代数43最优化方法44数据结构35应用统计46计算机模拟37计算机编程28预测理论29数学实验3 【模型求解】多目标规划 数学模型讨论与思考最优解与1=0，2=1的结果相同学分最多多目标规划 最优解与1=1，2=0的结果相同课程最少数 学 模 型