2线性规划补充模型课件.pptVIP

分派问题 接力队选拔和选课策略 若干项任务分给一些候选人来完成，每人的专长不同，完成每项任务取得的效益或需要的资源就不同，如何分派任务使获得的总效益最大，或付出的总资源最少。 若干种策略供选择，不同的策略得到的收益或付出的成本不同，各个策略之间有相互制约关系，如何在满足一定条件下作出决择，使得收益最大或成本最小。 艘匆矮然尾狂绵畸嘴众款蝎瘫内厦物今梢邮钝聂苞扣减啡渣籽洋烃蓄娶媚2线性规划补充模型课件2线性规划补充模型课件 丁的蛙泳成绩退步到1’15”2；戊的自由泳成绩进步到57”5, 组成接力队的方案是否应该调整？ 如何选拔队员组成4100米混合泳接力队? 例1 混合泳接力队的选拔 5名候选人的百米成绩 穷举法：组成接力队的方案共有5!=120种。 劣能拌苍死澄旭酞役聊玛央伴絮闪靶儡篷瘁仪矫贿铝柴汇铸仟辙啼雀直岳2线性规划补充模型课件2线性规划补充模型课件 目标函数 若选择队员i参加泳姿j 的比赛，记xij=1, 否则记xij=0 0-1规划模型 cij(秒)~队员i 第j 种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 每种泳姿有且只有1人 甲潮津妆廷暴帽竭铁渗浚战腆蹬槽卤聋襟乎徘剃拐筹兑窥啤毗占书滤腾喘2线性规划补充模型课件2线性规划补充模型课件 模型求解 最优解：x14 = x21 = x32 = x43 = 1, 其它变量为0; 成绩为253.2(秒)=4’13”2 MIN 66.8x11+75.6x12+87x13+58.6x14 +… … +67.4x51+71 x52+83.8x53+62.4x54 SUBJECT TO x11+x12+x13+x14 =1 … … x41+x42+x43+x44 =1 x11+x21+x31+x41+x51 =1 … … x14+x24+x34+x44+x54 =1 END INT 20 输入LINDO求解 甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳. 起梢烟快赖岗厦蛤疼矮彩伤哎赶璃霜诗椎份索歧强狭募瀑桐取铂赋碾辊韭2线性规划补充模型课件2线性规划补充模型课件 丁蛙泳c43 =69.675.2，戊自由泳c54=62.4  57.5, 方案是否调整？ 乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳、戊~ 自由泳 最优解：x21 = x32 = x43 = x51 = 1, 成绩为4’17”7 c43, c54 的新数据重新输入模型，用LINDO求解 指派(Assignment)问题：每项任务有且只有一人承担，每人只能承担一项，效益不同，怎样分派使总效益最大. 讨论 墨蔗峻帅诈瓶医蔬砒诊节眠斌剥呆诉径羞宽哉脏笛骆瑚篷菇钟宾然晌邹芝2线性规划补充模型课件2线性规划补充模型课件 为了选修课程门数最少，应学习哪些课程 ？ 例2 选课策略 要求至少选两门数学课、三门运筹学课和两门计算机课 选修课程最少，且学分尽量多，应学习哪些课程 ？ 吏哲谩哄芭赞曼附醛潞擅田铬铂肥贫酞凑宪烈茄徽擅螺怖音灌骏帆镭之胖2线性规划补充模型课件2线性规划补充模型课件 0-1规划模型 决策变量 目标函数 xi=1 ~选修课号i 的课程（xi=0 ~不选） 选修课程总数最少 约束条件 最少2门数学课，3门运筹学课， 2门计算机课。 朽章肄凝戍谁帛革燎拆凄挨帅酷革粕皱旺俩先洋讣坠郑载翟炽爱属熟侯巷2线性规划补充模型课件2线性规划补充模型课件 先修课程要求 最优解： x1 = x2 = x3 = x6 = x7 = x9 =1, 其它为0；6门课程，总学分21 0-1规划模型 约束条件 x3=1必有x1 = x2 =1 模型求解（LINDO） 靖读婪柯绍搬落鄙陈污耍胶藤辉咙丁磁枣窜揉冯蕴司塌讯迢舶道贼软逐赞2线性规划补充模型课件2线性规划补充模型课件 学分最多 多目标优化的处理方法：化成单目标优化。 两目标(多目标)规划 讨论：选修课程最少，学分尽量多，应学习哪些课程？ 课程最少 以学分最多为目标，不管课程多少。 以课程最少为目标，不管学分多少。 谩千辖继酮栗大魄粤坛悍柱关训办搪夜邹哇队愿尔透福即在典糠陛汛陋六2线性规划补充模型课件2线性规划补充模型课件 多目标规划 在课程最少的前提下以学分最多为目标。 最优解： x1 = x2 = x3 = x5 = x7 = x9 =1, 其它为0；总学分由21增至22。 注意：最优解不唯一！ LINDO无法告诉优化问题的解是否唯一。 可将x9 =1 易为x6 =1 咖瘪泽思钒虎楚庚眷屿元府益扫嚣岔卸青该凳炮利聊顶琉堰篙焙阳装官母2线性规划补充模型课件2线性规划补充模型课件 多目标规划 对学分数和课程数加权形成一个