指派問題ppt課件-wenkub.com
2025-04-27 18:05 本頁面
【正文】 Step 2 計算 yk , 在 中擦去 得 求 的最大匹配 Mk+1 ；Step 3 若 則 Mk 為最優(yōu)解， fmin= yk否則，令 k = k+1， go to step 2 .167。4 瓶頸分配問題167。3 指派問題的應(yīng)用Example 5 現(xiàn)有 6 項任務(wù)，由 4 個工廠來完成，已知各個工廠完成各項任務(wù)的費用矩陣為 C ， 應(yīng)如何分配任務(wù)，使總費用最小 ？具體分別 無要求 ；一廠至多完成兩項 ； 一廠至多完成兩項， 至少完成一項 .Solution: 無要求碰巧，符合 3的要求Z min = 13167。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 = 28167。2 指派問題 設(shè)有 n 個人員去完成 n 項任務(wù)，第 i 人完成第 j 項任務(wù)的效益為 ，要求每人完成且僅完成一項，問如何分配，使完成 n 項任務(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 四人，他們將中文翻譯成不同語言所需時間如表 , 問應(yīng)分配何人去完成何任務(wù)（一人完成一項任務(wù)），使所需總時間最少？Solution: 當分配第 i 人完成第 j 項任務(wù)否則設(shè).167。1 最大基數(shù)匹配問題Theorem ( Berge ,1957 ) M 是 A 的最大分配的充要條件是不存在可增廣鏈 .匈牙利算法 ：Step 1 任給一初始分配 M ， 設(shè) S 為未被 M 分配的行 集合 ；Step 2 如果 ，則此時已得到最大分配 ， End 否則，取 ；Step 3 尋找 xi 出發(fā)的可增廣鏈， 如果存在，則進行增廣 ； 且令 Go to Step 2。1 最大基數(shù)匹配問題x3x1x2 y2y1y3x4x5y4y5 該問題也可用矩陣表示如果 xi 會做 yj否則11111111110 0 0000000000000 在矩陣中尋找什么？ 尋找最多的不同行不同列的 1 元素 .(二部圖 G 的 鄰接矩陣 ) 稱為獨立元（素）第四章 指派問題如何尋找 ？ 禮讓原則 從每行、每列中， 1 最少的行或列先取，一樣多時隨意 . 遺憾的是這是錯的 167。3 指派問題的應(yīng)用167。信息處理中的組合優(yōu)化 第四章 指派問題 指派 問題 （ Assignment Probl
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1