1、第第3章章 整數(shù)規(guī)劃整數(shù)規(guī)劃哈爾濱工程大學(xué)哈爾濱工程大學(xué) 理學(xué)院理學(xué)院戴運(yùn)桃戴運(yùn)桃Email: 3.1 整數(shù)規(guī)劃整數(shù)規(guī)劃定義定義 規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。法能有效地求解一切整數(shù)規(guī)劃。整數(shù)規(guī)劃的數(shù)學(xué)模型整數(shù)規(guī)劃的數(shù)學(xué)模型njxmi

2、bxatsxcxfjnjijijnjjj,2,1,0,2,1,),(.)(max(min)11且為整數(shù) 若要求所有若要求所有 xj 的解為整數(shù)，稱為的解為整數(shù)，稱為純整數(shù)規(guī)劃純整數(shù)規(guī)劃 若要求部分若要求部分 xj 的解為整數(shù)，稱為的解為整數(shù)，稱為混合整數(shù)規(guī)劃混合整數(shù)規(guī)劃 對(duì)應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為對(duì)應(yīng)沒有整數(shù)解要求的線性規(guī)劃稱之為松弛問題松弛問題 整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問題的最優(yōu)解引例引例 某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱某廠擬用火車裝運(yùn)甲、乙兩種貨物集裝箱，每箱的體積、重量、可獲利潤(rùn)以及裝運(yùn)所受限制如下：的體積、重量、可獲利

3、潤(rùn)以及裝運(yùn)所受限制如下：貨物集裝箱貨物集裝箱體積體積(米米3)重量重量(百斤百斤)利潤(rùn)利潤(rùn)(百元百元)甲甲5220乙乙4510 托運(yùn)限制托運(yùn)限制 2413 問兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？問兩種貨物各裝運(yùn)多少箱，可使獲得利潤(rùn)最大？返回 設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為設(shè)甲、乙兩種貨物裝運(yùn)箱數(shù)分別為x1和和x2。顯然，。顯然，x1、x2 都要求為整數(shù)都要求為整數(shù),于是可建立整數(shù)規(guī)劃模型如下：于是可建立整數(shù)規(guī)劃模型如下： Max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2為整數(shù)為整數(shù) (5) 是不是可通過把不考

4、慮整數(shù)要求求得的最優(yōu)解經(jīng)過是不是可通過把不考慮整數(shù)要求求得的最優(yōu)解經(jīng)過“化化整整”得到滿足整數(shù)要求的最優(yōu)解呢？得到滿足整數(shù)要求的最優(yōu)解呢？v容易求得相應(yīng)的線性規(guī)劃問題的最優(yōu)解為容易求得相應(yīng)的線性規(guī)劃問題的最優(yōu)解為 x1=4.8，x2=0，max z=96v現(xiàn)在來分析上述線性規(guī)劃問題的最優(yōu)解是否是整數(shù)規(guī)劃現(xiàn)在來分析上述線性規(guī)劃問題的最優(yōu)解是否是整數(shù)規(guī)劃問題的最優(yōu)解問題的最優(yōu)解因?yàn)橐驗(yàn)閤1表示的是托運(yùn)甲種貨物的箱數(shù)，目前得到的最表示的是托運(yùn)甲種貨物的箱數(shù)，目前得到的最優(yōu)解不是整數(shù)，所以不合條件的要求。優(yōu)解不是整數(shù)，所以不合條件的要求。是不是可以把所得的非整數(shù)最優(yōu)解經(jīng)過是不是可以把所得的非整數(shù)最優(yōu)解

5、經(jīng)過“化整化整”就可就可得到合于條件的整數(shù)最優(yōu)解呢得到合于條件的整數(shù)最優(yōu)解呢?o如將如將(x1=4.8，x2=0)湊整為湊整為(x1=5，x2=0)，這樣就破，這樣就破壞了條件壞了條件(關(guān)于體積的限制關(guān)于體積的限制)，因而它不是可行解；，因而它不是可行解；o如將如將(x1=4.8，x2=0)舍去尾數(shù)舍去尾數(shù)0.8，變?yōu)椋優(yōu)?x1=4，x2=0)，這當(dāng)然滿足各約束條件，因而是可行解，但不是最這當(dāng)然滿足各約束條件，因而是可行解，但不是最優(yōu)解，因?yàn)楫?dāng)優(yōu)解，因?yàn)楫?dāng)x1=4，x2=0, 時(shí)時(shí)z=80；而當(dāng)；而當(dāng)x1=4，x2=1(這也是可行解這也是可行解)時(shí)，時(shí)，z=90。 圖中畫圖中畫(+)號(hào)的點(diǎn)表

