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