匈牙利法是一件大的事物若除去一件小的事物，對這件事沒有多大影響。1955年，庫恩(W．W．Kuhn)利用匈牙利數學家康尼格(D．Konig)的關於矩陣中獨立“0”元素的定理，提出了求解指派問題的一種方法，習慣上稱之為匈牙利法。
基本介紹
- 中文名：匈牙利法
- 外文名：Hungarian method
- 所屬領域：運籌學
- 提出時間：1955年
- 提出人：庫恩
- 套用：求解指派問題
理論基礎,算法步驟,套用,
理論基礎
（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行有直線覆蓋時，令
；無直線覆蓋時。令
；
③當矩陣中的第j列有直線覆蓋時，令
；無直線覆蓋時，令
；
④令原矩陣的每個元素
分別減去
和
．
(6)回到(2)，反覆進行，直到矩陣的每一行都有一個加括弧的零元素為止。即找到最優分配方案。
在實際的任務分配中，還可能出現人員（或設備）數與任務數不相等的情況，而且要求每個人員只先完成一件任務（在人員數少於任務數時），或者有些人員可暫不安排任務（在人員數多餘任務數時），可稱這樣的問題為不平衡的指派問題，此時，可通過虛擬人員或虛擬任務使之轉化為一般（平衡）的指派問題，即在原矩陣中增加一些行或者列，使之成為方陣，在極小型問題中所增加的元素應充分的大，如為原矩陣中最大的元素的值，而在極大型問題中增加的元素應足夠的小。如可取零值。
套用
在實際中經常會遇到這樣的問題，某單位需要完成n項任務，恰好有n個人可以承擔這些任務。由於每個人的專長不同。同一件工作由不同的人去完成，效率(例如所花的時間或費用)是不同的，於是就會出現應分配哪個人去完成哪項任務，使完成這幾項任務的總效率最高(例如總時間最省、總費用最少等)．這類問題稱為分配問題，又稱為指派問題。
匈牙利法是最優利用生產資源，計算、調整最優分配方案變數的經營分析方法。其目的和衡量標準是在對資源、材料分配中的已知數據作變換處理的基礎上，提出所求取的目標對象(被測算的產品資源)的最優分配方案，它們的機會成本最小。即以未被採用的方案所造成的損失來衡量、評價被選擇方案的假定成本為零值方式，論證分配方案的最最佳化程度。其特點是在求解最優分配方案時，要求滿足約束條件前提下，產品加工的機會成本為零，由此使得總的加工成本為最低，並驗證方案變數的最優解和調整的幅度、限度。
