淺析指派問題的匈牙利解法成稿講解

1、洛陽師范學(xué)院本科畢業(yè)論文淺析指派問題的匈牙利解法胡小芹數(shù)學(xué)科學(xué)學(xué)院數(shù)學(xué)與應(yīng)用數(shù)學(xué)學(xué)號 :040414057指導(dǎo)教師 :蘇孟龍摘要 : 對于指派問題 , 可以利用許多理論進(jìn)行建模并加以解決,但匈牙利解法是解決指派問題的一種非常簡單有效的方法,并且可以解決多種形式的指派問題,但匈牙利算法本身存在著一些問題,本文主要介紹了匈牙利算法的基本思想,基本步驟 ,以及它的改進(jìn)方法 .在匈牙利算法的基礎(chǔ)上,本文還介紹了兩種更簡便實(shí)用的尋找獨(dú)立零元素的方法最小零元素消耗法和對角線法.關(guān)鍵詞 : 指派問題 ;匈牙利解法 ;最小零元素消耗法 ;對角線法0 引言在現(xiàn)實(shí)生活中經(jīng)常會(huì)遇到把幾個(gè)任務(wù)分派給幾個(gè)不同的對象去完

2、成, 由于每個(gè)對象的條件不同 , 完成任務(wù)的效率和效益亦不同 . 指派問題的目標(biāo)就是如何分派使所消耗的總資源最少（或總效益最優(yōu)） , 如給工人分派工作 , 給車輛分配道路 , 給工人分配機(jī)床等等 , 同時(shí)許多網(wǎng)絡(luò)問題 （如旅行問題 , 任務(wù)分配問題 , 運(yùn)輸問題等） , 都可以演化成指派問題來解決 . 在現(xiàn)實(shí)生活中 , 指派問題是十分常見的問題 , 而匈牙利解法是解決指派問題的一種非常簡單有效的方法 . 本文主要介紹匈牙利解法的基本原理及思想 , 解題步驟 , 不足與改進(jìn) , 以使匈牙利法更能有效地解決指派問題 .1 指派問題及其數(shù)學(xué)模型指派問題是指由 m 項(xiàng)任務(wù) , 需要 n 個(gè)人來承擔(dān) ,

3、 每人只能承擔(dān)一項(xiàng)任務(wù), 且每項(xiàng)1洛陽師范學(xué)院本科畢業(yè)論文任務(wù)只能有一人來承擔(dān), 由于各人的專長不同, 各人完成的任務(wù)不同, 導(dǎo)致其效率也各不相同 . 因此 , 就產(chǎn)生怎樣科學(xué)地指派任務(wù) , 才能使完成各項(xiàng)任務(wù)所消耗的總資源最少（或總成本最低等） , 由于 m, n 不同 , 指派問題可分為以下三種情況 :第一、當(dāng) mn 時(shí), 即為每人指派一項(xiàng)任務(wù).第二、當(dāng) mn 時(shí), 即任務(wù)數(shù)人數(shù) , 這時(shí)可虛設(shè) (mn) 個(gè)人構(gòu)成 mm 的效率矩陣 , 并且這 (mn) 個(gè)人在執(zhí)行這 m 項(xiàng)任務(wù)時(shí)的效率應(yīng)該是效率最高.第三、當(dāng) mn 時(shí), 即配置人數(shù)任務(wù)數(shù) , 這時(shí)應(yīng)虛設(shè) ( nm) 項(xiàng)任務(wù) , 并且這

4、n 個(gè)人在執(zhí)行這 (nm) 項(xiàng)任務(wù)時(shí)的成本最低 .通過虛設(shè)任務(wù)或人 , 指派問題的效率矩陣都可以轉(zhuǎn)化成方陣. 匈牙利解法要求指派問題最小化 , 其數(shù)學(xué)模型為設(shè)用 cij0 (i , j1,2, n ) 表示指派第 i 個(gè)人去完成第j 項(xiàng)任務(wù)時(shí)所用的時(shí)間,定義決策變量xij1表示第 i 個(gè)人完成第 j項(xiàng)任務(wù) ,0表示不指派第 i 個(gè)人完成第 j 項(xiàng)任務(wù) .則問題可轉(zhuǎn)化為 0-1 線性規(guī)劃問題 :nnmin Zciji1j 1nxij1,j1,2, n,i1s tnxij1,i1,2, n,j1xij或i,j1,2,.01,n如果指派問題要求的是最大化問題如max F , 則可以轉(zhuǎn)化為最小化問題,

5、 一般方 法 是 :取 Mmax c(i , j 1,2 n), 令bM c (i , j 1,2 , n),則ijijijnnmin fbij , 有 FnMf ,從而求 max F .i 1j 12 指派問題的解法匈牙利解法2洛陽師范學(xué)院本科畢業(yè)論文“匈牙利解法”最早是由匈牙利數(shù)學(xué)家D.Konig 用來求矩陣中 0 元素的一種方法 , 由此他證明了“矩陣中獨(dú)立0 元素的最大個(gè)數(shù)等于能覆蓋所有0 元素的最少直線數(shù)” .1955 年由 W.W.Knhu 在求解著名的指派問題時(shí)引用了這一結(jié)論, 并對具體解法做了改進(jìn) , 仍稱為匈牙利解法 .2.1 匈牙利解法的基本原理和解題思想從根本上講 , 求

