運籌學__指派問題

1、 在實際中經常會遇到這樣的問題，在實際中經常會遇到這樣的問題，有有n n 項不同的任務，項不同的任務，需要需要n n 個人分別完成其中的一項，個人分別完成其中的一項，但由于任務的性質和各人的專長不同，但由于任務的性質和各人的專長不同，因此各人去完成不同的任務的效率因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。（或花費的時間或費用）也就不同。于是產生了一個于是產生了一個問題問題: :應指派哪個人去完成哪項任務，應指派哪個人去完成哪項任務，使完成使完成 n n 項任務的總效率最高（或所需時間最少），項任務的總效率最高（或所需時間最少），這類問題稱為這類問題稱為指派問題指派問題或分派

2、問題。或分派問題。 有一份中文說明書，有一份中文說明書，要分別譯成要分別譯成英、日、德、俄英、日、德、俄四種文字四種文字，分別記作分別記作E E 、 J J 、 G G 、 R ,R ,交與交與甲、乙、丙、丁甲、乙、丙、丁 四個人四個人去完成去完成. .因個人專長不同，因個人專長不同，他們完成翻譯不同語種的說明書所需的時間他們完成翻譯不同語種的說明書所需的時間(h)(h)如表所示如表所示. .應如何指派，使四個人分別完成這四項任務應如何指派，使四個人分別完成這四項任務總時間總時間為最小？為最?。?任務任務人員人員E EJ JG GR R甲甲2 2151513134 4乙乙10104 41414

3、1515丙丙9 9141416161313丁丁7 78 811 119 9一、指派問題的數學模型一、指派問題的數學模型（一）（一）舉例舉例v這是一個這是一個標準型的指派問題標準型的指派問題指派指派v對應每個指派問題，需有類似上表那樣的數表，對應每個指派問題，需有類似上表那樣的數表，效率效率矩陣矩陣或或系數系數矩陣矩陣C=(cij)nn=c11 c12 c1n c21 c22 c2n cn1 cn1 cnn C=(cij )=2151341041415914161378119則該指派問題的數學模型為：則該指派問題的數學模型為：11121314434441412151341191141140 11

4、4min(, ). .(, )(, )ijjijiijzxxxxxxxistxjxi j或或，求解題時通常需引入求解題時通常需引入0-10-1變量變量：x xij ij=1 (i=1,2,3,4)=1 (i=1,2,3,4)表示第表示第i i人只能完成一項任務人只能完成一項任務Sx xij ij=1 (j=1,2,3,4)=1 (j=1,2,3,4)表示第表示第j j 項任務只能由一人去完成。項任務只能由一人去完成。滿足約束條件的解稱為可行解，滿足約束條件的解稱為可行解，可寫成矩陣形式，叫作可寫成矩陣形式，叫作解矩陣解矩陣。)4 , 1j;4 , 1i (ji, 0ji, 1xij 項項任任務

5、務個個人人去去完完成成第第不不分分配配第第項項任任務務個個人人去去完完成成第第分分配配第第 1000000101000010 xij如本例的一個可行解矩陣（但不一定是最優(yōu)解）如本例的一個可行解矩陣（但不一定是最優(yōu)解）指派問題的指派問題的解矩陣解矩陣應具有如下應具有如下特點特點：（1 1）解矩陣解矩陣(x(xij ij) )中各行各列的元素之和都是中各行各列的元素之和都是1 1；（2 2）可行解（最優(yōu)解）中恰含有個非零元，即可行解（最優(yōu)解）中恰含有個非零元，即4 4個個1 1；（3 3）可行解（最優(yōu)解）矩陣中的可行解（最優(yōu)解）矩陣中的1 1恰取于恰取于不同行不同列。不同行不同列?？梢钥吹娇梢钥吹?/p>

6、指派指派問題問題既是既是0-1 規(guī)劃問題，也是運輸問題規(guī)劃問題，也是運輸問題，所以也可用整數規(guī)劃，所以也可用整數規(guī)劃，0-1 規(guī)劃，規(guī)劃，或運輸問題的解法去求解。或運輸問題的解法去求解。（二）（二）指派問題的數學模型指派問題的數學模型 1. 指派問題的一般指派問題的一般提法提法： v設設m個人被指派去做個人被指派去做m件工作，件工作， 規(guī)定每個人只做一件工作，規(guī)定每個人只做一件工作， 每件工作只有一個人去做。每件工作只有一個人去做。v已知第已知第i個人去做第個人去做第j 件工作的的效率（件工作的的效率（ 時間或費用）時間或費用） 為為cij (i=1.2m;j=1.2m) ，并假設，并假設ci

7、j 0。 問應如何指派才能使總效率最高或總時間問應如何指派才能使總效率最高或總時間 總費用最低總費用最低 ？設設c cij ij 表示指派問題的表示指派問題的效率矩陣效率矩陣，令，令)m, 1j;n, 1i (ji, 0ji, 1xij 項項任任務務個個人人去去完完成成第第不不分分配配第第項項任任務務個個人人去去完完成成第第分分配配第第則指派問題的數學模型一般形式為：則指派問題的數學模型一般形式為： )m, 1jn, 1i (10 x)m, 1j (1x)n, 1i (1x. t . sxczmax)(minijn1iijm1jijm1im1jijij；或或或或x xij ij 為第為第 i

8、i 個人個人指派指派去做去做第第 j j 項任務；項任務；c cij ij 為第為第 i i 個人為完成第個人為完成第 j j 項任務時的工時消項任務時的工時消耗耗，或稱效率，或稱效率； c cij ij n n mm 為為效率矩陣效率矩陣2.2. 指派問題數學模型指派問題數學模型一般形式一般形式如果一個指派模型滿足以下三個條件：如果一個指派模型滿足以下三個條件： 1) 1)目標要求為目標要求為minmin 2) 2)效率矩陣效率矩陣(c (cij ij) )為為mm階方陣階方陣 3)3)效率矩陣中所有元素效率矩陣中所有元素c cij ij00, ,且為常數且為常數則稱上面的數學模型為指派問題

