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

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

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

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

4、得最優(yōu)解為：x1=4.8 x2=0 max z=96 但x1是托運(yùn)甲種貨物的箱數(shù)，現(xiàn)在它不是整數(shù)，所以不合條件的要求。 是不是可以把所得的非整數(shù)的最優(yōu)解經(jīng)過“化整”就可得到合于條件的整數(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)然滿足各約束條件，因而是可行解，但不是最優(yōu)解，因?yàn)楫?dāng)x1=4，x2=0, 時(shí)z=80。但當(dāng)x1=4，x2=1(這也是可行解)時(shí)，z=90。 圖中畫(+)號(hào)的點(diǎn)表示可行的整數(shù)解。湊整的(5，0)點(diǎn)不在可行域內(nèi)，

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

6、的點(diǎn)那樣，然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解。對(duì)于小型的問題，變量數(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ì)于大型問題，可行的整數(shù)組合數(shù)是很大的。 例如在本章第5節(jié)的指派問題(這也是整數(shù)線性規(guī)劃)中，將n項(xiàng)任務(wù)指派n個(gè)人去完成，不同的指派方案共有n!種，當(dāng)n=10，這個(gè)數(shù)就超過300萬；當(dāng)n=20，這個(gè)數(shù)就超過21018，如果一一計(jì)算，就是用每秒百萬次的計(jì)算機(jī)，也要幾萬年

7、的功夫，很明顯，解這樣的題，窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。 分支定界解法(branch and bound method)就是其中的一個(gè)。 分支定界法可用于解純整數(shù)或混合的整數(shù)線性規(guī)劃問題。在20世紀(jì)60年代初由Land Doig和Dakin等人提出。由于這方法靈活且便于用計(jì)算機(jī)求解，所以現(xiàn)在它已是解整數(shù)線性規(guī)劃的重要方法。 設(shè)有最大化的整數(shù)線性規(guī)劃問題A，與它相應(yīng)的線性規(guī)劃為問題B，從解問題B開始，若其最優(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ū)域(稱為分支)的方法，逐步減小和增大，最終求到z*。例 2 求解A max z=40 x1+90 x2 9x1+ 7x256 7x1+20 x270 (5.2) x1，x20 x1，x2整數(shù) 解解 先不考慮條件，即解相應(yīng)的線性規(guī)劃B,(見圖5-2)，得最優(yōu)解x1=4.81，x2=1.82，z0=356 可見它不符合整數(shù)條件。這時(shí)z0是問題A的最優(yōu)目標(biāo)函數(shù)值z(mì)*的上界，記作z0= 。而在x1=0，x2=0時(shí)，顯然是問題A的一個(gè)整數(shù)可行解，這時(shí)z=0，是z*的一個(gè)下界，記作 =0，即0z*356zz分支定界法的解法 首先注意其中一個(gè)非整數(shù)變量的解，如x1，在問題B的解

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

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