運(yùn)籌學(xué)指派問題ppt課件

1、第五節(jié) 指派問題（Assignment Problem） 1. 標(biāo)準(zhǔn)指派問題的提法及模型 指派問題的標(biāo)準(zhǔn)形式是：有n個人和n件事，已知第i個人做第j件事的費(fèi)用為cij（i，j=1，2，n），要求確定人和事之間的一一對應(yīng)的指派方案，使完成這n件事的總費(fèi)用最小,數(shù)學(xué)模型為,其中矩陣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

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

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

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

5、為了消除負(fù)元素）。得到新的系數(shù)矩陣，返回步2。 以例說明匈牙利法的應(yīng)用,例1：求解效率矩陣為如下的指派問題的最優(yōu)指派方案,解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素,第二步：確定獨(dú)立0元素,第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換,第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素的個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么,由解矩陣可得指派方案和最優(yōu)值為32,例2 某大型工程有五個

6、工程項(xiàng)目，決定向社會公開招標(biāo)，有五家建筑能力相當(dāng)?shù)慕ㄖ痉謩e獲得中標(biāo)承建。已知建筑公司Ai（I=1，2，3，4，5）的報(bào)價cij（百萬元）見表，問該部門應(yīng)該怎樣分配建造任務(wù)，才能使總的建造費(fèi)用最小,解：第一步：系數(shù)矩陣的變換（目的是得到某行或列均有0元素,第二步：確定獨(dú)立0元素, 即加圈,元素的個數(shù)m=4，而n=5，進(jìn)行第三步,第三步：作最少的直線覆蓋所有的0元素，目的是確定系數(shù)矩陣的下一個變換,第四步：對上述矩陣進(jìn)行變換，目的是增加獨(dú)立0元素個數(shù)。方法是在未被直線覆蓋的元素中找出一個最小元素，然后在打“”行各元素中都減去這一元素，而在打“”列的各元素都加上這一最小元素，以保持原來0元素不變

7、（消除負(fù)元素）。得到新的系數(shù)矩陣。（它的最優(yōu)解和原問題相同，為什么？因?yàn)閮H在目標(biāo)函數(shù)系數(shù)中進(jìn)行操作,此矩陣中已有5個獨(dú)立的0元素，故可得指派問題的最優(yōu)指派方案為,也就是說，最優(yōu)指派方案為：讓A1承建B3， A2承建B2，A3承建B1，A4承建B4，A5承建B5。這樣安排建造費(fèi)用為最小，即 7+9+6+6+6=34（百萬元,3. 一般的指派問題 在實(shí)際應(yīng)用中，常會遇到各種非標(biāo)準(zhǔn)形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。 最大化指派問題 設(shè)最大化指派問題系數(shù)矩陣C中最大元素為m。令矩陣B=(bij)=(m-cij), 則以B為系數(shù)矩陣的最小化指派問題和以C為系數(shù)

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