運籌學-指派問題課件1

1、第五節(jié) 指 派 問 題第五節(jié) 指 派 問 題本節(jié)內(nèi)容的安排指派問題的數(shù)學模型匈 牙 利 算 法本節(jié)內(nèi)容的安排指派問題的數(shù)學模型匈 牙 利 算 法 在實際中經(jīng)常會遇到這樣的問題，有n 項不同的任務，需要n 個人分別完成其中的一項，但由于任務的性質(zhì)和各人的專長不同，因此各人去完成不同的任務的效率（或花費的時間或費用）也就不同。于是產(chǎn)生了一個問題:應指派哪個人去完成哪項任務，使完成 n 項任務的總效率最高（或所需時間最少），這類問題稱為指派問題或分派問題。 在實際中經(jīng)常會遇到這樣的問題， 例7： 有一份中文說明書，要分別譯成英、日、德、俄四種文字，分別記作E 、 J 、 G 、 R ,交與甲、乙、丙

2、、丁 四個人去完成.因個人專長不同，他們完成翻譯不同語種的說明書所需的時間(h)如表所示.應如何指派，使四個人分別完成這四項任務總時間為最??？ 任務人員EJGR甲215134乙1041415丙9141613丁78119一、指派問題的數(shù)學模型（一）舉例例7： 有一份中文說明書， 任務EJGR甲21這是一個標準型的指派問題類似有：有n項加工任務，怎樣指派到n臺機床上分別完成； 有n條航線，怎樣指定n艘船分別去航行. 等。對應每個指派問題，需有類似上表那樣的數(shù)表， 表中數(shù)據(jù)稱為效率矩陣或系數(shù)矩陣，其元素cij0(i,j=1,2,n)，表示指派第i人去完成第j 項任務時的效率（或時間、成本等）效率矩陣

3、或系數(shù)矩陣C=(cij)nn=c11 c12 c1n c21 c22 c2n cn1 cn1 cnn 這是一個標準型的指派問題效率矩陣C=(cij)nn=c11C=(cij )=2151341041415914161378119C=(cij )=215134則該指派問題的數(shù)學模型為：求解題時通常需引入0-1變量：xij=1 (i=1,2,3,4)表示第i人只能完成一項任務xij=1 (j=1,2,3,4)表示第j 項任務只能由一人去完成。滿足約束條件的解稱為可行解，可寫成矩陣形式，叫作解矩陣。則該指派問題的數(shù)學模型為：求解題時通常需引入0-1變量：x如本例的一個可行解矩陣（但不一定是最優(yōu)解）指

4、派問題的解矩陣應具有如下特點：（1）解矩陣(xij)中各行各列的元素之和都是1；（2）可行解（最優(yōu)解）中恰含有個非零元，即4個1；（3）可行解（最優(yōu)解）矩陣中的1恰取于不同行不同列。如本例的一個可行解矩陣（但不一定是最優(yōu)解）指派問題的解矩陣應可以看到指派問題既是0-1 規(guī)劃問題，也是運輸問題，所以也可用整數(shù)規(guī)劃，0-1 規(guī)劃，或運輸問題的解法去求解?？梢钥吹街概蓡栴}既是0-1 規(guī)劃問題，也是運輸問題，（二）指派問題的數(shù)學模型 1. 指派問題的一般提法： 設m個人被指派去做m件工作， 規(guī)定每個人只做一件工作， 每件工作只有一個人去做。已知第i個人去做第j 件工作的的效率（ 時間或費用） 為cij

5、 (i=1.2m;j=1.2m) ，并假設cij 0。 問應如何指派才能使總效率最高或總時間 總費用最低 ？（二）指派問題的數(shù)學模型設cij表示指派問題的效率矩陣，令則指派問題的數(shù)學模型一般形式為：xij 為第 i 個人指派去做第 j 項任務；cij 為第 i 個人為完成第 j 項任務時的工時消耗，或稱效率；cij nm 為效率矩陣2. 指派問題數(shù)學模型一般形式設cij表示指派問題的效率矩陣，令則指派問題的數(shù)學模型一如果一個指派模型滿足以下三個條件： 1)目標要求為min 2)效率矩陣(cij)為m階方陣 3)效率矩陣中所有元素cij0,且為常數(shù)則稱上面的數(shù)學模型為指派問題的標準形.3. 指派