6、指派問題的最優(yōu)解就是要在 n 階方陣中找到 n 個(gè)這樣的元素 , 它們分布在不同行不同列上 , 并且這些元素之和為最小 , 而要使這些元素之和為最小 , 就要使其中的每一個(gè)元素盡可能的小最好這些元素都是其所在行所在列上的最小元素 .而指派問題的最優(yōu)解又具有這樣的性質(zhì)（定理1）: 若從系數(shù)矩陣 (cij ) 的每行（列）各元素中分別減去該行（列）的最小元素, 得到的新矩陣 (bij ) , 那么以 (bij ) 為系數(shù)矩陣求得的最優(yōu)解與用(cij ) 求得最優(yōu)解相同 .由于新矩陣 (bij ) 中每行每列都有最小元“0 ”, 因此 , 求原指派問題的最優(yōu)解轉(zhuǎn)化為在 (bij ) 中指出 n 個(gè)分

7、布在不同行不同列上的“0 ”元素（簡稱為獨(dú)立 0 元素） ,而根據(jù)考尼格（ Konig ）證明的定理（定理 2）: 矩陣中獨(dú)立元素的 0 最多個(gè)數(shù)等于能覆蓋所有零元素的最少直線數(shù) , 利用這一定理 , 就可以通過尋找“能覆蓋所有零元素的最少直線數(shù)” 來確定 (bij ) 中獨(dú)立元 0 素的具體數(shù)量 . 若 (bij ) 中獨(dú)立 0 元素的個(gè)數(shù)少于矩陣的階數(shù) n , 就要繼續(xù)對矩陣 (bij ) 進(jìn)行化簡 , 直到找到 n 個(gè)獨(dú)立 0 元素為止 , 這就是匈牙利解法的基本原理和解題思想 .2.2 匈牙利解法的解題步驟第一步 : 變換效益矩陣 , 使新矩陣中的每行每列至少有一個(gè)0 .（1）行變換

8、: 找出每行最小元素 , 再從該行各元素中減去這個(gè)最小元素.（2）列變換 : 從所得新矩陣中找出每列中的最小元素 , 再從該列各元素中減去這個(gè)最小元素 .第二步 : 進(jìn)行試指派 , 以尋找最優(yōu)解 .（1）逐行檢查從第一行開始 , 如果該行只有一個(gè)零元素, 就對這個(gè)零元素打上括號, 劃去與3洛陽師范學(xué)院本科畢業(yè)論文打括號零元素同在一列的其他零元素 , 如果該行沒有零元素 , 或有兩個(gè)或多個(gè)零元素（已劃去的不計(jì)在內(nèi)） , 則轉(zhuǎn)下行 .打括號的意義可理解為該項(xiàng)任務(wù)已分配給某人 . 如果該行只有一個(gè) 0 , 說明只能有唯一分配 . 劃掉同列括號零元素可理解為該任務(wù)已分配 , 此后不再考慮分配給他人 .

9、 當(dāng)該行有兩個(gè)或更多的零元素時(shí) , 不計(jì)括號內(nèi)的 , 其理由是至少有兩個(gè)分配方案 , 為使以后分配時(shí)具有一定的靈活性 , 故暫不分配 .（2）逐列檢查在行檢查的基礎(chǔ)上 , 由第一列開始檢查 , 如果該列只有一個(gè)零元素 , 就對這個(gè)零元素打括號 , 再劃去與打括號零元素同行的其它零元素 . 若該列沒有零元素或有兩個(gè)以上零元素 , 則轉(zhuǎn)下一列 .（3）重復(fù)（ 1）、（2）兩步后 , 可能出現(xiàn)以下三種情況 : 每行都有一個(gè)零元素標(biāo)出括號, 顯然打括號的零元素必然位于不同行不同列 , 因此得到最優(yōu)解 . 每行每列都有兩個(gè)或兩個(gè)以上的零 , 這表示對這個(gè)人可以分配不同任務(wù)中的任意一個(gè) . 這時(shí)可以從所剩

10、零元素最少的行開始 , 比較這行各零元素所在列中元素的個(gè)數(shù) , 選擇零元素少的那列這個(gè)零元素打括號 , 劃掉同行同列的其他它零元素 ,然后重復(fù)前面的步驟 , 直到所有 0 都作了標(biāo)記 . 矩陣中所有零都作了標(biāo)記 , 但標(biāo)有 ( 0 ) 的元素個(gè)數(shù)少于 m 個(gè) , 則轉(zhuǎn)下步 . 第三步 : 做最少的直線覆蓋所有零元素 , 以確定該系數(shù)矩陣中能找到最多的獨(dú)立 0 元素 . 對沒有（）的行打 ; 對打的行上所有含 0 元素的列打 ; 再對打的列上有（）的行打 ; 重復(fù)上兩步 , 直到過程結(jié)束 ; 對沒有打的行劃橫線 , 對所有打的列劃垂線 .這就得到了能覆蓋矩陣中所有0 元素的最少直線數(shù) .第四步

