指派問(wèn)題ppt課件(編輯修改稿)
2025-05-27 18:05 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 G RA 2 15 13 4B 10 4 14 15C 9 14 16 13D 7 8 11 9 任務(wù)人員 E J G R aiA 2 15 13 4 1B 10 4 14 15 1C 9 14 16 13 1D 7 8 11 9 1bj 1 1 1 1 也是一個(gè)特殊的運(yùn)輸問(wèn)題 . 所以 ,分配問(wèn)題可用解 IP 問(wèn)題方法（如：分支定界法 ), 或解運(yùn)輸問(wèn)題的表上作業(yè)法 . 但是， IP 是 NPC 問(wèn)題；有基變量 2n1 個(gè)，而有 n1 個(gè)為零，高度退化 . 1955年， KuhnMunkras 提出了解 AP 的算法，將求AP 轉(zhuǎn)化為求完備匹配問(wèn)題，其計(jì)算復(fù)雜性為 O(n3) . 由于算法引用了匈牙利數(shù)學(xué)家 K246。nig 的結(jié)論 ,所以，該算法也稱為匈牙利算法 .第四章 指派問(wèn)題Theorem ( K246。nig ,1931 ) Definition 圖 G = ( V， E ) ，一個(gè)頂點(diǎn)在 C 中，稱 C 為 G 的一個(gè) 點(diǎn) （對(duì)邊的） 覆蓋 .點(diǎn)集 若 G 中每條邊至少有點(diǎn)數(shù)最少的點(diǎn)覆蓋 C 稱為 G 的 最小點(diǎn)覆蓋 . 二部圖 G = ( X， Y， E ) ， M 為最大匹配， C 為最小點(diǎn)覆蓋，則有 監(jiān)測(cè)點(diǎn)的設(shè)置等是最小點(diǎn)覆蓋的應(yīng)用 . 點(diǎn)覆蓋 在二部圖 G 的 鄰接矩陣 上如何表示？Proof Theorem 的證明Proof : 顯然 ，若 ， 則若 ， 設(shè) X1為在 M 中沒(méi)有獨(dú)立元的行的集合 .如右 令 Z 是 X1 中行出發(fā)的關(guān)于 M 的交互鏈上的所有點(diǎn)， 如右 記則 表示 S 中的行的所有 1 對(duì)應(yīng)的列取則 B 是 A 的一個(gè)覆蓋， 如果不是，則有 1 元素行在 S 列在 YT 中，這與 矛盾 .而 ，顯然所以 B 是最小覆蓋 . 證畢167。2 指派問(wèn)題 顯然， Ex . 2 的可行解可用一個(gè) 01 矩陣表示 . 表示 ： 因此，求解指派問(wèn)題可在效益矩陣上進(jìn)行 .Theorem 如果從效益矩陣 (cij) 的第 i 行中每個(gè)元素減去 a 和第 j 列中每個(gè)元素加上 b ，得到一個(gè)新的效益矩陣 . 則以 為新的目標(biāo)函數(shù)與原目標(biāo)函數(shù)的指派問(wèn)題最優(yōu)解相同 . 第四章 指派問(wèn)題匈牙利算法 ：Step 1 使效益矩陣各行各列出現(xiàn)零元素 ；具體：從效益矩陣的每行各元素減去該行最小元素；再?gòu)乃镁仃嚨拿苛懈髟販p去該列最小元素 .稱各行各列所減的數(shù)值之總和為 縮減量 ，記為 S .S = 2+4+9+7+4+2 = 28167。2 指派問(wèn)題Step 2 試尋求最優(yōu)解； 用上節(jié)的求最大匹配的算法 .這時(shí)得到最大匹配 M .如果 ，則已得到最優(yōu)解； 即28 = S每行每列有零元素，能保證有 n 個(gè)獨(dú)立零元素嗎？ 如果 ， 則 go to step 3 ；第四章 指派問(wèn)題Step 3 作縮減后的效益矩陣的 最小覆蓋 ；具體： a、對(duì)沒(méi)有 0 的行打 √ ； b、對(duì)已打 √ 的行中所有含 0 元素的列打 √； c、 對(duì)打 √ 的列上有 0 的行打 √； d、重復(fù) b、 c ，直到得不出新的打 √ 的行列 為止； e、對(duì)打 √ 的列畫縱線，沒(méi)打 √ 行畫橫線 . 這就得到 最小覆蓋 .167。2 指派問(wèn)題Example 3求 效益矩陣為 C 的最小指派 .Solution:√√√縮減量 S1 = 26此時(shí)， . 第四章 指派問(wèn)題Step
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1