匈牙利解法概述_匈牙利解法的步骤_匈牙利解法

匈牙利解法概述
　　匈牙利解法是求解指派问题的一种新颖而又简便的解法，它是美国数学家库恩(Kuhn)于1955年提出的．库恩引用了匈牙利数学家康尼格(Konig)一个关于矩阵中0元素的定理：系数矩阵中独立0元素的最多个数等于能覆盖所有0元素的最小直线数，这种解法称为匈牙利法．

　　指派问题的最优解有这样一个性质，若从系数矩阵的一行(列)各元素中分别减去该行(列)的最小元素，得到新矩阵，那么以新矩阵为系数矩阵求得的最优解和用原矩阵求得的最优解相同．利用这个性质，可使原系数矩阵变换为含有很多0元素的新矩阵，而最优解保持不变．

匈牙利解法的步骤
　　具体操作为第一步：使指派问题的系数矩阵经变换，在各行各列中都出现0元素．(1)从系数矩阵的每行元素减去该行的最小元素；(2)再从所得系数矩阵的每列元素中减去该列的最小元素．第二步：进行试指派．若此时得到的mPn，应回到第一步，重新对系数矩阵进行变换。但要把第一步的过程改为(1)从系数矩阵的每列元素减去该列的最小元素；(2)再从所得系数矩阵的每行元素中减去该行的最小元素．这样做就使得新矩阵的0元素比较多些．再进入第二步进行试指派就可以得到最优解．利用前面的性质可以证明这个最优解就是我们所要求的原问题的最优解，从而使得求解变得更为简捷。