匈牙利法解決人數(shù)及任務(wù)數(shù)不等的指派問(wèn)題

匈牙利法解決人數(shù)與任務(wù)數(shù)不等的指派問(wèn)題于凱重慶科技學(xué)院經(jīng)濟(jì)管理學(xué)院物流專(zhuān)業(yè)重慶沙坪壩區(qū)摘要：本文將討論運(yùn)籌學(xué)中的指派問(wèn)題，而且屬于非標(biāo)準(zhǔn)指派問(wèn)題，即人數(shù)與任務(wù)數(shù)不相等的指派問(wèn)題，應(yīng)當(dāng)視為一個(gè)多目標(biāo)決策問(wèn)題，首先要求指派給個(gè)人任務(wù)數(shù)目?jī)蓛芍g相差不能超過(guò)1,其次要求所需總時(shí)間最少，并且給出了該類(lèi)問(wèn)題的求解方法。關(guān)鍵詞：運(yùn)籌學(xué)指派問(wèn)題匈牙利算法系數(shù)矩陣解矩陣引言：在日常的生產(chǎn)生活中常遇到這樣的問(wèn)題：有n項(xiàng)任務(wù)，有n個(gè)人員可以去承擔(dān)這n項(xiàng)任務(wù)，但由于每位人員的特點(diǎn)與專(zhuān)長(zhǎng)不同，各對(duì)象完成各項(xiàng)任務(wù)所用的時(shí)間費(fèi)用或效益不同：有因任務(wù)性質(zhì)要求和管理上需要等原因，每項(xiàng)任務(wù)只能由一個(gè)人員承擔(dān)來(lái)完成，這就涉及到應(yīng)該指派哪個(gè)人員去完成哪項(xiàng)任務(wù)，才能使完成n項(xiàng)任務(wù)花費(fèi)總時(shí)間最短,總費(fèi)用最少，產(chǎn)生的總效益最佳。我們把這類(lèi)最優(yōu)匹配問(wèn)題稱(chēng)為指派問(wèn)題或分配問(wèn)題。指派問(wèn)題的解法——匈牙利法早在1955年庫(kù)恩(w.w.ku.hn)就提出了指派問(wèn)題的解法，該方法是以匈牙利數(shù)學(xué)家康尼格(koning)提出的一個(gè)關(guān)于矩陣中0元素的定理為基礎(chǔ)，因此得俎匈牙利法(TheHungonrianMethodofAssignment)匈牙利解法的基本原理和解題思路直觀的講，求指派問(wèn)題的最優(yōu)方案就是要在n階系數(shù)矩陣中找出n個(gè)分布于不用行不同列的元素使得他們的和最小。而指派問(wèn)題的最優(yōu)解又有這樣的性質(zhì)：若從系數(shù)矩陣C(ij)的一行(列)各元素都減去該行(列)的最小元素，得到新矩陣CB(ij)，那么以CB(ij)為系數(shù)矩陣求得的最優(yōu)解和原系數(shù)矩陣C(ij)求得的最優(yōu)解相同。由于經(jīng)過(guò)初等變換得到的新矩陣CB(ij)中每行(列)的最小元素均為"O"，因此求原指派問(wèn)題C(ij)的最優(yōu)方案就等于在新矩陣CB(ij)中找出n個(gè)分布于不同行不同列的"O"元素(簡(jiǎn)稱(chēng)為“獨(dú)立O元素”)，這些獨(dú)立O元素就是CB(ij)的最優(yōu)解，同時(shí)與其對(duì)應(yīng)的原系數(shù)矩陣的最優(yōu)解。匈牙利法的具體步驟第一步：使指派問(wèn)題的系數(shù)矩陣經(jīng)過(guò)變換在各行各列中都出現(xiàn)O元素。先將系數(shù)矩陣的每行中的每個(gè)元素減去本行中的最小元素。再?gòu)南禂?shù)矩陣的每列中的每個(gè)元素減去本列的最小元素。第二步：進(jìn)行試指派，以尋求最優(yōu)解。(l)從含有O元素個(gè)數(shù)最少的行(列)開(kāi)始，給某個(gè)O元素加圈，記作◎,然后劃去與◎所在同行(列)雜英他O元素，記作0。(注：從含元素少的開(kāi)始標(biāo)記◎的原則)(2)重復(fù)進(jìn)行(1)的操作，直到所有O元素都記作◎或0,稱(chēng)作“禮讓原則”。(3)按以上方法操作后，若◎元素?cái)?shù)目m'等于矩陣階數(shù)n,那么指派問(wèn)題最優(yōu)解已得到。若m<n,則轉(zhuǎn)入下一步。第三步：做最少的直線覆蓋所有的O元素，以確定該系數(shù)矩陣中能找到最多的獨(dú)立O元素。(1)對(duì)沒(méi)有◎的行打J號(hào)；(2)對(duì)已打J號(hào)的行中含有0元素所在的列打1號(hào)：（3）對(duì)已打J號(hào)的列中含有◎元素所在的行打J號(hào)：（4）重復(fù)（2）、（3）直到得不到新J號(hào)的行和列為止：（5）對(duì)沒(méi)有V號(hào)的行畫(huà)一橫線，有J號(hào)的列畫(huà)一豎線。如此便可以覆蓋所有的O元素（注：這里的O元素是指◎或0）第四步：以上畫(huà)線的目的是為了選取新的最小元素，以便增加O元素，最后達(dá)到?元素個(gè)數(shù)m二n。（1）為此在沒(méi)有被直線覆蓋的所有元素中找出最小元素，然后將沒(méi)有被直線覆蓋的每個(gè)元素都減去該最小元素，同時(shí)把打“1”的列中的每個(gè)元素加上該最小元素，以保證原O元素不變。（2）再按照第二步原則進(jìn)行選取獨(dú)立O元素。若得到n個(gè)◎元素，則已是該矩陣的最優(yōu)解（同時(shí)也是原矩陣的最優(yōu)解）；否則，回到第三步重復(fù)進(jìn)行。第五步：在第四步得到的最優(yōu)解情況下的系數(shù)矩陣變換為解矩陣。將系數(shù)矩陣中的所有◎都變成元素1，而其他元素均變成0元素，得到的新矩陣便為原指派問(wèn)題的解矩陣,根據(jù)解矩陣中1元素所在的行、列數(shù)，去確左派哪個(gè)人員去做哪項(xiàng)任務(wù)。（注:在解矩陣（乂4）中，Xij=o元素表示不派第i個(gè)人去完成第j項(xiàng)任務(wù)，XijJ表示指派第i個(gè)人去完成第j項(xiàng)任務(wù)）需要對(duì)匈牙利法的第二步畫(huà)0行的說(shuō)明：當(dāng)指派問(wèn)題的系數(shù)矩陣經(jīng)過(guò)變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上。元素時(shí)，這時(shí)可以任選一行（列）中某個(gè)o元素，再劃去同行（列）苴他O元素。這時(shí)會(huì)出現(xiàn)多重優(yōu)化解，對(duì)應(yīng)著多種最優(yōu)的指派方案。如果出現(xiàn)此種情況，各位讀者不必疑惑。極大化指派問(wèn)題以上討論的均限于極小化的指派問(wèn)題，對(duì)于極大化的問(wèn)題，即求MqyZ=工工（例如：如何安排n個(gè)工程隊(duì)去完成n個(gè)項(xiàng)目才能使總收益最大）以下是解決該問(wèn)題的原理部分：可令bl}=M-cjj（其中M是原系數(shù)矩陣（c?）中最大的元素）則原系數(shù)矩陣變換成新矩陣（女石），這時(shí)＞0，符合匈牙利法的條件，而且等式為為切內(nèi)二為工（M—q坨恒成立，所以，當(dāng)新的系數(shù)矩陣取到極小化指派問(wèn)題的?? ??ij ij解矩陣時(shí)，就對(duì)應(yīng)著原問(wèn)題的最大化指派方案的最優(yōu)指派方案。人員數(shù)不等于任務(wù)數(shù)的指派問(wèn)題：以上我們討論的問(wèn)題均是標(biāo)準(zhǔn)型指派問(wèn)題，但在實(shí)際生活中可能出現(xiàn)人手不夠或者任務(wù)較少人員較多的情況，該類(lèi)問(wèn)題當(dāng)然也可以利用匈牙利法求解。從以上討論了匈牙利法的原理可知匈牙利法適用于系數(shù)矩陣為方陣的指派問(wèn)題，從這個(gè)基本原則出發(fā)，給系數(shù)矩陣并非方陣的問(wèn)題，添加虛擬人員或任務(wù)使英構(gòu)成標(biāo)準(zhǔn)型指派問(wèn)題，從而進(jìn)一步利用匈牙利法求解最優(yōu)解，而且構(gòu)造的方陣的最優(yōu)解同時(shí)也是原問(wèn)題的最優(yōu)解。3.1人數(shù)大于任務(wù)數(shù)的指派問(wèn)題下而結(jié)合例子說(shuō)明人數(shù)m大于任務(wù)數(shù)n的指派問(wèn)題的解法。