6、問題數(shù)學模型標準形式如果一個指派模型滿足以下三個條件：3. 指派問題數(shù)學模型標4. 指派模型的標準形的特點:含有mm個決策變量,均為0-1變量m+m2m個約束方程 給定一個指派問題時，必須給出效率矩陣（系數(shù)矩陣） C=(cij)mxm,且cij0，因此必有最優(yōu)解 。 指派問題有2m個約束條件，但可行解（即解矩陣）中有且只有m個是非零值，即m個值取為，其余取為, 是自然高度退化的。4. 指派模型的標準形的特點: 給定一個指派問題時，必須給出 指派問題是0-1 規(guī)劃的特例， 也是運輸問題的特例，所以可用整數(shù)規(guī)劃，0-1 規(guī)劃或運輸問題的解法去求解， 但這就如同用單純形法去求解運輸問題一樣， 是不合

7、算的。 根據(jù)指派問題的特點可以有更簡便的解法， 就是匈牙利算法， 其重要依據(jù)是： 系數(shù)矩陣中獨立 0 元素的最多個數(shù)等于能覆蓋所有 0 元素的最少直線數(shù)。 指派問題是0-1 規(guī)劃的特例，二 匈牙利算法思路算法原理算法步驟二 匈牙利算法思路算法原理算法步驟 匈牙利法基于這樣一個明顯的事實： 如果在m階效率矩陣中，所有元素cij0， 而其中有m個位于不同行不同列的一組0元素， 則在解矩陣中，只要令對應于這些0元素位置的xij1，其余的xij0，就得到最優(yōu)解。 此時的最優(yōu)解為（一） 思路 匈牙利法基于這樣一個明顯的事實：（一） 思路令x11=1，x23=1，x32=1，x44=1，即可得最優(yōu)解，其解

8、矩陣為如效率矩陣為恰有4個不同行不同列的0系數(shù)問題是如何找到位于不同行、不同列的m個0元素？min Z=Z0令x11=1，x23=1，x32=1，x44=1，即可得最優(yōu)匈牙利算法基本思想：對同一工作i來說，所有人的效率都提高或降低同一常數(shù)，不會影響最優(yōu)分配；同樣，對同一人j來說,做所有工作的效率都提高或降低同一常數(shù)，也不會影響最優(yōu)分配。匈牙利算法基本思想：匈牙利數(shù)學家狄康尼格(DKonig)證明的兩個定理（二）算法的基本原理定理1 如果從指派問題效率矩陣cij的每一行元素中分別減去(或加上)一個常數(shù)ui(被稱為該行的位勢)，從每一列分別減去(或加上)一個常數(shù)vj(稱為該列的位勢)，得到一個新的

9、效率矩陣bij，若其中bij=cij-ui-vj，則bij的最優(yōu)解的結(jié)構等價于cij的最優(yōu)解的結(jié)構.匈牙利數(shù)學家狄康尼格(DKonig)證明的兩個定理（二）證明：將從bij中得到的解代入分配問題模型的目標函數(shù)式，有證明：將從bij中得到的解指派問題最優(yōu)解的性質(zhì)：若從效率矩陣(cij)的一行（列）各元素中分別減去該行（列）的最小元素得到的新矩陣(bij)，那么以(bij)為效率矩陣求得的最優(yōu)解的結(jié)構和用原來的效率矩陣(cij)求得的最優(yōu)解的結(jié)構相同。-匈牙利算法基本思想1指派問題最優(yōu)解的性質(zhì)：-匈牙利算法基本思想1利用這個性質(zhì)，可使原系數(shù)矩陣變換為含有很多 0元素的新系數(shù)矩陣，而最優(yōu)解保持不變，

