運(yùn)籌學(xué)_指派問(wèn)題

1、第四節(jié)第四節(jié) 指指 派派 問(wèn)問(wèn) 題題 assignment problem 在生活中經(jīng)常遇到這樣的問(wèn)題，某在生活中經(jīng)常遇到這樣的問(wèn)題，某單位需完成單位需完成n n項(xiàng)任務(wù)，恰好有項(xiàng)任務(wù)，恰好有n n個(gè)人可承個(gè)人可承擔(dān)這些任務(wù)。由于每人的專長(zhǎng)不同，各擔(dān)這些任務(wù)。由于每人的專長(zhǎng)不同，各人完成任務(wù)不同人完成任務(wù)不同( (或所費(fèi)時(shí)間或所費(fèi)時(shí)間) )，效率也，效率也不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪不同。于是產(chǎn)生應(yīng)指派哪個(gè)人去完成哪項(xiàng)任務(wù)，使完成項(xiàng)任務(wù)，使完成n n項(xiàng)任務(wù)的總效率最高項(xiàng)任務(wù)的總效率最高( (或所需總時(shí)間最小或所需總時(shí)間最小) )。這類問(wèn)題稱為指。這類問(wèn)題稱為指派問(wèn)題或分派問(wèn)題。派問(wèn)題或分派

2、問(wèn)題。例例1 1 有一份中文說(shuō)明書(shū)，需譯成英、日、德、有一份中文說(shuō)明書(shū)，需譯成英、日、德、俄四種文字。分別記作俄四種文字。分別記作E E、J J、G G、R R?，F(xiàn)有甲、乙、?，F(xiàn)有甲、乙、丙、丁四人。他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種丙、丁四人。他們將中文說(shuō)明書(shū)翻譯成不同語(yǔ)種的說(shuō)明書(shū)所需時(shí)間如表的說(shuō)明書(shū)所需時(shí)間如表1 1所示。問(wèn)應(yīng)指派何人去所示。問(wèn)應(yīng)指派何人去完成何工作，使所需總時(shí)間最少完成何工作，使所需總時(shí)間最少? ? 表1任務(wù)人員 E J G R 甲 乙 丙 丁 2 10 9 7 15 4 14 8 13 14 16 11 4 15 13 9 耗時(shí) 類似有：有類似有：有n n項(xiàng)加工任務(wù)，怎樣指

3、派到項(xiàng)加工任務(wù)，怎樣指派到n n臺(tái)機(jī)床上分別完成的問(wèn)題；有臺(tái)機(jī)床上分別完成的問(wèn)題；有n n條航線，怎樣條航線，怎樣指定指定n n艘船去航行問(wèn)題艘船去航行問(wèn)題。對(duì)應(yīng)每個(gè)指派問(wèn)。對(duì)應(yīng)每個(gè)指派問(wèn)題，需有類似表題，需有類似表1 1那樣的數(shù)表，稱為效率矩陣那樣的數(shù)表，稱為效率矩陣或，其元素或，其元素c cijij0(i,j=1,20(i,j=1,2，n n) )表示指派表示指派第第i i人去完成第人去完成第j j項(xiàng)任務(wù)時(shí)的效率項(xiàng)任務(wù)時(shí)的效率( (或時(shí)間、成或時(shí)間、成本等本等) )。解題時(shí)需引入變量。解題時(shí)需引入變量x xijij；其取值只能；其取值只能是是1 1或或0 0。并令。并令 項(xiàng)任務(wù)人去完成第當(dāng)

4、不指派第項(xiàng)任務(wù)人去完成第當(dāng)指派第jijixij, 0, 1當(dāng)問(wèn)題要求極小化時(shí)數(shù)學(xué)模型是：當(dāng)問(wèn)題要求極小化時(shí)數(shù)學(xué)模型是： 1111min1,1,2,1,1,2,10nnijijijnijinijjijzc xxjnxinx目目標(biāo)標(biāo)函函數(shù)數(shù)約約束束條條件件或或()表 示 每 人 僅 做 一 件 事 情（表示一項(xiàng)工作只能由一個(gè)人完成）（xij）是nn矩陣,對(duì)應(yīng)于效率矩陣(cij).111111jniijinnnjnnxxxxxxxxx11,1,2,nijixjn表明各行之和為1 。11,1,2,nijjxin表明各列之和為1 。 滿足約束條件的可行解xij構(gòu)成的可行解矩陣，矩陣中有n個(gè)為1,其余都為