9、的標準形則稱上面的數學模型為指派問題的標準形. .3.3. 指派問題數學模型指派問題數學模型標準形式標準形式4.4. 指派模型的標準形的指派模型的標準形的特點特點: :含有含有mmmm個決策變量個決策變量, ,均為均為0-10-1變量變量m+mm+m2m2m個約束方程個約束方程 給定一個指派問題時，必須給出效率矩陣（系數矩陣）給定一個指派問題時，必須給出效率矩陣（系數矩陣） C=(cC=(cij ij) )mxmmxm, ,且且c cij ij 0 0，因此必有最優(yōu)解，因此必有最優(yōu)解 。 m1im1jijij0 xcMinZ指派問題有指派問題有2m2m個約束條件，個約束條件，但但可行解（即解矩

10、陣）中可行解（即解矩陣）中有且只有有且只有mm個個是是非零非零值值，即即mm個值取為，其余取為個值取為，其余取為, , 是自然高度退化的是自然高度退化的。 指派指派問題問題是是0-1 規(guī)劃的特例，規(guī)劃的特例， 也是運輸問題的特例，所以可用整數規(guī)劃，也是運輸問題的特例，所以可用整數規(guī)劃，0-1 規(guī)劃或運輸問題的解法去求解，規(guī)劃或運輸問題的解法去求解， 但這就如同用單純形法去求解運輸問題一樣，但這就如同用單純形法去求解運輸問題一樣， 是不合算的。是不合算的。 根據指派問題的特點可以有更簡便的解法，根據指派問題的特點可以有更簡便的解法， 就是就是匈牙利算法匈牙利算法， 其重要其重要依據依據是：是：

11、系數矩陣中獨立系數矩陣中獨立 0 元素的最多個數等于能覆蓋元素的最多個數等于能覆蓋所有所有 0 元素的最少直線數。元素的最少直線數。 二二 匈牙利算法匈牙利算法思路思路算法原理算法原理算法步驟算法步驟 匈牙利法基于這樣一個匈牙利法基于這樣一個明顯的明顯的事實事實： 如果在如果在m m階效率矩陣中，所有元素階效率矩陣中，所有元素c cijij00， 而其中有而其中有m m個位于不同行不同列的一組個位于不同行不同列的一組0 0元素，元素， 則在解矩陣中，只要令對應于這些則在解矩陣中，只要令對應于這些0 0元素位置的元素位置的x xijij1 1，其余的，其余的x xijij0 0，就得到最優(yōu)解。，

