指派問題ppt課件-在線瀏覽
2025-06-17 18:05本頁面
【正文】 陣給出它的數(shù)學(xué)模型及求解方法 .167。1 最大基數(shù)匹配問題x3x1x2 y2y1y3x4x5y4y5 該問題也可用矩陣表示如果 xi 會(huì)做 yj否則11111111110 0 0000000000000 在矩陣中尋找什么？ 尋找最多的不同行不同列的 1 元素 .(二部圖 G 的 鄰接矩陣 ) 稱為獨(dú)立元（素）第四章 指派問題如何尋找 ？ 禮讓原則 從每行、每列中， 1 最少的行或列先取，一樣多時(shí)隨意 . 遺憾的是這是錯(cuò)的 167。不同行不同列的 ① ，稱為 A 的一個(gè)分配，用 M 表示。1 最大基數(shù)匹配問題Theorem ( Berge ,1957 ) M 是 A 的最大分配的充要條件是不存在可增廣鏈 .匈牙利算法 ：Step 1 任給一初始分配 M ， 設(shè) S 為未被 M 分配的行 集合 ；Step 2 如果 ，則此時(shí)已得到最大分配 ， End 否則，取 ；Step 3 尋找 xi 出發(fā)的可增廣鏈， 如果存在，則進(jìn)行增廣 ； 且令 Go to Step 2。對(duì)圖 G 的最大匹配，結(jié)論也成立proofTheorem 的證明Proof : 必要性 ： 若 M 是 A 的最大分配，顯然 A 中無關(guān)于 M 的可增廣鏈，不然 M 還可以增廣成獨(dú)立元更多的分配，與 M 是最大分配相違；充分性 ： 反證，若 M 不是最大分配， 則存在分配 M1,作 由于 M2 是由 M， M1 中非公共部分組成，而 M , M1 都是分配，所以從 M2 的任一 1 出發(fā)，按交互鏈得到方法，得到的鏈必是 M, M1 中的 1 交替出現(xiàn) . √√ √√√√√ 由于 ，所以在所有的交互鏈中，必有一條鏈屬于 M1 的 1 多于屬于 M 的 1 ，且以 M1 的 1 出發(fā)、結(jié)束，這是關(guān)于 M 的可增廣鏈 . 與 條件矛盾 . 證畢√第四章 指派問題Example 1 求 G 的最大匹配，G 的鄰接矩陣如右所示 ： √Solution: 不妨設(shè)初始匹配取 x3，從 x3y2 出發(fā)，√√得一增廣鏈：增廣得 ：√√√√√取 x4， 得一增廣鏈：增廣得 ：取 x5，從 x5y3 出發(fā)，√得一交互鏈，但不是增廣鏈 .從 x5y4 出發(fā)， 因 y4 未被分配，所以對(duì) x5y4 加圈，得：所以， M 是最大匹配，且是完備匹配 .167。2 指派問題 設(shè)有 n 個(gè)人員去完成 n 項(xiàng)任務(wù)，第 i 人完成第 j 項(xiàng)任務(wù)的效益為 ，要求每人完成且僅完成一項(xiàng)，問如何分配，使完成 n 項(xiàng)任務(wù)的總效益 最佳 .可以是 max 、 min先考察 min稱 C = (cij)nn 為 效益矩陣 . 第四章 指派問題Example 2 任務(wù)人員 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 四人，他們將中文翻譯成不同語言所需時(shí)間如表 , 問應(yīng)分配何人去完成何任務(wù)（一人完成一項(xiàng)任務(wù)），使所需總時(shí)間最少？Solution: 當(dāng)分配第 i 人完成第 j 項(xiàng)任務(wù)否則設(shè).167。nig 的結(jié)論 ,所以，該算法也稱為匈牙利算法 .第四章 指派問題Theorem ( K246。2 指派問題 顯然， Ex . 2 的可行解可用一個(gè) 01 矩陣表示 .
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1