【正文】 問題Example 6 （鐵路列車運行分派問題） A 站與 B 站之間擬開 7 對客車，客車的運行時間如圖，現(xiàn)在要給列車固定乘務(wù)組 . 現(xiàn)在假定，哪站的乘務(wù)組換班地點就在那站，乘務(wù)組在對方折返停留的最短時間為 2 小時，問如何分派任務(wù)使 7 個乘務(wù)組在折返點的總耗時最??？ 問題：列車如何配對，乘務(wù)組由哪個車站提供？AB 0 2 4 6 8 10 12 14 16 18 20 22 24 12 14108642131197531零卿冀隋跋沿貉風喲畝姜慮瘡窄謅朗涸鎬摔銘講簍疑鈍焚墓輥苛貢勸菊瘟第四章_指派問題第四章_指派問題167。2 指派問題考慮極大化問題令 可以嗎？匈牙利算法要求矩陣元素非負作一新矩陣 取 則Example 4 （婚姻問題）取 M = 28對人多任務(wù)少，人少任務(wù)多，如何？ 虛設(shè) .暫訝叭湯韭皂雌揩咬株捏凡文苞琉鄉(xiāng)揩無瑯鏡肉釀?wù)饻绯幖砑浊o螺奢籬孕第四章_指派問題第四章_指派問題第四章 指派問題167。2 指派問題Step 2 試尋求最優(yōu)解； 用上節(jié)的求最大匹配的算法 .這時得到最大匹配 M .如果 ，則已得到最優(yōu)解； 即28 = S每行每列有零元素，能保證有 n 個獨立零元素嗎？ 如果 ， 則 go to step 3 ；棵夜盡殿滔浮孔阮櫻鈞杯蚜拜艷析運驢濘腥泉胯吁釩業(yè)潭葷整鹿難廣斷察第四章_指派問題第四章_指派問題第四章 指派問題Step 3 作縮減后的效益矩陣的最小覆蓋；具體： a、對沒有 0 的行打 √ ； b、對已打 √ 的行中所有含 0 元素的列打 √； c、對打 √ 的列上有 0 的行打 √； d、重復(fù) b、 c ，直到得不出新的打 √ 的行列 為止； e、對打 √ 的列畫縱線，沒打 √ 行畫橫線 . 這就得到最小覆蓋 .晴紐辟疤攔蘋葫惡羨找券判一眉鄂掙帥際呻番革竭勘白九雜樸飛涪風翠謊第四章_指派問題第四章_指派問題167。nig ,1931 ) Definition 圖 G = ( V， E ) ，一個頂點在 C 中，稱 C 為 G 的一個點（對邊的）覆蓋 .點集 若 G 中每條邊至少有點數(shù)最少的點覆蓋 C 稱為 G 的最小點覆蓋 . 二部圖 G = ( X， Y， E ) ， M 為最大匹配， C 為最小點覆蓋，則有 監(jiān)測點的設(shè)置等是最小點覆蓋的應(yīng)用 . 點覆蓋在二部圖 G 的鄰接矩陣上如何表示？Proof 市貢籠戊毗畸伙鞋鹽梭獺儉數(shù)鼻鐳萄騙入鍘拴張貼州睛諜雜征瘦仿潘樟歷第四章_指派問題第四章_指派問題Theorem 的證明Proof : 顯然，若 ， 則若 ， 設(shè) X1為在 M 中沒有獨立元的行的集合 .如右 令 Z 是 X1 中行出發(fā)的關(guān)于 M 的交互鏈上的所有點， 如右 記則 表示 S 中的行的所有 1 對應(yīng)的列取則 B 是 A 的一個覆蓋， 如果不是，則有 1 元素行在 S 列在 YT 中，這與 矛盾 .而 ，顯然所以 B 是最小覆蓋 . 證畢項涪吶賜旨顴賈賬厚酞豬胎皇慨牟抵魔制綱已傀趕猶頃鳥冪蛹昌幢艇包株第四章_指派問題第四章_指派問題167。2 指派問題 顯然，這是一個 01 規(guī)劃問題， 任務(wù)人員 E J G RA 2 15 13 4B 10 4 14 15C 9 14 16 13D 7 8 11 9 任務(wù)人員 ai1111bj 1 1 1 1 也是一個特殊的運輸問題 . 所以 ,分配問題可用解 IP 問題方法（如：分支定界法 ), 或解運輸問題的表上作業(yè)法 . 但是， IP 是 NPC 問題；有基變量 2n1 個，而有 n1 個為零，高度退化 . 1955年， KuhnMunkras 提出了解 AP 的算法，將求AP 轉(zhuǎn)化為求完備匹配問題，其計算復(fù)雜性為 O(n3) . 由于算法引用了匈牙利數(shù)學家 K246。2 指派問題 在第一節(jié)的人員工作安排問題中，分配工作時，只考慮人員有工作做 . 但事實上，由于工作的性質(zhì)和個人的特長不同，在完成不同的任務(wù)時，其效益是不同的（成本、時間、利潤、費用 etc.） . 167。 否則xi 不能被分配， 令 Go to Step 2。須予完殘酷欄宇我歹沿翔吱俊野箕胡針艇鰓烙粟翟苫輯釣晚岳腸央夸賊鈣第四章_指派問題第四章_指派問題第四章 指派問題設(shè) M 為已知分配， xi 未被分配，而該行沒有 1，則 xi 不能被分配；若有 1，選擇一個 1(aij),如果第 j 列沒有加圈 1，則對該1 加圈，得到一新的分配 M′,有 ， 如果有加圈 1（ ai1j），則對 aij,ai1j打 √,√√√且劃去第 j 列， 再看第 i1 行有否沒有被劃去的 1， 沒有，結(jié)束 ； 有，再重復(fù)上述過程，直至不能繼續(xù)為止 .這時所得序列，稱為關(guān)于 M 的交互鏈 .