12、就得到最優(yōu)解。 此時的最優(yōu)解為此時的最優(yōu)解為（一） 思路0141208302323020939140令令x x11 11=1=1，x x2323=1=1，x x3232=1=1，x x4444=1=1，即可得最優(yōu)解，即可得最優(yōu)解，其其解矩陣解矩陣為為如如效率矩陣效率矩陣為為恰有恰有4 4個不同行個不同行不同列的不同列的0 0系數系數 1000001001000001問題是如何找到位于不同行、不同列的問題是如何找到位于不同行、不同列的mm個個0 0元素？元素？min Z=Z0匈牙利數學家狄匈牙利數學家狄康尼格康尼格(D(DKonigKonig) )證明的兩個定理證明的兩個定理（二）算法的基本原理

13、（二）算法的基本原理定理定理1 1 如果從指派問題效率矩陣如果從指派問題效率矩陣c cij ij 的每一行元素中分別的每一行元素中分別減去減去( (或加上或加上) )一個常數一個常數u ui i( (被稱為該行的位勢被稱為該行的位勢) )，從每一列分別減去從每一列分別減去( (或加上或加上) )一個常數一個常數v vj j( (稱為該列的位勢稱為該列的位勢) )，得到一個新的效率矩陣得到一個新的效率矩陣bbij ij ，若其中若其中b bij ij=c=cij ij-u-ui i-v-vj j，則則bbij ij 的最優(yōu)解的結構等價于的最優(yōu)解的結構等價于c cij ij 的最優(yōu)解的結構的最優(yōu)解

14、的結構. .將從將從bbij ij 中得到的解中得到的解代入分配問題模型的目標函數式，有代入分配問題模型的目標函數式，有 m1jjm1im1iim1jijijm1iijm1jjm1im1jijm1iim1jijijm1im1jijjiijm1im1jijijvuxcxvxuxcx)vuc(xbzv利用這個性質，可使原系數矩陣變換為含有很多利用這個性質，可使原系數矩陣變換為含有很多 0 0元素的新系數矩陣，而最優(yōu)解保持不變，元素的新系數矩陣，而最優(yōu)解保持不變，v在系數矩陣在系數矩陣(b(bij ij) )中，把位于不同行不同列的中，把位于不同行不同列的0 0元素，元素， 簡稱為簡稱為獨立的獨立的

15、0 0元素元素。v問題是問題是： 能否找到位于不同行、不同列的能否找到位于不同行、不同列的mm個個0 0元素？元素？ 若能在系數矩陣若能在系數矩陣(b(bij ij) )中找出中找出mm個獨立的個獨立的0 0元素；元素； 則令則令 解矩陣解矩陣(x(xij ij) )中對應這中對應這mm個獨立的個獨立的0 0元素的元素的x xij ij取值為取值為1 1， 其他元素取值為其他元素取值為0 0。 將其代入目標函數中得到將其代入目標函數中得到z zb b=0=0，它一定是最小值。，它一定是最小值。v這就是以這就是以(b(bij ij) )為系數矩陣的指派問題的最優(yōu)解。為系數矩陣的指派問題的最優(yōu)解。

16、 從而也就得到了原問題的最優(yōu)解。從而也就得到了原問題的最優(yōu)解。庫恩（庫恩（W.W.KuhnW.W.Kuhn）于）于19551955年給出了指派年給出了指派 問題的問題的解法，解法，他引用匈牙利數學家狄他引用匈牙利數學家狄康尼格（康尼格（d.konigd.konig) )關于矩關于矩陣中獨立零元素的定理陣中獨立零元素的定理( (即定理即定理2)2)：系數矩陣中獨立的系數矩陣中獨立的“0”0”元素的最多個數等于覆蓋元素的最多個數等于覆蓋所有所有“0”0”元素的最少直線數元素的最少直線數 -匈牙利算法基本思想匈牙利算法基本思想2 2庫恩給出的指派問題的解法稱為庫恩給出的指派問題的解法稱為匈牙利算法匈

