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

,整數(shù)規(guī)劃 制作：傅明睿,Mathematical modeling,整數(shù)規(guī)劃是什么?,規(guī)劃中的變量（部分或全部）限制為整數(shù)時(shí)，稱(chēng)為整數(shù)規(guī)劃。若在線(xiàn)性規(guī)劃模型中，變量限制為整數(shù)，則稱(chēng)為整數(shù)線(xiàn)性規(guī)劃。目前所流行的求解整數(shù)規(guī)劃的方法，往往只適用于整數(shù)線(xiàn)性規(guī)劃。目前還沒(méi)有一種方法能有效地求解一切整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃的分類(lèi),變量全限制為整數(shù)時(shí)，稱(chēng)純（完全）整數(shù)規(guī)劃。 變量部分限制為整數(shù)的，稱(chēng)混合整數(shù)規(guī)劃。 變量只能取0或1時(shí)，稱(chēng)之為0-1整數(shù)規(guī)劃。,Mathematical modeling,整數(shù)規(guī)劃模型的建立 整數(shù)規(guī)劃模型的求解 完全枚舉法 分支定界法 割平面法 0-1數(shù)規(guī)劃模整型,Mathematical modeling,例1 集裝箱運(yùn)貨問(wèn)題： 已知甲乙兩種貨物的裝運(yùn)和獲利情況如下表所示，問(wèn)：甲乙兩貨物各托運(yùn)多少箱，可使獲得利潤(rùn)最大？,Mathematical modeling,解：設(shè) 為甲乙兩貨物各托運(yùn)箱數(shù),Mathematical modeling,(1) 原線(xiàn)性規(guī)劃有最優(yōu)解，當(dāng)自變量限制為整數(shù)后，其整數(shù)規(guī)劃解出現(xiàn)下述情況： a原線(xiàn)性規(guī)劃最優(yōu)解全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解與線(xiàn)性規(guī)劃最優(yōu)解一致。 b原線(xiàn)性規(guī)劃最優(yōu)解不全是整數(shù)，則整數(shù)規(guī)劃最優(yōu)解小于原線(xiàn)性規(guī)劃最優(yōu)解（max）或整數(shù)規(guī)劃最優(yōu)解大于原線(xiàn)性規(guī)劃最優(yōu)解（min）。,Mathematical modeling,例2 今有一臺(tái)機(jī)器將一周生產(chǎn)的兩種型號(hào)的冷飲杯存儲(chǔ)在150立方米的儲(chǔ)藏室 里,并同時(shí)進(jìn)行出售.已知這臺(tái)機(jī)器能在6小時(shí)內(nèi)生產(chǎn)一百箱號(hào)杯,5小時(shí)內(nèi)生產(chǎn)一百箱號(hào)杯,生產(chǎn)以百箱為單位計(jì)算,預(yù)計(jì)每周生產(chǎn)60小時(shí).如果號(hào)杯每百箱占體積10立方米,每百箱可獲利潤(rùn)500元,每周售出數(shù)量不會(huì)超過(guò)800箱;號(hào)杯每百箱占體積20立方米, 每百箱可獲利潤(rùn)450元,每周售出數(shù)量不受限制.為保證總收益為最大,每周應(yīng)安排生產(chǎn)、號(hào)杯各多少百箱？,Mathematical modeling,解: 設(shè)每周生產(chǎn)、號(hào)杯各 百箱,則有如下數(shù)學(xué)模型,返回,Mathematical modeling,例3：設(shè)整數(shù)規(guī)劃問(wèn)題如下,完全枚舉法,Mathematical modeling,現(xiàn)求整數(shù)解（最優(yōu)解）：如用“舍入取整法”可得到4個(gè)點(diǎn)即(1，3) (2，3)(1，4)(2，4)。顯然，它們都不可能是整數(shù)規(guī)劃的最優(yōu)解。 故按整數(shù)規(guī)劃約束條件，其可行解肯定在線(xiàn)性規(guī)劃問(wèn)題的可行域內(nèi)且為整數(shù)點(diǎn)。故整數(shù)規(guī)劃問(wèn)題的可行解集是一個(gè)有限集，如圖所示。,求得（2，2）（3，1）點(diǎn)為最大值，。 在求解整數(shù)規(guī)劃問(wèn)題時(shí)，可將集合內(nèi)的整數(shù)點(diǎn)一一找出，其最大目標(biāo)函數(shù)的值為最優(yōu)解，此法為完全枚舉法。,返回,Mathematical modeling,對(duì)有約束條件的最優(yōu)化問(wèn)題（其可行解為有限數(shù)）的所有可行解空間恰當(dāng)?shù)剡M(jìn)行系 統(tǒng)搜索，這就是分枝與定界內(nèi)容。通常，把全部可行解空間反復(fù)地分割為越來(lái)越小的子 集，稱(chēng)為分枝；并且對(duì)每個(gè)子集內(nèi)的解集計(jì)算一個(gè)目標(biāo)下界（對(duì)于最小值問(wèn)題），這稱(chēng) 為定界。在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進(jìn)一步分枝，這樣，許多子集可不予考慮，這稱(chēng)剪枝。這就是分枝定界法的主要思路。,分支定界法,Mathematical modeling,例4 用分支定界法求以下整數(shù)規(guī)劃,Mathematical modeling,Mathematical modeling,開(kāi)始,V0 X1=2.25,X2=3.75;Z0=41.25,X23,X24,V1 X1=3,X2=3,Z2=39,V2 X1=1.8,X2=4,Z1=41,X12,X11,V3 X1=1,X2=4.44, Z4=40.56,V6 X1=0,X2=5,Z6=40,V5 X1=1,X2=4,Z5=37,V4 不可行,X24,X25,Mathematical modeling,0-1整數(shù)規(guī)劃,1.什么是0-1整數(shù)規(guī)劃？ 2.什么時(shí)候采用0-1整數(shù)規(guī)劃法？,0-1 整數(shù)規(guī)劃是一種特殊形式的整數(shù)規(guī)劃，這時(shí)的決策變量xi 只取兩個(gè)值0或1，一般的解法為隱枚舉法。,正如計(jì)算機(jī)只懂得0,1兩個(gè)數(shù)，1代表是，0代表否。同樣的，在0-1整數(shù)規(guī)劃中的0和1并不是真真意義上的數(shù)，而是一個(gè)衡量事件是否發(fā)生的標(biāo)準(zhǔn)。一般來(lái)說(shuō)，我們?cè)趶亩鄠€(gè)事物中選出其中一部分，在一定的條件下求解最優(yōu)情況時(shí)可以采用0-1整數(shù)規(guī)劃法。,Mathematical modeling,例5一個(gè)旅行者要到某地作兩周的帶包旅行,裝背包時(shí),他發(fā)現(xiàn)除了已裝的必需物件外,他還能再裝5公斤重的東西.他打算從下列4種東西中選取,使增加的重量不超過(guò)5公斤又能使使用價(jià)值最大.這4種東西的重量和使用價(jià)值(這里用打分?jǐn)?shù)的辦法表示價(jià)值)如下表所示,問(wèn)旅行者應(yīng)該選取哪些物件為好？,Mathematical modeling,解：建立模型為,Mathematical modeling,Mathematical modeling,由上表可知，問(wèn)題的最優(yōu)解為 X*=( x1 =1 x2=0 x3=1 ) 但此法太繁瑣，工作量相當(dāng)大。而隱枚舉法就是在此基礎(chǔ)上，通過(guò)加入一定的條件，就能較快的求得最優(yōu)解： 找到x1 =0 x2=0 x3=1 是一個(gè)可行解，為盡快找到最優(yōu)解，可將3 x12 x25 x3 5 作為一個(gè)約束，凡是目標(biāo)函數(shù)值小于5 的組合不必討論，如下表。,Mathematical modeling,例6 求解下列0-1規(guī)劃問(wèn)題,Mathematical modeling,解：對(duì)于0-1 規(guī)劃問(wèn)題，由于每個(gè)變量只取0，1兩個(gè)值，一般會(huì)用窮舉法來(lái)解，即將所有的0，1 組合找出，使目標(biāo)函數(shù)達(dá)到極值要求就可求得最優(yōu)解。,Mathematical modeling,例7(指派問(wèn)題) 有5個(gè)工人，要分派他們分別