第5章指派問題

1、運運 籌籌 帷帷 幄幄 之之 中中決決 勝勝 千千 里里 之之 外外整數(shù)規(guī)劃整數(shù)規(guī)劃Integer Programming Integer Programming 第五五章一、一、01變量及其應(yīng)用變量及其應(yīng)用 01變量常被用來表示系統(tǒng)是否處于某個特定狀態(tài)，變量常被用來表示系統(tǒng)是否處于某個特定狀態(tài)，或者決策時是否取某個特定方案。例如或者決策時是否取某個特定方案。例如: : x1,P0,P 策策取取方方案案策策不不取取方方案案當(dāng)當(dāng)決決時時當(dāng)當(dāng)決決時時當(dāng)問題有多項要素，每項要素皆有兩種選擇時，可用一組當(dāng)問題有多項要素，每項要素皆有兩種選擇時，可用一組01變量來描述。設(shè)問題有有限項要素變量來描述。設(shè)問

2、題有有限項要素E1， E2，En,其其中每項中每項Ej有兩種選擇有兩種選擇Aj和不選擇和不選擇Aj（j=1,2,n,n）,則令則令jjjjjEAx jnEA1,(1,2,)0, L L若若若若選選擇擇選選擇擇在應(yīng)用中，有時會遇到變量可以取多個整數(shù)值的問題。如在應(yīng)用中，有時會遇到變量可以取多個整數(shù)值的問題。如果用果用01變量來表示，也可以用一組變量來表示，也可以用一組01變量來取代。變量來取代。 如如x取取09之間的任意整數(shù)時。之間的任意整數(shù)時。 x=20 x0+ 21x1 + 22x2 + 23x3 9（1）兩個約束中，只有一個起作用。兩個約束中，只有一個起作用。 例：例：a11x1+a12x

3、2B1 a21x1+a22x2B2 例例5.9 含有相互排斥的約束條件的問題含有相互排斥的約束條件的問題解：引入解：引入0-1變量變量Y1, Y2和足夠大的正數(shù)和足夠大的正數(shù)M，則，則 a11x1+a12x2B1+M1Y1 a21x1+a22x20（3 3）若）若a個約束條件中只能有個約束條件中只能有b個起作用。個起作用。 則令則令01變量之和為變量之和為a-b。 注意：可用統(tǒng)一注意：可用統(tǒng)一M，但，但M的取值必須足夠的大。的取值必須足夠的大。例例5.10 固定費用問題固定費用問題解：設(shè)解：設(shè)Xj是第是第j種產(chǎn)品的產(chǎn)量。種產(chǎn)品的產(chǎn)量。Yj是是01變量，表示是（變量，表示是（Yj=1）否（否（Y

4、j=0）生產(chǎn)第）生產(chǎn)第j種產(chǎn)品。種產(chǎn)品。 單耗量 產(chǎn)品資源IIIIII資源量A248500B234300C123100單件可變費用456固定費用100150200單件售價81012maxZ=4X1 +5X2 +6X3 100Y1 150Y2 200Y3 2X1+4X2 +8X3 5005002X1+3X2 +4X3 300300X1+2X2 +3X3 100100X1 M1Y1 X2 M2Y2X3 M3 Y3X1 , X2 , X3 0 整數(shù)整數(shù)Y1 ,Y2 ,Y3為為01變量變量。 s.t.用用4臺機床加工臺機床加工3件產(chǎn)品。各產(chǎn)品的機床加工順序，以及產(chǎn)件產(chǎn)品。各產(chǎn)品的機床加工順序，以及產(chǎn)品

5、品I在機床在機床j上加工工時上加工工時aij見表。見表。例例5.11 工件排序問題工件排序問題 由于某種原因，產(chǎn)品由于某種原因，產(chǎn)品2 2的加工總時間不得超過的加工總時間不得超過d d，現(xiàn)要，現(xiàn)要求確定各件產(chǎn)品在機床上的加工方案，使在最短的時間內(nèi)求確定各件產(chǎn)品在機床上的加工方案，使在最短的時間內(nèi)加工完全部產(chǎn)品。加工完全部產(chǎn)品。產(chǎn)品1產(chǎn)品2產(chǎn)品3a11機床1a21機床1a13機床3a22機床2a23機床2a33機床3a14機床4a24機床4機床機床1 ： x11+a11 x21+ My1 及及 x21+a21 x11 + M(1-y1 )機床機床2 ： x22+a22 x32 + My2 及及