6、示可行的整數(shù)解。湊整得到的號(hào)的點(diǎn)表示可行的整數(shù)解。湊整得到的(5，0)點(diǎn)點(diǎn)不在可行域內(nèi)，而不在可行域內(nèi)，而C點(diǎn)又不合于條件。為了滿足題中要求，點(diǎn)又不合于條件。為了滿足題中要求，表示目標(biāo)函數(shù)的表示目標(biāo)函數(shù)的z的等值線必須向原點(diǎn)平行移動(dòng)，直到第一的等值線必須向原點(diǎn)平行移動(dòng)，直到第一次遇到帶次遇到帶“+”號(hào)號(hào)B點(diǎn)點(diǎn)(x1=4，x2=1)為止。這樣，為止。這樣，z的等值線就的等值線就由由z=96變到變到z=90，它們的差值為，它們的差值為z=96-90=6，表示利潤(rùn)的降，表示利潤(rùn)的降低，這是由于變量的不可分性低，這是由于變量的不可分性(裝箱裝箱)所引起的。所引起的。v由上例看出，將其相應(yīng)的線性規(guī)劃的最

7、優(yōu)解經(jīng)過由上例看出，將其相應(yīng)的線性規(guī)劃的最優(yōu)解經(jīng)過“化整化整”來解原整數(shù)線性規(guī)劃，雖是最容易想到的，來解原整數(shù)線性規(guī)劃，雖是最容易想到的，但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解，甚至根本不但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解，甚至根本不是可行解。因此有必要對(duì)整數(shù)線性規(guī)劃的解法進(jìn)行是可行解。因此有必要對(duì)整數(shù)線性規(guī)劃的解法進(jìn)行專門研究。專門研究。v在求解整數(shù)線性規(guī)劃時(shí)，如果可行域是有界的，首在求解整數(shù)線性規(guī)劃時(shí)，如果可行域是有界的，首先容易想到的方法就是窮舉所有可行的整數(shù)解，即先容易想到的方法就是窮舉所有可行的整數(shù)解，即列出圖中所有標(biāo)有列出圖中所有標(biāo)有“+ +”的整數(shù)點(diǎn)，然后比較它們的的整數(shù)點(diǎn)，然后比較它們

8、的目標(biāo)函數(shù)值，從而確定最優(yōu)解。目標(biāo)函數(shù)值，從而確定最優(yōu)解。v對(duì)于規(guī)模較小的問題，變量個(gè)數(shù)很少，可行解的組對(duì)于規(guī)模較小的問題，變量個(gè)數(shù)很少，可行解的組合數(shù)也較小時(shí)，這個(gè)方法是可行的，也是有效的。合數(shù)也較小時(shí)，這個(gè)方法是可行的，也是有效的。如在例如在例1 1中，變量只有中，變量只有x x1 1和和x x2 2。由條件，由條件，x x1 1所能所能取的整數(shù)值為取的整數(shù)值為0 0、1 1、2 2、3 3、4 4共共5 5個(gè)；由條件，個(gè)；由條件，x x2 2所能取的整數(shù)值為所能取的整數(shù)值為0 0、1 1、2 2共共3 3個(gè)。因此所有可個(gè)。因此所有可能的整數(shù)組合能的整數(shù)組合( (不都是可行的不都是可行的)

9、 )數(shù)是數(shù)是3 35=155=15個(gè)，個(gè)，窮舉法還是勉強(qiáng)可用的。窮舉法還是勉強(qiáng)可用的。v對(duì)于大型問題，可行的整數(shù)組合數(shù)會(huì)很大。對(duì)于大型問題，可行的整數(shù)組合數(shù)會(huì)很大。例如在指派問題中，將例如在指派問題中，將n項(xiàng)任務(wù)指派項(xiàng)任務(wù)指派n個(gè)人去完成，個(gè)人去完成，不同的指派方案共有不同的指派方案共有n!種，當(dāng)種，當(dāng)n=10時(shí)，可能的指時(shí)，可能的指派方案數(shù)超過派方案數(shù)超過300萬；當(dāng)萬；當(dāng)n=20，超過，超過21018。顯。顯然，窮舉法是不可取的。然，窮舉法是不可取的。v應(yīng)尋找僅檢查可行的整數(shù)組合的一部分，就能定出最應(yīng)尋找僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解的方法。分支定界解法就是其中之一。優(yōu)

10、的整數(shù)解的方法。分支定界解法就是其中之一。v分枝定界法可用于解純整數(shù)或混合整數(shù)線性規(guī)劃問題。分枝定界法可用于解純整數(shù)或混合整數(shù)線性規(guī)劃問題。20世紀(jì)世紀(jì)60年代初由年代初由Land Doig和和Dakin等提出，是解等提出，是解整數(shù)線性規(guī)劃的重要方法之一。整數(shù)線性規(guī)劃的重要方法之一。分枝定界法分枝定界法 繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為繼續(xù)求解定界，重復(fù)下去，直到得到最優(yōu)解為止止?；舅枷牖舅枷雟例例 求解問題求解問題A min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x1，x2整數(shù)例題演示例題演示v問題問題A對(duì)應(yīng)的松弛問題對(duì)應(yīng)的松弛問題B

11、 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20vB1 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x15 分枝分枝vB2 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 vB21 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23分枝分枝vB22 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x24 vB211 min z = -10 x1-