17、牙利算法定理定理2 2 若效率矩陣若效率矩陣C C的元素可分成的元素可分成“0”0”與非與非“0”0”兩部分，則兩部分，則覆蓋所有覆蓋所有“0”0”元素的元素的獨立的獨立的“0”0”元素的元素的最多個數最多個數 已知矩陣中有若干已知矩陣中有若干0 0元素，設覆蓋全部元素，設覆蓋全部0 0元素元素最少需最少需mm條直線條直線，又設位于，又設位于不同行不同列的不同行不同列的0 0有有MM個個. .因覆蓋因覆蓋MM中的每個中的每個0 0至少用一條直線，故有至少用一條直線，故有mm MM下面要證明下面要證明M M m.m.i1i2irj1j2jc如圖假定覆蓋所有如圖假定覆蓋所有0 0元素的元素的mm條

18、直線條直線有有r r行、行、c c列，列，m=r+c.m=r+c.所有所有r r行上不在行上不在j j1 1，j jc c列上的列上的0 0元元素個數素個數 r r，這些，這些0 0元素至少有元素至少有r r個位個位于不同列于不同列同理：所有同理：所有c c列上不在列上不在i i1 1，i ir r行上行上的的0 0元素個數元素個數c c ，且這些，且這些0 0元素至元素至少有少有c c個位于不同個位于不同若上述兩部分若上述兩部分0 0個數總和為個數總和為S S，則，則SSmm；其中有；其中有mm個，又它們個，又它們必無重復元素，彼此獨立，必無重復元素，彼此獨立，則則S S M,M,故故有有m

19、mMM， 故可得故可得M=m.M=m.定理定理2 2說明說明：1. 1. 只要表中含有不同行或不同列的只要表中含有不同行或不同列的“0”0”元素，元素， 都可以通過直線覆蓋的方式來找到它們都可以通過直線覆蓋的方式來找到它們2. 2. 當覆蓋直線的當覆蓋直線的最少條數最少條數達到達到mm條條時，時， 必恰有必恰有mm個獨立個獨立“0”0”元素元素存在于表中存在于表中推論推論1 1：覆蓋所有：覆蓋所有“0”0”元素的元素的直線數直線數不同行不同列的不同行不同列的“0”0”元素的元素的最多個數（最多個數（mm）推論推論2 2：覆蓋所有：覆蓋所有“0”0”元素的元素的最少直線數最少直線數不同行不同列的

20、不同行不同列的“0”0”元素的元素的個數個數覆蓋所有覆蓋所有“0”0”元素的元素的獨立的獨立的“0”0”元素元素 的的最多個數最多個數( (三三) ) 匈牙利算法的步驟匈牙利算法的步驟 任務任務人員人員E EJ JG GR R甲甲2 2151513134 4乙乙10104 414141515丙丙9 9141416161313丁丁7 78 811 119 9經第一步變換后，系數矩陣中每行每列都已有了經第一步變換后，系數矩陣中每行每列都已有了0 0元素元素但需找出但需找出mm個獨立的個獨立的0 0元素。元素。若能找出，就以這些獨立若能找出，就以這些獨立0 0元素對應解矩陣元素對應解矩陣(x(xij

21、 ij) )中中的元素為的元素為1 1，其余為，其余為0 0，這就得到最優(yōu)解。，這就得到最優(yōu)解。當當mm較小時，可用觀察法、試探法去找出較小時，可用觀察法、試探法去找出mm個獨立個獨立0 0元素。元素。若若mm較大時，就必須按一定的步驟去找，較大時，就必須按一定的步驟去找，常用的步驟為常用的步驟為: :步驟目標效率矩陣的變換：使表中有足夠多的0行變換各行都有0生成的0對應的工時最小列變換各列都有0生成的0對應的工時最小檢查矩陣：確定是否有m個獨立0覆蓋直線數列檢查只有一個0，則標出以示該任務以優(yōu)勢方案派出并將該行劃掉以示該人以優(yōu)勢方案安排如有多個0，則暫不標記該任務可派給多個人，哪個最優(yōu)未定覆

