- 1、本文档共143页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
在实际中经常会遇到这样的问题,有n 项不同的任务,需要n 个人分别完成其中的一项,但由于任务的性质和各人的专长不同,因此各人去完成不同的任务的效率(或花费的时间或费用)也就不同。于是产生了一个问题,应指派哪个人去完成哪项任务,使完成 n 项任务的总效率最高(或所需时间最少),这类问题称为分配问题或指派问题。 一、指派问题及数学模型 第五节 指派问题与匈牙利法 指派问题举例 甲、乙、丙、丁四个人,A、B、C、D四项任务,不同的人做不同的工作效率不同,如何指派不同的人去做不同的工作使效率最高,即花费的总时间最短? 解:对于这个问题,很容易建立一个数学模型的, 引入0-1变量 , 当 =1时,表示分配第i个人完成第j项任务 当 =0时,表示不分配第i个人完成第j项任务 第五节 指派问题与匈牙利法 一项任务只由一个人完成,有如下约束 一人只能完成一项任务,有如下约束 第五节 指派问题与匈牙利法 例: 人事部门欲安排四人到四个不同岗位工作,每个岗位一个人。经考核四人在不同岗位的成绩(百分制)如表所示,如何安排他们的工作使总成绩最好。 工作 人员 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 第五节 指派问题与匈牙利法 设 数学模型如下: 要求每人做一项工作,约束条件为: 第五节 指派问题与匈牙利法 每项工作只能安排一人,约束条件为: 变量约束: 第五节 指派问题与匈牙利法 第五节 指派问题与匈牙利法 指派问题的数学模型: 工作任务 效率 工人 要求每个工人有一项工作,每项工作只有一个工人来作.如何安排使总的效益最好. 第五节 指派问题与匈牙利法 第五节 指派问题与匈牙利法 二、指派问题的解法—匈牙利法 匈牙利法(1955年W.W.Kuhn求解分配问题,使用了匈牙利数学家Kuhn的两个定理,故称匈牙利解法. 定理1 第五节 指派问题与匈牙利法 第二步,用单纯形法求松弛问题,得最终单纯形表。 cj → 8 5 0 0 CB 基 b x1 x2 x3 x4 0 x3 12 2 3 1 0 0 x4 6 [2] -1 0 1 cj-zj 8 5 0 0 0 x3 6 0 [4] 1 -1 8 x1 3 1 -1/2 0 1/2 cj-zj 0 9 0 -4 5 x2 3/2 0 1 1/4 -1/4 8 x1 15/4 1 0 1/8 3/8 cj-zj 0 0 -9/4 -7/4 松弛问题的最优解 , ,非整数规划的可行解。 第三节 割平面法 第三步,引进割平面 在最终单纯形表中选择分数部分最大的基变量 列出该行约束: 将所有系数分成整数与一个正的分数之和: 将分数部分移至右端: 分析右边的分数项,其取值小于1,即得到了Gomory约束: 第三节 割平面法 第四节 0-1规划与隐枚举法 如果线性规划中的所有决策变量的取值只能取0、1,则这类线性规划问题是一种特殊的整数规划问题称之为0-1规划,把只能取0或1值的变量称为0-1变量。0-1变量是一种逻辑变量。 第四节 0-1规划与隐枚举法 其数学模型如下: 第四节 0-1规划与隐枚举法 本节先介绍引入0-1变量的实际问题: ① 投资场所(项目)的选定 ②相互排斥的约束条件 ③关于固定费用的问题 然后,再研究0-1规划问题的一般解法---隐枚举法。 第四节 0-1规划与隐枚举法 一、引入0-1变量的实际问题 投资场所的选定——相互排斥的计划 例 : 某公司拟在市东、西、南三区建立门市部。拟议中有7个位置(点)Ai (i=1,2,…,7)可供选择。规定: 在东区,由A1,A2,A3三个点中至多选两个; 在西区,由A4,A5两个点中至少选一个; 在南区,由A6,A7两个点中至少选一个。 如选用Ai点,设备投资估计为bi元, 每年可获利润估计为ci元, 但投资总额不能超过B元。 问应选择哪几个点可使年利润为最大? 解题时先引入0-1变量xi (=1,2,…,7) 问题建模: 2. 相互排斥的约束条件 设运货有车运和船运两种方式, 用车运的体积限制条件为: 5x1+4x2≤24 用船运的体积限制条件为: 7x1+3x2≤45 这两条件是互相排斥的。 为了统一在一个问题中,引入0-1变量y,令 (
您可能关注的文档
最近下载
- 2023压力容器设计审核人员考试题库-1.docx
- 合并肥厚性心肌病的麻醉.pptx VIP
- 小区幼儿园经营管理投标文件.docx
- TSGD7006—2023年压力管道监督检验规则.docx
- 2023年新青岛版(六三制)二年级上册科学全册课件.pptx
- 全国说课比赛一等奖课件.ppt
- 第一单元+史前时期:原始社会与中华文明的起源(单元复习课件)-【大单元教学】2024-2025学年七年级历史上册同步备课系列(统编版2024).pptx VIP
- (完整版)小升初字音、字形、词语练习.pdf VIP
- 【2024秋】人教版三年级语文上册教学工作计划(及进度表).docx
- 护理专业调研报告(高职).docx VIP
文档评论(0)