12、20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23 x17 分枝分枝vB212 min z = -10 x1-20 x2 5x1+8x260 x18 x24 x1，x20 x16 x23 x18 x1 5x16問題問題B的解為的解為:z0=-136 x1=5.6 x2=4問題問題B2為為:z1=-135x1=6.00 x2=3.75問題問題B1為為:z1=-130 x1=5.00 x2=4.00-136=Z*=-130-136=Z*=0-135=Z*=-130問題問題B21為為:z1=-132 x1=7.2 x2=3.00問題問題B22為為:無可無可行解行解x2 3x

13、24問題問題B211為為:z1=-130 x1=7.00 x2=3.00問題問題B212為為:z1=-130 x1=8.00 x2=2.50 x1 7x18-132=Z*=-130-130=Z*=-130分枝定界法一般步驟分枝定界法一般步驟問題問題(B)(B)無可行解，則無可行解，則(A)(A)也無可行解，停止；也無可行解，停止； 0-1型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種型整數(shù)規(guī)劃是整數(shù)規(guī)劃的一種特殊形式，它的變量特殊形式，它的變量xj僅取值僅取值0或或1。這。這種只能取種只能取0或或1的變量稱為的變量稱為0-1變量變量或或二二進(jìn)制變量。進(jìn)制變量。3.2 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃 例例：某公司擬在市東、

14、西、南三區(qū)建立門市部。擬：某公司擬在市東、西、南三區(qū)建立門市部。擬議中有議中有7個(gè)位置個(gè)位置Ai（i=1，2,7）可供選擇規(guī)定）可供選擇規(guī)定 在東區(qū)，由在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由在西區(qū)，由A4，A5，兩個(gè)點(diǎn)中至少選一個(gè)；，兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由在南區(qū)，由A6，A7，兩個(gè)點(diǎn)中至少選一個(gè)。，兩個(gè)點(diǎn)中至少選一個(gè)。 如果選擇如果選擇Ai點(diǎn)，設(shè)備投資估計(jì)為點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤(rùn)元，每年可獲利潤(rùn)ci元，但投資總額不能超過元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大？利潤(rùn)為最大？72101

15、，點(diǎn)點(diǎn)不不選選擇擇點(diǎn)點(diǎn)選選擇擇設(shè)設(shè) iAAxiii則該問題的則該問題的數(shù)學(xué)模型數(shù)學(xué)模型為：為： 71maxiiixcz2321 xxx154 xx72101，或或 ixi 176 xx 7iiiBxb 在整數(shù)規(guī)劃中，如果變量在整數(shù)規(guī)劃中，如果變量xi僅取僅取0或或1，這時(shí)變量，這時(shí)變量xi稱稱為為01變量，這時(shí)的整數(shù)規(guī)劃稱為變量，這時(shí)的整數(shù)規(guī)劃稱為01型整數(shù)規(guī)劃。型整數(shù)規(guī)劃。28 在本章開始的在本章開始的例例1中，關(guān)于運(yùn)貨的體積限制為中，關(guān)于運(yùn)貨的體積限制為 5x1+4x224 (1) 今設(shè)運(yùn)貨有車運(yùn)和船運(yùn)兩種方式，上面的條件系用車運(yùn)時(shí)今設(shè)運(yùn)貨有車運(yùn)和船運(yùn)兩種方式，上面的條件系用車運(yùn)時(shí)的限制條

16、件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為 7x1+3x245 (2) 這兩個(gè)條件是互相排斥的。為了統(tǒng)一在一個(gè)問題中，引入這兩個(gè)條件是互相排斥的。為了統(tǒng)一在一個(gè)問題中，引入0-1變量變量y，令，令當(dāng)采用車運(yùn)方式當(dāng)采用船運(yùn)方式, 0, 1y含有互斥約束條件的問題含有互斥約束條件的問題 Max z20 x1+10 x2 (1) 5x1+4x224 (2) 2x1+5x213 (3) x1,x20 (4) x1,x2為整數(shù)為整數(shù) (5)29 于是，于是，(1)式和式和(2)式可由下述條件式可由下述條件(3)式和式和(4)式來代替：式來代替： 5x1+4x224+yM

17、 (3) 7x1+3x245+(1 y)M (4) 其中其中M是充分大的數(shù)。是充分大的數(shù)。 可以驗(yàn)證可以驗(yàn)證: 當(dāng)當(dāng)y=0時(shí)，時(shí)，(3)式就是式就是(1)式，而式，而(4)式自然成立，因而是式自然成立，因而是多余的。當(dāng)多余的。當(dāng)y=1時(shí)，時(shí)，(4)式就是式就是(2)式，而式，而(3)式是多余的。式是多余的。 引入的變量引入的變量y不必出現(xiàn)在目標(biāo)函數(shù)內(nèi)，即認(rèn)為在目標(biāo)函不必出現(xiàn)在目標(biāo)函數(shù)內(nèi)，即認(rèn)為在目標(biāo)函數(shù)內(nèi)數(shù)內(nèi)y的系數(shù)為的系數(shù)為0。 30v如果有如果有m個(gè)互相排斥的約束條件個(gè)互相排斥的約束條件(型型)：i1x1+i2x2+inxnbi，i=1，2，,m 為了保證這為了保證這m個(gè)約束條件只有一個(gè)起