10、在系數(shù)矩陣(bij)中，把位于不同行不同列的0元素， 簡稱為獨立的0元素。問題是： 能否找到位于不同行、不同列的m個0元素？ 若能在系數(shù)矩陣(bij)中找出m個獨立的0元素； 則令 解矩陣(xij)中對應這m個獨立的0元素的xij取值為1， 其他元素取值為0。 將其代入目標函數(shù)中得到zb=0，它一定是最小值。這就是以(bij)為系數(shù)矩陣的指派問題的最優(yōu)解。 從而也就得到了原問題的最優(yōu)解。利用這個性質(zhì)，可使原系數(shù)矩陣變換為含有很多 庫恩（W.W.Kuhn）于1955年給出了指派 問題的解法，他引用匈牙利數(shù)學家狄康尼格（d.konig)關于矩陣中獨立零元素的定理(即定理2)：系數(shù)矩陣中獨立的“0”

11、元素的最多個數(shù)等于覆蓋所有“0”元素的最少直線數(shù) -匈牙利算法基本思想2庫恩給出的指派問題的解法稱為匈牙利算法庫恩（W.W.Kuhn）于1955年給出了指派 問題的解法，定理2 若效率矩陣C的元素可分成“0”與非“0”兩部分，則覆蓋所有“0”元素的最少直線數(shù)=獨立的“0”元素的最多個數(shù)證明： 已知矩陣中有若干0元素，設覆蓋全部0元素最少需m條直線，又設位于不同行不同列的0有M個.因覆蓋M中的每個0至少用一條直線，故有mM下面要證明M m.i1i2irj1j2jc如圖假定覆蓋所有0元素的m條直線有r行、c列，m=r+c.所有r行上不在j1，jc列上的0元素個數(shù) r，這些0元素至少有r個位于不同列

12、同理：所有c列上不在i1，ir行上的0元素個數(shù)c ，且這些0元素至少有c個位于不同定理2 若效率矩陣C的元素可分成“0”與非“0”兩部分，若上述兩部分0個數(shù)總和為S，則Sm；其中有m個，又它們必無重復元素，彼此獨立，則SM,故有mM， 故可得M=m.若上述兩部分0個數(shù)總和為S，則Sm；其中有m個，又它們必無定理2說明：只要表中含有不同行或不同列的“0”元素， 都可以通過直線覆蓋的方式來找到它們2. 當覆蓋直線的最少條數(shù)達到m條時， 必恰有m個獨立“0”元素存在于表中推論1：覆蓋所有“0”元素的直線數(shù)不同行不同列的“0”元素的最多個數(shù)（m）推論2：覆蓋所有“0”元素的最少直線數(shù)不同行不同列的“0

13、”元素的個數(shù)覆蓋所有“0”元素的最少直線數(shù) = 獨立的“0”元素 的最多個數(shù)定理2說明：推論1：覆蓋所有“0”元素的直線數(shù)覆蓋所有“02.系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少直線數(shù)。1.若從效率矩陣(cij)的一行（列）各元素中分別減去該行（列）的最小元素得到的新矩陣(bij)，那么以(bij)為效率矩陣求得的最優(yōu)解的結(jié)構和用原來的效率矩陣(cij)求得的最優(yōu)解的結(jié)構相同。匈牙利算法依據(jù)：2.系數(shù)矩陣中獨立0元素的最多個數(shù)等于能覆蓋所有0元素的最少(三) 匈牙利算法的步驟 任務人員EJGR甲215134乙1041415丙9141613丁78119例7:(三) 匈牙利算法的步