例1：設(shè)有三項(xiàng)任務(wù)丁「T「T3，可以安排的的人為M2.M3.“4去完成，各人完成各項(xiàng)工作所花費(fèi)的時(shí)間勺如表3.1所示，問(wèn)應(yīng)如何指派所用的總時(shí)間1120）10 14141610 141416105 0T—已找出四個(gè)獨(dú)立元素。最少？務(wù)時(shí)T.T,Ts21513■10114M391116M47811解：第一步：添加M-N個(gè)虛擬任務(wù)，并賦予各人完成這些虛擬任務(wù)的時(shí)間為0?此時(shí)將問(wèn)題轉(zhuǎn)化為人數(shù)與任務(wù)相等的指派問(wèn)題（注：本題N二3）r2 15 13010414、0(q) 914160<7 811第二步：運(yùn)用匈牙利法求解11"100010故例010故例1的解矩陣為(Xy)=000<001所以最優(yōu)指派方案為Mi完成T「Ng完

1°J成T.完成「而卜舄沒(méi)有任務(wù)?；ㄙM(fèi)總時(shí)間最少為minz=CH+C22+C43=2+4+11=17（小時(shí)）任務(wù)數(shù)大于人數(shù)的指派問(wèn)題下面結(jié)合例2說(shuō)明任務(wù)數(shù)n大于人數(shù)m的指派問(wèn)題的解法。、例2設(shè)有四項(xiàng)任務(wù)T「T2>T3.T「可以安排三個(gè)人卜1「M2.M3去完成，各人完成各項(xiàng)工作所需的時(shí)間5如表4.1所示，問(wèn)應(yīng)該指派哪個(gè)人去完成哪項(xiàng)任務(wù)所用的總時(shí)間最少？