18、作用，我們引入個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)個(gè)0-1變量變量yi(i=1,2,，m)和一個(gè)充分大的常數(shù)和一個(gè)充分大的常數(shù)M，且，且下面這一組下面這一組m+1個(gè)約束條件個(gè)約束條件 i1x+i2x2+inxnbi+yiM i=1,2,，m (5) y1+y2+ym=m 1 (6) 就合乎上述的要求。這是因?yàn)?，由于就合乎上述的要求。這是因?yàn)?，由?6)式，式，m個(gè)個(gè)yi中中只有一個(gè)能取只有一個(gè)能取0值，設(shè)值，設(shè)yi*=0，代入，代入(5)式，就只有式，就只有i=i*這這個(gè)約束條件起作用，而別的式子都是多余的。個(gè)約束條件起作用，而別的式子都是多余的。 對(duì)于對(duì)于0-1型整數(shù)規(guī)劃，一般采用型整數(shù)規(guī)

19、劃，一般采用隱枚舉法隱枚舉法，而不必采，而不必采用完全枚舉法。包括用完全枚舉法。包括: (1)只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件只要發(fā)現(xiàn)某個(gè)變量組合不滿足其中一個(gè)約束條件時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。時(shí)，就不必再去檢驗(yàn)其他約束條件是否可行。 (2)若已發(fā)現(xiàn)一個(gè)可行解，則可根據(jù)它的目標(biāo)函數(shù)值若已發(fā)現(xiàn)一個(gè)可行解，則可根據(jù)它的目標(biāo)函數(shù)值產(chǎn)生一個(gè)過濾條件，對(duì)于目標(biāo)函數(shù)值比它差的變量組合產(chǎn)生一個(gè)過濾條件，對(duì)于目標(biāo)函數(shù)值比它差的變量組合就不必再去檢驗(yàn)它的可行性；在以后的求解中每當(dāng)發(fā)現(xiàn)就不必再去檢驗(yàn)它的可行性；在以后的求解中每當(dāng)發(fā)現(xiàn)更好的可行解就替換原來的過濾條件。更好的可行解就替換原來的

20、過濾條件。0-1型整數(shù)規(guī)劃的解法型整數(shù)規(guī)劃的解法 例例 : 用隱枚舉法求解下列用隱枚舉法求解下列01型整數(shù)規(guī)劃型整數(shù)規(guī)劃 106434422523max3213221321321321或或，xxxxxxxxxxxxxxxxz3)001(11 zX，增增加加一一個(gè)個(gè)約約束束條條件件：3523321 xxx該條件稱為過濾條件該條件稱為過濾條件解：解：先通過試探找一個(gè)可行解先通過試探找一個(gè)可行解，所有可能所有可能的可行解的可行解約束條件約束條件可行解可行解否否Z值值 (0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1) 0 5 -1 1 0

21、 1 5 -2 3 1 1 1 0 5 3 1 5 8 0 2 1 1 8 1 6 2 6 8*101* zX，所有可能所有可能的可行解的可行解約束條件約束條件可行解可行解否否Z值值 (0，0，0)(0，0，1)(0，1，0)(1，0，0)(0，1，1)(1，0，1)(1，1，0)(1，1，1) 0 5 -1 1 0 1 5 -2 3 3 8 0 2 1 1 8 1 6 8*101* zX， 0 0 0 0 0所有可能所有可能的可行解的可行解約束條件約束條件可行解可行解否否Z值值 (1，0，1)(1，1，1)(0，1，1)(1，0，0)(0，1，1)(1，1，0)(0，0，0)(0，1，0)

22、8 6 5 3 3 1 0 -2 8*101* zX， 0 2 1 1 836v注意注意： 一般常重新排列一般常重新排列xi的順序使目標(biāo)函數(shù)中的順序使目標(biāo)函數(shù)中xi的系數(shù)是遞增的系數(shù)是遞增(不不減減)的，在上例中，改寫的，在上例中，改寫 z=3x1 2x2+5x3= 2x2+3x1+5x3 因?yàn)橐驗(yàn)?2，3，5是遞增的序，變量是遞增的序，變量(x2，x1，x3)也按下述順也按下述順序取值：序取值：(0，0，0)，(0，0，1)，(0，1，0)，(0，1，1)， 這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。這樣，最優(yōu)解容易比較早的發(fā)現(xiàn)。 再結(jié)合過濾條件的改進(jìn)，更可使計(jì)算簡(jiǎn)化。再結(jié)合過濾條件的改進(jìn)，更可使計(jì)算簡(jiǎn)

