型整數(shù)規(guī)劃PPT學(xué)習(xí)教案

1、會計(jì)學(xué)1型整數(shù)規(guī)劃型整數(shù)規(guī)劃 4.1 引入引入01 變量的實(shí)例變量的實(shí)例 1.確定投資方案相互排斥的計(jì)劃 例4 某市工商銀行擬抽調(diào)a萬元資金對小五金、小百貨和洗滌劑三個行業(yè)給予低息貸款。由于資金有限，只能在四個小五金企業(yè)A1、A2、A3、A4 中至多選兩個；在五個小百貨企業(yè)A5、A6、A7、A8 中至多選三個；在四個洗滌劑企業(yè)A9、A10、A11、A12 中至多選兩個給予低息貸款。已知企業(yè)Ai得到貸款ai萬元后，可獲利bi萬元。問工商銀行應(yīng)如何發(fā)放貸款，可使總利潤最大？ 解：因?yàn)楸締栴}只要求解決是否給企業(yè)貸款，因此可用01 變量描述所求方案。設(shè)12, 2 , 1,i貸款A(yù)不給貸款給A,01xi

2、ii于是，根據(jù)題意，本問題可描述為： maxZ=121iiixbaxaiii121241iix395iix21210iixXi=0或1,i=1,2, ,12第1頁/共7頁 這是一個01整數(shù)規(guī)劃問題。與其相類似的問題很多，比如：投資項(xiàng)目的選擇；投資場所的選定；工廠的選址；新產(chǎn)品開發(fā)方案的確定等等?？傊?，凡是一些相互排斥的計(jì)劃、方案的確定問題都可以歸結(jié)為與例4 類似的01整數(shù)規(guī)劃問題。 2.相互排斥的約束條件 回顧本章例1，用集裝箱托運(yùn)甲、乙兩種貨物，根據(jù)每件貨物的體積、重量、可獲利潤，以及集裝箱的托運(yùn)限制得整數(shù)規(guī)劃模型如下： （x1,x2分別表示甲、乙貨物托運(yùn)的件數(shù)） maxZ=20 x1+10

3、 x2 5x1+4x224 2x1+5x213 x1,x20，整數(shù) 今設(shè)集裝箱有車運(yùn)和船運(yùn)兩種方式，（3）式是車運(yùn)時的重量限制條件。如用船運(yùn)時關(guān)于重量的限制條件為 2x1+5x220試確定集裝箱托運(yùn)甲、乙貨物的數(shù)量及運(yùn)輸方式，使總利潤最大。 為了建立問題的模型，除了設(shè)甲、乙貨物托運(yùn)的件數(shù)分別為x1,x2外，還要把運(yùn)輸方式表示出來。由于只有兩種運(yùn)輸方式，所第2頁/共7頁以可設(shè)船運(yùn)車運(yùn),01y在約束條件中，兩種不同運(yùn)輸方式對應(yīng)的重量約束條件是相互排斥的，所以不能簡單地將它們都寫到約束中。利用y這個01變量可以將上述兩個重量約束改寫成： 2x1+5x213+（1-y）M 2x1+5x220+yM 其

4、中M是相當(dāng)大正數(shù)，顯然當(dāng)y=1時，式就是車運(yùn)的重量限制條件，而式自然成立，因而是多余的；當(dāng)y=0時，式就是船運(yùn)的重量限制條件，而式成為多余的。經(jīng)過這樣處理后，問題的數(shù)學(xué)模型可以寫成如下形式： maxZ=20 x1+10 x2 5x1+4x2242x1+5x213+（1-y）M2x1+5x220+yMx1,x20，整數(shù) y=0或1第3頁/共7頁類似地，如果有m個相互排斥的約束條件： ai1x1+ai2x2+ainxnbi （i=1,2,m) 為了保證這m個條件只有一個起作用，可以引入m個01變量 yi（i=1,2,m)和充分大正常數(shù)M，將這個約束條件改寫成： ai1x1+ai2x2+ainxnb

5、i+yiM （i=1,2,m) y1+y2+ym=m-1顯然，這些yi中只能有一個取0值，因而這m個約束只能有一個起作用，而其余都是多余的。第4頁/共7頁第5頁/共7頁 例5 求解 maxZ=3x1-2x2+5x3 x1+2x2-x32 x1+4x2+x34 x1+ x2 3 4x2+x36 x1,x2,x3=0或1解：調(diào)整x1,x2的順序，使目標(biāo)函數(shù)中變量的系數(shù)呈遞增（不減）的順序,則問題變?yōu)椋?maxZ=-2x2+3x1+5x3 2x2+x1-x32 4x2+x1+x34 x2+x1 3 4x2 +x36 x1,x2,x3=0或1按二進(jìn)制數(shù)碼從小到大的順序排列并檢查各個解，先計(jì)算解的目標(biāo)值，若目標(biāo)值小于目前可行解最好的目標(biāo)值，則不必檢查是否滿足約束條件，當(dāng)所有解被檢查完畢，就可判斷出最優(yōu)解。計(jì)算結(jié)果可列表表示，見左表。解（x2，x1，x3）目標(biāo)值約束條件 （0 0 0）0 （0 0 1）5 （0 1 0）- - - - -（0 1 1）8 （1 0 0）-