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

1、 Mathematical modeling2整數(shù)規(guī)劃是什么整數(shù)規(guī)劃是什么?規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱為整數(shù)規(guī)規(guī)劃中的變量（部分或全部）限制為整數(shù)時(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ù)時(shí)，稱純（完

2、全）整數(shù)規(guī)劃。變量全限制為整數(shù)時(shí)，稱純（完全）整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量只能取變量只能取0或或1時(shí)，稱之為時(shí)，稱之為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立方米的儲藏室立方米的儲藏室 里里,并同時(shí)進(jìn)行出售并同時(shí)進(jìn)行出售.已已知這臺機(jī)器能在知這臺機(jī)器能在6小時(shí)內(nèi)生產(chǎn)一百箱小時(shí)內(nèi)生產(chǎn)一百箱號杯號杯,5小時(shí)內(nèi)小時(shí)內(nèi)生產(chǎn)一百箱生產(chǎn)一百箱號杯號杯,生產(chǎn)以百箱為單位計(jì)算生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每預(yù)計(jì)每周生產(chǎn)周生產(chǎn)60小時(shí)小時(shí).如果如果號杯每百箱占體積號杯每百箱占體積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個(gè)點(diǎn)即個(gè)點(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ī)劃問題的可行解集是一個(gè)有

7、限集，如行解集是一個(gè)有限集，如圖所示。圖所示。 求得求得（2，2）（）（3，1）點(diǎn)為最大值，。點(diǎn)為最大值，。 在求解整數(shù)規(guī)劃問題時(shí)，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，在求解整數(shù)規(guī)劃問題時(shí)，可將集合內(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ù)地分割為越來越小的子集，稱為分枝；并且對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)集，稱為分枝；并且對每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(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.什么時(shí)候采用什么時(shí)候采用0-1整數(shù)規(guī)劃法？整數(shù)規(guī)劃法？0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量這時(shí)的決策變量xi 只取兩個(gè)值只取兩個(gè)值0或或1，一般的解，一般的解法為隱枚舉法。法為隱枚舉法。正如計(jì)算機(jī)只懂得正如計(jì)算機(jī)只懂得0,1兩個(gè)數(shù)，兩個(gè)數(shù)，1代表是，代表是，0代代表否。同樣的，在表否。同樣的，在0-1整數(shù)規(guī)劃中的整數(shù)規(guī)劃中的0和和1并不是并不是真真意義上的數(shù)，而是一個(gè)衡量事件是否發(fā)生真真意義上的數(shù)，而是一個(gè)衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來說，我們在從多個(gè)事物中選出的標(biāo)準(zhǔn)。一般來說，我們在從多個(gè)事物中選出其中一部分，在一定的條件下求解

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

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 是一個(gè)可行解，為盡快找到最優(yōu)解，可將是一個(gè)可行解，為盡快找到最優(yōu)解，可將3 x12x25 x3 5 作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于作為一個(gè)約束，凡是目標(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ī)劃問題，由于每個(gè)變量只取規(guī)劃問題，由于每個(gè)變量只取0，1兩個(gè)值，一兩個(gè)值，一般會用窮舉法來解，即將所有的般會用窮舉法來解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。達(dá)到極值要求就可求得最優(yōu)解。Mathematical modeling23例例7(指派問題指派問題) 有有5個(gè)工人，要分派他們分別完個(gè)工人，要分派他們分別完成成5項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如下表，問應(yīng)如何安排工作，可使總的消耗時(shí)間最表，問應(yīng)如何安排工作，可使總的消耗時(shí)間最??？??？Mathematical modeling2410,1,2,5ijijxi j