5、0,而且這這n個(gè)個(gè)1必位于矩陣的不必位于矩陣的不同行不同列上。同行不同列上。對(duì)應(yīng)于可行解xij的目標(biāo)值是這n個(gè)cij之和.可行解矩陣可行解矩陣工作工作人人顯然，解矩陣(xij)中各行各列的元素之和都是1，但這不是最優(yōu)。如例1的一個(gè)可行解矩陣01000010()10000001ijx E J G R 指派問(wèn)題是0-1規(guī)劃的特例，當(dāng)然可用整數(shù)線性規(guī)劃、0-1規(guī)劃的解法去求解，但可以利用指派問(wèn)題的特點(diǎn)設(shè)計(jì)更簡(jiǎn)便的解法，下面介紹匈牙利法。定理定理1 設(shè)()ijn nBb是效率矩陣,若可行解x*的n個(gè)1(在解矩陣的不同行不同列上)對(duì)應(yīng)的n個(gè)bij都為0, 則x*是最優(yōu)解.(顯然z(x*)=0) 因此需對(duì)

6、效率矩陣作變換,使變換后效率矩陣()ijn nb含有含有n個(gè)不同行不同列個(gè)個(gè)不同行不同列個(gè)0.由此求得最優(yōu)解矩陣的n個(gè)1是對(duì)應(yīng)于效率矩陣的這n個(gè)0.如效率矩陣為0*14939200*23230*38012140*令,10000010()01000001ijx則xij是最優(yōu)解11minnnijijijzb x定理定理2 2 設(shè)給定了以C = (cij)為效率矩陣指派問(wèn)題G，現(xiàn)將C的元素cij 改變?yōu)閯t以B= ( )為效率矩陣指派問(wèn)題G與G有相同的最優(yōu)解。 指派問(wèn)題的最優(yōu)解有這樣性質(zhì)，若從效率矩陣(cij)的一行(列)各元素中分別減去該行(列)的最小元素，得到新矩陣(bij)，那么以(bij)為效

7、率矩陣求得的最優(yōu)解和用原效率矩陣求得的最優(yōu)解相同 。即,ijijijijbc與為常數(shù)ijb證: 首先效率矩陣的這種變化只是目標(biāo)值在變換，并不影響約束方程組，其次用z和 z分別記問(wèn)題G與G的目標(biāo)函數(shù)值,則() ijijijijijijijijijiijjijijijjiijijzb xcxc xxxz即z和 z只相差一個(gè)常數(shù),故它們有相同的最優(yōu)解. 利用這個(gè)性質(zhì)，可使原效率矩陣變換變換為含有很多0元素的新效率矩陣，而最優(yōu)解保持不變，在效率矩陣(bij)中，我們關(guān)心位于不同行不同列的0元素，以下簡(jiǎn)稱為獨(dú)立的0元素。 若能在效率矩陣(bij)中找出n個(gè)獨(dú)立的0元素；則令解矩陣(xij)中對(duì)應(yīng)這n個(gè)獨(dú)

8、立的0元素的元素取值為1，其他元素取值為0。將其代入目標(biāo)函數(shù)中得到 ，它一定是最小。 這就是以(bij)為效率矩陣的指派問(wèn)題的最優(yōu)解。也就得到了原問(wèn)題的最優(yōu)解。0ijijijzb x 以下用例1來(lái)說(shuō)明指派問(wèn)題的解法。第一步：使指派問(wèn)題的效率矩陣經(jīng)變換，在各行各列中都出現(xiàn)0元素。(1) 從效率矩陣的每行元素減去該行的最小元素；(2) 再?gòu)乃眯示仃嚨拿苛性刂袦p去該列的最小元素。若某行(列)已有0元素，那就不必再減了。例1的計(jì)算為min215134210414154()9141613978119701311201370*60101160*69()05740*5320142010*042mini

9、jijcb行例如列行列都有零元素最優(yōu)解為最優(yōu)解為00010100()10000010ijx定理定理3 若矩陣C可分成”0”與非”0”兩部分,則覆蓋”0”元素的最少直線最少直線等于位于不同行不同列的”0”元素的最大個(gè)數(shù)最大個(gè)數(shù).如50*202230*000*105729800*406365覆蓋”0”元素的最少直線為4條,位于不同行不同列的”0”元素的最大個(gè)數(shù)也為4.01370606905320100()ijb再如例1直線數(shù)位于不同行不同列的”0”元素的最大個(gè)數(shù)也為4.第二步第二步: 做能覆蓋所有零元素的最少數(shù)目的直線集合。此時(shí)，若直線數(shù)等于 n ，則已可得出最優(yōu)解。否則，轉(zhuǎn)第三步 。第三步第三步

