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

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

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

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

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