運(yùn)籌學(xué)指派問題PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1其中矩陣C稱為是效率矩陣或系數(shù)矩陣。 其解的形式可用0-1矩陣的形式來描述，即 (xij)nn。 標(biāo)準(zhǔn)的指派問題是一類特殊的整數(shù)規(guī)劃問題，又是特殊的0-1規(guī)劃問題和特殊的運(yùn)輸問題。1955年W. W. Kuhn利用匈牙利數(shù)學(xué)家D. Konig關(guān)于矩陣中獨(dú)立零元素的定理, 提出了解指派問題的一種算法, 習(xí)慣上稱之為匈牙利解法。2. 匈牙利解法 匈牙利解法的關(guān)鍵是指派問題最優(yōu)解的以下性質(zhì)：若從指派若從指派問題的系數(shù)矩陣問題的系數(shù)矩陣C=（cij）的某行（或某列）各元素分別減去一個(gè)）的某行（或某列）各元素分別減去一個(gè)常數(shù)常數(shù)k，得到一個(gè)新的矩陣，得到一個(gè)新的矩陣C=（cij)，則以，則以C和

2、和C為系數(shù)矩陣的兩為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。個(gè)指派問題有相同的最優(yōu)解。（這種變化不影響約束方程組，而只是使目標(biāo)函數(shù)值減少了常數(shù)k，所以，最優(yōu)解并不改變。） 對(duì)于指派問題，由于系數(shù)矩陣均非負(fù)，故若能在在系數(shù)矩陣中找到n個(gè)位于不同行和不同列的零元素（獨(dú)立的0元素），則對(duì)應(yīng)的指派方案總費(fèi)用為零，從而一定是最優(yōu)的。作變換，其不變性是最優(yōu)解第1頁/共19頁匈牙利法匈牙利法的步驟如下： 步1：變換系數(shù)矩陣。對(duì)系數(shù)矩陣中的每行元素分別減去該行的最小元素；再對(duì)系數(shù)矩陣中的每列元素分別減去該列中的最小元素。若某行或某列已有0元素，就不必再減了（不能出現(xiàn)負(fù)元素）。 第2頁/共19頁 步2：在變換后的

3、系數(shù)矩陣中確定獨(dú)立0元素（試指派）。若獨(dú)立0元素已有n個(gè)，則已得出最優(yōu)解；若獨(dú)立0元素的個(gè)數(shù)少于n個(gè)，轉(zhuǎn)步3。 確定獨(dú)立0元素的方法：當(dāng)n較小時(shí)，可用觀察法、或試探法；當(dāng)n較大時(shí)，可按下列順序進(jìn)行 從只有一個(gè)0元素的行（列）開始，給這個(gè)0元素加圈，記作，然后劃去所在的列（行）的其它0元素，記作。給只有一個(gè)0元素的列（行）的0加圈，記作，然后劃去所在行的0元素，記作。反復(fù)進(jìn)行，直到系數(shù)矩陣中的所有0元素都被圈去或劃去為止。 如遇到行或列中0元素都不只一個(gè)（存在0元素的閉回路），可任選其中一個(gè)0元素加圈，同時(shí)劃去同行和同列中的其它0元素。被劃圈的0元素即是獨(dú)立的0元素。第3頁/共19頁步3：作最少

4、數(shù)目的直線，覆蓋所有0元素（目的是確定系數(shù)矩陣的下一個(gè)變換），可按下述方法進(jìn)行1） 對(duì)沒有的行打“”號(hào)；2） 在已打“”號(hào)的行中，對(duì) 所在列打“”3）在已打“”號(hào)的列中，對(duì)所在的行打“”號(hào)；4）重復(fù)2）3），直到再也找不到可以打“”號(hào)的行或列為止；5）對(duì)沒有打“”的行劃一橫線，對(duì)打“”的列劃一縱線，這樣就得到覆蓋所有0元素的最少直線數(shù)。第4頁/共19頁 步4：繼續(xù)變換系數(shù)矩陣，目的是增加獨(dú)立0元素的個(gè)數(shù)。方法是在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（為了消除負(fù)元素）。得到新的系數(shù)矩陣，返回步2。

