分支定界法PPT課件

1、精品課程運籌學(xué)精品課程運籌學(xué)3.1 分枝定界法的基本思想分枝定界法的基本思想 考慮純整數(shù)線性規(guī)劃問題考慮純整數(shù)線性規(guī)劃問題 )(P00 xP的的最最優(yōu)優(yōu)解解不不滿滿足足整整數(shù)數(shù)要要求求0ix0iixx 10 iixx為為整整數(shù)數(shù)向向量量xxbAxtsxcT0.min , 0.min0iiTxxxxbAxtsxc 為為整整數(shù)數(shù)向向量量1, 0.min0 iiTxxxxbAxtsxc為為整整數(shù)數(shù)向向量量精品課程運籌學(xué))(P)(1P)(2P)(3P)(4P)(5P)(6P0iixx 10 iixx2kkxx 12 kkxx3llxx 13 llxx分分 枝枝 樹樹分分 枝枝 過過 程程分枝過程在某個

2、點上由下述兩個原因之一而停止：分枝過程在某個點上由下述兩個原因之一而停止： 相應(yīng)的松弛相應(yīng)的松弛LP問題的解是滿足整數(shù)要求的；問題的解是滿足整數(shù)要求的； 相應(yīng)松弛相應(yīng)松弛LP問題是不可行的問題是不可行的 .精品課程運籌學(xué)定界過程定界過程假假設(shè)設(shè)在在某某一一時時刻刻，到到當(dāng)當(dāng)時時為為止止所所得得到到的的最最好好的的滿滿足足整整數(shù)數(shù)要要求求解解的的目目標(biāo)標(biāo)函函數(shù)數(shù)值值是是mz，而而且且我我們們正正打打算算由由某某一一點點kx分分枝枝， 該該點點子子域域?qū)?yīng)應(yīng)的的 ILP 的的下下界界為為kTkxcz ，若若mkzz ，這這意意味味著著點點kx的的所所有有后后代代得得到到的的各各個個解解x的的目目

3、標(biāo)標(biāo)函函數(shù)數(shù)值值均均有有 mkTzzxc 因因此此無無須須由由kx繼繼續(xù)續(xù)分分枝枝. 死點死點被剪枝被剪枝精品課程運籌學(xué)3.2 分枝定界法計算步驟分枝定界法計算步驟 例例3.3.13.3.1 用分枝定界法求解整數(shù)線性規(guī)劃用分枝定界法求解整數(shù)線性規(guī)劃 ，整整數(shù)數(shù)0,121124124.)(min212212121xxxxxxxtsxx精品課程運籌學(xué) 01x2x )(min21xx )(P)(1P)(2P11 x21 x4,)25,23(00 zxT精品課程運籌學(xué))(P)(1P)(2P11 x21 x4,)25,23(00 zxT 01x2x )(1P問問題題)(2P問問題題1x2x12 x22

4、xTxz)23, 1(,2511 27,)23, 2(22 zxT)(3P)(4P精品課程運籌學(xué))(P)(1P)(2P11 x21 x4,)25,23(00 zxT)(3P)(4P12 x22 xTxz)23, 1(,2511 27,)23, 2(22 zxT 01x2x)(3P問問題題22 x)(4P問問題題)(5P)(6P21 x31 x無解無解Txz)1 ,25. 2(,25. 333 精品課程運籌學(xué)無解無解Txz)1 , 2(, 355 01x2x)(5P問問題題31 x)(6P問問題題)(P)(1P)(2P11 x21 x4,)25,23(00 zxT)(3P)(4P12 x22 x

5、Txz)23, 1(,2511 27,)23, 2(22 zxT)(5P)(6P21 x31 x無解無解Txz)1 ,25. 2(,25. 333 最優(yōu)解最優(yōu)解精品課程運籌學(xué)第第1步步 第第2步步 解整數(shù)線性規(guī)劃問題的分枝定界法步驟：解整數(shù)線性規(guī)劃問題的分枝定界法步驟： 令令活活點點集集合合： O （注注： “O”代代表表原原問問題題，下下面面的的正正整整數(shù)數(shù)“k”代代表表子子問問題題)(kP） ，上上界界 ：U，當(dāng)當(dāng)前前最最好好的的整整數(shù)數(shù)解解： ； 若活點集合若活點集合 ，則轉(zhuǎn)向第，則轉(zhuǎn)向第 7 步，否則，選擇步，否則，選擇一個分枝點一個分枝點 k活點集合，從活點集合中去掉點活點集合，從活

6、點集合中去掉點 k； 第第3步步 解解點點k對對應(yīng)應(yīng)的的松松弛弛 LP 問問題題，若若此此問問題題無無解解，轉(zhuǎn)轉(zhuǎn)回回第第 2 步步； 精品課程運籌學(xué)第第4步步 第第5步步 第第6步步 若點若點k對應(yīng)的松弛對應(yīng)的松弛 LP 問題的最優(yōu)值問題的最優(yōu)值Uzk ，則點則點k被剪枝，轉(zhuǎn)回第被剪枝，轉(zhuǎn)回第 2 步；步； 若若點點k對對應(yīng)應(yīng)的的松松弛弛 LP 問問題題的的最最優(yōu)優(yōu)解解kx滿滿足足整整數(shù)數(shù)要要求求（此此時時一一定定有有Uzk ） ，則則上上界界kzU ：，當(dāng)當(dāng)前前最最好好的的整整數(shù)數(shù)解解：kx ，轉(zhuǎn)轉(zhuǎn)回回第第 2 步步； 若若點點k對對應(yīng)應(yīng)的的松松弛弛 LP 問問題題的的最最優(yōu)優(yōu)解解kx不不滿滿足足整整數(shù)數(shù)要要求求，按按kx某某個個非非整整數(shù)數(shù)分分量量生生成成點點 k的的兩兩個個后后代代點點， 令令這這兩兩個個后后代代點點為為活活點點， 并并加加入入到到活活點點集集合合中中， 轉(zhuǎn)回第轉(zhuǎn)回第2步；步； 精品課程運籌學(xué)第第7步步若當(dāng)前最好的整數(shù)解：若當(dāng)前最好的整數(shù)解： ， U，則原，則原ILP 問題無