分配問題與匈牙利法.ppt

分配問題與匈牙利法 指派問題的數(shù)學(xué)模型的標(biāo)準(zhǔn)形式 設(shè)n個(gè)人被分配去做n件工作 規(guī)定每個(gè)人只做一件工作 每件工作只有一個(gè)人去做 已知第i個(gè)人去做第j件工作的效率 時(shí)間或費(fèi)用 為Cij i 1 2 n j 1 2 n 并假設(shè)Cij 0 問應(yīng)如何分配才能使總效率 時(shí)間或費(fèi)用 最高 設(shè)決策變量 分配問題與匈牙利法 指派問題的數(shù)學(xué)模型為 分配問題與匈牙利法 克尼格定理 如果從分配問題效率矩陣 aij 的每一行元素中分別減去 或加上 一個(gè)常數(shù)ui 從每一列中分別減去 或加上 一個(gè)常數(shù)vj 得到一個(gè)新的效率矩陣 bij 則以 bij 為效率矩陣的分配問題與以 aij 為效率矩陣的分配問題具有相同的最優(yōu)解 分配問題與匈牙利法 指派問題的求解步驟 1 變換指派問題的系數(shù)矩陣 cij 為 bij 使在 bij 的各行各列中都出現(xiàn)0元素 即從 cij 的每行元素都減去該行的最小元素 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素 2 進(jìn)行試指派 以尋求最優(yōu)解 在 bij 中找盡可能多的獨(dú)立0元素 若能找出n個(gè)獨(dú)立0元素 就以這n個(gè)獨(dú)立0元素對應(yīng)解矩陣 xij 中的元素為1 其余為0 這就得到最優(yōu)解 分配問題與匈牙利法 找獨(dú)立0元素 常用的步驟為 從只有一個(gè)0元素的行開始 給該行中的0元素加圈 記作 然后劃去 所在列的其它0元素 記作 這表示該列所代表的任務(wù)已指派完 不必再考慮別人了 依次進(jìn)行到最后一行 從只有一個(gè)0元素的列開始 畫 的不計(jì)在內(nèi) 給該列中的0元素加圈 記作 然后劃去 所在行的0元素 記作 表示此人已有任務(wù) 不再為其指派其他任務(wù)了 依次進(jìn)行到最后一列 若仍有沒有劃圈的0元素 且同行 列 的0元素至少有兩個(gè) 比較這行各0元素所在列中0元素的數(shù)目 選擇0元素少這個(gè)0元素加圈 表示選擇性多的要 禮讓 選擇性少的 然后劃掉同行同列的其它0元素 可反復(fù)進(jìn)行 直到所有0元素都已圈出和劃掉為止 分配問題與匈牙利法 若 元素的數(shù)目m等于矩陣的階數(shù)n 即 m n 那么這指派問題的最優(yōu)解已得到 若m n 則轉(zhuǎn)入下一步 3 用最少的直線通過所有0元素 其方法 對沒有 的行打 對已打 的行中所有含 元素的列打 再對打有 的列中含 元素的行打 重復(fù) 直到得不出新的打 號(hào)的行 列為止 對沒有打 號(hào)的行畫橫線 有打 號(hào)的列畫縱線 這就得到覆蓋所有0元素的最少直線數(shù)l 注 l應(yīng)等于m 若不相等 說明試指派過程有誤 回到第2步 另行試指派 若l m n 表示還不能確定最優(yōu)指派方案 須再變換當(dāng)前的系數(shù)矩陣 以找到n個(gè)獨(dú)立的0元素 為此轉(zhuǎn)第4步 分配問題與匈牙利法 4 變換矩陣 bij 以增加0元素在沒有被直線通過的所有元素中找出最小值 沒有被直線通過的所有元素減去這個(gè)最小元素 直線交點(diǎn)處的元素加上這個(gè)最小值 新系數(shù)矩陣的最優(yōu)解和原問題仍相同 轉(zhuǎn)回第2步 分配問題與匈牙利法 例4 6有一份中文說明書 需譯成英 日 德 俄四種文字 分別記作A B C D 現(xiàn)有甲 乙 丙 丁四人 他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示 問如何分派任務(wù) 可使總時(shí)間最少 分配問題與匈牙利法 解 1 變換系數(shù)矩陣 增加0元素 5 2 試指派 找獨(dú)立0元素 找到3個(gè)獨(dú)立零元素但m 3 n 4 分配問題與匈牙利法 3 作最少的直線覆蓋所有0元素 獨(dú)立零元素的個(gè)數(shù)m等于最少直線數(shù)l 即l m 3 n 4 4 沒有被直線通過的元素中選擇最小值為1 變換系數(shù)矩陣 將沒有被直線通過的所有元素減去這個(gè)最小元素 直線交點(diǎn)處的元素加上這個(gè)最小值 得到新的矩陣 重復(fù)2 步進(jìn)行試指派 分配問題與匈牙利法 試指派 得到4個(gè)獨(dú)立零元素 所以最優(yōu)解矩陣為 即完成4個(gè)任務(wù)的總時(shí)間最少為 2 4 1 8 15 分配問題與匈牙利法 例4 7已知四人分別完成四項(xiàng)工作所需時(shí)間如下表 求最優(yōu)分配方案 分配問題與匈牙利法 解 1 變換系數(shù)矩陣 增加0元素 2 試指派 找獨(dú)立0元素 獨(dú)立0元素的個(gè)數(shù)為4 指派問題的最優(yōu)指派方案即為甲負(fù)責(zé)D工作 乙負(fù)責(zé)B工作 丙負(fù)責(zé)A工作 丁負(fù)責(zé)C工作 這樣安排能使總的工作時(shí)間最少 為4 4 9 11 28 分配問題與匈牙利法 例4 8已知五人分別完成五項(xiàng)工作耗費(fèi)如下表 求最優(yōu)分配方案 分配問題與匈牙利法 1 2 解 1 變換系數(shù)矩陣 增加0元素 分配問題與匈牙利法 2 試指派 找獨(dú)立0元素 獨(dú)立0元素的個(gè)數(shù)l 4 5 故畫直線調(diào)整矩陣 分配問題與匈牙利法 選擇直線外的最小元素為1 直線外元素減1 直線交點(diǎn)元素加1 其他保持不變 分配問題與匈牙利法 l m 4 n 5 選擇直線外最小元素為1 直線外元素減1 直線交點(diǎn)元素加1 其他保持不變 得到新的系數(shù)矩陣 分配問題與匈牙利法 總費(fèi)用為 5 7 6 6 4 28 注 此問題有多個(gè)最優(yōu)解 分配問題與匈牙利法 總費(fèi)用為 7 9 4 3 5 28 分配問題與匈牙利法 總費(fèi)用為 8 9 4 3 4 28 分配問題與匈牙利法 課堂練習(xí) 用匈牙利法求解下列指派問題 練習(xí)1 練習(xí)2 分配問題與匈牙利法 48 21 答案 分配問題與匈牙利法 非標(biāo)準(zhǔn)型的指派問題 匈牙利法的條件是 模型求最小值 效率cij 0 當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時(shí) 處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式 然后用匈牙利法來求解 分配問題與匈牙利法 1 最大化指派問題 處理方法 設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素 令矩陣B m cij nn則以B為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解 例4 9某人事部門擬招聘4人任職4項(xiàng)工作 對他們綜合考評的得分如下表 滿分100分 如何安排工作使總分最多 分配問題與匈牙利法 解 M 95 令 用匈牙利法求解C 最優(yōu)解為 即甲安排做第二項(xiàng)工作 乙做第三項(xiàng) 丙做第四項(xiàng) 丁做第三項(xiàng) 最高總分Z 92 95 90 80 357 分配問題與匈牙利法 2 不平衡的指派問題 當(dāng)人數(shù)m大于工作數(shù)n時(shí) 加上m n項(xiàng)虛擬工作 例如 當(dāng)人數(shù)m小于工作數(shù)n時(shí) 加上n m個(gè)人 例如 分配問題與匈牙利法 3 一個(gè)人可做幾件事的指派問題 若某人可做幾件事 則將該人化作相同的幾個(gè) 人 來接受指派 且費(fèi)用系數(shù)取值相同 例如 丙可以同時(shí)任職A和C工作 求最優(yōu)指派方案 分配問題與匈牙利法 4 某事一定不能由某人做的指派問題 將該人做此事的效率系數(shù)取做足夠大的數(shù) 可用M表示 例4 10分配甲 乙 丙 丁四個(gè)人去完成A B C D E五項(xiàng)任務(wù) 每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示 由于任務(wù)數(shù)多于人數(shù) 考慮任務(wù)E必須完成 其他4項(xiàng)中可任選3項(xiàng)完成 試確定最優(yōu)分配方案 使完成任務(wù)的總時(shí)間最少 分配問題與匈牙利法 解 1 這是不平衡的指派問題 首先轉(zhuǎn)換為標(biāo)準(zhǔn)型