匈牙利法
匈牙利法
匈牙利法，是求解及小型（優化方向為極小）指派問題的一種方法，這種方法最初由w.w.kuhn提出，后經改進而形成，解法基於匈牙利數學家D.König給出的一個定理而得名。
匈牙決謂“配題”，“指派題”題。類題般敘述：題配完。完項務。
匈牙利法
述換，（）列含元素，稱列元素獨元素。
（2）若（bij）有n個獨立的0元素，由此可得一個解矩陣，方法為在X中令對應於（bij）的0元素位置的元素為1，其它位置的元素為0，則X為指派問題的最優解。
（3）D.König定理：矩陣中獨立0元素的最多個數等於能覆蓋所有0元素的最少直線數。
根據上面的原理，匈牙利法可分為如下的四個步驟：
1.對效率矩陣(cij)做變換得（bij），使（bij）中每行每列均有0元素，實現的方法是：
（1）從（cij）的每行元素中減去該行的最小元素；
（2）再從所得矩陣的每列元素中減去該列的最小元素，得（bij）.
2.求（bij）的獨立0元素。行列相間地對0元素給出兩種標記“*”和“△”，它們分別表示該元素“是”或“不是”獨立0元素，在所有的0元素全局有標記時，若獨立0元素（即標有*的0元素）的個數為n時，已得最優解，否則轉第3步，
標記的方法是：搜索含有未被標記的0元素且個數最少的行（或列），等概率地從中隨機選擇一個0元素給以標記*，並對該元素所在的行和列中其它未被標記的0元素給以標記△。
顯然標記過程可在有限步完成，從經濟意義上看，當給位置為(i,j) 的0元素標記*時，就意味著將第j項工作分配給第i個人員，此時完成任務的效率最高，同時對人員i和工作j的指派已經完成，需將對第i行和第j列的未被標記的0元素標記△,以示以後不再考慮它們的指派，應當說明：在按行（或列）進行標記時，若有多個未被標記的0元素時，上述方法只保證這種指派的局部最優性，在全局上是否最優依賴於獨立0元素的個數是否等於n .
3.確定矩陣（bij）中獨立0元素的最多個數m,當m
確定m的方法是：據（bij）中未被刪除的部分搜索不含標記*的0元素所在的行，給該行以標號“√”，若該行有標記為△的0元素，刪去該元素所在的列，在不具有滿足上述條件的行時，過程終止。設被標記的行數為k，刪去的列數為l。則m=n-k+l.
這一步的依據是D.König定理，這是因為對被刪除的每一列和未被標記的每一行做直線，這些直線式覆蓋所有0元素所需要的最少的直線，從而直線條數為（bij）中獨立0元素最多的個數，在m=n時，表示在第2步中某一次指派僅為局部最優，但不為全局最優，演演算法要求退回第2步，重新進行指派，第2步中關於等概率地隨機選取標記為*的0元素可使新指派得以實現。在m
4.對（bij）再做變換以增加獨立0元素的個數。
方法為：求出所有已標記“√”的行中且未被刪除部分包含元素的最小值，然後，所有已標記的行中的每一個元素（含已刪除部分）加上這一最小值，而它刪除的列中的每一個元素減去該值，得到一個新矩陣，仍記為（bij）,去掉所有的標記，轉第2步。
在人員數和任務n不是很大時，匈牙利法是求解指派問題的有效方法，且易於編製成軟體。
在實際問題中還可能遇到極大型的指派問題，我們可以將之轉化為極小型問題，然後應用匈牙利法求解，具體地，令C’ij=M-Cij， i，j=1,2,3,…,n
其中M為一個足夠大的正數以保證c’ij非負，例如可取M 為矩陣C中的最大元素，這樣可生成一個以（c’ij）為矩陣的極小型指派問題，由於，nM為固定的常數，兩個指派問題有最同的最優解。
在實際的任務分配中，還可能出現人員（或設備）數與任務數不相等的情況，而且要求每個人員只先完成一件任務（在人員數少於任務數時），或者有些人員可暫不安排任務（在人員數多餘任務數時），可稱這樣的問題為不平衡的指派問題，此時，可通過虛擬人員或虛擬任務使之轉化為一般（平衡）的指派問題，即在原矩陣中增加一些行或者列，使之成為方陣，在極小型問題中所增加的元素應充分的大，如為原矩陣中最大的元素的值，而在極大型問題中增加的元素應足夠的小。如可取零值。
目錄