第二題 指派問題

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

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

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

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

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

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

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

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

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

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

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

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