6、x32+a32 x22 + M(1-y2)機床機床3 ： x13+a13 x33 + My3 及及 x33+a33 x13 + M(1-y3)機床機床4： x14+a14 x24 + My4 及及 x24+a24 x14 + M(1-y4)解：設(shè)產(chǎn)品解：設(shè)產(chǎn)品i在機床在機床j上開始加工的時間為上開始加工的時間為xij（1）同一件產(chǎn)品在不同機床上的加工順序約束）同一件產(chǎn)品在不同機床上的加工順序約束（2）每一臺機床對不同產(chǎn)品上的加工順序約束）每一臺機床對不同產(chǎn)品上的加工順序約束產(chǎn)品產(chǎn)品1 ： x11+a11 x13 及及 x13+a13 x14產(chǎn)品產(chǎn)品2 ： x21+a21 x22 及及 x22+

7、a22 x24 產(chǎn)品產(chǎn)品3 ： x32+a32 x33（4）目標(biāo)函數(shù)的建立）目標(biāo)函數(shù)的建立x24+ a24 -x21 d d（3）產(chǎn)品）產(chǎn)品2的加工時間總約束的加工時間總約束w x14+a14 w x24+a24 w x33+a33min z=wmin z=max(x14+a14 , x24+a24 , x33+a33)隱枚舉法隱枚舉法(max)原則：原則：1 1、用試探法，求出一個可行解，以它的目標(biāo)值作為當(dāng)前最、用試探法，求出一個可行解，以它的目標(biāo)值作為當(dāng)前最好值好值Z02 2、增加過濾條件、增加過濾條件Z Z03 3、將、將xi 按按ci由小由小大排列（大排列（min 大大小小） 01 整

8、數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量變量xi 只取兩個值只取兩個值0 0或或1 1，一般的解法為隱枚舉法。，一般的解法為隱枚舉法。例例5.12：max z = 3x1 -2x2+5x3x1 +2x2 - x3 2 x1 +4x2 +x3 4 x1 + x2 3 4x2+x3 6 x1 , x2 , x3為為0或或1解：解： 觀察得解觀察得解(x1 , x2 , x3 )T=(1 ,0 ,0)T Z0 =3過濾條件過濾條件：3x1 - 2x2+5x3 3將將(x1 ， x2 ，x3 )T (x2 ，x1 ，x3 )T 解解(x2 x1 x3

9、) 目標(biāo)值目標(biāo)值 Z0 當(dāng)前最好值當(dāng)前最好值 (0 ,0 ,0) 0 5 (0 ,1 ,0) 3 8 (1 ,0 ,0) -2 (1 ,0 ,1) 3 (1 ,1 ,0) 1 (1 ,1 ,1) 6 最優(yōu)解最優(yōu)解 x = (1 ,0 ,1 )T Z=8設(shè)設(shè)n 個人被分配去做個人被分配去做n 件工作，規(guī)定每個人只做一件工作，件工作，規(guī)定每個人只做一件工作，每件工作只有一個人去做。已知第每件工作只有一個人去做。已知第i個人去做第個人去做第j 件工作的效率件工作的效率（ 時間或費用）為時間或費用）為Cij(i=1.2n;j=1.2n)并假設(shè)并假設(shè)Cij 0。問應(yīng)。問應(yīng)如何分配才能使總效率（如何分配才

10、能使總效率（ 時間或費用）最高？時間或費用）最高？設(shè)決策變量設(shè)決策變量 ),.,2 , 1,(ji0ji1njixij 件件事事個個人人做做第第不不指指派派第第件件事事個個人人做做第第指指派派第第指派問題的數(shù)學(xué)模型為：指派問題的數(shù)學(xué)模型為： ).2.1,1(0).2.1( 1).2.1( 1min1111njixnjxnixxcZijniijnjijninjijij或或取取如果從分配問題效率矩陣如果從分配問題效率矩陣aij的每一行元素中分別減去的每一行元素中分別減去(或加上或加上)一個常數(shù)一個常數(shù)ui，從每一列中分別減去，從每一列中分別減去(或加上或加上)一個常數(shù)一個常數(shù)vj，得到一個新的效率

11、矩陣，得到一個新的效率矩陣bij，則以，則以bij為效率矩陣的分配為效率矩陣的分配問題與以問題與以aij為效率矩陣的分配問題具有相同的最優(yōu)解。為效率矩陣的分配問題具有相同的最優(yōu)解。1) 變換指派問題的系數(shù)矩陣變換指派問題的系數(shù)矩陣(cij)為為(bij)，使在，使在(bij)的各行各列的各行各列中都出現(xiàn)中都出現(xiàn)0元素，即元素，即 從從(cij)的每行元素都減去該行的最小元素；的每行元素都減去該行的最小元素； 再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。再從所得新系數(shù)矩陣的每列元素中減去該列的最小元素。2) 進行試指派，以尋求最優(yōu)解。進行試指派，以尋求最優(yōu)解。 在在(bij)中找盡可能多的