11、: 非最優(yōu)陣的變換零元素的移動(dòng).（ 1）在沒有被直線覆蓋的所有元素中 , 找出最小元素 ;（ 2）所有未被直線覆蓋的元素都減去這個(gè)最小元素 ;4洛陽師范學(xué)院本科畢業(yè)論文（ 3）覆蓋線十字交叉處的元素都加上這個(gè)最小元素 ; （ 4）只有一條直線覆蓋的元素的值保持不變 .第五步 : 回到第二步 , 反復(fù)進(jìn)行 , 直到矩陣中每行每列都有一個(gè)打（）的0 元素為止 , 即找到最優(yōu)解 .2.3 匈牙利算法的一點(diǎn)注記（1）匈牙利算法第一步變換效益矩陣使每行每列都出現(xiàn)零元素 , 一般方法是先行變換 , 再列變換 , 但先列變換再行變換最優(yōu)解不變 .（2）有些時(shí)候先行后列變換后不能得到最優(yōu)解 , 但先列后行變換

12、時(shí)卻能直接找到最優(yōu)解 , 從而減少了計(jì)算步驟 , 使計(jì)算簡明 . 如下所示 :先行變換 , 再列變換得21097(0)82515414811(0)54B141611B3(0)013241513901145只找到三個(gè)獨(dú)立 0 元素 , 不是最優(yōu)解 . 那么先列變換 , 后行變換得2109706(0)015414813(0)51B141611B63(0)137415139(0)920每行每列都有“ ( 0 ) ” , 得到最優(yōu)解 .3 匈牙利法的不足與改進(jìn)3.1 不足和改進(jìn)（一）以上是匈牙利法的常規(guī)解題方法 , 雖然能有效地解決指派問題 , 但是其解題過程中還存在以下兩點(diǎn)不足 :第一、在匈牙利算法

13、的第二步中用“試指派”的方法尋找獨(dú)立0 元素 , 道理簡單 , 也能很快找到獨(dú)立 0 元素 , 但對于一個(gè) n 階方陣 , 這些獨(dú)立 0 元素在矩陣中可能有 n 種排列方式 , 這樣在矩陣中標(biāo)出來的獨(dú)立 0 元素排列很亂 , 沒有規(guī)律 . 另外 , 對于某些矩陣 0 元素排列的比較有規(guī)律 , 本可以用別的更簡單的方法尋找獨(dú)立 0 元素 ,而用這種“一般性”的方法比較麻煩.第二、在匈牙利算法的第三步“做最少的直線覆蓋所有0 元素”過程中 , 一會(huì)5洛陽師范學(xué)院本科畢業(yè)論文兒針行 , 一會(huì)兒針對列 , 一會(huì)兒對沒有（）的打 , 一會(huì)兒又對有（）的打 , 一會(huì)對沒有打號的（行）劃線 , 一會(huì)又對打號

14、的（列）劃線 , 這樣變來變?nèi)チ钊藭烆^轉(zhuǎn)向 , 稍不注意就會(huì)出錯(cuò), 特別是對于這種畫法每一步的意圖以及內(nèi)在原理, 大多數(shù)人難以理解 , 具體步驟很難記住, 難以掌握 , 這就影響了這一理論在實(shí)際工作中的應(yīng)用 .算法的改進(jìn) :第一、尋找獨(dú)立 0 元素的一種新方法對角線法.對角線法的原理 : 根據(jù)要在指派問題化簡后的系數(shù)矩陣( bij ) 中找出 n 個(gè)獨(dú)立 0元素 , 而這些獨(dú)立 0 元素又分布在方陣的不同行不同列上 , 利用這一特點(diǎn) , 我們可以對矩陣 ( bij ) 的行（或列）進(jìn)行某種調(diào)換 , 就一定可以使這些獨(dú)立 0 元素按矩陣的對角線排列 , 這樣凡是出現(xiàn)在對角線上的零元素一定是獨(dú)立

15、0 元素 , 而非對角線上的零元素也一定是非獨(dú)立 0 元素 , 這樣我們既能很快找到所有獨(dú)立 0 元素 , 又能直觀地發(fā)現(xiàn)矩陣中獨(dú)立 0 元素的個(gè)數(shù) .方法 : 從 0 元素?cái)?shù)量最少的行開始 , 選擇該列第一個(gè) 0 元素 , 根據(jù)該 0 元素所在行的位置確定該列元素在新矩陣中列的位置 （若該 0 元素所在行是第 i 行, 那么就將該 0 元素所在列放在新矩陣的第 i 列）, 并在原矩陣中劃去這一列 , 并劃掉同行其它 0 元素 , 再在剩下的矩陣中重新比較各列 0 元素的數(shù)量 , 并按前面方法進(jìn)行 , 直至完成.這樣就可以將所有獨(dú)立 0 元素集中放在新矩陣的對角線上, 當(dāng)對角線上全為 0時(shí),

16、就得到了指派問題的最優(yōu)解, 如果對角線上某一處不為0 , 說明該矩陣中獨(dú)立 0元素?cái)?shù)量不足 , 這時(shí)需要對矩陣作進(jìn)一步化簡 .應(yīng)用示例 :尋找矩陣 B 中的獨(dú)立 0 元素505050500505B =2003B =2003B10032（第一列與第四0440044044000401040140105050列交換）或 B22300（第二列與第四列交換）004401046洛陽師范學(xué)院本科畢業(yè)論文第二、最少直線的一種簡單畫法.畫法原理 : 根據(jù)定理“矩陣中獨(dú)立0 元素的最多個(gè)數(shù)恰好等于能覆蓋所有0 元素的最少直線數(shù)” , 也就是說矩陣中有多少個(gè)獨(dú)立0 元素 , 就需要多少條直線將所有0 元素覆蓋 ,

