- 1、本文档共91页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
线性整数规划模型课件
* * 2. 指派(或分配)问题 * * 2. 指派(或分配)问题 指派问题的一般模型: * * 2. 指派(或分配)问题 指派问题的一般模型: * * 匈牙利算法的基本思想 因为每个指派问题都有一个相应的效益矩阵,通过初等变换修改效益矩阵的行或列,使得在每一行或列中至少有一个零元素,直到在不同行不同列中都至少有一个零元素为止。从而得到与这些零元素相对应的一个完全分配方案,这个方案对原问题而言是一个最优的分配方案。 3. 指派问题的匈牙利算法 * * 用LINGO求解0-1规划模型 4、0-1规划的LINGO解法 如何选拔队员组成4?100m混合泳接力队? 例1 混合泳接力队的选拔 5名候选人的百米成绩 穷举法:组成接力队的方案共有5!=120种. 甲 乙 丙 丁 戊 蝶泳 仰泳 蛙泳 自由泳 讨论:丁的蛙泳成绩退步到 ;戊的自由泳成绩进步到 , 组成接力队的方案是否应该调整? 目标函数 若选择队员i参加泳姿j 的比赛,记xij=1, 否则记xij=0 0-1规划模型 cij(s)~队员i第j 种泳姿的百米成绩 约束条件 每人最多入选泳姿之一 cij i=1 i=2 i=3 i=4 i=5 j=1 66.8 57.2 78 70 67.4 j=2 75.6 66 67.8 74.2 71 j=3 87 66.4 84.6 69.6 83.8 j=4 58.6 53 59.4 57.2 62.4 每种泳姿有且只有1人 模型求解 MODEL: sets: person/1..5/; position/1..4/; link(person,position): c, x; endsets data: c= 66.8, 75.6, 87, 58.6, 57.2, 66, 66.4, 53, 78, 67.8, 84.6, 59.4, 70, 74.2, 69.6, 57.2, 67.4, 71, 83.8, 62.4; enddata 输入LINGO求解 min=@sum(link: c*x); @for(person(i): @sum(position(j):x(i,j))=1;); @for(position(i): @sum(person(j):x(j,i))=1;); @for(link: @bin(x)); END 模型求解 最优解:x14 = x21 = x32 = x43 = 1, 其他变量为0; 输入LINGO求解 甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳. 成绩为253.2(s)= 甲 乙 丙 丁 戊 蝶泳 仰泳 蛙泳 自由泳 丁蛙泳c43 = 69.6?75.2 (s),戊自由泳c54= 62.4 ? 57.5 (s), 方案是否调整? 敏感性分析? 新方案:乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳、戊~ 自由泳 IP一般没有与LP相类似的理论,LINGO输出的敏感性分析结果通常是没有意义的. c43, c54 的新数据重新输入模型,用LINGO求解 原分配方案: 甲~ 自由泳、乙~ 蝶泳、丙~ 仰泳、丁~ 蛙泳. 讨论 最优解:x21 = x32 = x43 = x51 = 1, 成绩为 混合泳接力队的选拔 指派(Assignment)问题:有若干项任务, 每项任务必有且只能有一人承担,每人只能承担一项,不同人员承担不同任务的效益(或成本)不同,怎样分派各项任务使总效益最大(或总成本最小)? 人员数量与任务数量相等 人员数量大于任务数量(本例) 人员数量小于任务数量 ? 建立0-1规划模型是常用方法 为了选修课程门数最少,应学习哪些课程 ? 例 选课策略 要求至少选两门数学课、三门运筹学课和两门计算机课 课号 课名 学分 所属类别 先修课要求 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门运
您可能关注的文档
最近下载
- 锅炉补给水安装操作运行维护手册(终版.pdf
- 【高中地理】新鲁教版必修第一册期末知识梳理:第二单元 从地球圈层看地表环境(含答案及解析).pdf VIP
- 中考数学模拟题汇总《数与式》专项练习及答案解析.docx
- 纳博特科技机器人控制系统操作手册V5.5.pdf
- 富士VG7变频器操作手册.pdf
- 稻盛和夫阿米巴经营.pdf
- 小学道德与法治三年级第三单元:我们的公共生活大单元整体教学设计2024.docx
- 【高中地理】新鲁教版必修第一册期末知识梳理:第一单元 从宇宙看地球(学生考试版).pdf VIP
- English_for_Human_Resources_book人力资源.pdf
- 湖南五凌电力有限公司招聘笔试题库2023.pdf
文档评论(0)