運(yùn)籌學(xué)PPT.ppt

1、1,0-1整數(shù)規(guī)劃是整數(shù)規(guī)劃中的特殊情形，它的變 量取值僅為0或1。這時(shí)x稱(chēng)為0-1變量或二進(jìn)制變量。 在實(shí)際問(wèn)題中，如果引入0-1變量就可以把有各種情 況需要分別討論的線性規(guī)劃問(wèn)題統(tǒng)一到一個(gè)問(wèn)題中進(jìn) 行討論。 對(duì)于01 規(guī)劃問(wèn)題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用枚舉法來(lái)解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。,第四節(jié) 0-1型整數(shù)規(guī)劃的求解,枚舉法雖有思路簡(jiǎn)單、操作方便的特點(diǎn)，但當(dāng)變量數(shù)較大時(shí)，卻不是一種可行的辦法，因?yàn)閚個(gè)變量的組合數(shù)為2n ，它是指數(shù)函數(shù)，當(dāng)n較大時(shí)，2n 是一個(gè)非常大的數(shù)，所以要完全寫(xiě)出所有解的組合是不可能的，下面介紹隱枚舉法的思想。

2、 所謂隱枚舉法，就是只檢查變量取值組合的一部分（而不是全部），就能求出問(wèn)題最優(yōu)解的方法。,3,隱枚舉法的計(jì)算步驟： （1）找出任意一可行解，目標(biāo)函數(shù)值為Z0；則Z0是極大（?。┗瘑?wèn)題的一個(gè)下（上）界，為求解的一個(gè)初始過(guò)濾條件。 （2）列出所有可能解，對(duì)每個(gè)可能解先計(jì)算其目標(biāo)函數(shù)值Z，再比較Z和Z0的大小。若Z（）Z0，再檢驗(yàn)其它約束條件，如果滿(mǎn)足所有約束條件，則此解是可行解，Z為一個(gè)新的下（上）界，即為一個(gè)新的過(guò)濾條件；如果不滿(mǎn)足某個(gè)約束條件時(shí)，則不必去檢查其他約束條件是否可行，該解不可行。若Z（）Z0，則可判斷其不是最優(yōu)解，就不必檢驗(yàn)它的可行性了。 （3）按上述步驟檢查完所有決策變量取值的每

3、一種組合，目標(biāo)函數(shù)值最大(最小)的解就是最優(yōu)解。,例一、求解下列01 規(guī)劃問(wèn)題,解：隱枚舉法就是在牧舉法的基礎(chǔ)上，通過(guò)加入一定的條件，就能較快的求得最優(yōu)解。本例 x1 =0 x2=0 x3=1 是一個(gè)可行解，為盡快找到最優(yōu)解，可將3 x12 x25 x3 5 作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5 的組合不必討論，如下表。,6,第四節(jié) 0-1型整數(shù)規(guī)劃,目標(biāo)函數(shù)探索法求解01規(guī)劃的步驟： 第一步：變換目標(biāo)函數(shù)和約束方程 （1）將價(jià)值系數(shù)前的符號(hào)cj進(jìn)行統(tǒng)一： 在目標(biāo)函數(shù)求極大時(shí)，統(tǒng)一帶負(fù)號(hào)，求極小時(shí)，統(tǒng)一 帶正號(hào)，不滿(mǎn)足上述條件時(shí)，用yj = 1- xj進(jìn)行變換。 （2）目標(biāo)函數(shù)中按cj絕對(duì)值從小

4、到大的順序排列決策變量項(xiàng)，約 束方程組按該決策變量項(xiàng)的順序重新排列。 第二步：用目標(biāo)函數(shù)探索法求最優(yōu)解 以Z的最優(yōu)值為界，從優(yōu)到劣，逐步搜索，直到獲得可行解，此 解即為最優(yōu)解。,7,例：某廠擬在A，B，C，D，E五個(gè)城市中建立若干個(gè)產(chǎn)品經(jīng)銷(xiāo)聯(lián)營(yíng)點(diǎn)，各處設(shè)點(diǎn)都需資金、人力、設(shè)備等，而這樣的需求量及能提供的利潤(rùn)，各處不同，有些點(diǎn)也可能虧本，但卻能獲得貸款和人力等。設(shè)數(shù)據(jù)已知（見(jiàn)下表），為使總收益最大，問(wèn)廠方應(yīng)作出何種最優(yōu)選點(diǎn)決策？,解：上述各城市是否被選，可用決策變量 表示 根據(jù)已知數(shù)據(jù)可建數(shù)模如下：,僅從目標(biāo)函數(shù)看，為使總收益最大，應(yīng)取 即選A、B、C三城建聯(lián)營(yíng)點(diǎn)，D、E不選。這時(shí)，總收益為：Z

5、=17.8（十萬(wàn)元）；但從約束方程來(lái)看，這個(gè)決策不可行。 每個(gè)城市都有可能入選和不入選，即取值有0或1兩種狀態(tài)；有5個(gè)變量，這樣的組合有 個(gè)。我們并不需要列出所有可行組合，感興趣的僅是目標(biāo)函數(shù)值最優(yōu)的可行組合。只要按目標(biāo)函數(shù)值從優(yōu)到劣順序列出組合，逐個(gè)檢驗(yàn)可行性，最先滿(mǎn)足所有約束方程的組合就是最優(yōu)解；而劣于最優(yōu)解的組合即使可行，也不用列出和檢驗(yàn)。這相當(dāng)于把枚舉法得出的所有非優(yōu)組合隱去不算，故稱(chēng)為隱枚舉法。,個(gè),9,第一步：變換目標(biāo)函數(shù)和約束方程組。 將價(jià)值系數(shù) 前的符號(hào)統(tǒng)一帶負(fù)號(hào)； 令 目標(biāo)函數(shù)中按 值從小到大排列決策變量項(xiàng)，約束方程組按該決策變量項(xiàng)的順序重新排列，得：,10,第二步：用目標(biāo)函數(shù)值探索法求最優(yōu)解。 以Z的最大值為上界，逐步向下搜索，直至獲得可行解為止，即為最優(yōu)解。列表求解如下表。,