指派問題ppt課件(完整版)
【正文】 i 人完成第 j 項(xiàng)任務(wù)否則設(shè).167。3 指派問題的應(yīng)用Example 5 現(xiàn)有 6 項(xiàng)任務(wù)，由 4 個(gè)工廠來完成，已知各個(gè)工廠完成各項(xiàng)任務(wù)的費(fèi)用矩陣為 C ， 應(yīng)如何分配任務(wù)，使總費(fèi)用最小 ？具體分別 無要求 ；一廠至多完成兩項(xiàng) ； 一廠至多完成兩項(xiàng)， 至少完成一項(xiàng) .Solution: 無要求碰巧，符合 3的要求Z min = 13167。Step 2 計(jì)算 yk , 在 中擦去 得 求 的最大匹配 Mk+1 ；Step 3 若 則 Mk 為最優(yōu)解， fmin= yk否則，令 k = k+1， go to step 2 .167。4 瓶頸分配問題167。2 指派問題 顯然， Ex . 2 的可行解可用一個(gè) 01 矩陣表示 . 表示 ： 因此，求解指派問題可在效益矩陣上進(jìn)行 .Theorem 如果從效益矩陣 (cij) 的第 i 行中每個(gè)元素減去 a 和第 j 列中每個(gè)元素加上 b ，得到一個(gè)新的效益矩陣 . 則以 為新的目標(biāo)函數(shù)與原目標(biāo)函數(shù)的指派問題最優(yōu)解相同 . 第四章 指派問題匈牙利算法 ：Step 1 使效益矩陣各行各列出現(xiàn)零元素 ；具體：從效益矩陣的每行各元素減去該行最小元素；再從所得矩陣的每列各元素減去該列最小元素 .稱各行各列所減的數(shù)值之總和為 縮減量 ，記為 S .S = 2+4+9+7+4+2 = 28167。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。3 指派問題的應(yīng)用167。4 瓶頸分配問題第四章 指派問題167。 否則xi 不能被分配 ， 令 Go to Step 2。2 指派問題Step 2 試尋求最優(yōu)解； 用上節(jié)的求最大匹配的算法 .這時(shí)得到最大匹配 M .如果 ，則已得到最優(yōu)解； 即28 = S每行每列有零元素，能保證有 n 個(gè)獨(dú)立零元素嗎？ 如果 ， 則 go to step 3 ；第四章 指派問題Step 3 作縮減后的效益矩陣的 最小覆蓋 ；具體： a、對沒有 0 的行打 √ ； b、對已打 √ 的行中所有含 0 元素的列打 √； c、 對打 √ 的列上有 0 的行打 √； d、重復(fù) b、 c ，直到得不出新的打 √ 的行列 為止； e、對打 √ 的列畫縱線，沒打 √ 行畫橫線 . 這就得到 最小覆蓋 .167。4 瓶頸分配問題經(jīng)典分配問題（ AP） 任務(wù)人員 E J G RA 2 15 13 4B 10 4 14 15C 9 14 16 13D 7 8 11 9每人完成一個(gè)任務(wù)每個(gè)任務(wù)一人完成條件：目標(biāo)： 總完成時(shí)間最少總效益最佳數(shù)學(xué)模型：求解方法： 匈牙利算法.第四章 指派問題瓶頸分配問題 (BAP)每人完成一個(gè)任務(wù)每個(gè)任務(wù)一人完成條件：目標(biāo)： 最大完成時(shí)間最小經(jīng)典分配問題： z = 5 瓶頸分配問題： z = 2數(shù)學(xué)模型： 當(dāng)分配第 i 人完成第 j 項(xiàng)任務(wù)否則設(shè)167。4 瓶頸分配問題 對原效益矩陣 C 的元素 cij 的不同的值按從小到大的順序排序 . c(k) 為第 k 個(gè)值，用 s 表示不同 c(k) 值的個(gè)數(shù)，則定義數(shù)列 d(t) 如下：構(gòu)建新
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1