1、匈牙利算法示例,信管網(wǎng)()：最專業(yè)信息系統(tǒng)項目管理師網(wǎng)站,（二）、解題步驟：,指派問題是0-1 規(guī)劃的特例，也是運輸問題的特例，當(dāng)然可用整數(shù)規(guī)劃，0-1 規(guī)劃或運輸問題的解法去求解，這就如同用單純型法求解運輸問題一樣是不合算的。利用指派問題的特點可有更簡便的解法，這就是匈牙利法，即系數(shù)矩陣中獨立 0 元素的最多個數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。,第一步：變換指派問題的系數(shù)矩陣（cij）為(bij)，使在(bij)的各行各列中都出現(xiàn)0元素，即 (1) 從（cij）的每行元素都減去該行的最小元素； (2) 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。,第二步：進行試指派，以尋求最優(yōu)解

2、。 在(bij)中找盡可能多的獨立0元素，若能找出n個獨立0元素，就以這n個獨立0元素對應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。找獨立0元素，常用的步驟為： (1)從只有一個0元素的行(列)開始，給這個0元素加圈，記作 。然后劃去 所在列(行)的其它0元素，記作 ；這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 (2)給只有一個0元素的列(行)中的0元素加圈，記作；然后劃去 所在行的0元素，記作 (3)反復(fù)進行(1)，(2)兩步，直到盡可能多的0元素都被圈出和劃掉為止。,(4)若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個，則從剩有0元素最少的行(列)開始，比較這

3、行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其它0元素?？煞磸?fù)進行，直到所有0元素都已圈出和劃掉為止。 （5）若 元素的數(shù)目m 等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。 第三步：作最少的直線覆蓋所有0元素。 (1)對沒有的行打號； (2)對已打號的行中所有含元素的列打號； (3)再對打有號的列中含 元素的行打號；,(4)重復(fù)(2)，(3)直到得不出新的打號的行、列為止； (5)對沒有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋所有0元素的最少直線數(shù) l 。l 應(yīng)等于m，若不相等，

4、說明試指派過程有誤，回到第二步(4)，另行試指派；若 lm n，須再變換當(dāng)前的系數(shù)矩陣，以找到n個獨立的0元素，為此轉(zhuǎn)第四步。 第四步：變換矩陣(bij)以增加0元素。 在沒有被直線覆蓋的所有元素中找出最小元素，然后打各行都減去這最小元素；打各列都加上這最小元素（以保證系數(shù)矩陣中不出現(xiàn)負(fù)元素）。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第二步。,例一：,2,4,9,7,4,2,有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？,例二、,求解過程如下： 第一步，變換系數(shù)矩陣：,5,第二步，試指派：,找到 3 個獨立零元素 但 m = 3 n = 4,第三步，作最少的直線覆蓋所有0元素：,獨立零元素的個數(shù)m等于最少直線數(shù)l，即lm=3n=4；,第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打各行都減去1；打各列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派：,得到4個獨立零元素， 所以最優(yōu)解矩陣為：,15,練習(xí)：,11,5,7,6,4,戊,6,9,6,3,7,丁,8,6,4,5,8,丙,9,11,7,12,9,乙,11,8,9,5,7,甲,E,D,C,B,A,