第5章 整數(shù)線(xiàn)性規(guī)劃-第1,2節(jié)

1、第5章 整數(shù)線(xiàn)性規(guī)劃 第1節(jié) 整數(shù)線(xiàn)性規(guī)劃問(wèn)題的提出 第2節(jié) 分支定界解法 第3節(jié) 割平面解法 第4節(jié) 0-1型整數(shù)線(xiàn)性規(guī)劃 第5節(jié) 指派問(wèn)題第1節(jié) 整數(shù)線(xiàn)性規(guī)劃問(wèn)題的提出 在前面討論的線(xiàn)性規(guī)劃問(wèn)題中，有些最優(yōu)解可能是分?jǐn)?shù)或小數(shù)，但對(duì)于某些具體問(wèn)題，常有要求解答必須是整數(shù)的情形(整數(shù)解)。 例如，所求解是機(jī)器的臺(tái)數(shù)、完成工作的人數(shù)或裝貨的車(chē)數(shù)等，分?jǐn)?shù)或小數(shù)的解答就不合要求。 為了滿(mǎn)足整數(shù)解的要求，初看起來(lái)，似乎只要把已得到的帶有分?jǐn)?shù)或小數(shù)的解經(jīng)過(guò)“舍入化整”就可以了。但這常常是不行的，因?yàn)榛蟛灰?jiàn)得是可行解；或雖是可行解，但不一定是最優(yōu)解。 因此，對(duì)求最優(yōu)整數(shù)解的問(wèn)題，有必要另行研究。我們稱(chēng)

2、這樣的問(wèn)題為整數(shù)線(xiàn)性規(guī)劃(integer linear programming)，簡(jiǎn)稱(chēng)ILP，整數(shù)線(xiàn)性規(guī)劃是最近幾十年來(lái)發(fā)展起來(lái)的規(guī)劃論中的一個(gè)分支。 整數(shù)線(xiàn)性規(guī)劃中如果所有的變數(shù)都限制為(非負(fù))整數(shù)，就稱(chēng)為純整數(shù)線(xiàn)性規(guī)劃(pure integer linear programming)或稱(chēng)為全整數(shù)線(xiàn)性規(guī)劃(all integer linear programming)；如果僅一部分變數(shù)限制為整數(shù)，則稱(chēng)為混合整數(shù)計(jì)劃(mixed integer linear programming)。 整數(shù)線(xiàn)性規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變數(shù)取值僅限于0或1。本章最后講到的指派問(wèn)題就是一個(gè)0-1規(guī)劃問(wèn)

3、題。 現(xiàn)舉例說(shuō)明用前述單純形法求得的解不能保證是整數(shù)最優(yōu)解。 例1：某廠(chǎng)擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤(rùn)以及托運(yùn)所受限制如表5-1所示。問(wèn)兩種貨物各托運(yùn)多少箱，可使獲得利潤(rùn)為最大? 表5-1 現(xiàn)在我們解這個(gè)問(wèn)題，設(shè)x1，x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)(當(dāng)然都是非負(fù)整數(shù))。 這是一個(gè)(純)整數(shù)線(xiàn)性規(guī)劃問(wèn)題，用數(shù)學(xué)式可表示為：max z =20 x1+10 x2 5x1+4x224 2x1+5x213 (5.1) x1，x20 x1，x2整數(shù) 它和線(xiàn)性規(guī)劃問(wèn)題的區(qū)別僅在于最后的條件?，F(xiàn)在我們暫不考慮這一條件，即解(以后我們稱(chēng)這樣的問(wèn)題為與原問(wèn)題相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題)很容易求

