《運(yùn)籌學(xué)課件：第5章 整數(shù)線性規(guī)劃-第1-4節(jié)》由會(huì)員分享，可在線閱讀，更多相關(guān)《運(yùn)籌學(xué)課件：第5章 整數(shù)線性規(guī)劃-第1-4節(jié)（66頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

2、可以了。但這常常是不行的，因?yàn)榛蟛灰姷檬强尚薪?；或雖是可行解，但不一定是最優(yōu)解。因此，對求最優(yōu)整數(shù)解的問題，有必要另行研究。我們稱這樣的問題為整數(shù)線性規(guī)劃(integerlinearprogramming)，簡稱ILP，整數(shù)線性規(guī)劃是最近幾十年來發(fā)展起來的規(guī)劃論中的一個(gè)分支。 整數(shù)線性規(guī)劃中如果所有的變數(shù)都限制為(非負(fù))整數(shù)，就稱為純整數(shù)線性規(guī)劃(pureintegerlinearprogramming)或稱為全整數(shù)線性規(guī)劃(allintegerlinearprogramming)；如果僅一部分變數(shù)限制為整數(shù)，則稱為混合整數(shù)計(jì)劃(mixedintegerlinearprogramming)

3、。整數(shù)線性規(guī)劃的一種特殊情形是0-1規(guī)劃，它的變數(shù)取值僅限于0或1。本章最后講到的指派問題就是一個(gè)0-1規(guī)劃問題。 現(xiàn)舉例說明用前述單純形法求得的解不能保證是整數(shù)最優(yōu)解。例1某廠擬用集裝箱托運(yùn)甲乙兩種貨物，每箱的體積、重量、可獲利潤以及托運(yùn)所受限制如表5-1所示。問兩種貨物各托運(yùn)多少箱，可使獲得利潤為最大?表5-1貨物 體積(m3/箱) 重量(100kg/箱) 利潤(100 元/箱) 甲 乙 5 4 2 5 20 10 托運(yùn)限制 24m3 1300kg 現(xiàn)在我們解這個(gè)問題，設(shè)x1，x2分別為甲、乙兩種貨物的托運(yùn)箱數(shù)(當(dāng)然都是非負(fù)整數(shù))。這是一個(gè)(純)整數(shù)線性規(guī)劃問題，用數(shù)學(xué)式可表示為： max

4、 z =20 x1+10 x2 5x1+4x224 2x1+5x213 (5.1) x1，x20 x1，x2整數(shù) 它和線性規(guī)劃問題的區(qū)別僅在于最后的條件?，F(xiàn)在我們暫不考慮這一條件，即解(以后我們稱這樣的問題為與原問題相應(yīng)的線性規(guī)劃問題)，很容易求得最優(yōu)解為:x1=4.8，x2=0，maxz=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，變

5、為(x1=4，x2=0)，這當(dāng)然滿足各約束條件，因而是可行解，但不是最優(yōu)解，因?yàn)楫?dāng)x1=4，x2=0,時(shí)z=80. 非整數(shù)的最優(yōu)解在C(4.8，0)點(diǎn)達(dá)到。但當(dāng)x1=4，x2=1(這也是可行解)時(shí)，z=90。本例還可以用圖解法來說明。見圖 5-1 圖中畫(+)號的點(diǎn)表示可行的整數(shù)解。湊整的(5，0)點(diǎn)不在可行域內(nèi)，而C點(diǎn)又不合于條件。為了滿足題中要求，表示目標(biāo)函數(shù)的z的等值線必須向原點(diǎn)平行移動(dòng)，直到第一次遇到帶“+”號B點(diǎn)(x1=4，x2=1)為止。這樣，z的等值線就由z=96變到z=90，它們的差值 z=96-90=6 表示利潤的降低，這是由于變量的不可分性(裝箱)所引起的。 由上例看出，將

