第二題 指派問題

1、Page 1將該人做此事的效率系數(shù)取做足夠大的數(shù)，可用將該人做此事的效率系數(shù)取做足夠大的數(shù)，可用M表示。表示。例例4.10 分配甲、乙、丙、丁四個(gè)人去完成分配甲、乙、丙、丁四個(gè)人去完成A、B、C、D、E五項(xiàng)五項(xiàng)任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人任務(wù)。每個(gè)人完成各項(xiàng)任務(wù)的時(shí)間如表所示。由于任務(wù)數(shù)多于人數(shù)，考慮任務(wù)數(shù)，考慮任務(wù)E必須完成，其他必須完成，其他4項(xiàng)中可任選項(xiàng)中可任選3項(xiàng)完成。試確定最項(xiàng)完成。試確定最優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。優(yōu)分配方案，使完成任務(wù)的總時(shí)間最少。 任務(wù)任務(wù)人員人員ABCDE甲甲2529314237乙乙3938262033丙丙34272840

2、32丁丁2442362345Page 2解解: 1) 這是不平衡的指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利這是不平衡的指派問題，首先轉(zhuǎn)換為標(biāo)準(zhǔn)型，再用匈牙利法求解。法求解。2) 由于任務(wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因?yàn)楣び捎谌蝿?wù)數(shù)多于人數(shù)，所以假定一名虛擬人，設(shè)為戊。因?yàn)楣ぷ髯鱁必須完成，故設(shè)戊完成必須完成，故設(shè)戊完成E的時(shí)間為的時(shí)間為M（M為非常大的數(shù)），其為非常大的數(shù)），其余效率系數(shù)為余效率系數(shù)為0，則標(biāo)準(zhǔn)型的效率矩陣表示為：，則標(biāo)準(zhǔn)型的效率矩陣表示為： 任務(wù)任務(wù)人員人員ABCDE甲甲2529314237乙乙3938262033丙丙3427284032丁丁2442362345戊戊

3、0000MPage 3用匈牙利法求出最優(yōu)指派方案為：用匈牙利法求出最優(yōu)指派方案為： 0010000001100000100000010即甲即甲B，乙，乙D，丙，丙E，丁，丁A, 任務(wù)任務(wù)C放棄。放棄。最少時(shí)間為最少時(shí)間為105。Page 4例例4.6 有一份中文說明書，需譯成英、日、德、俄四種文字，有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問中文說明書譯成不同語種的說明書所需時(shí)間如下表所示，問如何分派任務(wù)，可使總時(shí)間最少？如何分派任務(wù)，可使總時(shí)間

4、最少？ 任務(wù)任務(wù)人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982Page 5解：解：1）變換系數(shù)矩陣，增加變換系數(shù)矩陣，增加0元素。元素。2142 289541013895421176)( ijc 06733902451009545 01733402401004542）試指派（找獨(dú)立）試指派（找獨(dú)立0元素）元素）找到找到 3 個(gè)獨(dú)立零元素個(gè)獨(dú)立零元素 但但 m = 3 n = 4Page 63）作最少的直線覆蓋所有作最少的直線覆蓋所有0元素元素立零元素的個(gè)數(shù)獨(dú)立零元素的個(gè)數(shù)m等于最少等于最少直線數(shù)直線數(shù)l，即，即lm=3n

5、=4；4）沒有被直線通過的元素中選擇最小值為）沒有被直線通過的元素中選擇最小值為1，變換系數(shù)矩，變換系數(shù)矩陣，將沒有被直線通過的所有元素減去這個(gè)最小元素；直陣，將沒有被直線通過的所有元素減去這個(gè)最小元素；直線交點(diǎn)處的元素加上這個(gè)最小值。得到新的矩陣，重復(fù)線交點(diǎn)處的元素加上這個(gè)最小值。得到新的矩陣，重復(fù)2）步進(jìn)行試指派步進(jìn)行試指派Page 7 6244251343000 0 00試指派試指派 6244251343得到得到4個(gè)獨(dú)立零元素，個(gè)獨(dú)立零元素， 所以最優(yōu)解矩陣為：所以最優(yōu)解矩陣為： 0100001000011000即完成即完成4個(gè)任務(wù)的總時(shí)間最少個(gè)任務(wù)的總時(shí)間最少為：為：241+8=15P

6、age 8例例4.7 已知四人分別完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)已知四人分別完成四項(xiàng)工作所需時(shí)間如下表，求最優(yōu)分配方案。分配方案。 任務(wù)任務(wù)人員人員ABCD甲甲215134乙乙1041415丙丙9141613丁丁78119Page 9解：解：1）變換系數(shù)矩陣，增加變換系數(shù)矩陣，增加0元素。元素。79429118713161491514410413152 2424104750111006211130 00102350960607130 001023509606071302）試指派（找獨(dú)立）試指派（找獨(dú)立0元素）元素） 獨(dú)立獨(dú)立0元素的個(gè)數(shù)為元素的個(gè)數(shù)為4 , 指派問題的最優(yōu)指指派問題的最優(yōu)指

