分支定界法PPT課件

1、精品課程運(yùn)籌學(xué)精品課程運(yùn)籌學(xué)3.1 分枝定界法的基本思想分枝定界法的基本思想 考慮純整數(shù)線性規(guī)劃問(wèn)題考慮純整數(shù)線性規(guī)劃問(wèn)題 )(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ù)向向量量精品課程運(yùn)籌學(xué))(P)(1P)(2P)(3P)(4P)(5P)(6P0iixx 10 iixx2kkxx 12 kkxx3llxx 13 llxx分分 枝枝 樹樹分分 枝枝 過(guò)過(guò) 程程分枝過(guò)程在某個(gè)

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

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

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

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