《題指派問題》PPT課件

1、分配問題與匈牙利法,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)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。 2) 由于任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因為工作E必須完成，故設(shè)戊完成E的時間為M（M為非常大的數(shù)），其余效率系數(shù)為0，則標(biāo)準(zhǔn)型的效率矩陣表示為,分配問題與匈牙利法,用匈牙

2、利法求出最優(yōu)指派方案為,即甲B，乙D，丙E，丁A, 任務(wù)C放棄。 最少時間為105,分配問題與匈牙利法,例4.6 有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少,分配問題與匈牙利法,解：1）變換系數(shù)矩陣，增加0元素,5,2）試指派（找獨立0元素,找到 3 個獨立零元素 但 m = 3 n = 4,分配問題與匈牙利法,3）作最少的直線覆蓋所有0元素,獨立零元素的個數(shù)m等于最少直線數(shù)l，即lm=3n=4,4）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩陣，將沒

3、有被直線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。得到新的矩陣，重復(fù)2）步進行試指派,分配問題與匈牙利法,試指派,得到4個獨立零元素， 所以最優(yōu)解矩陣為,即完成4個任務(wù)的總時間最少為：241+8=15,分配問題與匈牙利法,例4.7 已知四人分別完成四項工作所需時間如下表，求最優(yōu)分配方案,分配問題與匈牙利法,解：1）變換系數(shù)矩陣，增加0元素,2）試指派（找獨立0元素,獨立0元素的個數(shù)為4 , 指派問題的最優(yōu)指派方案即為甲負責(zé)D工作，乙負責(zé)B工作，丙負責(zé)A工作，丁負責(zé)C工作。這樣安排能使總的工作時間最少，為4491128,分配問題與匈牙利法,例4.8 已知五人分別完成五項工作

4、耗費如下表，求最優(yōu)分配方案,分配問題與匈牙利法,1,2,解：1）變換系數(shù)矩陣，增加0元素,分配問題與匈牙利法,2）試指派（找獨立0元素,獨立0元素的個數(shù)l45，故畫直線調(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,分配

5、問題與匈牙利法,課堂練習(xí)：用匈牙利法求解下列指派問題,練習(xí)1,練習(xí)2,分配問題與匈牙利法,48,21,答案,分配問題與匈牙利法,非標(biāo)準(zhǔn)型的指派問題,匈牙利法的條件是：模型求最小值、效率cij0。 當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時，處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解,分配問題與匈牙利法,1. 最大化指派問題,處理方法：設(shè)m為最大化指派問題系數(shù)矩陣C中最大元素。令矩陣B（m-cij）nn則以B為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解,例4.9 某人事部門擬招聘4人任職4項工作，對他們綜合考評的 得分如下表（滿分100分），如何安排工作使總分最多,分配問題與匈牙利法,解: M95，令,用匈牙利法求解C，最優(yōu)解為,即甲安排做第二項工作、乙做第三項、丙做第四項、丁做第三項, 最高總分Z92959080357,分配問題與匈牙利法,2. 不平衡的指派問題,當(dāng)人數(shù)m大于工作數(shù)n時，加上mn項虛擬工作，例如,當(dāng)人數(shù)m小于工作數(shù)n時，加上nm個人，例如,分配問