4、得最優(yōu)解為：x1=4.8 x2=0 max z=96 但x1是托運(yùn)甲種貨物的箱數(shù)，現(xiàn)在它不是整數(shù)，所以不合條件的要求。 是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過(guò)“化整”就可得到合于條件的整數(shù)最優(yōu)解呢? 如將(x1=4.8，x2=0)湊整為(x1=5，x2=0)，這樣就破壞了條件(關(guān)于體積的限制)，因而它不是可行解； 如將(x1=4.8，x2=0)舍去尾數(shù)0.8，變?yōu)?x1=4，x2=0)，這當(dāng)然滿(mǎn)足各約束條件，因而是可行解，但不是最優(yōu)解，因?yàn)楫?dāng)x1=4，x2=0, 時(shí)z=80。但當(dāng)x1=4，x2=1(這也是可行解)時(shí)，z=90。 圖中畫(huà)(+)號(hào)的點(diǎn)表示可行的整數(shù)解。湊整的(5，0)點(diǎn)不在可行域內(nèi)，

5、而C點(diǎn)又不合于條件。為了滿(mǎn)足題中要求，表示目標(biāo)函數(shù)的z的等值線(xiàn)必須向原點(diǎn)平行移動(dòng)，直到第一次遇到帶“+”號(hào)B點(diǎn)(x1=4，x2=1)為止。 這樣，z的等值線(xiàn)就由z=96變到z=90，它們的差值z(mì)=96-90=6 表示利潤(rùn)的降低，這是由于變量的不可分性(裝箱)所引起的。 由上例看出，將其相應(yīng)的線(xiàn)性規(guī)劃的最優(yōu)解“化整”來(lái)解原整數(shù)線(xiàn)性規(guī)劃，雖是最容易想到的，但常常得不到整數(shù)線(xiàn)性規(guī)劃的最優(yōu)解，甚至根本不是可行解。因此有必要對(duì)整數(shù)線(xiàn)性規(guī)劃的解法進(jìn)行專(zhuān)門(mén)研究。第2節(jié) 分支定界解法 在求解整數(shù)線(xiàn)性規(guī)劃時(shí)，如果可行域是有界的，首先容易想到的方法就是窮舉變量的所有可行的整數(shù)組合，就像在圖5-1中畫(huà)出所有“+”號(hào)

6、的點(diǎn)那樣，然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解。對(duì)于小型的問(wèn)題，變量數(shù)很少，可行的整數(shù)組合數(shù)也是很小時(shí)，這個(gè)方法是可行的，也是有效的。 在例1中，變量只有x1和x2 由條件，x1所能取的整數(shù)值為0、1、2、3、4共5個(gè)；由條件，x2所能取的整數(shù)值為0、1、2共3個(gè)；它的組合(不都是可行的)數(shù)是35=15個(gè)，窮舉法還是勉強(qiáng)可用的。 對(duì)于大型問(wèn)題，可行的整數(shù)組合數(shù)是很大的。 例如在本章第5節(jié)的指派問(wèn)題(這也是整數(shù)線(xiàn)性規(guī)劃)中，將n項(xiàng)任務(wù)指派n個(gè)人去完成，不同的指派方案共有n!種，當(dāng)n=10，這個(gè)數(shù)就超過(guò)300萬(wàn)；當(dāng)n=20，這個(gè)數(shù)就超過(guò)21018，如果一一計(jì)算，就是用每秒百萬(wàn)次的計(jì)算機(jī)，也要幾萬(wàn)年

7、的功夫，很明顯，解這樣的題，窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。 分支定界解法(branch and bound method)就是其中的一個(gè)。 分支定界法可用于解純整數(shù)或混合的整數(shù)線(xiàn)性規(guī)劃問(wèn)題。在20世紀(jì)60年代初由Land Doig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)線(xiàn)性規(guī)劃的重要方法。 設(shè)有最大化的整數(shù)線(xiàn)性規(guī)劃問(wèn)題A，與它相應(yīng)的線(xiàn)性規(guī)劃為問(wèn)題B，從解問(wèn)題B開(kāi)始，若其最優(yōu)解不符合A的整數(shù)條件，那么B的最優(yōu)目標(biāo)函數(shù)必是A的最優(yōu)目標(biāo)函數(shù)z*的上界；而A的任意可行解的目標(biāo)函數(shù)值將是z*的一個(gè)下界。分支