22、蓋線數不能達到“最小”行檢查只有一個0，則標出以示該人以優(yōu)勢方案安排并將該列劃掉以示該任務以優(yōu)勢方案派出如有多個0，則暫不標記該人可執(zhí)行多個任務，哪個最優(yōu)未定覆蓋線數不能達到“最小”復查：當覆蓋直線數m時，在未被劃掉的元素中重復檢查注意：注意：第一步第一步 將系數矩陣進行變換將系數矩陣進行變換經一次運算就可得每行每列都有0元素的系數矩陣，第二步第二步2在在打打 行行各元素都各元素都減去減去這這最小元素最小元素2 2在打在打 列列中各元素都中各元素都加上加上這這 最小元素最小元素2 2，以保證原來，以保證原來0 0元素不變元素不變v當指派問題的系數矩陣，經過變換得到了同當指派問題的系數矩陣，經過

23、變換得到了同行和同列中都有兩個或兩個以上行和同列中都有兩個或兩個以上0 0元素時。這元素時。這時可以任選一行時可以任選一行( (列列) )中某一個中某一個0 0元素，再劃去元素，再劃去同行同行( (列列) )的其他的其他0 0元素。這時會出現多重解。元素。這時會出現多重解。 9131541116141381441579102min24114 5911005324100115780min 0 0 5 0 541100032450115280( )( )( )( )( )( )22 2 06031305443000923( )( )( )( )( )( )( )( )令對應于令對應于 零元素的零元

24、素的位置的決策變量位置的決策變量x xij ij=1.=1.0010010000011000 甲甲乙乙丙丙丁丁英英日日德德俄俄即最優(yōu)分配方案為即最優(yōu)分配方案為: :甲譯成俄文甲譯成俄文乙譯成日文乙譯成日文丙譯成英文丙譯成英文丁譯成德文丁譯成德文全部所需時間為全部所需時間為4+4+9+11=28h.4+4+9+11=28h.得解矩陣為：得解矩陣為： 9131541116141381441579102115764戊69637丁86458丙9117129乙118957甲EDCBA費 工作 用人員4347511576469637964589117129118957 713203630452014240

25、5263402-1 -2 5032015304310140305242402 l =m=4 n=55032015304310140305242402 5032015304310140305242402 5033004203310240306231301-1-1+1 5033004203310240306231301 l =m=4 n=5 5033004203310240306231301 5033004203310240306231301 6044003202300230206130300-1+1+1+1-1-1-1 6044003202300230206130300 此問題有多個最優(yōu)解此問題

26、有多個最優(yōu)解 6044003202300230206130300 6044003202300230206130300 有一份中文說明書，需譯成英、日、德、有一份中文說明書，需譯成英、日、德、 俄四種文字，分別記作俄四種文字，分別記作A A、B B、C C、D D。現有甲、乙、丙、?，F有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，間如下表所示，問如何分派任務，可使總時間最少？問如何分派任務，可使總時間最少？ 任務任務人員人員ABCD甲甲67112乙乙4598丙丙31104丁丁5982求解過程如下：求解過程如下：第一

