整數(shù)規(guī)劃和01規(guī)劃課件

1、整數(shù)規(guī)劃和0-1規(guī)劃1 mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃2整數(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ī)劃。mathemat

2、ical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃3整數(shù)規(guī)劃的分類整數(shù)規(guī)劃的分類變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。變量全限制為整數(shù)時，稱純（完全）整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量部分限制為整數(shù)的，稱混合整數(shù)規(guī)劃。變量只能取變量只能取0或或1時，稱之為時，稱之為0-1整數(shù)規(guī)劃。整數(shù)規(guī)劃。mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃4整數(shù)規(guī)劃模型的建整數(shù)規(guī)劃模型的建立立整數(shù)規(guī)劃模型的求整數(shù)規(guī)劃模型的求解解 完全枚舉法完全枚舉法 分支定界法分支定界法 割平面法割平面法0-10

3、-1數(shù)規(guī)劃模整型數(shù)規(guī)劃模整型mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃5例1 集裝箱運貨問題：已知甲乙兩種貨物的裝運和獲利情況如下表所示，問：甲乙兩貨物各托運多少箱，可使獲得利潤最大？mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃6且為整數(shù)0,135224451020max21212121xxxxxxxxz解：設解：設 為甲乙兩貨物各托運箱數(shù)為甲乙兩貨物各托運箱數(shù)12,x xmathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)

4、劃7(1) 原線性規(guī)劃有最優(yōu)解，當自變量限制為原線性規(guī)劃有最優(yōu)解，當自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況：整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況： a原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)原線性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。規(guī)劃最優(yōu)解與線性規(guī)劃最優(yōu)解一致。 b原線性規(guī)劃最優(yōu)解不全是整數(shù)，則整原線性規(guī)劃最優(yōu)解不全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解數(shù)規(guī)劃最優(yōu)解小于原線性規(guī)劃最優(yōu)解（max）或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)）或整數(shù)規(guī)劃最優(yōu)解大于原線性規(guī)劃最優(yōu)解（劃最優(yōu)解（min）。）。mathematical modelingmathematical modeling整

5、數(shù)規(guī)劃和0-1規(guī)劃8例例2 2 今有一臺機器將一周生產(chǎn)的兩種型號的冷飲杯今有一臺機器將一周生產(chǎn)的兩種型號的冷飲杯存儲在存儲在150立方米的儲藏室立方米的儲藏室 里里,并同時進行出售并同時進行出售.已已知這臺機器能在知這臺機器能在6小時內(nèi)生產(chǎn)一百箱小時內(nèi)生產(chǎn)一百箱號杯號杯,5小時內(nèi)小時內(nèi)生產(chǎn)一百箱生產(chǎn)一百箱號杯號杯,生產(chǎn)以百箱為單位計算生產(chǎn)以百箱為單位計算,預計每預計每周生產(chǎn)周生產(chǎn)60小時小時.如果如果號杯每百箱占體積號杯每百箱占體積10立方米立方米,每百箱可獲利潤每百箱可獲利潤500元元,每周售出數(shù)量不會超過每周售出數(shù)量不會超過800箱箱;號杯每百箱占體積號杯每百箱占體積20立方米立方米, 每

6、百箱可獲利潤每百箱可獲利潤450元元,每周售出數(shù)量不受限制每周售出數(shù)量不受限制.為保證總收益為最大為保證總收益為最大,每周應安排生產(chǎn)每周應安排生產(chǎn)、號杯各多少百箱？號杯各多少百箱？mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃912,x x解解: 設每周生產(chǎn)設每周生產(chǎn)、號杯各號杯各 百箱百箱,則有則有如下數(shù)學模型如下數(shù)學模型且為整數(shù)0,815020106056450500max211212121xxxxxxxxxz返回返回mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃10例例3

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

8、故整數(shù)規(guī)劃問題整數(shù)點。故整數(shù)規(guī)劃問題的可行解集是一個有限集，的可行解集是一個有限集，如圖所示。如圖所示。 求得（求得（2，2）（）（3，1）點為最大值，。）點為最大值，。 在求解整數(shù)規(guī)劃問題時，可將集合內(nèi)的整數(shù)點一一找出，在求解整數(shù)規(guī)劃問題時，可將集合內(nèi)的整數(shù)點一一找出，其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。其最大目標函數(shù)的值為最優(yōu)解，此法為完全枚舉法。返回返回mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃12對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）對有約束條件的最優(yōu)化問題（其可行解為有限數(shù)）的所有可行解空間恰當?shù)剡M行系的所

9、有可行解空間恰當?shù)剡M行系統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復地分割為越來越小的子行解空間反復地分割為越來越小的子集，稱為分枝；并且對每個子集內(nèi)的解集計算一個集，稱為分枝；并且對每個子集內(nèi)的解集計算一個目標下界（對于最小值問題），這稱目標下界（對于最小值問題），這稱為定界。在每次分枝后，凡是界限超出已知可行解為定界。在每次分枝后，凡是界限超出已知可行解集目標值的那些子集不再進一步分枝集目標值的那些子集不再進一步分枝，這樣，許多這樣，許多子集可不予考慮，這稱剪枝。這就是分枝定界法的子集可不予考慮，這稱剪枝。這就是分枝定界法的主要思路。

