3.2 求解指派问题的匈牙利算法
由于指派问题的特殊性，又存在着由匈牙利数学家D.Konig提出的更为简便的解法—匈牙利算法。算法主要依据以下事实：如果系数矩阵C?(cij)一行（或一列）中每一元素都加上或减去同一个数，得到一个新矩阵B?(bij) ，则以C或B为系数矩阵的指派问题具有相同的最优指派。
利用上述性质，可将原系数阵C 变换为含零元素较多的新系数阵B，而最优解不变。若能在B 中找出n个位于不同行不同列的零元素，令解矩阵中相应位置的元素取值为1，其它元素取值为零，则所得该解是以B为系数阵的指派问题的最优解，从而也是原问题的最优解。
由C到B的转换可通过先让矩阵C的每行元素均减去其所在行的最小元素得矩阵D，D的每列元素再减去其所在列的最小元素得以实现。
下面通过一例子来说明该算法。 例7 求解指派问题，其系数矩阵为
?16?17 C???24??17152122191919182222?18?? 17??16?解 将第一行元素减去此行中的最小元素15，同样，第二行元素减去17，第三行元素减去17，最后一行的元素减去16，得
?1?0 B1???7??1045342167?1?? 0??0?再将第3列元素各减去1，得
?10*37??*?0411? B2??*?7500??*?1350??以B2为系数矩阵的指派问题有最优指派 ???1234? ???2134?由等价性，它也是例7的最优指派。 有时问题会稍复杂一些。
例8 求解系数矩阵C的指派问题
?127979??89666??? C??717121412?
??15146610????4107106??解：先作等价变换如下
0?127979??50*2?2?6?89666?300*????7?717121412???0*1057????6?15146610?80*0?9??4?636?4107106???0 ??72?0??5??? 4?2??? 容易看出，从变换后的矩阵中只能选出四个位于不同行不同列的零元素，但n?5，最
优指派还无法看出。此时等价变换还可进行下去。步骤如下：
(1) 对未选出0元素的行打?； (2) 对?行中0元素所在列打?；
(3) 对?列中选中的0元素所在行打?； 重复（2）、（3）直到无法再打?为止。
可以证明，若用直线划没有打?的行与打?的列，就得到了能够覆盖住矩阵中所有零元素的最少条数的直线集合，找出未覆盖的元素中的最小者，令?行元素减去此数，?列元素加上此数，则原先选中的0元素不变，而未覆盖元素中至少有一个已转变为0，且新矩阵的指派问题与原问题也等价。上述过程可反复采用，直到能选取出足够的0元素为止。例如，对例5变换后的矩阵再变换，第三行、第五行元素减去2，第一列元素加上2，得
?7?4? ?0??11??00202?3000??8353?
?8004?4140???12345?现在已可看出，最优指派为??24135??。
??