17、而從匈牙利法解題步驟看矩陣中獨(dú)立0 元素的數(shù)量 m 及位置 , 在劃線前是已知 , 所以覆蓋 0 元素的最少直線數(shù) m 也是已知的 .由于任意兩個(gè)獨(dú)立0 元素“ ( 0 ) ”都不同行且不同列, 而蓋 0 線也只能按矩陣的行或列來劃 , 因此 , 一條蓋 0 線只能覆蓋一個(gè)“ ( 0 ) ”, 要覆蓋 m 個(gè)“ ( 0 ) ”就需要 m 個(gè)直線 . 基于“蓋 0 線”與獨(dú)立 0 元素“ ( 0 ) ”之間數(shù)量的一對一關(guān)系 , 只要我們始終圍繞著獨(dú)立 0 元素“( 0 ) ”來畫線 , 首先就能用最少的直線覆蓋所有的獨(dú)立 0元素 . 另外 , 由于矩陣中的非獨(dú)立 0 元素總是和某個(gè)獨(dú)立 0 元素

18、在同一行或同一列 , 因此畫蓋“ ( 0 ) ”線時(shí) , 只要我們能使每條蓋 0 線都盡可能多的附帶非獨(dú)立 0 元素 , 那我們就能實(shí)現(xiàn)用最少的直線覆蓋所有 0 元線 .具體畫法 :（1）標(biāo)記對“ ( 0 ) ”所在行和列上的 0 元素?cái)?shù)量在行列旁予以標(biāo)注 , 對沒有“ ( 0 ) ”的行與列的打號予以標(biāo)記 .（2）畫線從有 “ ( 0) ”的行與列中找出 0 元素最多的行（或列）畫一橫（或縱）線覆蓋這些 0 元素 .（3）修正從 “( 0 ) ”所在行與列上的 0 元素?cái)?shù)量減去已被覆蓋的0 元素?cái)?shù) .（4）重復(fù)上述過程 , 直至覆蓋所有 0 元素 .上述方法的關(guān)鍵是緊緊抓住獨(dú)立0 元素其所在

19、行與列上的0 元素的多少?zèng)Q定蓋 0 線的畫法（即畫線的先后和方向 , 橫向還是縱向） , 使每條線都能覆蓋盡可能多的 0 元素 . 另外 , 因某些非獨(dú)立 0 元素處在可被兩條蓋 0 線同時(shí)覆蓋的交叉點(diǎn)上 , 為減少重復(fù)性覆蓋 , 每畫一條線后都要對各行各列 0 元素?cái)?shù)予以修正（從中減去已被覆蓋的 0 元素?cái)?shù)） .示例 :試用最少的直線覆蓋下列矩陣中的所有0 元素5(0)2025(0)2022230(0)0230(0)03B(0)10572B (0)10572198(0)0498(0)04206365063657洛陽師范學(xué)院本科畢業(yè)論文21 235(0)20225(0)2020230(0)00

20、230(0)00B(0)105721B (0)10572198(0)04298(0)04206365063652 112 1 5(0)2020230(0)00B(0)10572198(0)040063652注意 : 當(dāng)矩陣中的行和列旁標(biāo)的 0 元素的數(shù)量相等時(shí) , 我們從中任意選擇一個(gè)畫線 , 但是當(dāng)此行（或列）中的 0 元素所對列（或行）中無“ ( 0 ) ”時(shí) , 只能先劃去此行（或列） . 比如上面的矩陣 B 中 , 第二行和第四列中 0 元素相等 , 都是最多（ 3 個(gè)） , 若先劃去第四列 , 則第二行中第五列中的 0 元素用這種方法無法劃去 , 若要?jiǎng)澣ミ@個(gè) 0 元素 , 則直線增

21、多 .3.2 不足和改進(jìn)（二）用于解決指派問題的匈牙利解法 , 在運(yùn)算過程中存在著兩個(gè)問題 : 第一、算法不完善 . 從未標(biāo)零元素最少的行取定 0 元素 , 不能保證 0 元素所在的列未標(biāo)零元素最少 . 因此 , 系數(shù)矩陣已存在最大匹配 , 但無法取得最大匹配 , 而算法中途停止 . 第二、計(jì)算步驟煩瑣 . 當(dāng) 0 元素不夠又沒有未標(biāo)零元素時(shí) , 作直線覆蓋 , 移動(dòng)零元素 , 然后再取定 0 元素 , 反復(fù)進(jìn)行 .一 改進(jìn)算法1 完善匈牙利算法選取零元素時(shí) , 若被劃行未標(biāo)零元素多于一個(gè) , 則要保證所標(biāo)的零元素所在的列未標(biāo)零元素最少利用此方法可以解決問題一2 改進(jìn)算法步驟（1）利用匈牙利算

