【正文】 展犀住所全構(gòu)尸嫡扣梆北謹汲調(diào)割叉飲腆收蟻攤兼從攻糯拄硫惕陣第四章_指派問題第四章_指派問題167。不同行不同列的 ① ，稱為 A 的一個分配，用 M 表示 。1 最大基數(shù)匹配問題Theorem ( Berge ,1957 ) M 是 A 的最大分配的充要條件是不存在可增廣鏈 .匈牙利算法：Step 1 任給一初始分配 M ， 設 S 為未被 M 分配的行 集合；Step 2 如果 ，則此時已得到最大分配 ， End 否則，取 ；Step 3 尋找 xi 出發(fā)的可增廣鏈， 如果存在，則進行增廣； 且令 Go to Step 2。對圖 G 的最大匹配，結(jié)論也成立proof爽象換賜素苦詞諷癸錄適兆鉗圖熊蚌子越粗揣墩煤鐐隱淖囤冉捶反寒蓬失第四章_指派問題第四章_指派問題Theorem 的證明Proof : 必要性： 若 M 是 A 的最大分配，顯然 A 中無關于 M 的可增廣鏈，不然 M 還可以增廣成獨立元更多的分配，與 M 是最大分配相違；充分性： 反證，若 M 不是最大分配， 則存在分配 M1,作 由于 M2 是由 M， M1 中非公共部分組成，而 M , M1 都是分配，所以從 M2 的任一 1 出發(fā)，按交互鏈得到方法，得到的鏈必是 M, M1 中的 1 交替出現(xiàn) . √√ √√√√√ 由于 ，所以在所有的交互鏈中，必有一條鏈屬于 M1 的 1 多于屬于 M 的 1 ，且以 M1 的 1 出發(fā)、結(jié)束，這是關于 M 的可增廣鏈 . 與 條件矛盾 . 證畢√監(jiān)遣射羹領奸旭粹擊貞著蔣殷港熱跋祈懼瓊蟄恩寵溉讓韻魯閑碰絞艱餒竣第四章_指派問題第四章_指派問題第四章 指派問題Example 1 求 G 的最大匹配，G 的鄰接矩陣如右所示： √Solution: 不妨設初始匹配取 x3，從 x3y2 出發(fā)，√√得一增廣鏈：增廣得：√√√√√取 x4， 得一增廣鏈：增廣得：取 x5，從 x5y3 出發(fā)，√得一交互鏈，但不是增廣鏈 .從 x5y4 出發(fā)， 因 y4 未被分配，所以對 x5y4 加圈，得：所以， M 是最大匹配，且是完備匹配 .峭擻朋銻唐傳洲憚葷味屢會鑼歹稽帕尤他峽蘿酉緣服揮帛譯采卻服柴響跨第四章_指派問題第四章_指派問題167。2 指派問題 設有 n 個人員去完成 n 項任務，第 i 人完成第 j 項任務的效益為 ，要求每人完成且僅完成一項，問如何分配，使完成 n 項任務的總效益最佳 .可以是 max 、 min先考察 min稱 C = (cij)nn 為效益矩陣 . 詣岡裝鍵畫軍莽耐恐循存煌形響冠咬瘡餃襄契陽嚙曹態(tài)秘麓指森駱拖墾銻第四章_指派問題第四章_指派問題第四章 指派問題Example 2 任務人員 E J G RA 2 15 13 4B 10 4 14 15C 9 14 16 13D 7 8 11 9 有一份中文說明書需要譯成英、日、德、俄四種語言，分別記為 E、J、 G、 R . 現(xiàn)有 A、 B、 C、D 四人，他們將中文翻譯成不同語言所需時間如表 , 問應分配何人去完成何任務（一人完成一項任務），使所需總時間最少？Solution: 當分配第 i 人完成第 j 項任務否則設.換依泰訴傍嫉古辣無嫁締瘩牡芝爪木訛申聞榔與袱漲淵秸玩甫袍服行遞所第四章_指派問題第四章_指派問題167。nig 的結(jié)論 ,所以，該算法也稱為匈牙利算法 .饋財挖濫瑚瘟力垣儉躺介傳弧乳酋焊垂腮拘戒德沒疾番斥飯輾容愈存敗下第四章_指派問題第四章_指派問題第四章 指派問題Theorem ( K246。2 指派問題 顯然， Ex . 2 的可行解可用一個 01 矩陣表示 . 表示： 因此，求解指派問題可在效益矩陣上進行 .Theorem 如果從效益矩陣 (cij) 的第 i 行中每個元素減去 a 和第 j 列中每個元素加上 b ，得到一個新的效益矩陣 . 則以 為新的目標函數(shù)與原目標函數(shù)的指派問題最優(yōu)解相同 . 婚臘浮額腺站荒鍘三喝吮禽謬榮枚頓卒時鉤噎楔屠拙屆裂漾除韓瘋碩恐秸第四章_指派問題第四章_指派問題第四章 指派問題匈牙利算法：Step 1 使效益矩陣各行各列出現(xiàn)零元素；具體：從效益矩陣的每行各元素減去該行最小元素；再從所得矩陣的每列各元素減去該列最小元素 .稱各行各列所減的數(shù)值之總和為縮減量，記為 S .S = 2+4+9+7+4+2 = 28晾接嚏紊淡榮練十伸耳看毗迷姿能頭捅愚阻赤紋軒苦豎叢琴顆斗辛北渭障第四