6、其相應(yīng)的線性規(guī)劃的最優(yōu)解“化整”來解原整數(shù)線性規(guī)劃，雖是最容易想到的，但常常得不到整數(shù)線性規(guī)劃的最優(yōu)解，甚至根本不是可行解。因此有必要對整數(shù)線性規(guī)劃的解法進(jìn)行專門研究。第第2節(jié)節(jié) 分支定界解法分支定界解法 在求解整數(shù)線性規(guī)劃時(shí)，如果可行域是有界的，首先容易想到的方法就是窮舉變量的所有可行的整數(shù)組合，就像在圖5-1中畫出所有“+”號的點(diǎn)那樣，然后比較它們的目標(biāo)函數(shù)值以定出最優(yōu)解。對于小型的問題，變量數(shù)很少，可行的整數(shù)組合數(shù)也是很小時(shí)，這個(gè)方法是可行的，也是有效的。在例1中，變量只有x1和x2 由條件，x1所能取的整數(shù)值為0、1、2、3、4共5個(gè)；由條件，x2所能取的整數(shù)值為0、1、2共3個(gè)，它的

7、組合(不都是可行的)數(shù)是35=15個(gè)，窮舉法還是勉強(qiáng)可用的。對于大型的問題，可行的整數(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ī)，也要幾萬年的功夫，很明顯，解這樣的題，窮舉法是不可取的。所以我們的方法一般應(yīng)是僅檢查可行的整數(shù)組合的一部分，就能定出最優(yōu)的整數(shù)解。分支定界解法(branch and bound method)就是其中的一個(gè). 分支定界法可用于解純整數(shù)或混合的整數(shù)線性規(guī)劃問題。在20世紀(jì)60年代初由

8、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è)下界。分支定界法就是將B的可行域分成子區(qū)域(稱為分支)的方法，逐步減小和增大，最終求到z*?，F(xiàn)用下例來說明：例 2 求解A max z=40 x1+90 x2 9x1+7x256 7x1+20 x270 (5.2) x1，x20 x1，x2整數(shù) 解解 先不考慮條件，即解相應(yīng)的線性

9、規(guī)劃B,(見圖5-2)，得最優(yōu)解x1=4.81，x2=1.82，z0=356 可見它不符合整數(shù)條件。這時(shí)z0是問題A的最優(yōu)目標(biāo)函數(shù)值z*的上界，記作z0= 。而在x1=0，x2=0時(shí)，顯然是問題A的一個(gè)整數(shù)可行解，這時(shí)z=0，是z*的一個(gè)下界，記作 =0，即0z*356。zzzzz分支定界法的解法 首先注意其中一個(gè)非整數(shù)變量的解，如x1，在問題B的解中x1=4.81。于是對原問題增加兩個(gè)約束條件x14，x15 可將原問題分解為兩個(gè)子問題B1和B2(即兩支)， 給每支增加一個(gè)約束條件，如圖5-3所示。這并不影響問題A的可行域，不考慮整數(shù)條件解問題B1和B2，稱此為第一次迭代。得到最優(yōu)解為：問題

10、B1 問題 B2 z1=349 x1=4.00 x2=2.10 z2=341 x1=5.00 x2=1.57 圖5-3 x14，x15 顯然沒有得到全部變量是整數(shù)的解。因z1z2，故將 改為349，那么必存在最優(yōu)整數(shù)解，得到z*，并且0z*349z繼續(xù)對問題B1和B2進(jìn)行分解 因z1z2，故先分解B1為兩支。增加條件x22者，稱為問題B3；增加條件x23者稱為問題B4。在圖5-3中再舍去x22與x33之間的可行域， 再進(jìn)行第二次迭代。繼續(xù)對問題B2進(jìn)行分解 解題的過程都列在圖5-4中。 圖5-4從以上解題過程可得到，用分支定界法求解整數(shù)線性規(guī)劃(最大化)問題的步驟為： 將要求解的整數(shù)線性規(guī)劃問