時(shí)間任務(wù)T,T,T；Mi215134M，■1041415M39141613構(gòu)造系數(shù)矩陣(XH)二00<o第二步：運(yùn)用匈牙利法求解0000000、00100100000100001>r構(gòu)造系數(shù)矩陣(XH)二00<o第二步：運(yùn)用匈牙利法求解0000000、00100100000100001>r000或10<000100010000000000100、0100001000,， 15 13 410 4 14 15(q)= 9 14 16 13OO.O0O0；131126010、11\o"CurrentDocument"05 7 4\o"CurrentDocument"<00 00>\o"CurrentDocument"1311 2◎10H119min? 8◎10112〉 ◎ 3 5 2、0◎二故解矩陣(。’)的解矩陣為(Xry)=1<001r000>此時(shí)問(wèn)題轉(zhuǎn)化成人員與任務(wù)數(shù)相等的指派問(wèn)題o對(duì)應(yīng)的原指派問(wèn)題的方案為：M「完成完成丁2，卜乂完成而任務(wù)T3沒(méi)有‘215134、分配，為了使四項(xiàng)任務(wù)都完成，需要進(jìn)行二次指派。原系數(shù)矩陣為1041415,9141613,顯然T3列最小元素位于第一行，即口任務(wù)讓M「做。所以最終指派方案為完成T“「兩項(xiàng)，卜【2完成丁2，完成T"所需要的總時(shí)間為minz=CI4+C22+C31+C13=4+4+9+13=30(小時(shí))