14、驟 任務EJG第一步：變換系數(shù)矩陣,使指派問題的系數(shù) 矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素：從系數(shù)矩陣的每行元素減去該行的最小元素。再從所得系數(shù)矩陣的每列元素減去該列的最小元素。若某行已經(jīng)有0元素，就不必再減了。第一步：變換系數(shù)矩陣,使指派問題的(cij)=2 15 13 4 4 14 159 14 16 13 7 8 11 92 4 9 70 13 11 26 0 10 110 5 7 40 1 4 24 20 13 7 06 0 6 90 5 3 20 1 0 0(cij)=2 15 13 42 4 第二步：圈出不同行且不同列的元素，進行試指派，以尋找最優(yōu)解。經(jīng)第一步變換后，系數(shù)矩陣中每行

15、每列都已有了0元素但需找出m個獨立的0元素。若能找出，就以這些獨立0元素對應解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。當m較小時，可用觀察法、試探法去找出m個獨立0元素。若m較大時，就必須按一定的步驟去找，常用的步驟為:第二步：圈出不同行且不同列的元素，進行試指派，以尋找最優(yōu)解從只有一個0元素的行（或列）開始， 給這個0元素加圈，記，這表示對這行所 代表的人，只有一種任務可指派。然后劃去所在的列（或行）的其他0元素，記作。這表示這列所代表的任務已指派完，不必再考慮別人0 13 7 0 6 6 9 5 3 20 1 0 0從只有一個0元素的行（或列）開始， 0 13 給只有一個0元

16、素的列（或行）中的0元素加圈， 記，然后劃去所在的行（或列）的其他0元素，記作。這表示這行所代表的人已指派完，不必再考慮他做別的任務了。反復進行上述兩步，直到所有的0元素都被圈出和劃掉為止。給只有一個0元素的列（或行）中的0元素加圈，反復進行上述兩步0 13 7 06 6 90 5 3 20 1 0 0從只有一個0元素的行（或列）開始，給這個0元素加圈，記。再給第三行的這個唯一的0元素加圈，記，得0 13 7 0從只有一個0元素的行（0 13 7 06 6 9 5 3 20 1 0 0然后劃去所在的列的其他0元素，記作，得0 13 7 0然后劃去所在的列的其 13 7 0 6 6 9 5 3

17、2 1 0 0給只有一個0元素的列的0元素加圈，記，得 13 7 0給只有一個0元素的列 13 7 0 6 6 9 5 3 2 1 0然后劃去所在的行的其他0元素，記作，得 13 7 0然后劃去所在的行的 13 7 0 6 6 9 5 3 2 1 給最后一個0元素加圈，記，得 13 7 0給最后一個0元素加圈 13 7 6 6 9 5 3 2 1 13 7 0 0 0 10 1 0 01 0 0 00 0 1 0可得獨立的0元素的個數(shù)就是矩陣的階數(shù),即n=m=4, 故得到最優(yōu)解：即甲譯俄文、乙譯日文、丙譯英文、丁譯德文所需時間最少。 Z=28小時0 0 0 1可得獨立的0元素若不同行不同列的元

18、素的數(shù)目n等于系數(shù)矩陣階數(shù)m,則令它們對應的xij，其余xij=0,那么這分配問題的最優(yōu)解已得到,計算停若nm，說明尚未找到最優(yōu)解，則轉(zhuǎn)下一步。即設法進一步變換矩陣，增加新的元素.若不同行不同列的元素的數(shù)目n等于系數(shù)矩陣階數(shù)m,則令它們對步驟目標效率矩陣的變換：使表中有足夠多的0行變換各行都有0生成的0對應的工時最小列變換各列都有0生成的0對應的工時最小檢查矩陣：確定是否有m個獨立0覆蓋直線數(shù)列檢查只有一個0，則標出以示該任務以優(yōu)勢方案派出并將該行劃掉以示該人以優(yōu)勢方案安排如有多個0，則暫不標記該任務可派給多個人，哪個最優(yōu)未定覆蓋線數(shù)不能達到“最小”行檢查只有一個0，則標出以示該人以優(yōu)勢方案安