11、題稱為問題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í)有z_*zzz進(jìn)行迭代 第一步：分支，在B的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量xj，其值為bj，以bj表示小于bj的最大整數(shù)。構(gòu)造兩個(gè)約束條件 xjbj和xjbj+1 將這兩個(gè)約束條件

12、，分別加入問題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ù)中若有小于 者，則剪掉這支(用打表示)，即以后不再考慮了。若大于 ，且不符合整數(shù)條件，則重復(fù)第一步驟。一直到最后得到z*為止，得最優(yōu)整數(shù)解xj*，j=1，n。 用分支定界法可解純整數(shù)線性規(guī)劃問題和混合整數(shù)線性規(guī)劃問題。它比窮舉法優(yōu)越。因?yàn)樗鼉H在一部分可行解的整數(shù)解中尋求最優(yōu)解，計(jì)算量比窮舉

13、法小。若變量數(shù)目很大，其計(jì)算工作量也是相當(dāng)可觀的。zz第第3節(jié)節(jié) 割平面解法割平面解法 整數(shù)線性規(guī)劃問題的可行域是整數(shù)點(diǎn)集（或稱格點(diǎn)集），割平面解法的思路是：首先不考慮變量xi是整數(shù)這一條件，仍然是用解線性規(guī)劃的方法去解整數(shù)線性規(guī)劃問題，若得到非整數(shù)的最優(yōu)解，然后增加能割去非整數(shù)解的線性約束條件(或稱為割平面)使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒有切割掉任何整數(shù)可行解。這個(gè)方法就是指出怎樣找到適當(dāng)?shù)母钇矫?不見得一次就找到)，使切割后最終得到這樣的可行域，它的一個(gè)有整數(shù)坐標(biāo)的極點(diǎn)恰好是問題的最優(yōu)解。這個(gè)方法是R.E.Gomory提出來的，所以又稱為Gomory的割平面法。以

14、下只討論純整數(shù)線性規(guī)劃的情形，現(xiàn)舉例說明。例例3 3 求解 目標(biāo)函數(shù) max z=x1+x2 約束條件： -x1+x21 3x1+x24 (5-3) x1，x20 x1，x2 整數(shù) 如不考慮條件，容易求得相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=34，x2=74，maxz=104 它就是圖5-5中域R的極點(diǎn)A，但不合于整數(shù)條件?，F(xiàn)設(shè)想，如能找到像CD那樣的直線去切割域R(圖5-6)，去掉三角形域ACD，那么具有整數(shù)坐標(biāo)的C點(diǎn)(1，1)就是域R的一個(gè)極點(diǎn)， 如在域R上求解，而得到的最優(yōu)解又恰巧在C點(diǎn)就得到原問題的整數(shù)解，所以解法的關(guān)鍵就是怎樣構(gòu)造一個(gè)這樣的“割平面”CD，盡管它可能不是唯一的，也可能不是一步

15、能求到的。下面仍就本例說明： 在原問題的前兩個(gè)不等式中增加非負(fù)松弛變量x3、x4，使兩式變成等式約束： -x1+x2+x3=1 3x1+x2+x4=4不考慮條件，用單純形表解題，見表5-2。表5-2cj 1 1 0 0 CB XB b x1 x2 x3 x4 0 0 x3 x4 1 4 -1 3 1 1 1 0 0 1 初始計(jì)算表 cj-zj 0 1 1 0 0 1 1 x1 x2 3/4 7/4 1 0 0 1 -1/4 3/4 1/4 1/5 最終計(jì)算表 cj-zj -5/2 0 0 -1/2 -1/2 從表5-2的最終計(jì)算表中，得到非整數(shù)的最優(yōu)解：x1=3/4，x2=7/4，x3=x4=

