匈牙利法
匈牙利法是一件大的事物若除去一件小的事物，對(duì)這件事沒(méi)有多大影響囤采。1955年，庫(kù)恩(W．W．Kuhn)利用匈牙利數(shù)學(xué)家康尼格(D．Konig)的關(guān)于矩陣中獨(dú)立“0”元素的定理惩淳，提出了求解指派問(wèn)題的一種方法蕉毯，習(xí)慣上稱(chēng)之為匈牙利法。
理論基礎(chǔ)
（1）若從效率矩陣(cij)的行（或列）的各元素中分別減去該行（或列）的最小元素后得到一個(gè)新矩陣（bij）,則以（bij）為效率矩陣的指派問(wèn)題與原問(wèn)題有相同的最優(yōu)解。
經(jīng)過(guò)上述變換后代虾，（bij）中的每行和每列都至少含有一個(gè)0元素进肯，稱(chēng)位于不同行不同列的0元素為獨(dú)立的0元素。
（2）若（bij）有n個(gè)獨(dú)立的0元素棉磨，由此可得一個(gè)解矩陣江掩，方法為在X中令對(duì)應(yīng)于（bij）的0元素位置的元素為1，其它位置的元素為0含蓉，則X為指派問(wèn)題的最優(yōu)解频敛。
（3）矩陣中獨(dú)立0元素的最多個(gè)數(shù)等于能覆蓋所有0元素的最少直線(xiàn)數(shù)。
算法步驟
匈牙利法的算法步驟如下：
(1)對(duì)指派問(wèn)題的系數(shù)矩陣進(jìn)行變換馅扣，使每行每列至少有一個(gè)元素為“0”．
①讓系數(shù)矩陣的每行元素去減去該行的最小元素小作；
②再讓系數(shù)矩陣的每列元素減去該列的最小元素昼捍。
(2)從第一行開(kāi)始，若該行只有一個(gè)零元素，就對(duì)這個(gè)零元素加括號(hào)抓狭，對(duì)加括號(hào)的零元素所在的列畫(huà)一條線(xiàn)覆蓋該列，若該行沒(méi)有零元素或者有兩個(gè)以上零元素(已劃去的不算在內(nèi))袒炉，則轉(zhuǎn)下一行氧腰，依次進(jìn)行到最后一行。
(3)從第一列開(kāi)始妆偏，若該列只有一個(gè)零元素刃鳄。就對(duì)這個(gè)零元素加括號(hào)(同樣不、考慮已劃去的零元素)钱骂。再對(duì)加括號(hào)的零元素所在行畫(huà)一條直線(xiàn)覆蓋該列叔锐。若該列沒(méi)有零元素或有兩個(gè)以上零元素，則轉(zhuǎn)下一列见秽，依次進(jìn)行到最后一列為止愉烙。
(4)重復(fù)上述步驟(1)和(2)可能出現(xiàn)3種情況：
①效率矩陣每行都有加括號(hào)的零元素，只要對(duì)應(yīng)這些元素令
就找到了最優(yōu)解解取。
②加括號(hào)的零元素個(gè)數(shù)少于m步责，但未被劃去的零元素之間存在閉回路，這時(shí)順著閉回路的走向禀苦，對(duì)每個(gè)間隔的零元素加一個(gè)括號(hào)蔓肯，然后對(duì)所有加括號(hào)的零元素所在行(或列)畫(huà)一條直線(xiàn)，同樣得到最優(yōu)解伦忠。
③矩陣中所有零元素或被劃去省核，或加上括號(hào)．但加括號(hào)的零元素少于m昆码，這時(shí)轉(zhuǎn)入(5)．
(5)按定理進(jìn)行如下變換：
①?gòu)木仃囄幢恢本€(xiàn)覆蓋的數(shù)字中找出一個(gè)最小的k邻储；
②當(dāng)矩陣中的第i行有直線(xiàn)覆蓋時(shí)旧噪，令Ui=0吨娜；無(wú)直線(xiàn)覆蓋時(shí)。令Ui=K淘钟；
③當(dāng)矩陣中的第j列有直線(xiàn)覆蓋時(shí)，令Vj=-K米母；無(wú)直線(xiàn)覆蓋時(shí)，令Vj=0铁瞒；
④令原矩陣的每個(gè)元素Aij分別減去Ui和Vj．
(6)回到(2)妙色，反復(fù)進(jìn)行，直到矩陣的每一行都有一個(gè)加括號(hào)的零元素為止慧耍。即找到最優(yōu)分配方案身辨。[1]
在實(shí)際的任務(wù)分配中芍碧，還可能出現(xiàn)人員（或設(shè)備）數(shù)與任務(wù)數(shù)不相等的情況，而且要求每個(gè)人員只先完成一件任務(wù)（在人員數(shù)少于任務(wù)數(shù)時(shí)）泌豆，或者有些人員可暫不安排任務(wù)（在人員數(shù)多余任務(wù)數(shù)時(shí)），可稱(chēng)這樣的問(wèn)題為不平衡的指派問(wèn)題洗贰，此時(shí)陨倡，可通過(guò)虛擬人員或虛擬任務(wù)使之轉(zhuǎn)化為一般（平衡）的指派問(wèn)題，即在原矩陣中增加一些行或者列兴革，使之成為方陣蜜唾，在極小型問(wèn)題中所增加的元素應(yīng)充分的大，如為原矩陣中最大的元素的值袁余，而在極大型問(wèn)題中增加的元素應(yīng)足夠的小。如可取零值棚饵。
