5.4 0-1 整數(shù)規(guī)劃.ppt

1、,第四節(jié) 0-1型整數(shù)規(guī)劃,本節(jié)內(nèi)容的安排,如果線性規(guī)劃中的所有決策變量的取值只能取 0、1， 則這類線性規(guī)劃問題是一種特殊的整數(shù)規(guī)劃問題 稱之為0-1規(guī)劃，把只能取0或1值的變量稱為0-1變量。 0-1變量是一種邏輯變量。 在某些特殊的實(shí)際問題中，我們只需做是非選擇， 如：是否采納某方案，某任務(wù)是否可交給某人承擔(dān)， 集裝箱是否裝入某貨物等， 對(duì)于這類問題的變量可設(shè)置簡(jiǎn)化為0或1，,決策變量只取0和1的線性規(guī)劃問題， 其數(shù)學(xué)模型如下：,其中xj為0-1變量，也稱二進(jìn)制變量，邏輯變量。 xj僅取值0或1這個(gè)條件可由下述約束條件所代替。 xj1, xj0，整數(shù) 它和一般整數(shù)線性規(guī)劃的約束條件形式是

2、一致的。,作用： 在實(shí)際問題中，如果引入0-1變量， 就可以把有各種情況需要分別討論的 線性規(guī)劃問題統(tǒng)一在一個(gè)問題中討論了。,在本節(jié)我們先介紹引入0-1變量的實(shí)際問題：, 投資場(chǎng)所（項(xiàng)目）的選定 相互排斥的約束條件 關(guān)于固定費(fèi)用的問題,然后，再研究0-1規(guī)劃問題的一般解法-隱枚舉法。,一.引入0-1變量的實(shí)際問題,1. 投資場(chǎng)所的選定相互排斥的計(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)中至少選一個(gè)。

3、如選用Ai點(diǎn)，設(shè)備投資估計(jì)為bi元， 每年可獲利潤(rùn)估計(jì)為ci元， 但投資總額不能超過B元。 問應(yīng)選擇哪幾個(gè)點(diǎn)可使年利潤(rùn)為最大?,解題時(shí)先引入0-1變量xi (=1,2，7),于是問題可列成：,在東區(qū)，由A1，A2，A3三個(gè)點(diǎn)中至多選兩個(gè)； 在西區(qū)，由A4，A5兩個(gè)點(diǎn)中至少選一個(gè)； 在南區(qū)，由A6，A7兩個(gè)點(diǎn)中至少選一個(gè)。,2. 相互排斥的約束條件,在本章開始的例1 (P114)中，關(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) 這兩條件是互相排斥的。 為了統(tǒng)