16、0，max z=5/2不能滿足整數(shù)最優(yōu)解的要求。為此考慮將帶有分?jǐn)?shù)的最優(yōu)解的可行域中分?jǐn)?shù)部分割去，再求最優(yōu)解。就可以得到整數(shù)的最優(yōu)解?？蓮淖罱K計(jì)算表中得到非整數(shù)變量對應(yīng)的關(guān)系式：474143434141432431xxxxxx為了得到整數(shù)最優(yōu)解。將上式變量的系數(shù)和常數(shù)項(xiàng)都分解成整數(shù)和非負(fù)真分?jǐn)?shù)兩部分之和 (1+0)x1+(-1+3/4)x3+1/4x4=0+3/4 x2+(3/4)x3+(1/4)x4=1+3/4 然后將整數(shù)部分與分?jǐn)?shù)部分分開，移到等式左右兩邊，得到：43243314143431414343xxxxxxx現(xiàn)考慮整數(shù)條件 要求x1、x2都是非負(fù)整數(shù)，于是由條件、可知x3、x4也都

17、是非負(fù)整數(shù),這一點(diǎn)對以下推導(dǎo)是必要的，如不都是整數(shù)，則應(yīng)在引入x3、x4之前乘以適當(dāng)常數(shù)，使之都是整數(shù)。在上式中(其實(shí)只考慮一式即可)從等式左邊看是整數(shù)；等式右邊也應(yīng)是整數(shù)。但在等式右邊的()內(nèi)是正數(shù)；所以等式右邊必是非正數(shù)。就是說，右邊的整數(shù)值最大是零。于是整數(shù)條件可由下式所代替；041434343xx 即 -3x3-x4-3 這就得到一個(gè)切割方程(或稱為切割約束)，將它作為增加約束條件，再解例3。 引入松弛變量x5，得到等式 -3x3-x4+x5=-3 將這新的約束方程加到表5-2的最終計(jì)算表，得表5-3。041434343xx表5-3 cj 1 1 0 0 0 CB XB b x1 x2

18、 x3 x4 x5 1 1 0 x1 x2 x5 3/4 7/4 -3 1 0 0 0 1 0 -1/4 3/4 -3 1/4 1/4 -1 0 0 1 cj-zj -5/2 0 0 -1/2 -1/2 0 從表5-3的b列中可看到，這時(shí)得到的是非可行解，于是需要用對偶單純形法繼續(xù)進(jìn)行計(jì)算 選擇x5為換出變量，計(jì)算61121,321min0minljljjjjaazc將x3做為換入變量，再按原單純形法進(jìn)行迭代，得表5-4。 cj 1 1 0 0 0 CB XB b x1 x2 x3 x4 x5 1 1 0 x1 x2 x3 1 1 1 1 0 0 0 1 0 0 0 1 1/3 0 1/3 -