23、化。37z=3x1 2x2+5x3= 2x2+3x1+5x3指派問題指派問題n指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型n匈牙利解法求解指派問題匈牙利解法求解指派問題 n一般的指派問題一般的指派問題 有有n項(xiàng)任務(wù)，恰好項(xiàng)任務(wù)，恰好n個(gè)人承擔(dān)，第個(gè)人承擔(dān)，第i人完成第人完成第j 項(xiàng)任務(wù)項(xiàng)任務(wù)的花費(fèi)的花費(fèi)(時(shí)間或費(fèi)用等時(shí)間或費(fèi)用等)為為cij，要求確定人和事之間的一要求確定人和事之間的一一對(duì)應(yīng)的指派方案，使總花費(fèi)最省？一對(duì)應(yīng)的指派方案，使總花費(fèi)最省？指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型 任務(wù)任務(wù) 人員人員 E J G R 甲甲 乙乙 丙丙 丁丁 2 10

24、9 7 15 4 14 8 13 14 16 11 4 15 13 9 例例4 有一份中文說明書，需譯成英、日、德、俄四種有一份中文說明書，需譯成英、日、德、俄四種文字。分別記作文字。分別記作E、J、G、R。現(xiàn)有甲、乙、丙、丁現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書翻譯成不同語種的說明書所四人，他們將中文說明書翻譯成不同語種的說明書所需時(shí)間如下表。問應(yīng)指派何人去完成何工作，使所需需時(shí)間如下表。問應(yīng)指派何人去完成何工作，使所需總時(shí)間最少？總時(shí)間最少？指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型指派問題的標(biāo)準(zhǔn)形式及其數(shù)學(xué)模型 指派問題的系數(shù)矩陣如下：指派問題的系數(shù)矩陣如下：nnnnnnnnjiccccccccc

25、cC212222111211)(Cij的含義可以不同，如費(fèi)用、成本、時(shí)間等。的含義可以不同，如費(fèi)用、成本、時(shí)間等。為建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入為建立標(biāo)準(zhǔn)指派問題的數(shù)學(xué)模型，引入nn個(gè)個(gè)0-1變量：變量：jix指派問題的數(shù)學(xué)模型可寫成如下形式：指派問題的數(shù)學(xué)模型可寫成如下形式：1若派第若派第i人做第人做第j事事0 若不派第若不派第i人做第人做第j事事 （ij=1，2,，n） ninjijijxczmin11 n),1,jn;,1,(i101 1n), 1( 111 或或ijnjijniijx)n,i(xjx 第第j項(xiàng)工作由項(xiàng)工作由一個(gè)人做一個(gè)人做第第i人做人做一項(xiàng)工作一項(xiàng)工作指派問題的每個(gè)

26、可行解，可用矩陣表示如下：指派問題的每個(gè)可行解，可用矩陣表示如下：nnnnnnnnjixxxxxxxxxxX212222111211)(矩陣矩陣X中，每行各元素中只有中，每行各元素中只有1個(gè)元素為個(gè)元素為1,其余各元素等其余各元素等0；每列各元素中也只有每列各元素中也只有1個(gè)元素為個(gè)元素為1,其余各元素等其余各元素等0 。指派問題有指派問題有n！個(gè)可行解。個(gè)可行解。匈牙利法解題步驟匈牙利法解題步驟 1955年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于年，庫(kù)恩利用匈牙利數(shù)學(xué)家康尼格的關(guān)于矩陣中獨(dú)立零元素的定理，提出了解指派問題的一矩陣中獨(dú)立零元素的定理，提出了解指派問題的一種算法，稱為匈牙利解法。種算法

27、，稱為匈牙利解法。 標(biāo)準(zhǔn)指派問題是一種特殊的整數(shù)規(guī)劃問題，又標(biāo)準(zhǔn)指派問題是一種特殊的整數(shù)規(guī)劃問題，又是特殊的是特殊的0-1規(guī)劃問題。規(guī)劃問題。 匈牙利解法的關(guān)鍵是利用了匈牙利解法的關(guān)鍵是利用了指派問題最優(yōu)解的如指派問題最優(yōu)解的如下性質(zhì)下性質(zhì)： 若從指派問題的系數(shù)矩陣若從指派問題的系數(shù)矩陣C的某行（或某列）各元的某行（或某列）各元素分別減去該行（或列）的最小元素素分別減去該行（或列）的最小元素，得到一個(gè)新的得到一個(gè)新的矩陣矩陣C，則以則以C和和C 為系數(shù)矩陣的兩個(gè)指派問題有相為系數(shù)矩陣的兩個(gè)指派問題有相同的最優(yōu)解。同的最優(yōu)解。 （系數(shù)矩陣的變化并不影響數(shù)學(xué)模型的約束方程（系數(shù)矩陣的變化并不影響數(shù)

28、學(xué)模型的約束方程組，而只是目標(biāo)函數(shù)值減少了常數(shù)組，而只是目標(biāo)函數(shù)值減少了常數(shù)k，所以最優(yōu)解不所以最優(yōu)解不變）變）匈牙利法匈牙利法-2-4-9-7 若某行若某行(列列)已有已有0元素，那就不必再減了。例元素，那就不必再減了。例1的計(jì)算為：的計(jì)算為： 9 11 8 7 13 16 14 9 15 14 4 104 13 15 2)c(ij2 4 1 04 7 5 011 10 0 62 11 13 01. 使系數(shù)矩陣各行、各列出現(xiàn)零元素使系數(shù)矩陣各行、各列出現(xiàn)零元素 作法：系數(shù)矩陣各行元素減去所在行的最小元素，再作法：系數(shù)矩陣各行元素減去所在行的最小元素，再?gòu)乃镁仃嚨母髁袦p去所在列最小元素。從所

