匈牙利法的具体计算方法
假定甲单位有甲、乙、丙、丁、戊五个员 工，需要在一定的生产技术组织条件下， 完成A、B、C、D、E五项任务，每个员工完 成每项工作所需要耗费的工作时间，如表410所示。
请求出：员工与任务之间应当如何进行配 置，才能保证完成工作任务的时间最短？
各员工完成任务时间汇总表
求解的问题是最小化问题，如工作时间最 小化，费用最小化等
运用匈牙利法时所应注意的事项
匈牙利法的计算过程不唯一，最终矩阵的形式也 不唯一，但最终配置结果一定相同。 约减方法不唯一，可先进行行约减，再进行列约 减；也可以先进行列约减，再进行行约减。 盖“0”线画法不一，但要从含“0”最多的行和 列开始画盖“0”线。 求最优解时，要先找只含一个“0”的行（或列）， 将该行（或列）中的“0”打“√”；将带“√”的 “0”所在列6 12 3 2 4 4 18 9 12 17 11 6 14 19
矩阵一
11 14 5 15 10
5 0 7 13 1 0 9 0 5 0
4 0 2 3 8
13 6 2 8 13
6 8 3 6 4
矩阵二
3.检查矩阵二，若矩阵二各行各列均有“0” 则跳过此步，否则再继续进行约减最终我们 得到了矩阵三。 4 6 0 8 4 0 13 0 0 0 4 11 3 0 4 5 2 0 0 3 6 3 8 11 1
员工最终配置结果表 员工 任务 甲 乙 丙 丁 戊
A
B C D E
10
6 4 9 10
谢谢观看
表4-10
员工 任务 A B C D E 10 13 3 18 11 5 19 2 9 6 9 6 4 12 14 18 12 4 17 19 11 14 5 15 10 甲 乙 丙 丁 戊
1.以各员工完成各项任务的时间构造矩阵一 2.对矩阵一进行行约减即每一行数据减去本行数 据中的最小数，得矩阵二
其结果如矩阵七所示：
0√ 2 0X 4 0X 0X 13 4 0 √ 0X 4 0√ 6 3 8 7 0X 0X 2 7 2 4 0X 2 0√
矩阵七
8.即员工甲负责任务A，员工乙负责任务D， 员工丙负责任务B，员工丁负责任务C，员 工戊负责任务E，参照表4－10各员工完成 任务时间汇总表得出下表所示的员工配置
运用匈牙利法算法计算人与岗 位的配置
小组成员：董泽发 汪广真 赵云鹏 孙明东 宋启江 洪涛 黄冠 张来福
1.匈牙利法的起源和提出 2.匈牙利法运用于员工指派时应具备 的约束条件
3.运用匈牙利法时所应注意的事项 4.匈牙利法的具体计算方法
匈牙利法的起源和提出
匈牙利法是求解及小型（优化方向为极小） 指派问题的一种方法，这种方法最初由 w.w.kuhn提出，后经改进而形成，解法基 于匈牙利数学家D.König给出的一个定 理而得名。
6.通过重复第4、5步直到盖“0”线的数目等于矩阵 的维数。得到矩阵六 7.求最优解。对n维矩阵，找出不同行、不同列的n个 “0”，每个“0”的位置代表配置关系，具体步骤如下： 也就是前面的注意事项。 （1）先找只含有一个“0”的行（或列），将该行 （或列）中的“0”打“√” （2）将带“√”的“0”所在列（或行）中的“0”打 “X”。 （3）重复（1）步和（2）步至结束。若所有行列均 含有多个“0”，则从“0”的数目最少的行或列中一个 “0”打“√” 其结果如矩阵七所示，即员工甲负责任务A，员工乙 负责任务D，员工丙负责任务B，员工丁负责任务C， 员工戊负责任务E，参照表4－10各员工完成任务时 间汇总表得出表4－11所示的员工配置最终结果。
矩阵三
4 6 0 8 4
0 13 0 0 0
4 0 2 3 8
11 4 0 6 11
3 5 0 3 1
矩阵四
4.画盖“0”线。即画最少的线将矩阵三中的 0全部覆盖住，得矩阵四
5.数据转换。若盖“0”线的数目等于矩阵的维 数则直接跳到第七步，若盖“0”线的数目小 于矩阵的维数则要进行以下数据转换，操作步 骤如下： （1）.找出未被盖“0”线覆盖住的数中的最小 值ƛ，本题中的ƛ=1。 （2）.将未被盖“0”线覆住的数减去ƛ。 （3）.将盖“0”线交叉点的数加上ƛ。 3 0 4 10 2 0 0 4 7 2 5 13 0 3 4 2 13 0 0 4 矩 矩 0 1 3 0 0 0 4 6 0 0 阵 阵 五 六 7 0 3 5 2 4 0 3 2 2 3 0 8 10 0 0 0 8 7 0
匈牙利法的运算牵涉到线性代数中的矩阵 运算，具体的理论基础较为复杂！这里我 们只需要知道它的运算方法即可
匈牙利法运用于员工指派时应具备的约 束条件
指派问题是一种特殊的整数规划问题具体 一点就是：有M个员工去做N件任务，但每 个人的效率不一，而且一个人只能安排一 件任务，问怎样安排工作才能使效率最大 化 员工数目与任务数目相等