27、步，變換系數矩陣：第一步，變換系數矩陣：2142 289541013895421176)( ijc 0673390245100954 01733402401004545第二步，試指派：第二步，試指派：找到找到 3 3 個獨立零元素個獨立零元素 但但 m = 3 n = 4m = 3 n = 4 第三步，作最少的直線覆蓋所有第三步，作最少的直線覆蓋所有0 0元素：元素：獨立零元素的個數獨立零元素的個數mm等于最少直線數等于最少直線數l l，即，即l lm=3m=3n n=4=4； 第四步，變換矩陣第四步，變換矩陣( (bij) )以增加以增加0

28、 0元素：沒有被直線覆蓋的所有元素：沒有被直線覆蓋的所有元素中的最小元素為元素中的最小元素為1 1，然后打，然后打各行都減去各行都減去1 1；打；打各列都加上各列都加上1 1，得如下矩陣，并轉第二步進行試指派：，得如下矩陣，并轉第二步進行試指派： 0100001000011000得到得到4 4個獨個獨立零元素，立零元素， 所以最優(yōu)解所以最優(yōu)解矩陣為：矩陣為：06244251343 15 6244251343 在實際應用中，經常遇到非標準形式的指派在實際應用中，經常遇到非標準形式的指派問題。處理方法：問題。處理方法：化標準，再按匈牙利算法求解?；瘶藴?，再按匈牙利算法求解

29、。三、非標準形指派問題三、非標準形指派問題1. 1. 最大化指派問題最大化指派問題目標函數變?yōu)椋耗繕撕瘮底優(yōu)椋?m1im1jijijxazmaxa)a)上述目標函數等價于：上述目標函數等價于： m1im1jijijxazminb)b)應用應用定理一定理一，將之，將之化為標準形化為標準形：設最大化分配：設最大化分配問題效率矩陣問題效率矩陣A=aA=aij ij, ,其中其中最大元素最大元素為為mm。令。令B= B= bbij ij=m+(-am+(-aij ij) ) = =m-am-aij ij, , 則以則以B B為系數矩陣的最小為系數矩陣的最小化指派問題和以化指派問題和以A A為系數矩陣的

30、原最大化指派問為系數矩陣的原最大化指派問題有題有相同最優(yōu)解相同最優(yōu)解。最大化指派問題最大化指派問題 有有4 4種機械要分別安裝在種機械要分別安裝在4 4個工地，它們個工地，它們在在4 4個工地工作效率（見下表）不同。問應個工地工作效率（見下表）不同。問應如何指派安排，才能使如何指派安排，才能使4 4臺機械發(fā)揮總的效臺機械發(fā)揮總的效率最大？率最大？ 工地工地機器機器甲甲 乙乙 丙丙 丁丁30 25 40 3232 35 30 36 35 40 34 2728 43 32 38設最大化的指派問題系數陣設最大化的指派問題系數陣 ， 其中最大元素為其中最大元素為mm（本例中（本例中m=43m=43），

