第第5章章 整數(shù)線性規(guī)劃整數(shù)線性規(guī)劃第第5節(jié)節(jié) 指指 派派 問問 題題 在生活中經(jīng)常遇到這樣的問題，某單位需完成n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)。由于每人的專長(zhǎng)不同，各人完成任務(wù)不同(或所費(fèi)時(shí)間)，效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成n項(xiàng)任務(wù)的總效率最高(或所需總時(shí)間最小)。這類問題稱為指派問題或分派問題(assignment problem)。例7 有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作E、J、G、R?，F(xiàn)有甲、乙、丙、丁四人。他們將中文說明書翻譯成不同語(yǔ)種的說明書所需時(shí)間如表5-7所示。問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少? 表5-7任 務(wù)人員 E J G R 甲 乙 丙 丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 類似有：有n項(xiàng)加工任務(wù)，怎樣指派到n臺(tái)機(jī)床上分別完成的問題；有n條航線，怎樣指定n艘船去航行問題。對(duì)應(yīng)每個(gè)指派問題，需有類似表5-7那樣的數(shù)表，稱為效率矩陣或系數(shù)矩陣，其元素cij0(i,j=1,2，n)表示指派第i人去完成第j項(xiàng)任務(wù)時(shí)的效率(或時(shí)間、成本等)。解題時(shí)需引入變量xij；其取值只能是1或0。并令 項(xiàng)任務(wù)人去完成第當(dāng)不指派第項(xiàng)任務(wù)人去完成第當(dāng)指派第jijixij, 0, 1當(dāng)問題要求極小化時(shí)數(shù)學(xué)模型是： )195(01, 2 , 1, 1, 2 , 1, 1min或約束條件目標(biāo)函數(shù)ijjijiijijijijxnixnjxxcz顯然，解矩陣(xij)中各行各列的元素之和都是1。但這不是最優(yōu)。 約束條件說明第j項(xiàng)任務(wù)只能由1人去完成；約束條件說明第i人只能完成1項(xiàng)任務(wù)。 滿足約束條件的可行解xij也可寫成表格或矩陣形式，稱為解矩陣。 如例7的一個(gè)可行解矩 1000000101000010ijx指派問題是0-1規(guī)劃的特例，也是運(yùn)輸問題的特例；即n=m,aj=bi=1 當(dāng)然可用整數(shù)線性規(guī)劃，0-1規(guī)劃或運(yùn)輸問題的解法去求解，這就如同用單純形法求解運(yùn)輸問題一樣是不合算的。利用指派問題的特點(diǎn)可有更簡(jiǎn)便的解法。 指派問題的最優(yōu)解有這樣性質(zhì)，若從系數(shù)矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)， 那么以(bij)為系數(shù)矩陣求得的最優(yōu)解和用原系數(shù)矩陣求得的最優(yōu)解相同 。 利用這個(gè)性質(zhì)，可使原系數(shù)矩陣變換為含有很多0元素的新系數(shù)矩陣，而最優(yōu)解保持不變，在系數(shù)矩陣(bij)中，我們關(guān)心位于不同行不同列的0元素，以下簡(jiǎn)稱為獨(dú)立的0元素。 若能在系數(shù)矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)立的0元素的元素取值為1，其他元素取值為0。將其代入目標(biāo)函數(shù)中得到zb=0，它一定是最小。 這就是以(bij)為系數(shù)矩陣的指派問題的最優(yōu)解。也就得到了原問題的最優(yōu)解。 以下用例7來說明指派問題的解法。第一步：使指派問題的系數(shù)矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。(1) 從系數(shù)矩陣的每行元素減去該行的最小元素；(2) 再?gòu)乃孟禂?shù)矩陣的每列元素中減去該列的最小元素。若某行(列)已有0元素，那就不必再減了。例7的計(jì)算為行列都有零元素min24)(001023509606071302410475011100621113079429118713161491514410413152)(minijijbc第二步：進(jìn)行試指派，以尋求最優(yōu)解。為此，按以下步驟進(jìn)行。 經(jīng)第一步變換后，系數(shù)矩陣中每行每列都已有了0元素；但需找出n個(gè)獨(dú)立的0元素。若能找出，就以這些獨(dú)立0元素對(duì)應(yīng)解矩陣(xij)中的元素為1，其余為0，這就得到最優(yōu)解。當(dāng)n較小時(shí)，可用觀察法、試探法去找出n個(gè)獨(dú)立0元素。若n較大時(shí)，就必須按一定的步驟去找，常用的步驟為： (1) 從只有一個(gè)0元素的行(列)開始，給這個(gè)0元素加圈，記作。這表示對(duì)這行所代表的人，只有一種任務(wù)可指派。然后劃去所在列(行)的其他0元素，記作。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 (2) 給只有一個(gè)0元素列(行)的0元素加圈，記作；然后劃去所在行的0元素，記作。 (3) 反復(fù)進(jìn)行(1)，(2)兩步，直到所有0元素都被圈出和劃掉為止。 (4) 若仍有沒有劃圈的0元素，且同行(列)的0元素至少有兩個(gè)(表示對(duì)這個(gè)可以從兩項(xiàng)任務(wù)中指派其一)。這可用不同的方案去試探。從剩有0元素最少的行(列)開始，比較這行各0元素所在列中0元素的數(shù)目，選擇0元素少的那列的這個(gè)0元素加圈(表示選擇性多的要“禮讓”選擇性少的)。然后劃掉同行同列的其他0元素?？煞磸?fù)進(jìn)行，直到所有0元素都已圈出和劃掉為止。 (5) 若元素的數(shù)目m等于矩陣的階數(shù)n，那么這指派問題的最優(yōu)解已得到。若mn，則轉(zhuǎn)入下一步?，F(xiàn)用例7的(bij)矩陣，按上述步驟進(jìn)行運(yùn)算。按步驟(1)，先給b22加圈，然后給b31加圈，劃掉b11，b41；按步驟(2)，給b43加圈，劃掉b44，最后給b14加圈，得到 1235066713注意：矩陣中符號(hào)即是文中的符號(hào)。以下同?？梢妋=n=4,所以得最優(yōu)解為0100000100101000)(ijx這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文。所需總時(shí)間最少ijijijijijijbccccxczxbz)(28min0min14432231小時(shí)例8 求表5-8所示效率矩陣的指派問題的最小解。任 務(wù)人員 A B C D E 甲 乙 丙 丁 戊 12 8 7 15 4 7 9 17 14 10 9 6 12 6 7 7 6 14 6 10 9 6 9 10 9 表5-8解解 按上述第一步，將這系數(shù)矩陣進(jìn)行變換。 56360400892751000003220205467679107104106614159141217766698979712min經(jīng)一次運(yùn)算即得每行每列都有0元素的系數(shù)矩陣，再按上述步驟運(yùn)算，得到56364892751032225 這里的個(gè)數(shù)m=4，而n=5；所以解題沒有完成，這時(shí)應(yīng)按以下步驟繼續(xù)進(jìn)行。 第三步：作最少的直線覆蓋所有0元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立元素?cái)?shù)。為此按以下步驟進(jìn)行： (1) 對(duì)沒有的行打號(hào)； (2) 對(duì)已打號(hào)的行中所有含元素的列打號(hào)； (3) 再對(duì)打有號(hào)的列中含元素的行打號(hào)； (4) 重復(fù)(2)，(3)直到得不出新的打號(hào)的行、列為止。 (5) 對(duì)沒有打號(hào)的行畫一橫線，有打號(hào)的列畫一縱線，這就得到覆蓋所有0元素的最少直線數(shù)。 令這直線數(shù)為l。若ln，說明必須再變換當(dāng)前的系數(shù)矩陣，才能找到n個(gè)獨(dú)立的0元素，為此轉(zhuǎn)第四步：若l=n，而mn，應(yīng)回到第二步(4)，另行試探。 在例8中，對(duì)矩陣按以下次序進(jìn)行： 先在第五行旁打，接著可判斷應(yīng)在第1列下打，接著在第3行旁打。經(jīng)檢查不再能打了。對(duì)沒有打行，畫一直線以覆蓋0元素，已打的列畫一直線以覆蓋0元素。得注意：矩陣中的 符號(hào)，即文中的符號(hào)。56364892751032225 或由此可見l=4n。所以應(yīng)繼續(xù)對(duì)矩陣進(jìn)行變換。轉(zhuǎn)第四步。第四步： 對(duì)矩陣進(jìn)行變換的目的是增加0元素。為此在沒有被直線覆蓋的部分中找出最小元素。然后在打行各元素中都減去這最小元素，而在打列的各元素都加上這最小元素，以保證原來0元素不變。這樣得到新系數(shù)矩陣(它的最優(yōu)解和原問題相同)。若得到n個(gè)獨(dú)立的0元素，則已得最優(yōu)解，否則回到第三步重復(fù)進(jìn)行。 在例8的矩陣中，在沒有被覆蓋部分(第3、5行)中找出最小元素為2，然后在第3、5行各元素分別減去2，給第1列各元素加2，得到新矩陣。按第二步，找出所有獨(dú)立的0元素，得到矩陣。 3414040081105380000342020734144811538034227已具有n個(gè)獨(dú)立0元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為 由解矩陣得最優(yōu)指派方案 甲B，乙D，丙E，丁C，戊A 本例還可以得到另一最優(yōu)指派方案 甲B，乙C，丙E，丁D，戊A 所需總時(shí)間為min z=320000100100100000100000010 當(dāng)指派問題的系數(shù)矩陣，經(jīng)過變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上0元素時(shí)。這時(shí)可以任選一行(列)中某一個(gè)0元素，再劃去同行(列)的其他0元素。這時(shí)會(huì)出現(xiàn)多重解。 以上討論限于極小化的指派問題。對(duì)極大化的問題，即求)205(maxijijijxcz可令 bij=M-cij其中M是足夠大的常數(shù)(如選cij中最大元素為M即可)，這時(shí)系數(shù)矩陣可變換為B=(bij)這時(shí)bij0，符合匈牙利法的條件。目標(biāo)函數(shù)經(jīng)變換后，即解)215(minijijijxbz 所得最小解就是原問題的最大解，因?yàn)閕jijijijijijijijijijijijijijxcnMxcMxxcMxb)(因 nM 為 常 數(shù) ， 所 以 當(dāng) ijijijxb取 最 小 時(shí) ， ijijijxc便 為 最 大 。 有興趣的讀者可以進(jìn)入以下網(wǎng)站http:/www.ifors.ms.unimelb.edu.au/tutorial/提供了網(wǎng)上學(xué)習(xí)線性規(guī)劃單純形法表上求解和匈牙利法等方法。第5章 結(jié)束(歡迎對(duì)本課件的改進(jìn)和參與制作) 錢頌迪