19、排并將該列劃掉以示該任務以優(yōu)勢方案派出如有多個0，則暫不標記該人可執(zhí)行多個任務，哪個最優(yōu)未定覆蓋線數(shù)不能達到“最小”復查：當覆蓋直線數(shù)m時，在未被劃掉的元素中重復檢查步驟目標效率矩陣的變換：使表中有足夠多的0行變換各行都有0若仍有沒有劃圈的0元素，且同行（或列）的0元素至少有二個， (表示對這個人可以從兩項任務中指派其一)，從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個0元素加圈(表示選擇性多的要“禮讓”選擇性少的)然后劃掉同行同列的其他0元素，可反復進行，直到所有的0元素都被圈出和劃掉為止。注意：若仍有沒有劃圈的0元素，且同行（或列）的0元素至

20、少有二個， 例8 求下表所示效率矩陣的指派問題的 最小解。任務人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109例8 求下表所示效率矩陣的指派問題的 任務人員ABC12797989666717121491514661041071097 6 7 6 4第一步 將系數(shù)矩陣進行變換12797989666717121491514661041050202230000105729800406365經(jīng)一次運算就可得每行每列都有0元素的系數(shù)矩陣，50202230000105729800406365經(jīng)一次運5020223000105729800406365從只有一個0元

21、素的行開始，給這個0元素加圈，記第二步然后劃去所在的列的其他0元素，記作，得5020223000105729800406365從只有一502022300010572980046365從只有一個0元素的列開始，給這個0元素加圈，記，得502022300010572980046365從只有一52022300010572980046365然后劃去所在的行的其他0元素，記作，得52022300010572980046365然后劃去5222300010572980046365從只有一個0元素的列開始，給這個0元素加圈，記 ，得5222300010572980046365從只有一5222300105729

22、80046365然后劃去所在的行的其他0元素，記作，得522230010572980046365然后劃去5222310572980046365從只有一個0元素的列開始，給這個0元素加圈，記，得5222310572980046365從只有一522231057298046365然后劃去所在的行的其他0元素，記作，得522231057298046365然后劃去52223105729846365此時，獨立的的個數(shù)n=4,而系數(shù)矩陣的階數(shù)m=5, nm，轉(zhuǎn)下一步。52223105729846365此時，獨52223105729846365（1）對沒有的行，打第三步：作最少的直線覆蓋所有的0元素，以確定該

23、系數(shù)矩陣中能找到最多的獨立元素數(shù)。52223105729846365（1）52223105729846365（2）對已打行中所有含0元素的列打52223105729846365（252223105729846365（3）再對打列中含0元素的行打（4） 重復（2），（3）兩步，直到得不出新的打的行和列為止。52223105729846365（52223105729846365（5）對沒有打的行畫橫線 對有打的列畫縱線就得到覆蓋所有0元素的最少直線數(shù)。52223105729846365（第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找到最多的獨立元素數(shù)。對沒有的行，打；對已打行中所有含

24、0元素的列打；再對打列中含0元素的行打；重復上述兩步，直到得不出新的打行列為止。對沒有打行畫橫線，有打列畫縱線，就得到覆蓋所有0元素的最少直線數(shù)。第三步：作最少的直線覆蓋所有的0元素，以確定該系數(shù)矩陣中能找52223105729846365（1）在沒有被直線覆蓋的部分中找 出最小元素為2第四步：（2）然后在打行各元素都減去這最小元素252223105729846365（5020223000-2835098004-24143（3）而在打列中各元素都加上這 最小元素2，以保證原來0元素不變5020223000-2835098004-2414370202430000835011800404143這樣

25、得到新的系數(shù)矩陣（它的最優(yōu)解和原問題相同）。(4) 若得到m個獨立的0元素，則已經(jīng)得到最優(yōu)解。否則回到第二步重復進行。70202430000835011800404143這70202430000835011800404143在新的系數(shù)矩陣中重復第二步，尋找獨立0元素。70202430000835011800404143在新的系7020243000083501180044143從只有一個0元素的行開始，給這個0元素加圈，記然后劃去所在的列的其他0元素，記作。7020243000083501180044143從只有一702024300083501180044143從只有一個0元素的行開始，給這個0

