匈牙利解法（Hungarian method）
匈牙利解法简述
匈牙利解法是求解指派困难的一种新颖而又简便的解法，它是美国数学家库恩(Kuhn)于1955年提出的．库恩引用了匈牙利数学家康尼格(Konig)一个有关矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数，该种解法称为匈牙利法．
指派困难的最优解有如此一个性质，若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵，那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同．利用这个性质，可使原系数矩阵变换为含有很多0元素的新矩阵，而最优解维持不变．
匈牙利解法的步骤
具体操作为第一步：使指派困难的系数矩阵经变换，在各行各列中都显现0元素．(1)从系数矩阵的每行元素减去该行的最小元素；(2)再从所得系数矩阵的每列元素中减去该列的最小元素．第二步：执行试指派．若此时得到的mPn，应回到第一步，从新对系数矩阵执行变换。但要把第一步的过程改为(1)从系数矩阵的每列元素减去该列的最小元素；(2)再从所得系数矩阵的每行元素中减去该行的最小元素．如此做就致使新矩阵的0元素比较多些．再进入第二步执行试指派就可以得到最优解．利用前面的性质可以证明这个最优解就是我们所要求的原困难的最优解，进而致使求解变得更为简捷。
匈牙利解法的示例
步骤一：将这系数矩阵执行变换，使各行各列都显现0元素．从系数矩阵的每行元素减去该行的最小元素即得每行每列都有有0元素的系数矩阵．
步骤二：执行试指派，找出独立的0元素．独立0元素用Θ表明，其它0用Φ表明得到
……(1)
这里Θ的个数m=4,而n=5；困难没有得到求解，运用步骤三继续求解．
步骤三：作最少的直线覆盖所有的0元素，以确定该系数矩阵中能寻到最多的独立元素数．为此按下方步骤执行．
(1)对没有Θ的行打√号：；
(2)对已打√号的行中所含0元素的列打√号；
(3)再对所有打√号的列中的含有@元素的行打√号；
(4)重复2、3直到得不出新的打√号的行列为止．
(5)对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数．
令直线数为l．若l < n，表明务必再变换目前的系数矩阵，才可寻到n个独立的0元素，为此转换步骤四；若l = n，而m < n，应回到步骤二，另行试探．
在此例中，对矩阵(1)按下方次序执行：
先在第五行旁打√，接着可分析应在第一列下打√，接着在第3行旁打√，经检查不能再打√了．对没有打√行画一直线以覆盖0元素，对打√的列画一直线以覆盖0元素，得：
……(2)
自此可见l = 4 < n．所以应继续对(2)矩阵执行变换转步骤四．
步骤四：对(2)矩阵执行变换的目的是增长0元素．
为此在没有被直线覆盖的部分中找出最小元素．然后在打√行各元素中都减去这个最小元素，而在打√列的各元素上都加之这个最小元素，以保证原来0元素不变．如此得到新系数矩阵(它的最优解和原困难相同)．若得到n个独立的0元素，则已得最优解，否则回到步骤三重复执行．
在矩阵(2)中，在没有被覆盖部分(第3、5行)中寻到最小元素为2，然后在第3、5行各元素分别减去2。给第l列各元素加2，得到新矩阵(3)
……(3)
按步骤二，找出所有的独立0元素。得到矩阵(4)
……(4)
它具有n个独立0元素．这就得到了最优解，相应解矩阵为
由解矩阵得最优指派方案：
甲——B，乙——D，丙——E，丁——C，戊——A
所需总时间为minz=32．