匈牙利解法是求解指派问题的一种简便的解法，它提出首先由匈牙利数学家柯尼希提出。匈牙利解法利用了定理：係数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数。
指派问题的最优解有这样一个性质，若从係数矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵，那幺以新矩阵为係数矩阵求得的最优解和用原矩阵求得的最优解相同。利用这个性质，可使原係数矩阵变换为含有很多0元素的新矩阵，而最优解保持不变。
基本介绍
- 中文名：匈牙利解法
- 外文名：Hungarian method
- 学科：数学
- 套用：求解指派问题
- 提出者：柯尼希
- 条件：目标要求为min等
匈牙利解法的适用条件
匈牙利解法的适用于基于任务分配问题的标準型，标準型要满足下述三个条件：
（1）目标要求为min；
（2）效率矩阵
为n阶方阵；
（3）阵中所有元素
，且为常数。
求解步骤
指派问题的匈牙利法求解步骤：
（1）变换指派问题的係数矩阵(
) 为(
) ，使在(
) 的各行各列中都出现0元素，即从(
)的每行元素都减去该行的最小元素；再从所得新係数矩阵的每列元素中减去该列的最小元素。
（1）进行试指派，以寻求最优解。在(
)中找儘可能多的独立0元素，若能找出n 个独立0元素，就以这n 个独立0元素对应解矩阵(
)中的元素为1，其余为0，这就得到最优解。
找独立0元素，常用的步骤为：
1) 从只有一个0元素的行开始，给该行中的0元素加圈，记作◎ 。然后划去◎ 所在列的其它0元素，记作Ø ；这表示该列所代表的任务已指派完，不必再考虑别人了。依次进行到最后一行。
2) 从只有一个0元素的列开始（画Ø的不计在内），给该列中的0元素加圈，记作◎；然后划去◎ 所在行的0元素，记作Ø ，表示此人已有任务，不再为其指派其他任务了。依次进行到最后一列。
3) 若仍有没有划圈的0元素，且同行(列) 的0元素至少有两个，比较这行各0元素所在列中0元素的数目，选择0元素少这个0元素加圈(表示选择性多的要“礼让”选择性少的) 。然后划掉同行同列的其它0元素。可反覆进行，直到所有0元素都已圈出和划掉为止。
4) 若◎ 元素的数目m 等于矩阵的阶数n （即：m =n ），那幺这指派问题的最优解已得到。若m < n，则转入下一步。
（3）用最少的直线通过所有0元素。其方法：
1) 对没有◎的行打“√”；
2) 对已打“√” 的行中所有含Ø元素的列打“√” ；
3) 再对打有“√”的列中含◎ 元素的行打“√” ；
4) 重複1)、2)直到得不出新的打√号的行、列为止；
5) 对没有打√号的行画横线，有打√号的列画纵线，这就得到覆盖所有0元素的最少直线数 l。
注：l 应等于m ，若不相等，说明试指派过程有误，回到第2步，另行试指派；若l =m < n ，表示还不能确定最优指派方案，须再变换当前的係数矩阵，以找到n 个独立的0元素，为此转第（4）步。
（4）变换矩阵(
) 以增加0元素。在没有被直线通过的所有元素中找出最小值，没有被直线通过的所有元素减去这个最小元素；直线交点处的元素加上这个最小值。新係数矩阵的最优解和原问题仍相同。转回第（2）步。
示例
求解下图问题。
（1）将这係数矩阵进行变换，使各行各列都出现0元素．从係数矩阵的每行元素减去该行的最小元素即得每行每列都有有0元素的係数矩阵。
（2）进行试指派，找出独立的0元素。独立0元素用Θ表示，其它0用Φ表示得到（矩阵(1)）。
这里Θ的个数m=4，而n=5；问题没有得到求解，运用步骤（3）继续求解。
（3）作最少的直线覆盖所有的0元素，以确定该係数矩阵中能找到最多的独立元素数．为此按以下步骤进行．
(1) 对没有Θ的行打√号：；
(2) 对已打√号的行中所含0元素的列打√号；
(3) 再对所有打√号的列中的含有@元素的行打√号；
(4) 重複2、3直到得不出新的打√号的行列为止．
(5) 对没有打√号的行画一横线，有打√号的列画一纵线，这就得到覆盖所有0元素的最少直线数．
令直线数为l。若l<n，说明必须再变换当前的係数矩阵，才能找到n个独立的0元素，为此转换步骤四；若l=n，而m<n，应回到步骤（2），另行试探。
在此例中，对矩阵(1)按以下次序进行：先在第五行旁打√，接着可判断应在第一列下打√，接着在第3行旁打√，经检查不能再打√了．对没有打√行画一直线以覆盖0元素，对打√的列画一直线以覆盖0元素，得（矩阵(2)）：
由此可见l= 4 <n．所以应继续对矩阵(2)进行变换转步骤（4）。
（4）对矩阵(2)进行变换的目的是增加0元素。
为此在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这个最小元素，而在打√列的各元素上都加上这个最小元素，以保证原来0元素不变。这样得到新係数矩阵(它的最优解和原问题相同)．若得到n个独立的0元素，则已得最优解，否则回到步骤三重複进行。
在矩阵(2)中，在没有被覆盖部分(第3、5行)中找到最小元素为2，然后在第3、5行各元素分别减去2。给第l列各元素加2，得到新矩阵(3)：
按步骤（2），找出所有的独立0元素。得到矩阵(4)：
它具有n个独立0元素．这就得到了最优解，相应解矩阵为：
由解矩阵得最优指派方案： 甲——B，乙——D，丙——E，丁——C，戊——A，所需总时间为minz=32。