例3.（2006年北京大學(xué)考研題）某房地產(chǎn)公司計(jì)劃在一住宅小區(qū)建5棟不同型號(hào)的樓房Bj（j=l.2、???5），現(xiàn)有三個(gè)工程隊(duì)A「（i=L2、3），允許每個(gè)工程隊(duì)承接1-2棟樓。招投標(biāo)得出工程隊(duì)A,（i=L2、3）對(duì)新樓BJ（j=L2、??-5）的預(yù)算費(fèi)用為q,見(jiàn)表4-2,求總費(fèi)用最小的分派方案。施A3fB2八B4,B2B4A.3871511A279101412卷69131217思考：該問(wèn)題若是直接利用以上添加兩位虛擬工程隊(duì)方法求解，只能先求出3個(gè)工程隊(duì)各完成1項(xiàng)項(xiàng)目的最優(yōu)費(fèi)用，還有2項(xiàng)任務(wù)沒(méi)有工程隊(duì)承接。接下來(lái)還要添加1項(xiàng)虛擬任務(wù)，然后進(jìn)行第二次指派，確定第一次指派剩下來(lái)的2項(xiàng)任務(wù)由哪兩個(gè)工程隊(duì)再次承接?？紤]到以上做法較為繁瑣，我們尋求一次性尋找出最優(yōu)指派方案的解法。由施工隊(duì)數(shù)3與項(xiàng)目數(shù)5的關(guān)系考慮到，只有1個(gè)施工隊(duì)承擔(dān)單個(gè)任務(wù)，而其他兩個(gè)施工隊(duì)均承擔(dān)2項(xiàng)項(xiàng)目。因此我們可以添加一個(gè)虛擬項(xiàng)目，以便讓每個(gè)工程隊(duì)都可以承擔(dān)2項(xiàng)項(xiàng)目。但又考慮到要一次性指派完成求解，則不能有虛擬工程隊(duì)，而且利用匈牙利法一左要是方陣才行。于是構(gòu)造如下新系數(shù)矩陣C=[c.]6.6。解：第一步：將工程隊(duì)重排一次形成6支工程隊(duì)，添加一項(xiàng)虛擬項(xiàng)目。最終形成方陣。構(gòu)造的系數(shù)矩陣C疔0或c嚴(yán)第二步：匈牙利法求解該矩陣的指派問(wèn)題(8779106913(87791069133877910、913151101412、012170151101412012173203￥\o"CurrentDocument"0 0 4 0◎ 2 2 00 5 ◎ 3203￥\o"CurrentDocument"0 0 4 0◎ 2 2 00 5 ◎ 50 ◎ 4 00 2 2 ◎0 5 0 5P(00 3<2\o"CurrentDocument"0 ◎ 4 0 10220、◎◎ 5 0 5 0\o"CurrentDocument"0 0 4 0 10 2 2 ◎ 00 5 ◎ 5 0)\o"CurrentDocument"0100 0對(duì)應(yīng)的兩個(gè)解矩陣為(&)二0 0 0 0 00 1 0 0 0 11 0 0 0 0 0 則原指派問(wèn)題最佳的指派方案<00000b<00010 0為Aj—>B］和B3,A,—>8?和B5,A3—>B40第二種方案：Aj—>B］和B3,A2—>B5,A3TB2和B-苴總費(fèi)用最小為minz=3+7+12+9+12=43（貨幣單位）5.結(jié)束語(yǔ)在整篇論文中主要是討論如何用匈牙利算法來(lái)求解最優(yōu)指派的問(wèn)題。而且重點(diǎn)是人數(shù)與任務(wù)不等的問(wèn)題的解決，更