8、定界法就是將B的可行域分成子區(qū)域(稱(chēng)為分支)的方法，逐步減小和增大，最終求到z*。例 2 求解A max z=40 x1+90 x2 9x1+ 7x256 7x1+20 x270 (5.2) x1，x20 x1，x2整數(shù) 解解 先不考慮條件，即解相應(yīng)的線(xiàn)性規(guī)劃B,(見(jiàn)圖5-2)，得最優(yōu)解x1=4.81，x2=1.82，z0=356 可見(jiàn)它不符合整數(shù)條件。這時(shí)z0是問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界，記作z0= 。而在x1=0，x2=0時(shí)，顯然是問(wèn)題A的一個(gè)整數(shù)可行解，這時(shí)z=0，是z*的一個(gè)下界，記作 =0，即0z*356zz分支定界法的解法 首先注意其中一個(gè)非整數(shù)變量的解，如x1，在問(wèn)題B的解

9、中x1=4.81。于是對(duì)原問(wèn)題增加兩個(gè)約束條件x14，x15。 可將原問(wèn)題分解為兩個(gè)子問(wèn)題B1和B2(即兩支)，給每支增加一個(gè)約束條件，如圖5-3所示。 這并不影響問(wèn)題A的可行域，不考慮整數(shù)條件解問(wèn)題B1和B2，稱(chēng)此為第一次迭代。圖5-3 x14，x15 得到最優(yōu)解為： 顯然沒(méi)有得到全部變量是整數(shù)的解。 因z1z2，故將 改為349，那么必存在最優(yōu)整數(shù)解，得到z*，并且0z*349z繼續(xù)對(duì)問(wèn)題B1和B2進(jìn)行分解 因z1z2，故先分解B1為兩支。增加條件x22者，稱(chēng)為問(wèn)題B3；增加條件x23者稱(chēng)為問(wèn)題B4。在圖5-3中再舍去x22與x33之間的可行域， 再進(jìn)行第二次迭代。繼續(xù)對(duì)問(wèn)題B2進(jìn)行分解

10、圖5-4 解題的過(guò)程都列在圖5-4中。 從以上解題過(guò)程可得到，用分支定界法求解整數(shù)線(xiàn)性規(guī)劃（最大化）問(wèn)題的步驟為： 將要求解的整數(shù)線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題A， 將與它相應(yīng)的線(xiàn)性規(guī)劃問(wèn)題稱(chēng)為問(wèn)題B。 (1)解問(wèn)題B，可能得到以下情況： B沒(méi)有可行解，這時(shí)A沒(méi)有可行解，停止。 B有最優(yōu)解，并符合問(wèn)題A的整數(shù)條件，B的最優(yōu)解即為A的最優(yōu)解，停止。 B有最優(yōu)解，但不符合問(wèn)題A的整數(shù)條件，記它的目標(biāo)函數(shù)值為0z(2) 用觀察法找問(wèn)題A的一個(gè)整數(shù)可行解，一般可取xj=0，j=1,n，試探，求得其目標(biāo)函數(shù)值，并記作 。 以z*表示問(wèn)題A的最優(yōu)目標(biāo)函數(shù)值； 這時(shí)有zzzz*進(jìn)行迭代第一步：分支定界 分支 在B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以bj表示小于bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件xjbj和 xjbj+ 1 將這兩個(gè)約束條件，分別加入問(wèn)題B，求兩個(gè)后繼規(guī)劃問(wèn)題B1和B2。 不考慮整數(shù)條件求解這兩個(gè)后繼問(wèn)題。 定界 以每個(gè)后繼問(wèn)題為一分支標(biāo)明求解的結(jié)果，與其他問(wèn)題的解的結(jié)果中，找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界。 從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為新的下界，若無(wú)可行解， 0z第二步：比較與剪支 各分支的最優(yōu)目標(biāo)函數(shù)中若