29、得矩陣的各列減去所在列最小元素。(因一行中因一行中xij 取值取值一個(gè)一個(gè)1，其余為，其余為0，cij 同時(shí)減去一常數(shù)不影響同時(shí)減去一常數(shù)不影響xij取值取值)。匈牙利法解題步驟如下：匈牙利法解題步驟如下：2 4 1 04 7 5 011 10 0 62 11 13 0-4 -2 這就保證每行每列至少有一個(gè)這就保證每行每列至少有一個(gè)0元素，同時(shí)不出現(xiàn)元素，同時(shí)不出現(xiàn)負(fù)負(fù)元素元素。 2. 試求最優(yōu)解。試求最優(yōu)解。 0 0 1 0 2 3 5 0 9 6 0 6 0 7 13 0 作法：由獨(dú)立作法：由獨(dú)立0元素的行（列）開始，獨(dú)立元素的行（列）開始，獨(dú)立0元素處畫元素處畫 標(biāo)記標(biāo)記 ，在有，在有

30、的行列中劃去其它的行列中劃去其它0元素；再在剩余的元素；再在剩余的0元素中重復(fù)此做法，直至不能標(biāo)記元素中重復(fù)此做法，直至不能標(biāo)記 為止。為止。（1）當(dāng)遇到在所有的行和列中，）當(dāng)遇到在所有的行和列中，0元素都不止一個(gè)時(shí)（存在元素都不止一個(gè)時(shí)（存在0元素的閉回元素的閉回路），可任選其中一個(gè)路），可任選其中一個(gè)0元素加圈，同時(shí)劃去同行和同列中其他元素加圈，同時(shí)劃去同行和同列中其他0元素。元素。（2）如能找出）如能找出n個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的個(gè)位于不同行不同列的零元素，令對(duì)應(yīng)的xij= 1，其余其余xij = 0，得最優(yōu)解，結(jié)束；否則，看下面的例題轉(zhuǎn)第得最優(yōu)解，結(jié)束；否則，看下面的例題轉(zhuǎn)

31、第3步。步。 9 10 7 10 4 10 6 6 14 159 14 12 17 7 6 6 6 9 8 9 7 9 7 12 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0 2 0 5 7 6 7 6 4 例例 求表中所示效率矩陣的指派問題的最小解。求表中所示效率矩陣的指派問題的最小解。 任務(wù)任務(wù)人人ABCDE甲甲127979乙乙89666丙71712149丁15146610戊4107109經(jīng)行運(yùn)算即可得每行每列都有經(jīng)行運(yùn)算即可得每行每列都有0元素的系數(shù)矩陣。元素的系數(shù)矩陣。 5 6 3 6 04 0 0 8 92 7 5 10 00 0 0 3 22 0

32、 2 0 5再按上述步驟運(yùn)算，得到：再按上述步驟運(yùn)算，得到：所畫所畫 0元素少于元素少于n，未得到最優(yōu)解。未得到最優(yōu)解。 563604008927510000032202053. 作能覆蓋所有作能覆蓋所有0元素的最少直線數(shù)的直線集合元素的最少直線數(shù)的直線集合 (1) 對(duì)沒有對(duì)沒有 的行打的行打 號(hào)；號(hào)； (2) 對(duì)已打?qū)σ汛?號(hào)的行中所有號(hào)的行中所有0元素的所在列打元素的所在列打 號(hào)；號(hào)； (3) 再對(duì)打有再對(duì)打有 號(hào)的列中號(hào)的列中 0 元素的所在行打元素的所在行打 號(hào)；號(hào)； (4)重復(fù)重復(fù)(2),(3)直到得不出新的打直到得不出新的打 號(hào)的行號(hào)的行(列列)為止；為止； (5) 對(duì)沒有打?qū)]有

33、打 號(hào)的行畫一橫線，對(duì)打號(hào)的行畫一橫線，對(duì)打 號(hào)的列畫一號(hào)的列畫一 縱線，這就得到覆蓋所有縱線，這就得到覆蓋所有0元素的最少直線數(shù)元素的最少直線數(shù) 56360400892751000003220205 4.未被直線覆蓋的最小元素為未被直線覆蓋的最小元素為cij0,在在打打 號(hào)號(hào)行中各元素都行中各元素都減去減去cij0,打打 號(hào)號(hào)列中的各元素都加上列中的各元素都加上cij0。Cij=2 解為解為 3 4 1 4 0 4 0 0 8 110 5 3 8 0 0 0 0 3 4 2 0 2 0 7 5.返回步驟返回步驟2，重復(fù)上述步驟。，重復(fù)上述步驟。一般的指派問題一般的指派問題 在實(shí)際應(yīng)用中，常會(huì)