26、元素加圈，記702024300083501180044143從只有一70202430008351180044143然后劃去所在的列的其他0元素，記作。70202430008351180044143然后劃去7020243008351180044143從只有一個0元素的列開始，給這個0元素加圈，記7020243008351180044143從只有一720243008351180044143然后劃去所在的行的其他0元素，記作。720243008351180044143然后劃去72243008351180044143下面有二種指派方案：72243008351180044143下面有二722438351

27、1844143下面有二種指派方案：第一種指派方案7224383511844143下面有二0100000010000010010010000最優(yōu)解如下：Z=320100000010000010010010000最優(yōu)解如下指派問題結(jié)果如下：Z=32任務人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109指派問題結(jié)果如下：Z=32任務人員ABCDE甲127979乙7224383511844143第二種指派方案7224383511844143第二種指0100000100000010001010000最優(yōu)解如下：Z=320100000100000010001010

28、000最優(yōu)解如下指派問題結(jié)果如下：Z=32任務人員ABCDE甲127979乙89666丙71712149丁15146610戊4107109指派問題結(jié)果如下：Z=32任務人員ABCDE甲127979乙當指派問題的系數(shù)矩陣，經(jīng)過變換得到了同行和同列中都有兩個或兩個以上0元素時。這時可以任選一行(列)中某一個0元素，再劃去同行(列)的其他0元素。這時會出現(xiàn)多重解。 當指派問題的系數(shù)矩陣，經(jīng)過變換得到了同行和同列中都有兩個或兩例7：例7：min24114min 0 0 5 0( )( )( )22 2 ( )( )( )( )min2min 0 0 5 令對應于 零元素的位置的決策變量xij=1.即最

29、優(yōu)分配方案為:甲譯成俄文乙譯成日文丙譯成英文丁譯成德文全部所需時間為4+4+9+11=28h.得解矩陣為：令對應于 零元素的位置的決策變量xij=1.即最優(yōu)分配方案為練習1：115764戊69637丁86458丙9117129乙118957甲EDCBA費 工作 用人員練習1：115764戊69637丁86458丙9117129-1-2-1-2l =m=4 n=5l =m=4 n=5-1-1+1-1-1+1l =m=4 n=5l =m=4 n=5-1+1+1+1-1-1-1-1+1+1+1-1-1-1此問題有多個最優(yōu)解此問題有多個最優(yōu)解練習2:有一份中文說明書，需譯成英、日、德、 俄四種文字，分

30、別記作A、B、C、D?，F(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下表所示，問如何分派任務，可使總時間最少？ 任務人員ABCD甲67112乙4598丙31104丁5982練習2:有一份中文說明書，需譯成英、日、德、 俄四求解過程如下：第一步，變換系數(shù)矩陣：5第二步，試指派： 找到 3 個獨立零元素 但 m = 3 n = 4求解過程如下：5第二步，試指派： 找到 3 個 第三步，作最少的直線覆蓋所有0元素： 獨立零元素的個數(shù)m等于最少直線數(shù)l，即lm=3n=4； 第四步，變換矩陣(bij)以增加0元素：沒有被直線覆蓋的所有元素中的最小元素為1，然后打各行都減去1；打各

31、列都加上1，得如下矩陣，并轉(zhuǎn)第二步進行試指派： 第三步，作最少的直線覆蓋所有0元素： 得到4個獨立零元素， 所以最優(yōu)解矩陣為： 15得到4個獨立零元素， 所以最優(yōu)解矩陣為： 在實際應用中，經(jīng)常遇到非標準形式的指派問題。處理方法：化標準，再按匈牙利算法求解。三、非標準形指派問題1. 最大化指派問題在實際應用中，經(jīng)常遇到非標準形式的指派問題。處理方法：三、非目標函數(shù)變?yōu)椋篴)上述目標函數(shù)等價于：b)應用定理一，將之化為標準形：設最大化分配問題效率矩陣A=aij,其中最大元素為m。令B= bij=m+(-aij) =m-aij, 則以B為系數(shù)矩陣的最小化指派問題和以A為系數(shù)矩陣的原最大化指派問題有相