22、法 , 由系數(shù)矩陣 (cij ) 得到各行各列都有零元素的等效矩陣8洛陽師范學(xué)院本科畢業(yè)論文(bij ) .（2）若有未劃零元素 , 則選有未劃零元素最多的行或列作直線覆蓋, 直到?jīng)]有未劃零元素為止（3）若直線數(shù)目小于 n , 則在未劃元素中選取最小元素 , 未劃的各元素減去最小元素 , 直線交叉處的元素均加最小元素 , 轉(zhuǎn)2. 否則轉(zhuǎn) 4.（4）選取有未標(biāo)零元素最少的行( 或列 ) 取未標(biāo)零元素 , 記( 0 ), 同行同列的未標(biāo)零元素記 ; 若該行 ( 或列 ) 未標(biāo)零元素多于一個(gè) , 則選列 ( 或行 ) 中未標(biāo)零元素最少的本行未標(biāo)零元素為 ( 0 ), 直到 ( 0 ) 元素個(gè)數(shù)等于

23、n 為止（5）結(jié)束算法 , 得到最大匹配 . 令對應(yīng)于 ( 0 ) 的 xij1 , 其余的 xij0 , 并計(jì)算目標(biāo)函數(shù)值二 定義及定理定義 1 作直線覆蓋時(shí) , 被直線覆蓋的元素 , 稱為已劃元素 . 未被直線覆蓋的元素, 稱為未劃元素定義 2 求最大匹配時(shí) , 已作記號 ( 0 ) 和 的零元素稱為已標(biāo)元素 , 未作記號的零元素稱為未標(biāo)零元素定理矩陣 (bij ) 中已存在最大匹配的充要條件是直線覆蓋其中全部零元素的最少數(shù)目為 n 證明必要性若 (bij ) 中有最大匹配 , 則 (bij ) 中存在 n 個(gè)不同行不同列的零元素, 故至少 n 條直線才能覆蓋全部元素充分性若覆蓋全部零元素

24、的最少直線數(shù)目為n , 則 (bij ) 中有 n 個(gè)不同行不同列的零元素 . 否則可以用少于 n 條的直線能覆蓋全部元素.此算法的優(yōu)點(diǎn)是 , 先求具有最大匹配的等效矩陣, 再求最大匹配 . 求解過程中可以減少迭代次數(shù) , 降低計(jì)算量 , 并且對某些用匈牙利算法無法得到最大匹配的矩010陣?yán)么烁倪M(jìn)的算法可以得到最大匹配, 例如效益矩陣 (bij ) 002 .0033.3 不足和改進(jìn)（三）9洛陽師范學(xué)院本科畢業(yè)論文3.3.1匈牙利法存在的問題我們用“匈牙利法”處理了許多與分配問題相關(guān)的運(yùn)輸、調(diào)度問題, 大多數(shù)情況下算法是收斂的 , 得到了最優(yōu)解 , 而處理一些特殊數(shù)據(jù)時(shí)算法不收斂 , 無法找

25、出最優(yōu)解 , 矩陣階數(shù)越大的分配問題 , 不收斂的情況越多 .試驗(yàn)中 , 發(fā)現(xiàn)了一個(gè)較小階不收斂的系數(shù)矩陣, 下面用“匈牙利法”對該矩陣進(jìn)行分析224144441221123331231442434211413112311122131131422313342111331324131412141214314經(jīng)過算法第一步 ,得到修正的系數(shù)矩陣113033330110012220120331323100302001200011020020311202231000220213020301030103203進(jìn)行算法第二步 , 做分配方案 , 最終第 2 行無 ( 0 ) 標(biāo)記 , 使得第 2 行第 2

26、 列沒有分配113(0)333311 12 2 210洛陽師范學(xué)院本科畢業(yè)論文12(0)3313231 3(0)2 12 11 (0)2(0) 2 31 1 2 2231 2 2(0)213 2 3 1 3 1 32(0)3進(jìn)行算法第三步 , 最終所有的行和所有的列都有標(biāo)記, 所有的行末畫一條橫線 , 所有的列都畫上了豎線 , 各行列作標(biāo)記的順序如下 113 (0) 333311 122212(0)3313231 3 (0)2 12 11(0)2(0) 2 3 112 2231 2 2(0)213 2 (0) 3 1 3 1 32(0)3進(jìn)行算法第四步 , 沒有找到未被直線覆蓋的元素, 所以也

27、就無法找到最小的元素 , 也就不能產(chǎn)生新的效能矩陣 , 算法進(jìn)入死循環(huán) . 這就否定了“匈牙利法”主要過程的算法基礎(chǔ) . 若算法第二步未完成一個(gè)完全分配時(shí) , 則一定能生成一個(gè)新的效能矩陣 , 出現(xiàn)新的零元素 , 再重新進(jìn)行完全分配 , 最終一定能得到一個(gè)完全的最優(yōu)解 . 3.3.2 匈牙利算法的改進(jìn)為了使“匈牙利法”對任意數(shù)據(jù)都能有效的找到最優(yōu)解 , 我們在原算法的基礎(chǔ)上增加第六步 , 以及在第三步后面增加判斷功能 : 若生成 n 條直線 , 無法生成新的效能矩陣 , 則退出“匈牙利法” , 進(jìn)行第六步 .第六步 : 產(chǎn)生新的小系數(shù)矩陣 , 使原矩陣分解 .11洛陽師范學(xué)院本科畢業(yè)論文（1）

