分配問題與匈牙利法.pptVIP

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