10、主要思路。分支定界法分支定界法mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃13 例例4 4 用分支定界法求以下整數(shù)規(guī)劃用分支定界法求以下整數(shù)規(guī)劃1212122max5865945,0 xzxxxxxxxx且為整數(shù)mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃141x2xmathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃15開始開始v0 x1=2.25,x2=3.75;z0=41.25x23x24v1 x1=3,x2=3,z2

11、=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 modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃16 0-1整數(shù)規(guī)劃整數(shù)規(guī)劃1.什么是什么是0-1整數(shù)規(guī)劃？整數(shù)規(guī)劃？2.什么時候采用什么時候采用0-1整數(shù)規(guī)劃法？整數(shù)規(guī)劃法？0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時的決策變量這時的決策變量xi 只取兩個值只取兩個值0或或1，一般的解，一般的解

12、法為隱枚舉法。法為隱枚舉法。正如計算機只懂得正如計算機只懂得0,1兩個數(shù)，兩個數(shù)，1代表是，代表是，0代代表否。同樣的，在表否。同樣的，在0-1整數(shù)規(guī)劃中的整數(shù)規(guī)劃中的0和和1并不是并不是真真意義上的數(shù)，而是一個衡量事件是否發(fā)生真真意義上的數(shù)，而是一個衡量事件是否發(fā)生的標準。一般來說，我們在從多個事物中選出的標準。一般來說，我們在從多個事物中選出其中一部分，在一定的條件下求解最優(yōu)情況時其中一部分，在一定的條件下求解最優(yōu)情況時可以采用可以采用0-1整數(shù)規(guī)劃法。整數(shù)規(guī)劃法。mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃17例例5 5一個旅行

13、者要到某地作兩周的帶包旅行一個旅行者要到某地作兩周的帶包旅行,裝背包時裝背包時,他發(fā)他發(fā)現(xiàn)除了已裝的必需物件外現(xiàn)除了已裝的必需物件外,他還能再裝他還能再裝5公斤重的東西公斤重的東西.他打他打算從下列算從下列4種東西中選取種東西中選取,使增加的重量不超過使增加的重量不超過5公斤又能使公斤又能使使用價值最大使用價值最大.這這4種東西的重量和使用價值種東西的重量和使用價值(這里用打分數(shù)這里用打分數(shù)的辦法表示價值的辦法表示價值)如下表所示如下表所示,問旅行者應該選取哪些物件為問旅行者應該選取哪些物件為好？好？mathematical modelingmathematical modeling整數(shù)規(guī)劃和

14、0-1規(guī)劃18解：建立模型為解：建立模型為12341234max z=6x7392345s.t. 0,11,2,3,4ixxxxxxxximathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃19mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃20由上表可知，問題的最優(yōu)解為由上表可知，問題的最優(yōu)解為 x*=( x1=1x2=0 x3=1 ) 但此法但此法太繁瑣，工作量相當大。而隱枚舉法就是在此基礎上，通過加太繁瑣，工作量相當大。而隱枚舉法就是在此基礎上，通過加入一定的條件，就能較快的求得最

15、優(yōu)解：入一定的條件，就能較快的求得最優(yōu)解： 找到找到x1=0 x2=0 x3=1 是一個可行解，為盡快找到最優(yōu)解，可將是一個可行解，為盡快找到最優(yōu)解，可將3 x12x25 x3 5 作為一個約束，凡是目標函數(shù)值小于作為一個約束，凡是目標函數(shù)值小于5 的組合不必討論，的組合不必討論，如下表。如下表。mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃21例例6 6 求解下列求解下列0-1規(guī)劃問題規(guī)劃問題1231231231223123max32522 (1)44 (2). . 3 (3) 46 (4),01zxxxxxxxxxstxxxxx x

16、 x或mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃22解：對于解：對于0- -1 規(guī)劃問題，由于每個變量只取規(guī)劃問題，由于每個變量只取0，1兩個值，一兩個值，一般會用窮舉法來解，即將所有的般會用窮舉法來解，即將所有的0，1 組合找出，使目標函數(shù)組合找出，使目標函數(shù)達到極值要求就可求得最優(yōu)解。達到極值要求就可求得最優(yōu)解。mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃23例例7(7(指派問題指派問題) ) 有有5個工人，要分派他們分別完個工人，要分派他們分別完成成5項工作，每人做各項工作所消耗的時間如下項工作，每人做各項工作所消耗的時間如下表，問應如何安排工作，可使總的消耗時間最表，問應如何安排工作，可使總的消耗時間最??？??？mathematical modelingmathematical modeling整數(shù)規(guī)劃和0-1規(guī)劃2410,1,2,5ijijxi j分派第 工人完成第 工作其他