28、從第二步算法中 , 記下有 ( 0 ) 標(biāo)記的行號和列號 , 作為部分解進(jìn)行保存 .（2）從系數(shù)矩陣中抽取行列都沒有( 0 ) 標(biāo)記的數(shù)據(jù) , 組成一個(gè)新的小系數(shù)矩陣: Eij , i1,2, m, j1,2, m, mn .（3）將小系數(shù)矩陣再代入“匈牙利法”,繼續(xù)計(jì)算 ,得到小系數(shù)矩陣的分配解 , 把它添加到部分解的結(jié)果中去 , 組合得到一個(gè)新的解 , 如果新的解仍然不是完全解 , 則轉(zhuǎn)（ 1）繼續(xù)處理 .（4）對已分配的元素 , 兩兩一對組成任意一個(gè)矩形的斜對角頂點(diǎn) , 相加后生成一個(gè)基礎(chǔ)量 , 再將矩形的另一對斜對角頂點(diǎn)的元素相加 , 生成一個(gè)改變量 , 有 n 個(gè)已分配的元素將產(chǎn)生

29、123n2n1對基礎(chǔ)量和改變量 .（5）對于每對基礎(chǔ)量和改變量 , 如果存在基礎(chǔ)量大于改變量的情況 , 則找出基礎(chǔ)量與改變量差值最大的一對 , 由改變量取代基礎(chǔ)量 , 轉(zhuǎn)（ 4）繼續(xù)處理 .（6）得到整個(gè)分配的最優(yōu)解, 輸出分配結(jié)果 .在上例中 , 新的小系數(shù)矩陣僅為第 2 行和第 2 列, m 為 1. 另外 , 也沒有找到改變量小于基礎(chǔ)量的兩對值 , 所以無須進(jìn)行優(yōu)化 , 直接將該元素添加到部分解中去 , 通常新的小系數(shù)矩陣的階數(shù)都很小 .文獻(xiàn) 5 中給出了一個(gè) 2222 的系數(shù)矩陣 , 存在上述問題 , 利用改進(jìn)的匈牙利算法最終得到最優(yōu)解 .3.4 匈牙利算法的推廣匈牙利算法的關(guān)鍵是在變

30、換后的系數(shù)矩陣中找出n 個(gè)分布在不同行不同列的獨(dú)立 0 元素 , 而匈牙利算法計(jì)算過程比較麻煩, 文獻(xiàn) 8 , 文獻(xiàn) 9 在匈牙利算法的基礎(chǔ)上提出了兩種比較簡單的尋找獨(dú)立0 元素的方法 : 最小零元素消耗法及對角線法.3.4.1最小零元素消耗法基本思想 : 對于一個(gè)給定的矩陣 , 其中 0 元素的數(shù)目是一定的 , 這一定的 0 元素最多能分配出多少個(gè)0 元素來？當(dāng)分配出一個(gè)0 元素時(shí) , 該 0 元素所在行和列上的其它 0 元素就無法再分配 , 失去了作用 , 也就是說 , 分配出該 0 元素要用去 0 元素的個(gè)數(shù)為 : 該 0 元素本身 +該 0 元素所在行上的其它0 元素 +該 0 元素所

31、在列上的其它0 元素 , 稱此數(shù)為該 0 元素的 0 消耗數(shù) . 對于給定矩陣中的所有0 元素 , 可以很容易地找出其 0 消耗數(shù) , 根據(jù)動(dòng)態(tài)規(guī)劃的最優(yōu)化原理, 如果第 1次分配出 0 消耗數(shù)最少的12洛陽師范學(xué)院本科畢業(yè)論文0 元素 , 將消耗的 0 元素去掉 , 在余下的 0 元素中再分配 0 消耗最少的 0 元素 , 重復(fù)這樣的過程 , 最終結(jié)果必將得到最多次數(shù)的分配即最大分配 , 這就是最小 0 元素消耗法 .基本方法 : 利用匈牙利算法變換系數(shù)矩陣 , 使每行每列出現(xiàn) 0 元素 , 計(jì)算出各個(gè) 0 元素的消耗數(shù) , 分配處 0消耗數(shù)最少的那個(gè) 0 元素 , 以( 0 ) 標(biāo)記 .

32、此 0 元素所在行所在列以不起作用 , 再計(jì)算余下的個(gè)各個(gè) 0 元素的消耗數(shù) , 重復(fù)上述步驟 , 直至每行每列的 0 元素都標(biāo)記完 , 最終得到最大匹配 , 若標(biāo)記 ( 0 ) 的個(gè)數(shù)等于矩陣階數(shù) , 得到最優(yōu)解 .在應(yīng)用此方法的時(shí)候 , 當(dāng)遇到 0 消耗相同的 0 元素不止一個(gè) , 此時(shí)應(yīng)先分配哪個(gè) 0 元素呢？有以下三種情況:（1） 0 消耗數(shù)相同 , 但 0 元素在同一行或同一列上, 如下所示 :0(i1 , j )0(i, j1 )0(i, j2 )0(i 2, j)現(xiàn)就 0 元素在同一行的情況說 , 如果分配其任何一個(gè) , 另一個(gè)則被消耗掉 , 他們的 0 消耗數(shù)實(shí)際上是相同的,

