整數(shù)規(guī)劃和0-1規(guī)劃

1、 Mathematical modeling2整數(shù)規(guī)劃是什么整數(shù)規(guī)劃是什么?規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)規(guī)劃中的變量（部分或全部）限制為整數(shù)時，稱為整數(shù)規(guī)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)劃。若在線性規(guī)劃模型中，變量限制為整數(shù)，則稱為整數(shù)線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適線性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一用于整數(shù)線性規(guī)劃。目前還沒有一種方法能有效地求解一切整數(shù)規(guī)劃。切整數(shù)規(guī)劃。Mathematical modeling3整數(shù)規(guī)劃的分類整數(shù)規(guī)劃的分類變量全限制為整數(shù)時，稱純（完

2、全）整數(shù)規(guī)劃。變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量只能取變量只能取0或或1時，稱之為時，稱之為0-1整數(shù)規(guī)劃。整數(shù)規(guī)劃。Mathematical modeling4整數(shù)規(guī)劃模型的建立整數(shù)規(guī)劃模型的建立整數(shù)規(guī)劃模型的求解整數(shù)規(guī)劃模型的求解 完全枚舉法完全枚舉法 分支定界法分支定界法 割平面法割平面法0-1數(shù)規(guī)劃模整型數(shù)規(guī)劃模整型Mathematical modeling5例1 集裝箱運(yùn)貨問題：已知甲乙兩種貨物的裝運(yùn)和獲利情況如下表所示，問：甲乙兩貨物各托運(yùn)多少箱，可使獲得利潤最大？Mathematical mo

3、deling6且為整數(shù)0,135224451020max21212121xxxxxxxxz解：設(shè)解：設(shè) 為甲乙兩貨物各托運(yùn)箱數(shù)為甲乙兩貨物各托運(yùn)箱數(shù)12,x xMathematical modeling7(1) 原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為原線性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況： a原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 b原線性規(guī)劃最優(yōu)解不全是整數(shù)，則整數(shù)原線性規(guī)劃最優(yōu)解不全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解（規(guī)劃最優(yōu)解小于原

4、線性規(guī)劃最優(yōu)解（max）或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解（min）。）。Mathematical modeling8例例2 今有一臺機(jī)器將一周生產(chǎn)的兩種型號的冷飲杯今有一臺機(jī)器將一周生產(chǎn)的兩種型號的冷飲杯存儲在存儲在150立方米的儲藏室立方米的儲藏室 里里,并同時進(jìn)行出售并同時進(jìn)行出售.已已知這臺機(jī)器能在知這臺機(jī)器能在6小時內(nèi)生產(chǎn)一百箱小時內(nèi)生產(chǎn)一百箱號杯號杯,5小時內(nèi)小時內(nèi)生產(chǎn)一百箱生產(chǎn)一百箱號杯號杯,生產(chǎn)以百箱為單位計(jì)算生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每預(yù)計(jì)每周生產(chǎn)周生產(chǎn)60小時小時.如果如果號杯每百箱占體積號杯每百箱占體積10立方米立方米,每百箱可獲利潤

5、每百箱可獲利潤500元元,每周售出數(shù)量不會超過每周售出數(shù)量不會超過800箱箱;號杯每百箱占體積號杯每百箱占體積20立方米立方米, 每百箱可獲利潤每百箱可獲利潤450元元,每周售出數(shù)量不受限制每周售出數(shù)量不受限制.為保證總收益為最大為保證總收益為最大,每周應(yīng)安排生產(chǎn)每周應(yīng)安排生產(chǎn)、號杯各多少百箱？號杯各多少百箱？Mathematical modeling912,x x解解: 設(shè)每周生產(chǎn)設(shè)每周生產(chǎn)、號杯各號杯各 百箱百箱,則有如下則有如下數(shù)學(xué)模型數(shù)學(xué)模型且為整數(shù)0,815020106056450500max211212121xxxxxxxxxz返回返回Mathematical modeling10

6、例例3：設(shè)整數(shù)規(guī)劃問題如下：設(shè)整數(shù)規(guī)劃問題如下 且為整數(shù)0,13651914max21212121xxxxxxxxz完全枚舉法完全枚舉法Mathematical modeling11 現(xiàn)求整數(shù)解（最優(yōu)解）：現(xiàn)求整數(shù)解（最優(yōu)解）：如用如用“舍入取整法舍入取整法”可得到可得到4個點(diǎn)即個點(diǎn)即(1，3) (2，3)(1，4)(2，4)。顯然，它們都不。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。可能是整數(shù)規(guī)劃的最優(yōu)解。 故故按整數(shù)規(guī)劃約束條件，按整數(shù)規(guī)劃約束條件，其可行解肯定在線性規(guī)劃其可行解肯定在線性規(guī)劃問題的可行域內(nèi)且為整數(shù)問題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問題的可點(diǎn)。故整數(shù)規(guī)劃問題的可行解集是一個有

