《招聘与配置-匈牙利法.docx》由会员分享,可在线阅读,更多相关《招聘与配置-匈牙利法.docx(13页珍藏版)》请在三一文库上搜索。
1、精品招聘与配置匈牙利法P9698假定甲单位有甲、乙、丙、丁、戊五个员工,需要在一定的生产技术组织条件下,完成A、B、C、D、五项任务,每个员工完成每项工作所需要耗费的工作时间,如表 2 6所示。请求出:员工与任务之间应当如何进行配置,才能保证完成工作任务的时间最短?表2-6各员工完成任务时间汇总表单位:小时员工任务、甲乙丙丁戊A10591811B131961214C32445D189121715E116141910注意:由于存在以下两种情况,匈牙利法的计算过程不唯一,最终矩阵的形式也不唯一,但最终配置结果一定相同,1 .约减时,可先进行行约减,再进行列约减;也可先进行列约减,再进行行约减。2
2、.“盖0”线的画法不唯一。现列举两种解法如下:解法一:1 .以各个员工完成各项任务的时间构造矩阵一。表2 7矩阵一1059181113196121432445189121715116141910表28矩阵二50413671306810223903865081343 .检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,2.对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,一列数据减去本列数据中的最小数,得矩阵三。否则进行列约减,即每得矩阵二。表2 9矩阵三4041136130450020080363408111得图2 5。4 .画“盖0”线。即画最少的线将矩阵三中的0全部覆盖住,1111
3、35031图2 5 矩阵四操作技巧:从含“ 0”最多的行或列开始画“盖 0”线。线得数目小5 .数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖 0于矩阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:(1)找出未被“盖0”线覆盖的数中的最小值,例中 =1。(2)将未被“盖0”线覆盖住的数减去。(3)将“盖0”线交叉点的数加上。本例结果见表210矩阵五。表210矩阵五3041025130340130070352可编辑3081006.重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表 2 11。1010矩阵五2矩阵
4、五表 2 11矩阵六130460340322008707.求最优解。对n维矩阵,找出不同行、不同列的 n个“0”,每个“ 0”的位置代表一 对配置关系,具体步骤如下:(1)先找只含有一个“ 0”的行(或列),将该行(或列)中的“ 0”打。(2)将带的“ 0”所在列(或行)中的“ 0”打“ ”。(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“ 0”的数目最少的行或列中任选一个“0”打。其结果如表2 12矩阵七所示,即员工甲负责任务A,员工乙负责任务 D,员工丙负责任务B,员工丁负责任务C,员工戊负责任务E,参照表2 6各员工完成任务时间汇总表,得 出表2 13所示的员工配置
5、最终结果。表 212矩阵七0 V 04722130 V 040460 V 340 vz32200870表2 - 13 员工配置最终结果 单位:小时甲乙丙丁戊际、A10B6C4D9E10解法二:1 .以各个员工完成各项任务的时间构造矩阵一。表27矩阵10591811131961214324451891217151161419102 .对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二。表2 8矩阵二50413671306810223903861343 .检查矩阵二,若矩阵二各行各列均有“0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三。表29矩阵三11
6、13114.画“盖0”线。即画最少的线将矩阵三中的0全部覆盖彳3E,得图2 5。11112-5矩阵四操作技巧:从含“ 0”最多的行或列开始画“盖 0”线。5.数据转换。若“盖0”线的数目等于矩阵的维数则跳过此步,若“盖 0”线得数目小于矩阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下:精品(1)找出未被“盖0”线覆盖的数中的最小值,例中(2)将未被“盖0”线覆盖住的数减去(3)将“盖0”线交叉点的数加上本例结果见表2-10矩阵五。表2 10矩阵五1013106.重复4步和5步(计算过程见矩阵五a和矩阵五b),直到“盖0”线的数目等于矩阵的维数。本例最终矩阵见表 2 11。
7、1010矩阵五精品00172516037043034002200570矩阵五b表2 11 矩阵六001725160370430340022005707.求最优解。对n维矩阵,找出不同行、不同列的 n个“0”,每个“ 0”的位置代表对配置关系,具体步骤如下:(1)先找只含有一个“ 0”的行(或列),将该行(或列)中的“ 0”打。(2)将带的“ 0”所在列(或行)中的“ 0”打“ ”。(3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”,则从“ 0”的数目最少的行或列中任选一个“0”打。其结果如表2 12矩阵七所示,即员工甲负责任务A,员工乙负责任务 D,员工丙负责任务B,员工丁负责任务C,员工戊负责任务E,参照表2 6各员工完成任务时间汇总表,得 出表2 13所示的员工配置最终结果。表212 矩阵七0V01725160 v7370430 V 340 V 02200570vz表2 - 13 员工配置最终结果 单位:小时、员工任务 甲乙丙丁戊A10B6C4D9E10可编辑