5、 以例說明匈牙利法的應(yīng)用。9107104106614159141217766698979712例1：求解效率矩陣為如下的指派問題的最優(yōu)指派方案。第5頁/共19頁解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素）910710410661415914121776669897971256360400892751000003220205第二步：確定獨(dú)立0元素56360400892751000003220205元素的個(gè)數(shù)m=4，而n=5，進(jìn)行第三步。第6頁/共19頁第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個(gè)變換。第四步：對(duì)上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素的個(gè)數(shù)。方法是

6、在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？）56360400892751000003220205第7頁/共19頁0000100100100000100000010由解矩陣可得指派方案和最優(yōu)值為32。34140400811053800003420207第8頁/共19頁 例2 某大型工程有五個(gè)工程項(xiàng)目，決定向社會(huì)公開招標(biāo)，有五家建筑能力相當(dāng)?shù)慕ㄖ痉謩e獲得中標(biāo)承建。已知建筑公司Ai（I=1，2，3，4，5）的報(bào)價(jià)cij（百萬元）見表，

7、問該部門應(yīng)該怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最??？ 工程公司B1B2B3B4B5A14871512A279171410A3691287A46714610A56912106第9頁/共19頁5 ,2, 1,105 ,2, 115 ,2, 11.61084min515155541211jiorxixjxtsxxxxZijjijiij第10頁/共19頁61012961061476781296101417971215784解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素）04320405001232037710811030第二步：確定獨(dú)立0元素, 即加圈元素的個(gè)數(shù)m=4，而n=5，進(jìn)行第三步

8、。04320405001232037710811030第11頁/共19頁第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個(gè)變換。第四步：對(duì)上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素個(gè)數(shù)。方法是在未被直線覆蓋的元素中找出一個(gè)最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？因?yàn)閮H在目標(biāo)函數(shù)系數(shù)中進(jìn)行操作）04320405001232037710811030第12頁/共19頁043204050001211266018110300432140501012102660

9、081103104321405010121026600811031第13頁/共19頁此矩陣中已有5個(gè)獨(dú)立的0元素，故可得指派問題的最優(yōu)指派方案為：1000001000000010001000100也就是說，最優(yōu)指派方案為：讓A1承建B3， A2承建B2，A3承建B1，A4承建B4，A5承建B5。這樣安排建造費(fèi)用為最小，即7+9+6+6+6=34（百萬元）第14頁/共19頁3. 一般的指派問題 在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。 最大化指派問題 設(shè)最大化指派問題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij

10、), 則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。 人數(shù)和事數(shù)不等的指派問題 若人少事多，則添上一些虛擬的“人”。這些虛擬的人作各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多事少，則添上一些虛擬的“事”。這些虛擬的事被各人做的費(fèi)用系數(shù)同樣也取0。 一個(gè)人可做幾件事的指派問題 若某個(gè)人可做幾件事，則可將該人看做相同的幾個(gè)人來接受指派。這幾個(gè)人作同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。 某事一定不能由某人作的指派問題 若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)M。第15頁/共19頁 例3：對(duì)于例2的指派問題，為了保證工程質(zhì)量，經(jīng)研究決定，舍棄建筑公司A4和A5，而讓技術(shù)力量較強(qiáng)的建設(shè)公司A1，A2，A3參加招標(biāo)承建，根據(jù)實(shí)際情況，可允許每家建設(shè)公司承建一項(xiàng)或二項(xiàng)工程。求使總費(fèi)用最少的指派方案。 工程公司B1B2B3B4B5A14871512A279171410A3691287解：由于每家建筑公司最多可以承建兩項(xiàng)，因此可把每家建筑公司看成兩家建筑公司，其系數(shù)矩陣為第16頁/共19頁33221178129678129610141797101417971215784121578454321AAAAAABBBBB上面的系數(shù)矩陣有6行5列