33、只能表示一個(gè)分配 , 要么分配 0(i , j1 ) , 要么分配 0(i, j2 ) ,但第 i 行則可以確定下來 , 等其它 0 元素分配完以后 , 如 j1 , j 2 列中有一列確定 , 則第i 行可以具體確定出 0 元素 , 若 j1 , j2 列仍未確定 , 則說明最大分配小于n , 或者有多種最優(yōu)分配方案 . 對于同一列的情況 , 可以確定第 j 列 , 具體分配哪一個(gè) , 視其它 0元素的分配而定 .（2） 0 消耗數(shù)相同且互相影響 , 但 0 元素不同行不同列 , 此時(shí) 0 元素的消耗數(shù)必共同消耗一個(gè)或兩個(gè)0 元素 , 如下所示 :0(i1, j1 )0(i1 , j1 )0

34、00(i2 , j 2 )00(i2 , j2 )13洛陽師范學(xué)院本科畢業(yè)論文0(i1, j1 ) 、0(i2 , j 2 ) 的 0 消耗相同 , 設(shè)為 q , 他們的 0 消耗因共有 0 元素而相互影響 ,若先分配 0(i1, j1 ) , 則在余下的 0 元素中 0(i2 , j 2 ) 的 0 消耗數(shù)為 q1或 q2 , 必為最小 ,應(yīng)予與分配 . 反之也是 , 因此這種情況兩者應(yīng)同時(shí)分配.（3） 0 消耗數(shù)相同但互不影響 , 此時(shí)必為下圖所示 :0(i1, j1)0( i2 , j2 )此時(shí)若先分配 0(i1, j1 ) , 則在余下的 0 元素中 , 0(i2, j2 ) 的0消耗

35、必為最少 , 應(yīng)予與分配 , 反之也是 . 這種情況可將它們同時(shí)分配.綜合上述三種情況 , 當(dāng)遇到 0 消耗數(shù)相同的 0 元素時(shí) , 如果它們不在同一行同一列 , 可以將其同時(shí)分配 ; 如果在同一行同一列上 , 可將該行或該列分配 , 分配數(shù)加 1, 具體分配視其它 0 元素分配結(jié)果而定 .3.4.2對角線法匈牙利算法的實(shí)質(zhì)就是尋找 n 個(gè)分布在不同行不同列的零元素 , 而匈牙利算法本身計(jì)算過程較復(fù)雜 , 下面給出一種使系數(shù)矩陣對角線為零的算法對角線法 .基本步驟 :第一步 : 變換系數(shù)矩陣使每行每列都出現(xiàn)零元素, 同匈牙利算法第一步 .第二步 : 進(jìn)行行排序 , 即（1）在變換后的系數(shù)矩陣(

36、bij ) 的第 j 列元素中 ( j1,2, n) , 從第 j, j1, n行中選取最小元素 , 記為 bi0 j .（2）將 i0 行元素與 j 行進(jìn)行交換 .通過步驟二可使每列中的零元素或最小元素盡量出現(xiàn)在對角線上.若這樣選取的最小元素有兩個(gè)以上時(shí) , 則取這些最小元素所在行中第 n 個(gè)元素大者所對應(yīng)的元素為最小元素 ; 若第 n 個(gè)元素也相同 , 則取第 n 1個(gè)元素中大者對應(yīng)的元素為最小元素 , 以此類推 ; 若這些最小元素后各行對應(yīng)元素都相同 , 則取這些最小元素所在行中第 j 1 個(gè)元素小者對應(yīng)元素為最小元素 ; 若第 j 1 個(gè)元素相14洛陽師范學(xué)院本科畢業(yè)論文同 , 則取再

37、前一個(gè)元素中小者對應(yīng)元素為最小元素 , 以此類推 . 若這些最小元素所在行的對應(yīng)元素均相同 , 則可任選一最小元素所在行與第 j 行元素交換 .第三步 : 檢驗(yàn)若 bii0 (i1,2, n) , 則以得最優(yōu)解 , 過程結(jié)束 . 否則進(jìn)行第四步 .第四步 : 進(jìn)行行排序 , 排序過程類似于第二步 , 只須將第二步中的“列”改為“行” . 而“行”改為“列” , “后”改為“下” , “前”改為“上”即可 .第五步 : 若 bii0 (i1,2, n) , 則已得到最優(yōu)解 , 迭代過程停止 , 否則進(jìn)行第六步.第六步 : bij bijbii , j 1,2, , n .第七步 : 若 bij0