31、令矩陣），令矩陣nnijcC)(nnijnnijcmbB)()(本例中本例中38324328273440353630353232402530C511015169387138111131813B-3-7-3-0511015136050614801510-451101113601061080156圈圈0 0覆蓋覆蓋打打511011136010610801561B-1-1+141001012500062080166圈02B此時此時m=n=4,m=n=4,因此決策變量矩陣為因此決策變量矩陣為0010000110000100X即指派機械即指派機械安裝在工地丙，安裝在工地丙，機械機械安裝在工安裝在工地丁，

32、機械地丁，機械安裝在工地甲，機械安裝在工地甲，機械安裝在工安裝在工地乙，才能使地乙，才能使4 4臺機器發(fā)揮總的效率最大。其臺機器發(fā)揮總的效率最大。其總效率為總效率為38324328273440353630353232402530v人數和任務數不等的指派問題：人數和任務數不等的指派問題：v若人少任務多時，則添上一些虛擬的若人少任務多時，則添上一些虛擬的“人人”。這。這些虛擬的些虛擬的“人人”完成各任務的費用系數可取完成各任務的費用系數可取0，理解為這些費用實際上不會發(fā)生。理解為這些費用實際上不會發(fā)生。v若人多任務少時，則添上一些虛擬的若人多任務少時，則添上一些虛擬的“任

33、務任務”。這些虛擬的這些虛擬的“任務任務”被各人完成的費用系數同樣被各人完成的費用系數同樣也取也取0。三、非標準形指派問題三、非標準形指派問題 2 . 人數和任務數不等人數和任務數不等 工工作作 人人 1 3 6 2 6 2 7 1 4 4 3 3 6 5 8 4 6 4 3 7 5 5 2 4 3 6 5 7 6 2 工工作作 人人 1 3 6 2 6 0 0 2 7 1 4 4 0 0 3 3 6 5 8 0 0 4 6 4 3 7 0 0 5 5 2 4 3 0 0 6 5 7 6 2 0 0 增加假想列，以達到標準形式增加假想列，以達到標準形式 若某個人可做幾件事，則可將該人化作相若某

34、個人可做幾件事，則可將該人化作相同的幾個同的幾個“人人”來接受分配。這幾個來接受分配。這幾個“人人”做做同一件事的同一件事的費用系數費用系數當然都當然都一樣一樣。4.4.某事某事一定不能由某人做一定不能由某人做的分配問題：的分配問題： 若某事一定不能由某人做，則可將相應的若某事一定不能由某人做，則可將相應的費用系數取做足夠大的數費用系數取做足夠大的數MM，以使費用最小的，以使費用最小的最優(yōu)解中一定不會出現相應的分配方案。最優(yōu)解中一定不會出現相應的分配方案。3.3.一個人一個人可完成可完成多多件件任務任務的分配問題：的分配問題：三、非標準形指派問題三、非標準形指派問題某商業(yè)公司計劃開辦五家新商店

35、某商業(yè)公司計劃開辦五家新商店B Bi i(i (i=1,2,=1,2,5),5)。為了盡早建成。為了盡早建成 營業(yè)，商業(yè)公司營業(yè)，商業(yè)公司決定由決定由5 5家建筑公司家建筑公司A Aj j(j (j=1,2,=1,2,5),5)分別承建。已分別承建。已知建筑公司對新商店的建造報價（萬元）為知建筑公司對新商店的建造報價（萬元）為c cij ij(i,j(i,j=1,2,=1,2,5) ,5) 。商業(yè)公司應當對。商業(yè)公司應當對5 5家建筑公司家建筑公司 怎樣分配建筑任務，才能使總的建筑費用最少？怎樣分配建筑任務，才能使總的建筑費用最少？C610129610614767812961014179712

36、1578454321AAAAA54321BBBBB對于上例的指派問題，為了保證工程質量，經研對于上例的指派問題，為了保證工程質量，經研究決定，舍棄建筑公司究決定，舍棄建筑公司 A A4 4 和和 A A5 5 ，而讓技術，而讓技術力量較強的建筑公司力量較強的建筑公司 A A1 1 、 A A2 2 和和 A A3 3 來承來承建。根據實際情況，可以允許每家建筑公司承建建。根據實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。一家或兩家商店。求使總費用最少的指派方案。反映投標費用的系數矩陣為反映投標費用的系數矩陣為7812961014179712157841A2A3A1

37、B2B3B4B5B由于每家建筑公司最多可承建兩家新商店，因此，把每家由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（建筑公司化作相同的兩家建筑公司（ 和和這樣，系數矩陣變?yōu)椋哼@樣，系數矩陣變?yōu)椋篿A)3 , 2 , 1, iAi7812967812961014179710141797121578412157841B2B3B4B5B1A1A2A2A3A3A上面的系數矩陣有上面的系數矩陣有6 6行行5 5列，為了使列，為了使“人人”和和“任務任務”的數目相的數目相同，同，引入一件虛事引入一件虛事B B6 6 ，使之成為標準指派問題的系數矩陣：，使之成為標準指派問題

38、的系數矩陣：6B078129607812960101417970101417970121578401215784C1A1A2A2A3A3A1B2B3B4B5B6B再利用匈牙利法求解。再利用匈牙利法求解。078129607812960101417970101417970121578401215784C列變換00051200051203610130361013057000057000圈000051200051203610130361013057000057000-1-1+1再變換打覆蓋100512100512025902025902157000157000圈00100000010001000000

39、00010000100000001X1A2A3A1B2B3B4B5B6B最優(yōu)解最優(yōu)解: : A A1 1承建承建B B1 1和和B B3 3 , A , A2 2承建承建B B2 2 , A , A3 3承建承建B B4 4 和和B B5 5 總建筑費用為總建筑費用為 總建筑費用為總建筑費用為010000001000100000000010000100000001X1A2A3A1B2B3B4B5B6B781296781296101417971014179712157841215784C3578974Z （萬元）（萬元） 下表所示分配問題：下表所示分配問題：甲甲 乙乙 丙丙 丁丁A AB BC C3 3 2 -2 1 2 -2 12 2 -2 0 - -2 0 - -1 1 0- -1 1 0效率陣中的元素表示四個人效率陣中的元素表示四個人完成三項工作所創(chuàng)造的利潤完成三項