34、遇到各種非標(biāo)準(zhǔn)形式的指派問在實(shí)際應(yīng)用中，常會(huì)遇到各種非標(biāo)準(zhǔn)形式的指派問題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后題。通常的處理方法是先將它們轉(zhuǎn)化為標(biāo)準(zhǔn)形式，然后用匈牙利解法求解。用匈牙利解法求解。 最大化指派問題最大化指派問題 設(shè)最大化指派問題系數(shù)矩陣設(shè)最大化指派問題系數(shù)矩陣C中最大元素為中最大元素為m。令矩。令矩陣陣B=(bij)=(m-cij), 則以則以B為系數(shù)矩陣的最小化指派問題和為系數(shù)矩陣的最小化指派問題和以以C為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。為系數(shù)矩陣的原最大化指派問題有相同的最優(yōu)解。 人數(shù)和事數(shù)不等的指派問題人數(shù)和事數(shù)不等的指派問題 若人少事多，則添上一些虛擬的

35、若人少事多，則添上一些虛擬的“人人”。這些虛擬的。這些虛擬的人作各事的費(fèi)用系數(shù)可取人作各事的費(fèi)用系數(shù)可取0，理解為這些費(fèi)用實(shí)際上不會(huì)，理解為這些費(fèi)用實(shí)際上不會(huì)發(fā)生。若人多事少，則添上一些虛擬的發(fā)生。若人多事少，則添上一些虛擬的“事事”。這些虛。這些虛擬的事被各人做的費(fèi)用系數(shù)同樣也取擬的事被各人做的費(fèi)用系數(shù)同樣也取0。 一個(gè)人可做幾件事的指派問題一個(gè)人可做幾件事的指派問題 若某個(gè)人可做幾件事，則可將該人看做相同的幾個(gè)若某個(gè)人可做幾件事，則可將該人看做相同的幾個(gè)人來接受指派。這幾個(gè)人作同一件事的費(fèi)用系數(shù)當(dāng)然都人來接受指派。這幾個(gè)人作同一件事的費(fèi)用系數(shù)當(dāng)然都一樣。一樣。 某事一定不能由某人作的指派問

36、題某事一定不能由某人作的指派問題 若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系若某事一定不能由某個(gè)人做，則可將相應(yīng)的費(fèi)用系數(shù)取做足夠大的數(shù)數(shù)取做足夠大的數(shù)M。 例例 ：某大型工程有五個(gè)工程項(xiàng)目，決定向社會(huì)：某大型工程有五個(gè)工程項(xiàng)目，決定向社會(huì)公開招標(biāo)，建設(shè)公司公開招標(biāo)，建設(shè)公司A1，A2，A3參加招標(biāo)承建，根參加招標(biāo)承建，根據(jù)實(shí)際情況，可允許每家建設(shè)公司承建一項(xiàng)或二項(xiàng)工據(jù)實(shí)際情況，可允許每家建設(shè)公司承建一項(xiàng)或二項(xiàng)工程。求使總費(fèi)用最少的指派方案。程。求使總費(fèi)用最少的指派方案。 工程公司B1B2B3B4B5A14871512A279171410A36912873322117812967812961

37、0141797101417971215784121578454321AAAAAABBBBB上面的系數(shù)矩陣有上面的系數(shù)矩陣有6行行5列，為了使列，為了使“人人”和和“事事”的數(shù)目相同，引入的數(shù)目相同，引入一件虛擬的事一件虛擬的事B6，使之成為標(biāo)準(zhǔn)指派問題的系數(shù)矩陣：，使之成為標(biāo)準(zhǔn)指派問題的系數(shù)矩陣：解：由于每家建筑公司最多可以承建兩項(xiàng)，因此可把每家建筑公司看解：由于每家建筑公司最多可以承建兩項(xiàng)，因此可把每家建筑公司看成兩家建筑公司，其系數(shù)矩陣為成兩家建筑公司，其系數(shù)矩陣為332211078129607812960101417970101417970121578401215784654321AAA

38、AAABBBBBB然后，用匈牙利解法求解?？傻觅M(fèi)用最省為然后，用匈牙利解法求解。可得費(fèi)用最省為4+7+9+8+7=35（百萬元）（百萬元）v1. 用圖解法和單純形法求解線性規(guī)劃問題用圖解法和單純形法求解線性規(guī)劃問題 作業(yè)：作業(yè)：0,164826233. .3min212121212121xxxxxxxxxxtsxxzv2. 用單純形法求解線性規(guī)劃問題用單純形法求解線性規(guī)劃問題 0,1321731323. .43max3213213231321xxxxxxxxxxtsxxxzv3. 求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題 max z=3x1+2x2 2x1+3x214 2x1+x29 x1，x20 x