19、1/12 1/4 -1/3 cj-zj 2 0 0 0 -1/3 -1/6 由于 x1、x2的值已都是整數(shù)，解題已完成。 注意：新得到的約束條件 -3x3-x4-3 如用x1、x2表示，由、式得 3(1+x1-x2)+(4-3x1-x2)3 x21 這就是(x1，x2)平面內(nèi)形成新的可行域，即包括平行于x1軸的直線x2=1和這直線下的可行區(qū)域，整數(shù)點(diǎn)也在其中，沒有切割掉。直觀地表示在圖5-7中。但從解題過程來看，這一步是不必要的。圖5-7現(xiàn)把求一個(gè)切割方程的步驟歸納為：(1) 令xi是相應(yīng)線性規(guī)劃最優(yōu)解中為分?jǐn)?shù)值的一個(gè)基變量，由單純形表的最終表得到kikikibxax)45(其中iQ(Q指構(gòu)成

20、基變量號碼的集合)K kK(K指構(gòu)成非基變量號碼的集合)(2) 將bi和ik都分解成整數(shù)部分N與非負(fù)真分?jǐn)?shù)f之和，即 bi=Ni+fi，其中0fi1 ik=Nik+fik，其中0fik1 (5-5) 而N表示不超過b的最大整數(shù)。例如： 若b=2.35，則N=2，f=0.35 若b=-0.45，則N=-1,f=0.55 代入(5-4)式得kkkikiikikixffNxNx)65(3) 現(xiàn)在提出變量(包括松弛變量，參閱例3的注)為整數(shù)的條件(當(dāng)然還有非負(fù)的條件). 這時(shí)，上式由左邊看必須是整數(shù)，但由右邊看，因?yàn)?fi1，所以不能為正，即kkikixff)75(0這就是一個(gè)切割方程。 由(5-4)

21、式，(5-6)式，(5-7)式可知： 切割方程(5-7)式真正進(jìn)行了切割，至少把非整數(shù)最優(yōu)解這一點(diǎn)割掉了。 沒有割掉整數(shù)解，這是因?yàn)橄鄳?yīng)的線性規(guī)劃的任意整數(shù)可行解都滿足(5-7)式的緣故。第第4節(jié)節(jié) 0-1型整數(shù)線性規(guī)劃型整數(shù)線性規(guī)劃 0-1型整數(shù)線性規(guī)劃是整數(shù)線性規(guī)劃中的特殊情形，它的變量xi僅取值0或1。這時(shí)xi稱為0-1變量，或稱二進(jìn)制變量.xi僅取值0或1這個(gè)條件可由下述約束條件所代替。xi1,xi0，整數(shù) 它和一般整數(shù)線性規(guī)劃的約束條件形式是一致的。在實(shí)際問題中，如果引入0-1變量，就可以把有各種情況需要分別討論的線性規(guī)劃問題統(tǒng)一在一個(gè)問題中討論了。在本節(jié)我們先介紹引入0-1變量的實(shí)

22、際問題，再研究解法。注： 如果變量xi不是僅取值0或1，而是可取其他范圍的非負(fù)整數(shù)，這時(shí)可利用二進(jìn)制的記數(shù)法將它用若干個(gè)0-1變量來代替。例如，在給定的問題中，變量x可任取0與10之間的任意整數(shù)時(shí)，令x=20 x0+21x1+22x2+23x3. 這時(shí)，x就可用4個(gè)0-1變量x0，x1，x2，x3來代替。4.1引入0-1變量的實(shí)際問題1.投資場所的選定相互排斥的計(jì)劃例例4某公司擬在市東、西、南三區(qū)建立門市部。擬議中有7個(gè)位置(點(diǎn))Ai(i=1，2，7)可供選擇。規(guī)定： 在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一

23、個(gè)。 如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元，每年可獲利潤估計(jì)為ci元，但投資總額不能超過B元。問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤為最大?解題時(shí)先引入0-1變量xi(=1,2，7)7 , 2 , 1, 0, 1iAAxiii點(diǎn)沒有被選用當(dāng)點(diǎn)被選用當(dāng)令于是問題可列成：1011)85(2max76543217171iiiiiiixxxxxxxxBxbxcz約束條件目標(biāo)函數(shù)：2. 相互排斥的約束條件在本章開始的例1中，關(guān)于運(yùn)貨的體積限制為 5x1+4x224 (5-9) 今設(shè)運(yùn)貨有車運(yùn)和船運(yùn)兩種方式，上面的條件系用車運(yùn)時(shí)的限制條件，如用船運(yùn)時(shí)關(guān)于體積的限制條件為 7x1+3x245 (5-10) 這兩條件是互相

24、排斥的。為了統(tǒng)一在一個(gè)問中，引入0-1變量y，令當(dāng)采用車運(yùn)方式當(dāng)采用船運(yùn)方式, 0, 1y于是(5-9)式和(5-10)式可由下述的條件(5-11)式和(5-12)式來代替：5x1+4x224+yM (5-11)7x1+3x245+(1-y)M (5-12) 其中M是充分大的數(shù)。讀者可以驗(yàn)證，當(dāng)y=0時(shí)，(5-11)式就是(5-9)式，而(5-12)式自然成立，因而是多余的。當(dāng)y=1時(shí)(5-12)式就是(5-10)式，而(5-11)式是多余的。引入的變量y不必出現(xiàn)在目標(biāo)函數(shù)內(nèi)，即認(rèn)為在目標(biāo)函數(shù)式內(nèi)y的系數(shù)為0。 如果有m個(gè)互相排斥的約束條件(型)： i1x1+i2x2+inxnbi，i=1，2

25、，,m 為了保證這m個(gè)約束條件只有一個(gè)起作用，我們引入m個(gè)0-1變量yi(i=1,2,，m)和一個(gè)充分大的常數(shù)M，而下面這一組m+1個(gè)約束條件 i1x+i2x2+inxnbi+yiM，i=1,2,，m (5-13) y1+y2+ym=m-1 (5-14) 就合于上述的要求。這是因?yàn)?，由?5-14)式，m個(gè)yi中只有一個(gè)能取0值，設(shè)yi*=0，代入(5-13)式，就只有i=i*的約束條件起作用，而別的式子都是多余的。3. 關(guān)于固定費(fèi)用的問題 在討論線性規(guī)劃時(shí)，有些問題是要求使成本為最小。那時(shí)總設(shè)固定成本為常數(shù)，并在線性規(guī)劃的模型中不必明顯列出。但有些固定費(fèi)用(固定成本)的問題不能用一般線性規(guī)劃