38、, j1,2, n , 則返回第五步 . 否則 , 若 bik0 , 則令bjkbjkbik , j1,2, n , 返回第一步 .從上述過程來看 , 整個(gè)過程包括兩個(gè)基本部分, 第一部分是通過一系列矩陣的行列變換 , 把零元素排列在對角線上; 第二部分是最解的檢驗(yàn) , 即所有 bii0 時(shí), 已得到最優(yōu)解 .對于此算法的收斂性分析, 文獻(xiàn) 9 中給出了幾個(gè)定理 , 并進(jìn)行了證明 , 可以看出此改進(jìn)算法的收斂性極好, 可以有效地解決指派問題.4 對最大化指派問題的匈牙利解法的一點(diǎn)改進(jìn)對最大化的指派問題的解法, 一般方法是找出系數(shù)矩陣( cij ) 中的最大元素 , 即nM max cij (

39、j 1,2, , n) , 做矩陣 B , 其元素為 bij (i 1,2, n; j 1,2, , n) 且i 1bijMcij , 然后利用匈牙利解法最小化求B 的最優(yōu)解 . 下面我們在此基礎(chǔ)上對其提出一點(diǎn)改進(jìn) , 直接在原系數(shù)矩陣上進(jìn)行修改.修改的原則是 : 在最小化問題中 , 系數(shù)矩陣不能出現(xiàn)負(fù)數(shù) , 在最大化問題中 , 修改后的不能出現(xiàn)正元素 , 可出現(xiàn)零 .基本步驟 :第一步 : 修改系數(shù)矩陣 .15洛陽師范學(xué)院本科畢業(yè)論文每行都減去該行中最大元素, 每列都減去該列中最大元素.第二步 : 求最優(yōu)解 .選取新矩陣的零元素 , 已得到問題的最優(yōu)解 . 根據(jù)每個(gè)人只能完成一項(xiàng)任務(wù) , 每

40、項(xiàng)任務(wù)只能由一個(gè)人來完成的前提 , 則零元素只能選在不同行且不同列的元素 , 此時(shí)對應(yīng)被選中的零元素打上括號（） , 其對應(yīng)的 xij 等于 1, 其它的 xij 等于 0 , 如此劃出的零元素為 n 個(gè), 則便可求得最優(yōu)解 .如果劃出的零元素少于n 個(gè), 則轉(zhuǎn)入第三步 .第三步 : 繼續(xù)修改系數(shù)矩陣 .先找出無“ ( 0 ) ”號的行 , 然后找出該行有零的列 ; 最后找出該列有“ ( 0 ) ”的行 ; 重復(fù)后兩步 , 直到找不出滿足要求的列和行 ; 對找到的行和沒有找到的列的交叉元素加以比較 , 找出最大數(shù) , 找到的行各元素分別減去此數(shù) , 找到的列分別加上此數(shù) , 轉(zhuǎn)第二步利用這種方

41、法來解最大化指派問題時(shí) , 不需要用一個(gè)新矩陣代替原系數(shù)矩陣 , 可直接在原系數(shù)矩陣上進(jìn)行修改 , 這種解法為在計(jì)算機(jī)上算法的實(shí)現(xiàn)提供了方便 , 由于此最大化問題的求解步驟的多少與先后同匈牙利最小化問題的求解步驟的多少與先后是相對應(yīng)的 , 所以在編程時(shí) , 可以用以實(shí)參代替形象的方法 , 用同一段參數(shù)的程序去解決最大化、最小化兩個(gè)不同的問題 .5 結(jié)束語指派問題是運(yùn)籌學(xué)中的經(jīng)典問題 , 它的主要目標(biāo)是在解決問題時(shí) , 如何分派使所消耗的總資源最少（或總體效益最優(yōu)） . 如給工人分派工作 , 給車輛分配道路 , 給工人分配機(jī)床等等 , 同時(shí)許多網(wǎng)絡(luò)問題 （如旅行問題 , 任務(wù)分配問題 , 運(yùn)輸問

42、題等） , 都可以演化成指派問題來解決 . 在現(xiàn)實(shí)生活中 , 指派問題是十分常見的問題 , 而匈牙利解法是解決指派問題的一種非常簡單有效的方法 , 它能解決多種形式的指派問題 , 針對匈牙利算法存在一些不足 , 我們對其進(jìn)行了改進(jìn)和完善 , 利用改進(jìn)后的匈牙利算法 , 不僅能更有效地解決指派問題 , 而且為計(jì)算機(jī)編程提供了方便 .6 致謝這篇學(xué)位論文是在我的指導(dǎo)老師蘇孟龍老師的親切關(guān)懷和悉心指導(dǎo)下完成的 . 他嚴(yán)肅的科學(xué)態(tài)度 , 嚴(yán)謹(jǐn)?shù)闹螌W(xué)精神 , 精益求精的工作作風(fēng) , 深深地感染和激勵(lì)著我. 從課題的選擇到項(xiàng)目的最終完成 , 蘇老師都始終給予我細(xì)心的指導(dǎo)和不懈的支16洛陽師范學(xué)院本科畢業(yè)論文持. 在此謹(jǐn)向蘇老師致以誠摯的謝意和崇高的敬意.另外 , 我還要感謝在一起愉快度過的老師和同學(xué) , 正是由于你們的幫助和支持 , 我才能克服一個(gè)個(gè)的困難和疑惑 , 最終完成本論文 , 在此我想深深地對你們說一聲謝謝！參考文獻(xiàn) :1 林齊寧 . 運(yùn)籌學(xué) M. 北京郵電大學(xué)出版社 ,2002.2 施泉生 . 運(yùn)籌學(xué) M. 中國電子出版社 ,2004.3 胡運(yùn)權(quán)等 . 運(yùn)籌學(xué)基礎(chǔ)及應(yīng)用 M. 高等教育出版社 ,2004.4 張雷順 . 對最大化指派問題匈牙利解法的一點(diǎn)改進(jìn)J.鄭州工業(yè)大學(xué)學(xué)報(bào) ,2001,22(2):57-59.5 金升燦 . 指派問題的一種改進(jìn)算法 J. 佳木斯工學(xué)院報(bào) ,19