39、1，x2整數(shù) 4. 設(shè)有設(shè)有A、B、C、D四人去完成甲、乙、丙、丁四四人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，不同的人完成不同的任務(wù)時(shí)間不同，資料如下項(xiàng)任務(wù)，不同的人完成不同的任務(wù)時(shí)間不同，資料如下，求總時(shí)間最小的分配方案。，求總時(shí)間最小的分配方案。8 6 14 15 14 12 17 7 9 6 9 88 9 7 21)(ijcABCD 甲甲 乙乙 丙丙 丁丁 5. 設(shè)有設(shè)有A、B、C、D四人去完成甲、乙、丙、丁四四人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，不同的人完成不同的任務(wù)贏得不同，資料如下項(xiàng)任務(wù)，不同的人完成不同的任務(wù)贏得不同，資料如下，求總贏得最大的分配方案。，求總贏得最大的分配方案。4 8 3 9

40、9 11 8 78 7 10 68 5 6 4)(ijcABCD 甲甲 乙乙 丙丙 丁丁 6. 設(shè)有設(shè)有A、B、C、D、E五人去完成甲、乙、丙、丁五人去完成甲、乙、丙、丁四項(xiàng)任務(wù)，每人完成各項(xiàng)工作如表所示。規(guī)定每項(xiàng)工作四項(xiàng)任務(wù)，每人完成各項(xiàng)工作如表所示。規(guī)定每項(xiàng)工作只能有一個(gè)人去完成，每人最多承擔(dān)一項(xiàng)工作，又假定只能有一個(gè)人去完成，每人最多承擔(dān)一項(xiàng)工作，又假定D因某種原因決定不承擔(dān)丁項(xiàng)目，問應(yīng)該如何分配，才因某種原因決定不承擔(dān)丁項(xiàng)目，問應(yīng)該如何分配，才能使能使4項(xiàng)工作總得花費(fèi)時(shí)間最少？項(xiàng)工作總得花費(fèi)時(shí)間最少？8 6 13 15 2015 7 14 5 154 2 15 10 59 15 3 2

41、 01)(ijcA B C D E 甲甲 乙乙 丙丙 丁丁v例例 求解整數(shù)規(guī)劃問題求解整數(shù)規(guī)劃問題A max z=3x1+2x2 2x1+3x2 70 2x1+x270 x1，x20 x1，x2整數(shù) v解：先不考慮條件，即解相應(yīng)的線性規(guī)劃解：先不考慮條件，即解相應(yīng)的線性規(guī)劃B,(見見圖，得最優(yōu)解圖，得最優(yōu)解x1=4.81，x2=1.82，z0=356 可見它不符合整數(shù)條件。可見它不符合整數(shù)條件。這時(shí)這時(shí)z0是問題是問題A的最優(yōu)目標(biāo)函數(shù)值的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界，記作的上界，記作z0= 。而在而在x1=0，x2=0時(shí)，時(shí)，顯然是問題顯然是問題A的一個(gè)整數(shù)可行解，的一個(gè)整數(shù)可行解，這時(shí)這時(shí)z=0

42、，是，是z*的一個(gè)下界，的一個(gè)下界，記作記作 =0，即，即0z*356。zz分枝分枝 因?yàn)橐驗(yàn)?當(dāng)前均為非整數(shù)，故不滿足整數(shù)要求，當(dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個(gè)進(jìn)行分枝。設(shè)選任選一個(gè)進(jìn)行分枝。設(shè)選 進(jìn)行分枝，把可行集進(jìn)行分枝，把可行集分成分成2個(gè)子集：個(gè)子集： 因?yàn)橐驗(yàn)?與與5之間無整數(shù)，故這兩個(gè)子集內(nèi)的整數(shù)解之間無整數(shù)，故這兩個(gè)子集內(nèi)的整數(shù)解必與原可行集合整數(shù)解一致。這一步稱為分枝。必與原可行集合整數(shù)解一致。這一步稱為分枝。這兩個(gè)子集的規(guī)劃求解如下：這兩個(gè)子集的規(guī)劃求解如下：21,xx1x44.80921x514.80921x問題問題B1為為:Max z=40 x1+90 x2

43、9x1+7x256 7x1+20 x2 70 x1 4 x1,x20問題問題B2為為:Max z=40 x1+90 x2 9x1+7x256 7x1+20 x2 70 x1 5 x1,x2 068v x14，x15B1:z1=349 x1=4.00 x2=2.10B2:z2=341 x1=5.00 x2=1.5769v顯然，仍沒有得到全部變量是整數(shù)的解。因顯然，仍沒有得到全部變量是整數(shù)的解。因z1z2，故，故將將 改為改為349，那么必存在最優(yōu)整數(shù)解，得到，那么必存在最優(yōu)整數(shù)解，得到z*，并且，并且 0z*349v繼續(xù)對(duì)問題繼續(xù)對(duì)問題B1和和B2進(jìn)行分解。因進(jìn)行分解。因z1z2，故先分解，故先分解B1為為兩支。增加條件兩支。增加條件x22，稱為問題，稱為