12、獨立中找盡可能多的獨立0元素，若能找出元素，若能找出n個獨立個獨立0元元素，就以這素，就以這n個獨立個獨立0元素對應(yīng)解矩陣元素對應(yīng)解矩陣(xij)中的元素為中的元素為1，其余，其余為為0，這就得到最優(yōu)解。，這就得到最優(yōu)解。找獨立找獨立0元素，常用的步驟為：元素，常用的步驟為： 從只有一個從只有一個0元素的行開始，給該行中的元素的行開始，給該行中的0元素加圈，記作元素加圈，記作 。然后劃去然后劃去 所在列的其它所在列的其它0元素，記作元素，記作 ；這表示該列所代表的；這表示該列所代表的任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。任務(wù)已指派完，不必再考慮別人了。依次進行到最后一行。 從只有

13、一個從只有一個0元素的列開始（畫元素的列開始（畫的不計在內(nèi)），給該列中的的不計在內(nèi)），給該列中的0元素加圈，記作；然后劃去元素加圈，記作；然后劃去 所在行的所在行的0元素，記作元素，記作 ，表示，表示此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。此人已有任務(wù)，不再為其指派其他任務(wù)了。依次進行到最后一列。 若仍有沒有劃圈的若仍有沒有劃圈的0元素，且同行元素，且同行(列列)的的0元素至少有兩個，比元素至少有兩個，比較這行各較這行各0元素所在列中元素所在列中0元素的數(shù)目，選擇元素的數(shù)目，選擇0元素少這個元素少這個0元素加元素加圈圈(表示選擇性多的要表示選擇性多的要“禮讓禮讓”選擇性少的選

14、擇性少的)。然后劃掉同行同列。然后劃掉同行同列的其它的其它0元素?？煞磸?fù)進行，直到所有元素?？煞磸?fù)進行，直到所有0元素都已圈出和劃掉為止。元素都已圈出和劃掉為止。 若若 元素的數(shù)目元素的數(shù)目m 等于矩陣的階數(shù)等于矩陣的階數(shù)n（即：（即：mn），那么這指，那么這指派問題的最優(yōu)解已得到。若派問題的最優(yōu)解已得到。若m n, 則轉(zhuǎn)入下一步。則轉(zhuǎn)入下一步。3) 用最少的直線通過所有用最少的直線通過所有0元素。其方法：元素。其方法： 對沒有的行打?qū)]有的行打“”； 對已打?qū)σ汛颉啊?的行中所有含的行中所有含元素的列打元素的列打“” ； 再對打有再對打有“”的列中含的列中含 元素的行打元素的行打“” ； 重

15、復(fù)、直到得不出新的打重復(fù)、直到得不出新的打號的行、列為止；號的行、列為止； 對沒有打?qū)]有打號的行畫橫線，有打號的行畫橫線，有打號的列畫縱線，這就得到覆蓋號的列畫縱線，這就得到覆蓋所有所有0元素的最少直線數(shù)元素的最少直線數(shù) l 。注：注：l 應(yīng)等于應(yīng)等于m，若不相等，說明試指派過程有誤，回到第，若不相等，說明試指派過程有誤，回到第2步，另行試步，另行試指派；若指派；若 lm n，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系，表示還不能確定最優(yōu)指派方案，須再變換當(dāng)前的系數(shù)矩陣，以找到數(shù)矩陣，以找到n個獨立的個獨立的0元素，為此轉(zhuǎn)第元素，為此轉(zhuǎn)第4步。步。4) 變換矩陣變換矩陣(bij)以增加以增

16、加0元素元素在沒有被直線通過的所有元素中找出最小值，沒有被直在沒有被直線通過的所有元素中找出最小值，沒有被直線通過的所有元素減去這個最小元素；直線交點處的元素加線通過的所有元素減去這個最小元素；直線交點處的元素加上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回上這個最小值。新系數(shù)矩陣的最優(yōu)解和原問題仍相同。轉(zhuǎn)回第第2步。步。例例5.13 有一份中文說明書，需譯成英、日、德、俄四種文字，有一份中文說明書，需譯成英、日、德、俄四種文字，分別記作分別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問中文說明書譯成

