匈牙利法

（1）若从效率矩阵(cij)的行（或列）的各元素中分别减去该行（或列）的最小元素后得到一个新矩阵（bij）,则以（bij）为效率矩阵的指派问题与原问题有相同的最优解。

经过上述变换后，（bij）中的每行和每列都至少含有一个0元素，称位于不同行不同列的0元素为独立的0元素。

（2）若（bij）有n个独立的0元素，由此可得一个解矩阵，方法为在X中令对应于（bij）的0元素位置的元素为1，其它位置的元素为0，则X为指派问题的最优解。

（3）D.König定理：矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

根据上面的原理，匈牙利法可分为如下的四个步骤：

1.对效率矩阵(cij)做变换得（bij），使（bij）中每行每列均有0元素，实现的方法是：

（1）从（cij）的每行元素中减去该行的最小元素；

（2）再从所得矩阵的每列元素中减去该列的最小元素，得（bij）.

2.求（bij）的独立0元素。行列相间地对0元素给出两种标记“*”和“△”，它们分别表示该元素“是”或“不是”独立0元素，在所有的0元素全局有标记时，若独立0元素（即标有*的0元素）的个数为n时，已得最优解，否则转第3步，

标记的方法是：搜索含有未被标记的0元素且个数最少的行（或列），等概率地从中随机选择一个0元素给以标记*，并对该元素所在的行和列中其它未被标记的0元素给以标记△。

显然标记过程可在有限步完成，从经济意义上看，当给位置为(i,j) 的0元素标记*时，就意味着将第j项工作分配给第i个人员，此时完成任务的效率最高，同时对人员i和工作j的指派已经完成，需将对第i行和第j列的未被标记的0元素标记△,以示以后不再考虑它们的指派，应当说明：在按行（或列）进行标记时，若有多个未被标记的0元素时，上述方法只保证这种指派的局部最优性，在全局上是否最优依赖于独立0元素的个数是否等于n .

3.确定矩阵（bij）中独立0元素的最多个数m,当m
确定m的方法是： 据（bij）中未被删除的部分搜索不含标记*的0元素所在的行，给该行以标号“√”，若该行有标记为△的0元素，删去该元素所在的列，在不具有满足上述条件的行时，过程终止。设被标记的行数为k，删去的列数为l。则m=n-k+l.

这一步的依据是D.König定理，这是因为对被删除的每一列和未被标记的每一行做直线，这些直线式覆盖所有0元素所需要的最少的直线，从而直线条数为（bij）中独立0元素最多的个数，在m=n时，表示在第2步中某一次指派仅为局部最优，但不为全局最优，算法要求退回第2步，重新进行指派

，第2步中关于等概率地随机选取标记为*的0元素可使新指派得以实现。在m
4.对（bij）再做变换以增加独立0元素的个数。

方法为：求出所有已标记“√”的行中且未被删除部分包含元素的最小值，然后，所有已标记的行中的每一个元素（含已删除部分）加上这一最小值，而它删除的列中的每一个元素减去该值，得到一个新矩阵，仍记为（bij）,去掉所有的标记，转第2步。

在人员数和任务n不是很大时，匈牙利法是求解指派问题的有效方法，且易于编制成软件，。

在实际问题中还可能遇到极大型的指派问题，我们可以将之转化为极小型问题，然后应用匈牙利法求解，具体地，

令

C’ij=M-Cij， i，j=1,2,3,…,n

其中M为一个足够大的正数以保证c’ij非负，例如可取M 为矩阵C中的最大元素，这样可生成一个以（c’ij）为矩阵的极小型指派问题，由于

，

nM为固定的常数，两个指派问题有最同的最优解。

在实际的任务分配中，还可能出现人员（或设备）数与任务数不相等的情况，而且要求每个人员只先完成一件任务（在人员数少于任务数时），或者有些人员可暂不安排任务（在人员数多余任务数时），可称这样的问题为不平衡的指派问题，此时，可通过虚拟人员或虚拟任务使之转化为一般（平衡）的指派问题，即在原矩阵中增加一些行或者列，使之成为方阵，在极小型问题中所增加的元素应充分的大，如为原矩阵中最大的元素的值，而在极大型问题中增加的元素应足够的小。如可取零值。