7、派方案即為甲負(fù)責(zé)派方案即為甲負(fù)責(zé)D工作，乙負(fù)責(zé)工作，乙負(fù)責(zé)B工作，工作，丙負(fù)責(zé)丙負(fù)責(zé)A工作，丁負(fù)責(zé)工作，丁負(fù)責(zé)C工作。這樣安排工作。這樣安排能使總的工作時(shí)間最少，為能使總的工作時(shí)間最少，為4491128。Page 10例例4.8 已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最優(yōu)分已知五人分別完成五項(xiàng)工作耗費(fèi)如下表，求最優(yōu)分配方案。配方案。 任務(wù)任務(wù)人員人員ABCDE甲甲759811乙乙9127119丙丙85468丁丁73696戊戊467511Page 114347511576469637964589117129118957 7132036304520142405263402-1 -2解：解：1）變換

8、系數(shù)矩陣，增加）變換系數(shù)矩陣，增加0元素。元素。Page 12 5032015304310140305242402 50320153043101403052424022）試指派（找獨(dú)立）試指派（找獨(dú)立0元素）元素） 獨(dú)立獨(dú)立0元素的個(gè)數(shù)元素的個(gè)數(shù)l45，故畫直線調(diào)整矩陣。，故畫直線調(diào)整矩陣。Page 13 5032015304310140305242402選擇直線外的最小元素選擇直線外的最小元素為為1；直線外元素減；直線外元素減1，直線交點(diǎn)元素加直線交點(diǎn)元素加1，其，其他保持不變。他保持不變。Page 14 5033004203310240306231301l =m=4 n=5選擇直線外最小元

9、素為選擇直線外最小元素為1，直線外元素減直線外元素減1，直線交，直線交點(diǎn)元素加點(diǎn)元素加1，其他保持不，其他保持不變，得到新的系數(shù)矩陣。變，得到新的系數(shù)矩陣。Page 15 6044003202300230206130300總費(fèi)用為總費(fèi)用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問題有多個(gè)最優(yōu)解注：此問題有多個(gè)最優(yōu)解Page 16 6044003202300230206130300總費(fèi)用為總費(fèi)用為=7+9+4+3+5=28=7+9+4+3+5=28Page 17 6044003202300230206130300總費(fèi)用為總費(fèi)用為=8+9+4+3+4=28=8+9+4+3+4=2

10、8Page 18課堂練習(xí)：用匈牙利法求解下列指派問題。課堂練習(xí)：用匈牙利法求解下列指派問題。79 10 1213 12 16 1715 16 14 1511 12 15 163821038729764275842359106910練習(xí)練習(xí)1：練習(xí)練習(xí)2：Page 1979 10 1213 12 16 1715 16 14 1511 12 15 1638210387297642758423591069104848 21 21答案：答案：Page 20匈牙利法的條件是：模型求最小值、效率匈牙利法的條件是：模型求最小值、效率cij0。當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時(shí)，處理方法是先將當(dāng)遇到各種非標(biāo)準(zhǔn)形

11、式的指派問題時(shí)，處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。Page 21處理方法：設(shè)處理方法：設(shè)m為最大化指派問題系數(shù)矩陣為最大化指派問題系數(shù)矩陣C中最大元素。中最大元素。令矩陣令矩陣B（m-cij）nn則以則以B為系數(shù)矩陣的最小化指派問題和為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解。原問題有相同的最優(yōu)解。例例4.9 某人事部門擬招聘某人事部門擬招聘4人任職人任職4項(xiàng)工作，對他們綜合考評的項(xiàng)工作，對他們綜合考評的 得分如下表（滿分得分如下表（滿分100分），如何安排工作使總分最多。分），如何安排工作使總分最多。 888090869079

12、83829578879590739285丁丁丙丙乙乙甲甲CPage 22解解: M95，令，令)95(ijcC 71559516121301780522310C用匈牙利法求解用匈牙利法求解C，最優(yōu)解為：，最優(yōu)解為： 0100100000010010X即甲安排做第二項(xiàng)工作、乙做第三項(xiàng)、丙做第四項(xiàng)、丁做即甲安排做第二項(xiàng)工作、乙做第三項(xiàng)、丙做第四項(xiàng)、丁做第三項(xiàng)第三項(xiàng), 最高總分最高總分Z92959080357Page 23 當(dāng)人數(shù)當(dāng)人數(shù)m大于工作數(shù)大于工作數(shù)n時(shí)，加上時(shí)，加上mn項(xiàng)虛擬工作，項(xiàng)虛擬工作，例如：例如： 1235461714836111095 00000000001235461714836111095 當(dāng)人數(shù)當(dāng)人數(shù)m小于工作數(shù)小于工作數(shù)n時(shí)，加上時(shí)，加上nm個(gè)人，個(gè)人，例如例如 1716131074569102015 0000171613107