匈牙利法的应用实例 西华师范大学管理学院刘长江Tel：13980310639 QQ: 283076033员工任务指派方法*1假定甲单位有甲、乙、丙、丁、戊五个员工，需要在一 定的生产技术组织条件下，完成A、B、C、D、E五项任 务，每个员工完成每项工作所需要耗费的工作时间，如 表2-6所示。员工与任务之间应当如何进行配置，才能保 证完成工作任务的时间最短？ 甲乙丙丁戊A10591811B131961214C32445D89121715E116141910表2-6 各员员工完成任务时间汇总务时间汇总 表员工 任务Date2矩阵一10 5 9 18 11 13 19 6 12 14 3 2 4 4 5 18 9 12 17 15 11 6 14 19 101. 以各个员工完成各项任务的时间构造矩阵一Date32对矩阵一进行行约减，即每一行数据 减去本行数据中的最小数，得矩阵二。 5 0 4 13 6 7 13 0 6 8 1 0 2 2 3 9 0 3 8 6 5 0 8 13 4矩阵二Date43检查矩阵二，若矩阵二各行各列均有 “0”，则跳过此步，否则进行列约减，即每 一列数据减去本列数据中的最小数，本例 属于后一种情况，经变换得矩阵三。矩阵三 4 0 4 11 3 6 13 0 4 5 0 0 2 0 0 8 0 3 6 3 4 0 8 11 1注意：也可先进行列约减，再进行行约减。 Date54. 画“盖0”线。即画最少的线将矩阵三中的 0全部覆盖住，得矩阵矩阵四。操作技巧： 从含“0”最多的行或列开始画“盖0”线。 矩阵四4 0 4 11 3 6 13 0 4 5 0 0 2 0 0 8 0 3 6 3 4 0 8 11 1Date65.数据转换。若“盖0”线的数目等于矩阵的维数则直接 跳到第七步，若“盖0”线得数目小于矩阵得维数则进行 数据转换，本例属于后一种情况，应进行转换，操作步 骤如下：(1)找出未被“盖0”线覆盖的数中的最小值，例 中=1。(2)将未被“盖0”线覆盖住的数减去。(3)将“盖 0”线交叉点的数加上。本例结果见矩阵五。 矩阵五3 0 4 10 2 5 13 0 3 4 0 0 2 0 0 7 0 3 5 2 3 0 8 10 0 Date76.重复第4步和第5步，直到“盖0”线的数目等于矩 阵的维数。本例最终矩阵见矩阵六。矩阵六0 0 4 7 2 2 13 0 0 4 0 1 2 0 0 4 0 3 2 2 0 0 8 7 0Date80 0 4 7 2 2 13 0 0 4 0 1 2 0 0 4 0 3 2 2 0 0 8 7 0矩阵七7.求最优解。对n维矩阵，找不同行，不列的n个0“0”每个 “0”的位置代表一对配置关系，具体步骤如下： (1)先找只含有一个“0”的行，将该行中的“0”打“”。 (2)将带“”的“0”所在列(或行)中的“0”打“”。 (3)重复(1)步和(2)步至结束。若所有行列均含有多个“0”， 则从“0”的数目最少的行或列中任选一个“0”打“”。见矩 阵七 Date9得出表2-7所示的员工配置最终结果。即员工甲负责任 务A，员工乙负责任务D，员工丙负责任务B，员工丁 负责任务C，员工戊负责任务E。员工 任 务表2-7 员员工完成任务时间汇总务时间汇总 （单单位：小时时 ）10E9D4C6B10A戊丁丙乙甲Date10(二)匈牙利法的推广应用 当员工数目与任务数目不一致，或求最 大化问题时，可通过对问题进行改造使 之满足匈牙利法的要求。Date111. 员工数目与任务数目不一致的情况。Date121.员工数目与任务数目不一致的情况。 (1)当员工数目多于任务数目时，可增添虚任务，添的 虚任务的工作时间、利润为“0”。 例如乙公司目前有5个员工，需要完成4项任务 ，作的工作时间如表2-8所示。应如何分配任 务才能保证工作时间最短? 表2-8 员员工完成任务时间汇总务时间汇总 一151712918D54423C141261913B11189510A戊丁丙乙甲员员工 任 务务Date13分析：五个员工负责四项任务，则必有一员工没有任务， 此时可增添一项虚任务E，则各员工完成任务E的时间均 为0，上表变形为表2-9。此时本题可用匈牙利法计算。 表2-9 员员工完成任务时间汇总务时间汇总 二00000E151712918D54423C141261913B11189510A戊丁丙乙甲员员工任 务务Date14(2)当员工数目少于任务数目时，可让一个员工承担两 个任务。 例如，丙公司安排2个员工，完成3项任务，每 个员工完成每项工作的时间如表2-10所示。应 如何分配任务才能保证工作时间最短? 表2-1023C1913B510A乙甲员员工 任务务Date15分析：两个员工负责三项任务，则必有一个员工须 承担两项任务，因此增加甲和乙，分别表示他们完 成第二项工作的情况，则上表变形为表2-11。 表2-11 员员工完成任务时间汇总务时间汇总2233C19191313B551010A乙乙甲甲员员 工 任务务Date16表2-12 员员工完成任务时间汇总务时间汇总0000D2233C19191313B551010A乙乙甲甲表2-11中，员工数目多于任务数目，因此采用方法 (1)，添加虚任务D，得表2-12。此时本题可用匈牙利 法计算。员工任务Date172. 求最大化问题Date18当所求问题为求最大化值时，可用数据表 中最大的数据分别减去数据表中所有数据 ，得出新的数据表，则问题转化为求最小 值。Date19例如丁公司目前有5名员工完成5项任务，每个员工 完成各项任务所能获取的利润如表2-13所示。 表2-13员员工完成任务务收益汇总汇总 （单单位：万元）101914611E151712918D54423C141261913B11189510A戊丁丙乙甲员员工 任务务Date20表2-13中最大的数据为19。用19分别减去表中的各 个数据，则数据表转化为表2-14，本题可用匈牙利 法计算。 表2-14员员工完成任务务收益汇总汇总 （单单位：万元）905138E427101D1415151716C571306B8110149A戊丁丙乙甲员员工 任务务Date21lkxie163.com 密码：666666 Date22