4、一在一個(gè)問題中，引入0-1變量y，令,（1）兩個(gè)約束條件中只有一個(gè)起作用,車運(yùn),船運(yùn),于是(5-9)式和(5-10)式可由下述的條件(5-11)式和(5-12)式 來代替：5x1+4x224+yM (5-11)7x1+3x245+(1-y)M (5-12)其中M是充分大的數(shù) , y是0-1變量。,可以驗(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。,5x1+4x224 (5-9 ) 車運(yùn) 7x1+3x24

5、5 (5-10) 船運(yùn),為了保證這m個(gè)約束條件只有一個(gè)起作用， 引入m個(gè)0-1變量yi(i=1,2,，m)和一個(gè)充分大的常數(shù)M。,（2）在m個(gè)互相排斥的約束條件(型)： i1x1+i2x2+inxnbi，i=1，2，,m 中只有一個(gè)起作用,定義邏輯變量yi :,M為任意大 的正數(shù)，則有下式成立： 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*的約束條件起作用， 而別的式子都是多余的。,i1x+i2x2+inxnbi+y

6、iM，i=1,2,，m (5-13) y1+y2+ym=m-1 (5-14),例：利用0 1變量對(duì)下列各題分別表示成 一般線性約束條件 （a）x 1+x 2 2 或 2x 1+3x 2 5 ;,解：,（b）變量 x 只能取值0、3、5 或 7 中的一個(gè) ;,（c）變量x 或等于 0，或 50 ;,（d）若 x1 2，則 x2 1，否則x2 4 ;,（e）以下四個(gè)約束條件中至少滿足兩個(gè) x1+x2 5， x1 2， x3 2， x3+x4 6 .,3. 關(guān)于固定費(fèi)用的問題,在討論線性規(guī)劃時(shí)， 有些問題是要求使成本為最小。 這時(shí)總假定固定成本為常數(shù)， 并在線性規(guī)劃的模型中不必明顯列出。 但有些固定

7、費(fèi)用(固定成本)的問題 不能用一般線性規(guī)劃來描述， 但可改變?yōu)榛旌险麛?shù)線性規(guī)劃來解決，見下例。,例5: 某工廠為了生產(chǎn)某種產(chǎn)品， 有幾種不同的生產(chǎn) 方式可供選擇， 如選定投資高的生產(chǎn)方式(選購(gòu)自動(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)，暫不考慮其他約束條件。 問題的目標(biāo)是使所有產(chǎn)品的總生產(chǎn)費(fèi)用為最小. 解：采用

8、各種生產(chǎn)方式的總成本分別為：,在構(gòu)成目標(biāo)函數(shù)時(shí)，為了統(tǒng)一在一個(gè)問題中討論， 現(xiàn)引入0-1變量yj，令,于是目標(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)式,二 0-1型整數(shù)規(guī)劃的一般解法-隱枚舉法,解0-1型整數(shù)規(guī)劃最容易想到的方法， 和一般整數(shù)線性規(guī)劃的情形一樣，就是窮舉法， 即檢查變量取值為0或1的

9、每一種組合， 比較目標(biāo)函數(shù)值以求得最優(yōu)解， 這就需要檢查變量取值的2n個(gè)組合。 對(duì)于變量個(gè)數(shù)n較大(例如n10)，這幾乎是不可能的。 而隱枚舉法就是在此基礎(chǔ)上改進(jìn)的， 通過加入一定的條件，就能較快的求得最優(yōu)解。,只檢查變量取值的組合的一部分， 就能求到問題的最優(yōu)解， 這樣的方法稱為隱枚舉法(implicit enumeration)， 分枝定界法也是一種隱枚舉法。 其解題關(guān)鍵是尋找可行解，產(chǎn)生過濾條件。 過濾條件： 是滿足目標(biāo)函數(shù)值優(yōu)于計(jì)算過的可行解目標(biāo)函數(shù)值的約束條件。 當(dāng)然，對(duì)有些問題隱枚舉法并不適用， 所以有時(shí)窮舉法還是必要的。,下面舉例說明求解0-1型整數(shù)規(guī)劃的隱枚舉法,例6 : 目標(biāo)

10、函數(shù) max z=3x1-2x2+5x3 約束條件： x1+2x2-x32 x1+4x2+x34 (5-17) x1+x23 4x2+x36 x1，x2，x3=0或1 ,解題時(shí)先通過試探的方法找一個(gè)可行解，容易看出(x1，x2，x3)=(1，0，0) 就是合于條件的， 算出相應(yīng)的目標(biāo)函數(shù)值z(mì)=3。,我們?cè)谇笞顑?yōu)解時(shí)， 對(duì)于極大化問題，當(dāng)然希望z3， 于是增加一個(gè)約束條件： 3x1-2x2+5x33 后加的條件稱為過濾的條件(filtering constraint)。 這樣，原問題的線性約束條件就變成5個(gè)。 用全部枚舉的方法，3個(gè)變量共有23=8個(gè)解， 原來4個(gè)約束條件，共需32次運(yùn)算。 現(xiàn)在

11、增加了過濾條件， 如按下述方法進(jìn)行，就可減少運(yùn)算次數(shù)。 將5個(gè)約束條件按順序排好(表5-5)， 對(duì)每個(gè)解，依次代入約束條件左側(cè)，求出數(shù)值， 看是否適合不等式條件， 如某一條件不適合，同行以下各條件就不必再檢查， 因而就減少了運(yùn)算次數(shù)。,所以改進(jìn)過濾條件，用3x1-2x2+5x35 代替， 繼續(xù)進(jìn)行。,在計(jì)算過程中，若遇到z值已超過條件右邊的值，應(yīng)改變條件，使右邊值為迄今為止最大者， 然后繼續(xù)作。 例如，當(dāng)檢查點(diǎn)(0，0，1)時(shí)，因z=5(3)，,這種對(duì)過濾條件的改進(jìn)，更可以減少計(jì)算量。,再改進(jìn)過濾條件，用3x1-2x2+5x38 代替， 再繼續(xù)進(jìn)行。,至此，z值已不能改進(jìn)，即得到最優(yōu)解，解答如

12、前，但計(jì)算已簡(jiǎn)化。,本例計(jì)算過程實(shí)際只作16次運(yùn)算。 即求得最優(yōu)解(x1，x2，x3)=(1，0，1), max z=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ì)算簡(jiǎn)化,步驟： (1)、用試探法，求出一個(gè)可行解，以它的目標(biāo)值作為當(dāng)前最好值Z0 (2)、增加過濾條件Z Z0 (3)、將xi 按ci由小大排列。最小化問題反之。,解：1.觀察得解(x1 , x2 , x3 )=(1 ,0 ,0) ，Z0 =3 2.過濾條件：3x