免费预览已结束,剩余1页可下载查看
下载本文档
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
三级一、p259改为:二、匈牙利法 p9698假定甲单位有甲、乙、丙、丁、戊五个员工,需要在一定的生产技术组织条件下,完成a、b、c、d、e五项任务,每个员工完成每项工作所需要耗费的工作时间,如表26所示。请求出:员工与任务之间应当如何进行配置,才能保证完成工作任务的时间最短?表26 各员工完成任务时间汇总表 单位:小时 员工任务甲乙丙丁戊a10591811b131961214c32445d189121715e116141910注意:由于存在以下两种情况,匈牙利法的计算过程不唯一,最终矩阵的形式也不唯一,但最终配置结果一定相同,1约减时,可先进行行约减,再进行列约减;也可先进行列约减,再进行行约减。2“盖0”线的画法不唯一。现列举两种解法如下:解法一:1以各个员工完成各项任务的时间构造矩阵一。表27 矩阵一10591811131961214324451891217151161419102对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。表28 矩阵二50413671306810223903865081343检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三。表29 矩阵三40411361304500200803634081114画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住,得图25。4041136130450020080363408111图25 矩阵四操作技巧:从含“0”最多的行或列开始画“盖0”线。5数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线得数目小于矩阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:(1)找出未被“盖0”线覆盖的数中的最小值,例中1。(2)将未被“盖0”线覆盖住的数减去。(3)将“盖0”线交叉点的数加上。本例结果见表210 矩阵五。表210 矩阵五3041025130340130070352308100 6重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表211。3041025130340130070352308100矩阵五a00472213004046034032200870矩阵五b表211 矩阵六004722130040460340322008707求最优解。对n维矩阵,找出不同行、不同列的n个“0”,每个“0”的位置代表一对配置关系,具体步骤如下:(1)先找只含有一个“0”的行(或列),将该行(或列)中的“0”打“”。(2)将带“”的“0”所在列(或行)中的“0”打“”。(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“0”的数目最少的行或列中任选一个“0”打“”。其结果如表212矩阵七所示,即员工甲负责任务a,员工乙负责任务d,员工丙负责任务b,员工丁负责任务c,员工戊负责任务e,参照表26各员工完成任务时间汇总表,得出表213所示的员工配置最终结果。表212 矩阵七0 0 4722130 0 40 460 3 40 3220 0 870 表213 员工配置最终结果 单位:小时 员工任务甲乙丙丁戊a10b6c4d9e10解法二:1以各个员工完成各项任务的时间构造矩阵一。表27 矩阵一10591811131961214324451891217151161419102对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。表28 矩阵二50413671306810223903865081343检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三。表29 矩阵三40411361304500200803634081114画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住,得图25。4041136130450020080363408111图25 矩阵四操作技巧:从含“0”最多的行或列开始画“盖0”线。5数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖0”线得数目小于矩阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:(1)找出未被“盖0”线覆盖的数中的最小值,例中1。(2)将未被“盖0”线覆盖住的数减去。(3)将“盖0”线交叉点的数加上。本例结果见表210 矩阵五。表210 矩阵五3041025130340130070352308100 6重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表211。3041025130340130070352308100矩阵五a00172516037043034002200570矩阵五b表211 矩阵六001725160370430340022005707求最优解。对n维矩阵,找出不同行、不同列的n个“0”,每个“0”的位置代表一对配置关系,具体步骤如下:(1)先找只含有一个“0”的行(或列),将该行(或列)中的“0”打“”。(2)将带“”的“0”所在列(或行)中的“0”打“”。(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“0”的数目最少的行或列中任选一个“0”打“”。其结果如表212矩阵七所示,即员工甲负责任务a,员工乙负责任务d,员工丙负责任务b,员工丁负责任务c,员工戊负责任务e,
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2024-包工头劳务分包合同
- 六年级下册数学期中测试卷(黄金题型)
- 电子商务附有答案
- “特种兵式旅游”消费意愿及发展前景调研附有答案
- 圣诞节价值观答题竞赛附有答案
- 第17套卷 计算机知识题复制
- 智能物流仓储设计服务合同
- 2024-罐车买卖合同
- 2024-开发商委托物业合同
- 2024-洒水车租赁样板合同
- 《食品工艺学》第一篇肉制品加工技术和应用
- 大坝安全监测月度分析报告
- 东莞刻蚀设备项目可行性研究报告(范文)
- 大唐衣冠第一期文官武弁朝服全(精编版)
- 山东省青岛第五十八中学自主招生模拟试题化学试卷
- 短波电台通信的原理
- 电线电缆规格型号代表的含义
- 如何推算五黄日
- 上海交通大学医学院儿科学系
- 2022新苏教版小学科学五年级下册第二单元《仿生》全部教案(共4课)
- 格宾网石笼施工方案要点
评论
0/150
提交评论