17、不同語種的說明書所需時間如下表所示，問如何分派任務(wù)，可使總時間最少？如何分派任務(wù)，可使總時間最少？ 任務(wù)人員ABCD甲67112乙4598丙31104丁5982解：解：1）變換系數(shù)矩陣，增加變換系數(shù)矩陣，增加0元素。元素。2142 289541013895421176)( ijc 06733902451009545 01733402401004542）試指派（找獨立）試指派（找獨立0元素）元素）找到找到 3 個獨立零元素個獨立零元素 但但 m = 3 n = 43）作最少的直線覆蓋所有作最少的直線覆蓋所有0元素元素立零元素的個數(shù)獨立零元素的個

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

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

20、甲負責(zé)派方案即為甲負責(zé)D工作，乙負責(zé)工作，乙負責(zé)B工作，工作，丙負責(zé)丙負責(zé)A工作，丁負責(zé)工作，丁負責(zé)C工作。這樣安排工作。這樣安排能使總的工作時間最少，為能使總的工作時間最少，為4491128。例例5.15 已知五人分別完成五項工作耗費如下表，求最優(yōu)分已知五人分別完成五項工作耗費如下表，求最優(yōu)分配方案。配方案。 任務(wù)人員ABCDE甲759811乙9127119丙85468丁73696戊4675114347511576469637964589117129118957 7132036304520142405263402-1 -2解：解：1）變換系數(shù)矩陣，增加）變換系數(shù)矩陣，增加0元素。元素。 50

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

22、持不，其他保持不變，得到新的系數(shù)矩陣。變，得到新的系數(shù)矩陣。 6044003202300230206130300總費用為總費用為=5+7+6+6+4=28=5+7+6+6+4=28注：此問題有多個最優(yōu)解注：此問題有多個最優(yōu)解 6044003202300230206130300總費用為總費用為=7+9+4+3+5=28=7+9+4+3+5=28 6044003202300230206130300總費用為總費用為=8+9+4+3+4=28=8+9+4+3+4=28課堂練習(xí)：用匈牙利法求解下列指派問題。課堂練習(xí)：用匈牙利法求解下列指派問題。79 10 1213 12 16 1715 16 14 15

23、11 12 15 163821038729764275842359106910練習(xí)練習(xí)1：練習(xí)練習(xí)2：79 10 1213 12 16 1715 16 14 1511 12 15 1638210387297642758423591069104848 21 21答案：答案：匈牙利法的條件是：模型求最小值、效率匈牙利法的條件是：模型求最小值、效率cij0。當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時，處理方法是先將當(dāng)遇到各種非標(biāo)準(zhǔn)形式的指派問題時，處理方法是先將其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。其轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利法來求解。處理方法：設(shè)處理方法：設(shè)m為最大化指派問題系數(shù)矩陣為最大化指派問題系數(shù)

24、矩陣C中最大元素。中最大元素。令矩陣令矩陣B（m-cij）nn則以則以B為系數(shù)矩陣的最小化指派問題和為系數(shù)矩陣的最小化指派問題和原問題有相同的最優(yōu)解。原問題有相同的最優(yōu)解。例例5.16 某人事部門擬招聘某人事部門擬招聘4人任職人任職4項工作，對他們綜合考評項工作，對他們綜合考評的的 得分如下表（滿分得分如下表（滿分100分），如何安排工作使總分最多。分），如何安排工作使總分最多。 88809086907983829578879590739285丁丁丙丙乙乙甲甲C解解: M95，令，令)95(ijcC 71559516121301780522310C用匈牙利法求解用匈牙利法求解C，最優(yōu)解為：，最

25、優(yōu)解為： 0100100000010010X即甲安排做第二項工作、乙做第三項、丙做第四項、丁做即甲安排做第二項工作、乙做第三項、丙做第四項、丁做第三項第三項, 最高總分最高總分Z92959080357 當(dāng)人數(shù)當(dāng)人數(shù)m大于工作數(shù)大于工作數(shù)n時，加上時，加上mn項虛擬工作，項虛擬工作，例如：例如： 1235461714836111095 00000000001235461714836111095 當(dāng)人數(shù)當(dāng)人數(shù)m小于工作數(shù)小于工作數(shù)n時，加上時，加上nm個人，個人，例如例如 1716131074569102015 00001716131074569102015若某人可做幾件事，則將該人化作相同的幾個若某