求解整數(shù)規(guī)劃算法.doc

求解整數(shù)規(guī)劃算法分枝定界法原理步驟：將要求解的整數(shù)規(guī)劃問題稱為I L，與它相應(yīng)的線性規(guī)劃問題稱為問題L。 解問題L，可能得到以下情況之一： （a）L沒有可行解，這時(shí)I L也沒有可行解（b）L有最優(yōu)解，且解變量都是整數(shù)，因而它也是I L的最優(yōu)解，則停止；（c）L有最優(yōu)解，但不符合I L中的整數(shù)條件，記它的目標(biāo)函數(shù)值為，若記為I L的最優(yōu)目標(biāo)函數(shù)值，則必有 迭代：第一步：分枝：在L的最優(yōu)解中任選一個(gè)不符合整數(shù)條件的變量，設(shè)其值為，構(gòu)造兩個(gè)約束條件：和。將這兩個(gè)條件分別加入問題L，將L分成兩個(gè)后繼問題L1和L2。求解L1和L2。定界：以每個(gè)子問題的求解結(jié)果，與其它問題的解的結(jié)果一道，找出最優(yōu)目標(biāo)函數(shù)值最小者作為新的下界，替換，從已符合整數(shù)條件的各分枝中，找出目標(biāo)數(shù)值為最小者作為新的上界，即有。第二步比較與剪枝：各分枝的最優(yōu)目標(biāo)函數(shù)中若有大于者，則剪掉這一枝；若小于，且不符合整數(shù)條件，則重復(fù)第一步驟，一直到最后得到最優(yōu)目標(biāo)函數(shù)值為止，從而得最優(yōu)整數(shù)解。割平面算法求解整數(shù)規(guī)劃模型這個(gè)方法的基礎(chǔ)仍然是用解線性規(guī)劃的方法去解整數(shù)規(guī)劃問題，首先不考慮變量是整數(shù)的條件，但增加線性約束條件使得由原可行域中切割掉一部分，這部分只包含非整數(shù)解，但沒切割掉任何整數(shù)可行解。這個(gè)方法就是指怎樣找到適當(dāng)?shù)母钇矫妫骨懈詈笞罱K得到這樣的可行域，它的一個(gè)有整數(shù)坐標(biāo)的極點(diǎn)恰好是問題的最優(yōu)解。0-1型整數(shù)規(guī)劃一、解決的主要問題背包問題P35,售貨員問題P34,投資組合問題P33,投資決策問題P33,飛機(jī)排隊(duì)P31，（資料）集合覆蓋和布點(diǎn)問題P212運(yùn)籌學(xué)基礎(chǔ)，與生產(chǎn)方式有關(guān)的固定成本問題P213運(yùn)籌學(xué)基礎(chǔ)1 如果決策i為是或有0 如果決策i為否或無二、模型建立：假設(shè)現(xiàn)有m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為：求一組決策變量使其中