10、: 變換效率矩陣，使未被直線覆蓋的元素中出現(xiàn)零元素。回到第二步。 在未被直線覆蓋的元素中總有一個(gè)最小元素。對(duì)未被直線覆蓋的元素所在的行（或行）中各元素都減去這一最小元素，這樣，在未被直線覆蓋的元素中勢(shì)必會(huì)出現(xiàn)零元素，但同時(shí)卻又使已被直線覆蓋的元素中出現(xiàn)負(fù)元素。為了消除負(fù)元素，只要對(duì)它們所在的列（或行）中各元素都加上這一最小元素（可以看作減去這一最小元素的相反數(shù)）即可。50*202230*000*105729800*406365如-2-250*202230*00283509800*424143+270*202430*0008350*11800*40*4143第四步：進(jìn)行指派，尋求最優(yōu)解。需找出n

11、個(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元素的行(列)開(kāi)始，給這個(gè)0元素加圈，記作。這表示對(duì)這行所代表的人只有一種任務(wù)可指派。然后劃去所在列(行）的其他0元素，記作。這表示這列所代表的任務(wù)已指派完，不必再考慮別人了。 如此反復(fù)進(jìn)行，直到所有0元素都被圈出和劃掉為止。 (2)若遇到同行(列)的0元素至少有兩個(gè)(表示可以從兩項(xiàng)任務(wù)中指派其一)，可以任選一行(列)中某一個(gè)0元素，再劃去同行(列)的其他0元素。現(xiàn)用例1的(bi

12、j)矩陣，按上述步驟進(jìn)行運(yùn)算。先給b22加圈，然后給b31加圈，劃掉b11，b41；給b43加圈，劃掉b44，最后給b14加圈，得到 01370606905320100()ijb137669532101370*60*690*532010*0所以得最優(yōu)解為00010100()10000010ijx這表示：指定甲譯出俄文，乙譯出日文，丙譯出英文，丁譯出德文。所需總時(shí)間最少31224314028minminijijijijijijzb xzc xcccc E J GR甲乙丙丁 （小時(shí)）2151341041415()914161378119ijc例例2 某商業(yè)公司設(shè)計(jì)開(kāi)辦五家新聞商店 。為了盡早建成營(yíng)

13、業(yè)，商業(yè)公司通知了 五個(gè)建筑公司，以便讓每家新商店由一個(gè)建筑公司承建。建筑公司 對(duì)新商店 的建造費(fèi)用的投標(biāo)為 均見(jiàn)表。商業(yè)公司應(yīng)當(dāng)對(duì)五家建筑公司 怎樣分配建造任務(wù)，才能使總建造費(fèi)用最少？54321,BBBBB54321,AAAAAiAjBijc2A3A4A5A 487151279171410691287671461069121061B2B3B4B5B1AijcjBiA解：這是一個(gè)標(biāo)準(zhǔn)的指派問(wèn)題。若設(shè)0-1變量 則問(wèn)題的數(shù)學(xué)模型為 )5 , 4 , 3 , 2 , 1,(, 0, 1jiBABAxjijiij時(shí)不承建當(dāng)時(shí)承建當(dāng)5 , 4 , 3 , 2 , 11015 , 4 , 3 , 2 ,

14、 11. .61084min515155541211ixxjxtsxxxxzijjijiij或(一個(gè)商店只能由一個(gè)公司承建)(一個(gè)公司只能建造一個(gè)商店)現(xiàn)在，我們來(lái)解例2的指派問(wèn)題的效率矩陣為 61012961061477812910141791215786674C對(duì)各行元素分別減去本行的最小元素，對(duì)各列也如此，得 0432040501232377181103000004630408112633710281134000061012961061477812910141791215786674 容易看出，可用四條直線覆蓋所有零元素，這是最少數(shù)直線 集合，由于C的階數(shù) =5，故需對(duì)效率矩陣C繼續(xù)變換

15、。n0301 1801773023210050402340-4-7-6-6-6 -1 -3為了使未被直線覆蓋的元素中出現(xiàn)零元素，將第二行和第三行中各元素減去未被直線覆蓋元素中的最小元素1。但這樣一來(lái)，第一列中出現(xiàn)了負(fù)元素，因而再對(duì)第一列各元素分別加上1，即043214050012126608110310010432040500121266081103011004320405012323771811030000此時(shí)，已不能用少于五條直線來(lái)覆蓋所有零元素，故已可看得最優(yōu)指派方案。為了得到最優(yōu)指派方案，對(duì)效率矩陣進(jìn)行圈零：-1+1也就是說(shuō)，最優(yōu)指派方案為：讓也就是說(shuō)，最優(yōu)指派方案為：讓A A1 1

16、承建承建B B3 3, , A A2 2 承建承建B B2 2, A A3 3 承建承建 B B1 1, , A A4 4 承建承建 B B4 4, A A5 5 承建承建 B B5 5, 這樣，總的建設(shè)費(fèi)用這樣，總的建設(shè)費(fèi)用最少，為最少，為7+9+6+6+6=34萬(wàn)元。萬(wàn)元。130*1180*6620*121150*412340*0 01000 10001 00000 001000001X 所以，本題最優(yōu)解為所以，本題最優(yōu)解為先找出零元素最少行列先找出零元素最少行列,然然后對(duì)其它行列的零元素進(jìn)后對(duì)其它行列的零元素進(jìn)行篩選行篩選,保證各行列只有一保證各行列只有一個(gè)零元素個(gè)零元素.6101296

17、1061477812910141791215786674C5A12345AAAAAB1 B2 B3 B4 B5練習(xí)： 求表所示效率矩陣的指派問(wèn)題的最小解。表解解 按上述第一步，將這效率矩陣進(jìn)行變換。按上述第一步，將這效率矩陣進(jìn)行變換。 1279797502028966662300071712149701057215146610 6980044107109406365min經(jīng)一次運(yùn)算即得每行每列都有經(jīng)一次運(yùn)算即得每行每列都有0 0元素的效率矩陣，元素的效率矩陣，再按上述步驟運(yùn)算，得到再按上述步驟運(yùn)算，得到5020223000283509800424143502022300001057298004

18、06365可用四條直線覆蓋所有零元素，可用四條直線覆蓋所有零元素，這是最少數(shù)直線集合，由于這是最少數(shù)直線集合，由于C的階數(shù)的階數(shù)=5，故需對(duì)效率矩陣，故需對(duì)效率矩陣C繼續(xù)變換。繼續(xù)變換。第三行和第五行減第三行和第五行減2,得得3414040081105380000342020770202430000835011800404143第1列+2此時(shí)，已不能用少于五條直線來(lái)覆蓋所有零元素，故已可看得最優(yōu)指派方案。72243083511844143為了得到最優(yōu)指派方案，對(duì)效率矩陣進(jìn)行圈零：為了得到最優(yōu)指派方案，對(duì)效率矩陣進(jìn)行圈零：70*2024300*008350*1180*040*4143 已具有已具

19、有n n個(gè)獨(dú)立個(gè)獨(dú)立0 0元素。這就得到了最優(yōu)解，相應(yīng)元素。這就得到了最優(yōu)解，相應(yīng)的解矩陣為：的解矩陣為：由解矩陣得最優(yōu)指派方案：由解矩陣得最優(yōu)指派方案：甲甲B B，乙，乙D D，丙，丙E E，丁，丁C C，戊，戊A A本例還可以得到另一最優(yōu)指派方案：本例還可以得到另一最優(yōu)指派方案：甲甲B B，乙，乙C C，丙，丙E E，丁，丁D D，戊，戊A A所需總時(shí)間為所需總時(shí)間為min z=7+6+9+6+4=32min z=7+6+9+6+4=320100000010000010010010000ijx1279798966671712149151466104107109()ijc甲乙丙丁戊 A B

20、C D E 當(dāng)指派問(wèn)題的效率矩陣，經(jīng)過(guò)變換得到了同行和同列中都有兩個(gè)或兩個(gè)以上0元素時(shí)。這時(shí)可以任選一行(列)中某一個(gè)0元素，再劃去同行(列)的其他0元素。這時(shí)會(huì)出現(xiàn)多重解。 一般的指派問(wèn)題一般的指派問(wèn)題 1、最大化指派問(wèn)題、最大化指派問(wèn)題設(shè)最大化指派問(wèn)題效率矩陣 ，其中最大元素 為 。令矩陣 ，則以B為效率矩陣的最小指派問(wèn)題和以C為效率矩陣的原最大化指派問(wèn)題有相同最優(yōu)解。nnijcC)(mnnijnnijcmbB)()(例例4 矩陣 9118713161491514410413152C 的最大元素為 ，取 ，令1633c16m758930271212612311491611168167161

21、316161614169161516141641610164161316516216B則以C為效率矩陣的最大化指派問(wèn)題和以B為效率矩陣的最小化指派問(wèn)題有相同最優(yōu)解。當(dāng)效率矩陣為利潤(rùn)矩陣、產(chǎn)量矩陣等時(shí)，就產(chǎn)生最大化指派問(wèn)題。 2、人數(shù)和事數(shù)不等的指派問(wèn)題、人數(shù)和事數(shù)不等的指派問(wèn)題 若人少事多，則添上一些虛擬的“人”。這些虛擬的“人”做各事的費(fèi)用系數(shù)可取0（理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生），若人多事少，則添上一些虛擬的“事”，這些“事”被各人做的費(fèi)用系數(shù)同樣可取0。3、一個(gè)人可做幾件事的指派問(wèn)題、一個(gè)人可做幾件事的指派問(wèn)題 若某事一定不能由某人做，則可將相應(yīng)的費(fèi)用系數(shù)取作足夠大的數(shù)M。 若某人可做幾

22、件事，則可將該人化作相同的幾個(gè)“人”來(lái)接受指派，這幾個(gè)“人”做同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。 4、某事一定不能由某人做的指派問(wèn)題、某事一定不能由某人做的指派問(wèn)題例例5 對(duì)于例2 的指派問(wèn)題，為了加快建造速度，經(jīng)研究決定，舍棄建筑公司 和 ，而讓技術(shù)力量較強(qiáng)的建筑公司 和 來(lái)承建。根據(jù)實(shí)際情況，可以允許每家建筑公司承建一個(gè)或兩個(gè)商店。求使總費(fèi)用最少的指派方案。反映投標(biāo)費(fèi)用的效率矩陣為4A5A21,AA3A 12345123487151279171410691287BBBBBAAA由于每家建筑公司最多可承建兩個(gè)新商店，因此，把每家建筑公司化作相同的兩家（ 和 ）。上面的效率矩陣有六行五列，為了使“

23、人”和“事”的數(shù)目相同，引入一件虛事，使之成為標(biāo)準(zhǔn)指派問(wèn)題的效率矩陣，這樣效率矩陣為：iA3 , 2 , 1, iAi00075000075031106303110630215000215000C(每列減列中最小值)（3、4行減1）332211654321000000771010121288141415151212171777999988667744AAAAAACBBBBBB110000551122001122555902590270007000000000551122125912590570057000002200從最后的矩陣已能確定最優(yōu)解，有123101 0 0010 0 0000 1 1

24、AAA0*00*7520*9522150*0*覆蓋所有零元素的最少數(shù)直線數(shù)為612345BBBBB+1所以，最優(yōu)指派方案是應(yīng)由所以，最優(yōu)指派方案是應(yīng)由A1承建承建B1和和B3, A2承建承建 B2, A3承建承建B4和和B5。這樣，總的建造費(fèi)用最省，是。這樣，總的建造費(fèi)用最省，是 4+7+9+8+7=35萬(wàn)元。萬(wàn)元。487151279171410691287ijc例例6 從甲、乙、丙、丁、戊五人中挑選四人去完成從甲、乙、丙、丁、戊五人中挑選四人去完成A、B、C、D四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)所需的時(shí)間如表所示。規(guī)定四項(xiàng)任務(wù)。每人完成各項(xiàng)任務(wù)所需的時(shí)間如表所示。規(guī)定每項(xiàng)任務(wù)只能由一個(gè)人單獨(dú)完成，且每人最多承擔(dān)一項(xiàng)任務(wù)。每項(xiàng)任務(wù)只能由一個(gè)人單獨(dú)完成，且每人最多承擔(dān)一項(xiàng)任務(wù)。又假定甲必須保證承擔(dān)一項(xiàng)任務(wù)，丁不能承擔(dān)任務(wù)又假定甲必