理论基础

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

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

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

（3）矩阵中独立0元素的最多个数等于能覆盖所有0元素的最少直线数。

算法步骤

匈牙利法的算法步骤如下：

(1)对指派问题的系数矩阵进行变换，使每行每列至少有一个元素为“0”．

①让系数矩阵的每行元素去减去该行的最小元素；

②再让系数矩阵的每列元素减去该列的最小元素。

(2)从第一行开始，若该行只有一个零元素，就对这个零元素加括号，对加括号的零元素所在的列画一条线覆盖该列，若该行没有零元素或者有两个以上零元素(已划去的不算在内)，则转下一行，依次进行到最后一行。

(3)从第一列开始，若该列只有一个零元素。就对这个零元素加括号(同样不、考虑已划去的零元素)。再对加括号的零元素所在行画一条直线覆盖该列。若该列没有零元素或有两个以上零元素，则转下一列，依次进行到最后一列为止。

(4)重复上述步骤(1)和(2)可能出现3种情况：

①效率矩阵每行都有加括号的零元素，只要对应这些元素令就找到了最优解。

②加括号的零元素个数少于m，但未被划去的零元素之间存在闭回路，这时顺着闭回路的走向，对每个间隔的零元素加一个括号，然后对所有加括号的零元素所在行(或列)画一条直线，同样得到最优解。

③矩阵中所有零元素或被划去，或加上括号．但加括号的零元素少于m，这时转入(5)．

(5)按定理进行如下变换：

①从矩阵未被直线覆盖的数字中找出一个最小的k；

②当矩阵中的第i行有直线覆盖时，令；无直线覆盖时。令；