26、來描述，但可改變?yōu)榛旌险麛?shù)線性規(guī)劃來解決，見下例。例5某工廠為了生產(chǎn)某種產(chǎn)品，有幾種不同的生產(chǎn)方式可供選擇，如選定投資高的生產(chǎn)方式(選購自動(dòng)化程度高的設(shè)備)，由于產(chǎn)量大，因而分配到每件產(chǎn)品的變動(dòng)成本就降低；反之，如選定投資低的生產(chǎn)方式，將來分配到每件產(chǎn)品的變動(dòng)成本可能增加，所以必須全面考慮。今設(shè)有三種方式可供選擇，令 xj表示采用第j種方式時(shí)的產(chǎn)量； cj表示采用第j種方式時(shí)每件產(chǎn)品的變動(dòng)成本； kj表示采用第j種方式時(shí)的固定成本。 為了說明成本的特點(diǎn)，暫不考慮其他約束條件。采用各種生產(chǎn)方式的總成本分別為 在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問題中討論，現(xiàn)引入0-1變量yj，令3 , 2 , 10

27、, 00,jxxxckPjjjjjj當(dāng)當(dāng))155(0, 00, 1時(shí)即種生產(chǎn)方式當(dāng)不采用第時(shí)即種生產(chǎn)方式當(dāng)采用第jjjxjxjy于是目標(biāo)函數(shù)min z=(k1y1+c1x1)+(k2y2+c2x2)+(k3y3+c3x3)(5-15)式這個(gè)規(guī)定可由以下3個(gè)線性約束條件表示： xjyjM，j=1,2,3 (5-16) 其中M是個(gè)充分大的常數(shù)。 (5-16)式說明，當(dāng)xj0時(shí)yj必須為1； 當(dāng)xj=0時(shí)只有yj為0時(shí)才有意義， 所以(5-16)式完全可以代替(5-15)式4.2 0-1型整數(shù)線性規(guī)劃的解法 解 0-1型整數(shù)線性規(guī)劃最容易想到的方法，和一般整數(shù)線性規(guī)劃的情形一樣，就是窮舉法，即檢查變

28、量取值為0或1的每一種組合，比較目標(biāo)函數(shù)值以求得最優(yōu)解，這就需要檢查變量取值的2n個(gè)組合。對于變量個(gè)數(shù)n較大(例如n10)，這幾乎是不可能的。因此常設(shè)計(jì)一些方法，只檢查變量取值的組合的一部分，就能求到問題的最優(yōu)解。這樣的方法稱為隱枚舉法(implicit enumeration)，分枝定界法也是一種隱枚舉法。當(dāng)然，對有些問題隱枚舉法并不適用，所以有時(shí)窮舉法還是必要的。下面舉例說明一種解0-1型整數(shù)線性規(guī)劃的隱枚舉法例6 目標(biāo)函數(shù) max z=3x1-2x2+3x5約束條件： x1+2x2-x32 x1+4x2+x34 (5-17) x1+x23 4x1+x36 x1，x2，x3=0或1 解題時(shí)

29、先通過試探的方法找一個(gè)可行解，容易看出(x1，x2，x3)=(1，0，0)就是合于條件的，算出相應(yīng)的目標(biāo)函數(shù)值z=3。 我們求最優(yōu)解，對于極大化問題，當(dāng)然希望z3，于是增加一個(gè)約束條件： 3x1-2x2+5x33 后加的條件稱為過濾的條件(filtering constraint)。這樣，原問題的線性約束條件就變成5個(gè)。用全部枚舉的方法，3個(gè)變量共有23=8個(gè)解，原來4個(gè)約束條件，共需32次運(yùn)算?，F(xiàn)在增加了過濾條件，如按下述方法進(jìn)行，就可減少運(yùn)算次數(shù)。將5個(gè)約束條件按順序排好(表5-5)，對每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值，看是否適合不等式條件，如某一條件不適合，同行以下各條件就不必再檢

30、查，因而就減少了運(yùn)算次數(shù)。 本例計(jì)算過程如表5-5，實(shí)際只作24次運(yùn)算。 于是求得最優(yōu)解(x1，x2，x3)=(1，0，1), max z=8 在計(jì)算過程中，若遇到z值已超過條件右邊的值，應(yīng)改變條件，使右邊為迄今為止最大者，然后繼續(xù)作。例如，當(dāng)檢查點(diǎn)(0，0，1)時(shí)因z=5(3)，所以應(yīng)將條件換成 3x1-2x2+5x35 這種對過濾條件的改進(jìn)，更可以減少計(jì)算量。表5-5條件 點(diǎn) 滿足條件? 是()否() z 值 (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) (1,0,1) (1,1,0) (1,1,1) 0 5 -2 3 3 8 1 6 -1 1 1 0 2

31、 1 5 1 2 6 0 1 1 1 0 1 5 3 8 注意：一般常重新排列xi的順序使目標(biāo)函數(shù)中xi的系數(shù)是遞增(不減)的，在上例中，改寫 z=3x1-2x2+5x3=-2x2+3x1+5x3 因?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)。再結(jié)合過濾條件的改進(jìn)，更可使計(jì)算簡化 。在上例中 max z=-2x2+3x1+5x3 -2x2+3x1+5x33 2x2+x1-x32 4x2+x1+x34 (5-18) x2+x13 4x2+x36 解題時(shí)按下述步驟進(jìn)行(見表5-

32、6)：表5-6（a）（b）條件 點(diǎn) (x2,x1,x3) 滿足條件? 是()否() z 值 (0,0,0) (0,0,1) 0 5 -1 1 0 1 5 條件 點(diǎn) (x2,x1,x3) 滿足條件? 是()否() z 值 (0,1,0) (0,1,1) 3 8 0 2 1 1 8 改進(jìn)過濾條件，用 -2x2+3x1+5x35 代替，繼續(xù)進(jìn)行。 再改進(jìn)過濾條件，用 2x2+3x1+5x38 代替，再繼續(xù)進(jìn)行。至此，z值已不能改進(jìn)，即得到最優(yōu)解，解答如前，但計(jì)算已簡化。表5-6（c）條件 點(diǎn) (x2,x1,x3) 滿足條件? 是()否() z 值 (0,0,0) (0,0,1) (1,1,0) (1,1,1) 2 3 1 6 第5章，第1，2，3，4節(jié)結(jié)束