人力资源级匈牙利法解题思路.doc

《人力资源级匈牙利法解题思路.doc》由会员分享，可在线阅读，更多相关《人力资源级匈牙利法解题思路.doc（5页珍藏版）》请在课桌文档上搜索。

1、匈牙利法假定甲单位有甲、乙、丙、丁、戊五个员工,需要在一定的生产技术组织条件下,完成A、B、C、D、E五项任务,每个员工完成每项工作所需要耗费的工作时间,如表26所示.请求出：员工与任务之间应当如何进行配置,才能保证完成工作任务的时间最短？表26 各员工完成任务时间汇总表 单位：小时 员工任务甲乙丙丁戊A10591811B131961214C32445D189121715E116141910注意：由于存在以下两种情况,匈牙利法的计算过程不唯一,最终矩阵的形式也不唯一,但最终配置结果一定相同,1约减时,可先进行行约减,再进行列约减；也可先进行列约减,再进行行约减.2盖0”线的画法不唯一.现列举两

2、种解法如下：解法一：1以各个员工完成各项任务的时间构造矩阵一.表27矩阵一10591811131961214324451891217151161419102对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二.表28矩阵二50413671306810223903865081343检查矩阵二,若矩阵二各行各列均有0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三.表29矩阵三40411361304500200803634081114画盖0”线.即画最少的线将矩阵三中的0全部覆盖住,得图25.4041136130450020080363408111图25 矩

3、阵四操作技巧：从含0最多的行或列开始画盖0线.5数据转换.若盖0”线的数目等于矩阵的维数则跳过此步,若盖0”线得数目小于矩阵得维数则进行数据转换,本例属于后一种情况,应进行转换,操作步骤如下：1找出未被盖0线覆盖的数中的最小值,例中1.2将未被盖0线覆盖住的数减去.3将盖0线交叉点的数加上.本例结果见表210 矩阵五.表210矩阵五3041025130340130070352308100 6重复4步和5步计算过程见矩阵五a和矩阵五b,直到盖0”线的数目等于矩阵的维数.本例最终矩阵见表211.3041025130340130070352308100矩阵五a00472213004046034032

4、200870矩阵五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 46

5、0 340 3220 0 870 表213 员工配置最终结果 单位：小时 员工任务甲乙丙丁戊A10B6C4D9E10解法二：1以各个员工完成各项任务的时间构造矩阵一.表27矩阵一10591811131961214324451891217151161419102对矩阵一进行行约减,即每一行数据减去本行数据中的最小数,得矩阵二.表28矩阵二50413671306810223903865081343检查矩阵二,若矩阵二各行各列均有0”,则跳过此步,否则进行列约减,即每一列数据减去本列数据中的最小数,得矩阵三.表29矩阵三40411361304500200803634081114画盖0”线.即画最少的

6、线将矩阵三中的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.

7、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,参照表26各员工完成任务时间汇总表,得出表213所示的员工配置最终结果.表212 矩阵七00172516037043034002200570表213 员工配置最终结果 单位：小时 员工任务甲乙丙丁戊A10B6C4D9E10