32、同最優(yōu)解。目標函數(shù)變?yōu)椋篴)上述目標函數(shù)等價于：b)應用定理一，將之化最大化指派問題例: 有4種機械要分別安裝在4個工地，它們在4個工地工作效率（見下表）不同。問應如何指派安排，才能使4臺機械發(fā)揮總的效率最大？ 工地機器甲 乙 丙 丁30 25 40 3232 35 30 36 35 40 34 2728 43 32 38最大化指派問題例: 有4種機械要分別安裝在4個工地，它們在解：設最大化的指派問題系數(shù)陣 ， 其中最大元素為m（本例中m=43），令矩陣解：設最大化的指派問題系數(shù)陣 本例中-3-7-3-0-4圈0覆蓋打本例中-3-7-3-0-4圈0覆蓋打-1-1+1圈0此時m=n=4,因此決策

33、變量矩陣為-1-1+1圈0此時m=n=4,因此決策變量矩陣為即指派機械安裝在工地丙，機械安裝在工地丁，機械安裝在工地甲，機械安裝在工地乙，才能使4臺機器發(fā)揮總的效率最大。其總效率為即指派機械安裝在工地丙，機械安裝在工地丁，機械安裝在工人數(shù)和任務數(shù)不等的指派問題：若人少任務多時，則添上一些虛擬的“人”。這些虛擬的“人”完成各任務的費用系數(shù)可取0，理解為這些費用實際上不會發(fā)生。若人多任務少時，則添上一些虛擬的“任務”。這些虛擬的“任務”被各人完成的費用系數(shù)同樣也取0。三、非標準形指派問題 2 . 人數(shù)和任務數(shù)不等 人數(shù)和任務數(shù)不等的指派問題：三、非標準形指派問題 增加假想列，以達到標準形式增加假想

34、列，以達到標準形式 若某個人可做幾件事，則可將該人化作相同的幾個“人”來接受分配。這幾個“人”做同一件事的費用系數(shù)當然都一樣。4.某事一定不能由某人做的分配問題： 若某事一定不能由某人做，則可將相應的費用系數(shù)取做足夠大的數(shù)M，以使費用最小的最優(yōu)解中一定不會出現(xiàn)相應的分配方案。3.一個人可完成多件任務的分配問題：三、非標準形指派問題 若某個人可做幾件事，則可將該人化作相同的幾個例：某商業(yè)公司計劃開辦五家新商店Bi(i=1,2,5)。為了盡早建成 營業(yè)，商業(yè)公司決定由5家建筑公司Aj(j=1,2,5)分別承建。已知建筑公司對新商店的建造報價（萬元）為cij(i,j=1,2,5) 。商業(yè)公司應當對5

35、家建筑公司 怎樣分配建筑任務，才能使總的建筑費用最少？例：某商業(yè)公司計劃開辦五家新商店Bi(i=1,2,5)。對于上例的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司 A4 和 A5 ，而讓技術力量較強的建筑公司 A1 、 A2 和 A3 來承建。根據(jù)實際情況，可以允許每家建筑公司承建一家或兩家商店。求使總費用最少的指派方案。反映投標費用的系數(shù)矩陣為對于上例的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公由于每家建筑公司最多可承建兩家新商店，因此，把每家建筑公司化作相同的兩家建筑公司（ 和這樣，系數(shù)矩陣變?yōu)椋荷厦娴南禂?shù)矩陣有6行5列，為了使“人”和“任務”的數(shù)目相同，由于每家建筑公司最多可承建兩家新商店，因此，把每家上面的系數(shù)引入一件虛事B6 ，使之成為標準指派問題的系數(shù)矩陣：再利用匈牙利法求解。引入一件虛事B6 ，使之成為標準指派問題的系數(shù)矩陣：再利用匈列變換圈0-1-1+1再變換打覆蓋列變換圈0