7、限集，如行解集是一個有限集，如圖所示。圖所示。 求得求得（2，2）（）（3，1）點(diǎn)為最大值，。點(diǎn)為最大值，。 在求解整數(shù)規(guī)劃問題時，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，在求解整數(shù)規(guī)劃問題時，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法完全枚舉法。返回返回Mathematical modeling12對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地

8、分割為越來越小的子行解空間反復(fù)地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計(jì)算一個集，稱為分枝；并且對每個子集內(nèi)的解集計(jì)算一個目標(biāo)下界（對于最小值問題），這稱目標(biāo)下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解為定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。主要思路。分支定界法分支定界法Mathematical modeling13 例例4 用分支定界法求以下整數(shù)規(guī)劃用分支定界法求

9、以下整數(shù)規(guī)劃1212122max5865945,0 xzxxxxxxxx且為整數(shù)Mathematical modeling141x2xMathematical modeling15開始開始V0 X1=2.25,X2=3.75;Z0=41.25X23X24V1 X1=3,X2=3,Z2=39V2 X1=1.8,X2=4,Z1=41X12X11V3 X1=1,X2=4.44, Z4=40.56V6 X1=0,X2=5,Z6=40V5 X1=1,X2=4,Z5=37V4 不可行不可行X24X25Mathematical modeling16 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1.什么是什么是0-1整數(shù)規(guī)劃？整數(shù)

10、規(guī)劃？2.什么時候采用什么時候采用0-1整數(shù)規(guī)劃法？整數(shù)規(guī)劃法？0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量這時的決策變量xi 只取兩個值只取兩個值0或或1，一般的解，一般的解法為隱枚舉法。法為隱枚舉法。正如計(jì)算機(jī)只懂得正如計(jì)算機(jī)只懂得0,1兩個數(shù)，兩個數(shù)，1代表是，代表是，0代代表否。同樣的，在表否。同樣的，在0-1整數(shù)規(guī)劃中的整數(shù)規(guī)劃中的0和和1并不是并不是真真意義上的數(shù)，而是一個衡量事件是否發(fā)生真真意義上的數(shù)，而是一個衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來說，我們在從多個事物中選出的標(biāo)準(zhǔn)。一般來說，我們在從多個事物中選出其中一部分，在一定的條件下求解

11、最優(yōu)情況時其中一部分，在一定的條件下求解最優(yōu)情況時可以采用可以采用0-1整數(shù)規(guī)劃法。整數(shù)規(guī)劃法。Mathematical modeling17例例5一個旅行者要到某地作兩周的帶包旅行一個旅行者要到某地作兩周的帶包旅行,裝背包時裝背包時,他發(fā)他發(fā)現(xiàn)除了已裝的必需物件外現(xiàn)除了已裝的必需物件外,他還能再裝他還能再裝5公斤重的東西公斤重的東西.他打他打算從下列算從下列4種東西中選取種東西中選取,使增加的重量不超過使增加的重量不超過5公斤又能使公斤又能使使用價值最大使用價值最大.這這4種東西的重量和使用價值種東西的重量和使用價值(這里用打分?jǐn)?shù)這里用打分?jǐn)?shù)的辦法表示價值的辦法表示價值)如下表所示如下表所示

12、,問旅行者應(yīng)該選取哪些物件為問旅行者應(yīng)該選取哪些物件為好？好？Mathematical modeling18解：建立模型為解：建立模型為12341234max Z=6x7392345s.t. 0,11,2,3,4ixxxxxxxxiMathematical modeling19Mathematical modeling20由上表可知，問題的最優(yōu)解為由上表可知，問題的最優(yōu)解為 X*=( x1=1x2=0 x3=1 ) 但此法但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過加太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過加入一定的條件，就能較快的求得最優(yōu)解：入一定的條件，就能較快的

13、求得最優(yōu)解： 找到找到x1=0 x2=0 x3=1 是一個可行解，為盡快找到最優(yōu)解，可將是一個可行解，為盡快找到最優(yōu)解，可將3 x12x25 x3 5 作為一個約束，凡是目標(biāo)函數(shù)值小于作為一個約束，凡是目標(biāo)函數(shù)值小于5 的組合不必討論，的組合不必討論，如下表。如下表。Mathematical modeling21例例6 求解下列求解下列0-1規(guī)劃問題規(guī)劃問題1231231231223123max32522 (1)44 (2). . 3 (3) 46 (4),01Zxxxxxxxxxstxxxxx x x或Mathematical modeling22解：對于解：對于0- -1 規(guī)劃問題，由于每個變量只取規(guī)劃問題，由于每個變量只取0，1兩個值，一兩個值，一般會用窮舉法來解，即將所有的般會用窮舉法來解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。達(dá)到極值要求就可求得最優(yōu)解。Mathematical modeling23例例7(指派問題指派問題) 有有5個工人，要分派他們分別完個工人，要分派他們分別完成成5項(xiàng)工作，每人做各項(xiàng)工作所消耗的時間如下項(xiàng)工作，每人做各項(xiàng)工作所消耗的時間如下表，問應(yīng)如何安排工作，可使總的消耗時間最表，問應(yīng)如何安排工作，可使總的消耗時間最??？??？Mathematical modeling2410,1,2,5ijijxi j