5.2 分支界定解法【沐風(fēng)教學(xué)】

《5.2 分支界定解法【沐風(fēng)教學(xué)】》由會(huì)員分享，可在線閱讀，更多相關(guān)《5.2 分支界定解法【沐風(fēng)教學(xué)】（28頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、1優(yōu)講課堂 如果通過(guò)對(duì)全體可行的整數(shù)解逐個(gè)比較優(yōu)劣，如果通過(guò)對(duì)全體可行的整數(shù)解逐個(gè)比較優(yōu)劣，得到最優(yōu)解的方法，得到最優(yōu)解的方法，稱為完全枚舉法（窮舉法）。稱為完全枚舉法（窮舉法）。但在解的個(gè)數(shù)很多時(shí)，這往往是不可能的。但在解的個(gè)數(shù)很多時(shí)，這往往是不可能的。如果能通過(guò)僅如果能通過(guò)僅對(duì)部分可行整數(shù)解對(duì)部分可行整數(shù)解的討論，的討論，就得到原問(wèn)題的最優(yōu)解，就得到原問(wèn)題的最優(yōu)解，稱為部分枚舉法或隱枚舉法。稱為部分枚舉法或隱枚舉法。分枝定界法就是一種隱枚舉法分枝定界法就是一種隱枚舉法，這是一種應(yīng)用很廣的求解方法。這是一種應(yīng)用很廣的求解方法。v分枝定界法可以用來(lái)求解純整數(shù)規(guī)劃和混合整數(shù)分枝定界法可以用來(lái)求解

2、純整數(shù)規(guī)劃和混合整數(shù)規(guī)劃，它是整數(shù)規(guī)劃的常用解法。規(guī)劃，它是整數(shù)規(guī)劃的常用解法。2優(yōu)講課堂算法的依據(jù)算法的依據(jù)：“對(duì)于目標(biāo)函數(shù)值來(lái)講對(duì)于目標(biāo)函數(shù)值來(lái)講,整數(shù)規(guī)劃的整數(shù)規(guī)劃的 最優(yōu)解不會(huì)更優(yōu)于最優(yōu)解不會(huì)更優(yōu)于相應(yīng)的線性規(guī)劃問(wèn)題相應(yīng)的線性規(guī)劃問(wèn)題的最優(yōu)解的最優(yōu)解”。具體說(shuō)就是，對(duì)具體說(shuō)就是，對(duì)極大化極大化問(wèn)題，問(wèn)題，與整數(shù)規(guī)劃問(wèn)題相應(yīng)的線性規(guī)劃問(wèn)題（即松弛問(wèn)題）與整數(shù)規(guī)劃問(wèn)題相應(yīng)的線性規(guī)劃問(wèn)題（即松弛問(wèn)題）的目標(biāo)函數(shù)值，的目標(biāo)函數(shù)值，是該整數(shù)規(guī)劃問(wèn)題目標(biāo)函數(shù)的是該整數(shù)規(guī)劃問(wèn)題目標(biāo)函數(shù)的上界上界；任何滿足整數(shù)條件的可行解的目標(biāo)函數(shù)值將是其任何滿足整數(shù)條件的可行解的目標(biāo)函數(shù)值將是其下界下界。下面給出分

3、枝定界法具體作法下面給出分枝定界法具體作法3優(yōu)講課堂 首先首先，刪去，刪去，把原整數(shù)規(guī)劃把原整數(shù)規(guī)劃。其次其次，。主要主要特征特征就是就是。最后最后，如果相應(yīng)線性規(guī)劃沒(méi)有可行解，如果相應(yīng)線性規(guī)劃沒(méi)有可行解，則原整數(shù)規(guī)劃也沒(méi)有可行解。則停止；則原整數(shù)規(guī)劃也沒(méi)有可行解。則停止；如果相應(yīng)線性規(guī)劃有最優(yōu)解，如果相應(yīng)線性規(guī)劃有最優(yōu)解，且符合原整數(shù)規(guī)劃問(wèn)題的整數(shù)條件，且符合原整數(shù)規(guī)劃問(wèn)題的整數(shù)條件，則這個(gè)最優(yōu)解也是原整數(shù)規(guī)劃的最優(yōu)解，則這個(gè)最優(yōu)解也是原整數(shù)規(guī)劃的最優(yōu)解，那么整個(gè)計(jì)算過(guò)程結(jié)束；那么整個(gè)計(jì)算過(guò)程結(jié)束；4優(yōu)講課堂 如果相應(yīng)線性規(guī)劃有最優(yōu)解，如果相應(yīng)線性規(guī)劃有最優(yōu)解，但不符合原整數(shù)規(guī)劃問(wèn)題的整數(shù)條

4、件，但不符合原整數(shù)規(guī)劃問(wèn)題的整數(shù)條件，則這個(gè)最優(yōu)解不是原整數(shù)規(guī)劃的最優(yōu)解，則這個(gè)最優(yōu)解不是原整數(shù)規(guī)劃的最優(yōu)解，記此最優(yōu)值為原整數(shù)規(guī)劃問(wèn)題記此最優(yōu)值為原整數(shù)規(guī)劃問(wèn)題Z*的上界的上界,然后然后,用觀察法求出下界，用觀察法求出下界，轉(zhuǎn)入第二步。轉(zhuǎn)入第二步。5優(yōu)講課堂 主要主要特征特征是是。具體作法具體作法：從相應(yīng)線性規(guī)劃的最優(yōu)解中，從相應(yīng)線性規(guī)劃的最優(yōu)解中，任意選擇一個(gè)不滿足原整數(shù)規(guī)劃整數(shù)條件任意選擇一個(gè)不滿足原整數(shù)規(guī)劃整數(shù)條件的決策變量的決策變量x xj j=b bj j以使相應(yīng)線性規(guī)劃增加一個(gè)約束條件；以使相應(yīng)線性規(guī)劃增加一個(gè)約束條件；（或（或），），因而得到兩個(gè)新的線性規(guī)劃稱為因而得到兩個(gè)新的

5、線性規(guī)劃稱為分支分支，也稱為也稱為后繼問(wèn)題后繼問(wèn)題 。列出兩分支各自的數(shù)學(xué)模型，列出兩分支各自的數(shù)學(xué)模型，計(jì)算每支的最優(yōu)解和最優(yōu)值。計(jì)算每支的最優(yōu)解和最優(yōu)值。6優(yōu)講課堂 經(jīng)過(guò)分支之后，就有如下經(jīng)過(guò)分支之后，就有如下結(jié)論結(jié)論：分支后并沒(méi)有減少整數(shù)解，分支后并沒(méi)有減少整數(shù)解，故原整數(shù)規(guī)劃的可行域故原整數(shù)規(guī)劃的可行域兩兩支支可行域的并集?？尚杏虻牟⒓?。原整數(shù)規(guī)劃的最優(yōu)解原整數(shù)規(guī)劃的最優(yōu)解兩兩支支最優(yōu)值的最大值。最優(yōu)值的最大值。7優(yōu)講課堂 主要主要特征特征就是就是.：以每個(gè)后繼問(wèn)題為一分支標(biāo)明求解的結(jié)果，以每個(gè)后繼問(wèn)題為一分支標(biāo)明求解的結(jié)果，與其他問(wèn)題的解的結(jié)果中，與其他問(wèn)題的解的結(jié)果中，找出最優(yōu)目標(biāo)

6、函數(shù)值最大者作為找出最優(yōu)目標(biāo)函數(shù)值最大者作為新的上界新的上界 ；從已符合整數(shù)條件的各分支中，從已符合整數(shù)條件的各分支中，找出目標(biāo)函數(shù)值為最大者作為找出目標(biāo)函數(shù)值為最大者作為新的下界新的下界z，若無(wú)可行解，若無(wú)可行解，z=0 z8優(yōu)講課堂 各分支的最優(yōu)目標(biāo)函數(shù)中若有各分支的最優(yōu)目標(biāo)函數(shù)中若有小于小于 z z 者，者，則剪掉這支，即以后不再考慮了。則剪掉這支，即以后不再考慮了。若有若有大于大于z z,但不符合整數(shù)條件，則繼續(xù)分支，但不符合整數(shù)條件，則繼續(xù)分支，一直到最后得到一直到最后得到z z*=z z為止，為止，得最優(yōu)整數(shù)解得最優(yōu)整數(shù)解x xj j*，j=1j=1，n n用分支定界法可解純整數(shù)線

7、性規(guī)劃問(wèn)題和混合整數(shù)線用分支定界法可解純整數(shù)線性規(guī)劃問(wèn)題和混合整數(shù)線性規(guī)劃問(wèn)題。它比窮舉法優(yōu)越。性規(guī)劃問(wèn)題。它比窮舉法優(yōu)越。因?yàn)樗鼉H在一部分可行解的整數(shù)解中尋求最優(yōu)解，因?yàn)樗鼉H在一部分可行解的整數(shù)解中尋求最優(yōu)解，計(jì)算量比窮舉法小。計(jì)算量比窮舉法小。若變量數(shù)目很大，其計(jì)算工作量也是相當(dāng)可觀的。若變量數(shù)目很大，其計(jì)算工作量也是相當(dāng)可觀的。9優(yōu)講課堂它屬于最大化純整數(shù)規(guī)劃。為便于敘述，我們將它屬于最大化純整數(shù)規(guī)劃。為便于敘述，我們將其記作其記作A A。現(xiàn)在利用分枝定界法求解之?，F(xiàn)在利用分枝定界法求解之。,2,1,0 x,x6xx45x9x5x8x5yMax21212121 利用分枝定界法求解：利用分

8、枝定界法求解：A由由A A得到相應(yīng)線性規(guī)劃，記作得到相應(yīng)線性規(guī)劃，記作B B。10優(yōu)講課堂 采取圖解法或單純形法，求得采取圖解法或單純形法，求得B B的的最優(yōu)解（最優(yōu)解（x x1 1,x x2 2）=（2.25,3.75 2.25,3.75）最優(yōu)值最優(yōu)值 y ymax max=41.25=41.25。0 x,x6xx45x9x5x8x5yMax21212121B B B的最優(yōu)解不滿足的最優(yōu)解不滿足A A的整數(shù)條件，所以的整數(shù)條件，所以它并非它并非A A的最優(yōu)解。的最優(yōu)解。11優(yōu)講課堂 0 x,x3x6xx45x9x5x8x5yMax212212121 2.2.由由B B的 最 優(yōu) 解（的 最

9、優(yōu) 解（x x1 1 ,x x2 2）=（2.25,3.75 2.25,3.75）中，選擇決策變量）中，選擇決策變量x x2 2=3.75=3.75，按照既定的原則寫(xiě)出按照既定的原則寫(xiě)出B B的兩枝：的兩枝：0 x,x4x6xx45x9x5x8x5yMax212212121把它們依次記作把它們依次記作B B1 1和和B B2 2。解解B B1 1得：最優(yōu)解（得：最優(yōu)解（x x1 1，x x2 2）=（3 3，3 3）,最優(yōu)值最優(yōu)值 y ymaxmax=39=39解解B B2 2得：最優(yōu)解（得：最優(yōu)解（x x1 1，x x2 2）=（1.8,41.8,4）,最優(yōu)值最優(yōu)值 y ymaxmax=41

10、=41B1B212優(yōu)講課堂 B x1=2.25x2=3.75y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41x23x24UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=3913優(yōu)講課堂由圖可知。界為由圖可知。界為max 39max 39，41 =4141 =41。于是。于是 界枝是界枝是B B2 2。但是，。但是，B B2 2的最優(yōu)解不滿足的最優(yōu)解不滿足A A的整數(shù)條件，的整數(shù)條件，從而它不是從而它不是A A的最優(yōu)解。因此，應(yīng)當(dāng)再次分枝。的最優(yōu)解。因此，應(yīng)當(dāng)再次分枝。由由B B2 2的最優(yōu)解中，選擇決策變量的最優(yōu)解中

11、，選擇決策變量 x x1 1=1.8=1.8，寫(xiě)出寫(xiě)出B B2 2的兩枝：的兩枝：0 x,x1x4x6xx45x9x5x8x5yMax2112212121 0 x,x2x4x6xx45x9x5x8x5yMax2112212121解解B B2121得：最優(yōu)解（得：最優(yōu)解（x x1 1，x x2 2）=（1 1，4 4），最優(yōu)值），最優(yōu)值y ymaxmax=40.=40.解解B B2222得得:B B2222無(wú)可行解。無(wú)可行解。B21B2214優(yōu)講課堂 B x1=2.25 x2=3.75 y=41.25 B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41 B21 x1=1

12、x2=40/9 y=365/9 B22 無(wú)無(wú) 可可 行行 解解x23x24x11x12UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=39UB=UB=365/9LB=39LB=3915優(yōu)講課堂 0 x,x4x1x4x6xx45x9x5x8x5yMax21212212121 0 x,x5x1x4x6xx45x9x5x8x5yMax21212212121解解B B211211得：最優(yōu)解（得：最優(yōu)解（x x1 1,x x2 2）=（1,41,4）,最優(yōu)值最優(yōu)值 y ymax max=37=37。解解B B212212得：最優(yōu)解（得：最優(yōu)解（x x1 1,x x2

13、2）=（0,50,5）,最優(yōu)值最優(yōu)值 y ymax max=40=40。B212 B211由上圖可知，界為由上圖可知，界為max 39max 39，365/9365/9=365/9365/9 。界枝為。界枝為B B2121.因?yàn)橐驗(yàn)锽 B2121最優(yōu)解不滿足最優(yōu)解不滿足A A的整數(shù)條件，的整數(shù)條件，不是不是A A的最優(yōu)解。的最優(yōu)解。944x2 由由B B2121最優(yōu)解中，選擇變量最優(yōu)解中，選擇變量把把B B2121分成兩枝：分成兩枝：16優(yōu)講課堂 現(xiàn)在，已完成的求解過(guò)程和所得到的現(xiàn)在，已完成的求解過(guò)程和所得到的計(jì)算結(jié)果見(jiàn)下圖：計(jì)算結(jié)果見(jiàn)下圖：B x1=2.25 x2=3.75 y=41.25

14、B1 x1=3 x2=3 y=39 B2 x1=1.8 x2=4 y=41 B21 x1=1 x2=40/9 y=365/9 B22 無(wú)無(wú) 可可 行行 解解x2 3x2 4x1 1x1 2B211x1=1x2=4y=37B212x1=0 x2=5y=40 x2 5x2 4UB=41.25UB=41.25LB=0LB=0UB=41UB=41LB=39LB=39UB=UB=365/9LB=39LB=39UB=UB=40LB=40LB=4017優(yōu)講課堂12121212max322314.0.54.5,0,zxxxxs txxxx 且均取整數(shù)值且均取整數(shù)值18優(yōu)講課堂第一步：放寬第一步：放寬刪除整數(shù)條

15、件刪除整數(shù)條件 0 x,x5.4x5.0 x14x3x2.t.sx2x3zmax21212121L L0 0：L L0 0的最優(yōu)解為的最優(yōu)解為(3.25(3.25，2.5)2.5)，z z*=14.75=14.75轉(zhuǎn)第二步轉(zhuǎn)第二步.12121212max322314.0.54.5,0,zxxxxs txxxx 且且均均取取整整數(shù)數(shù)值值得整數(shù)規(guī)劃的松弛問(wèn)題如下：得整數(shù)規(guī)劃的松弛問(wèn)題如下：19優(yōu)講課堂x x1 1x x2 2OO第二步：分支與定界第二步：分支與定界.L L0 0的最優(yōu)解為的最優(yōu)解為 (3.25(3.25，2.52.5).).z z*=14.75=14.75 0 x,x2x5.4x5

16、.0 x14x3x2.t.sx2x3zmax212212121L L1 1：0 x,x3x5.4x5.0 x14x3x2.t.sx2x3zmax212212121L L2 2：L L1 1的最優(yōu)解為的最優(yōu)解為(3.5(3.5，2)2)，z z1 1=14.5=14.5L L2 2的最優(yōu)解為的最優(yōu)解為(2.5(2.5，3)3)，z z2 2=13.5=13.52 23 3未失去整數(shù)解未失去整數(shù)解即整數(shù)規(guī)劃的可行即整數(shù)規(guī)劃的可行域被全部保留域被全部保留其中其中1 1zz2 2，對(duì)，對(duì)L L1 1繼續(xù)分枝繼續(xù)分枝20優(yōu)講課堂L L1 1的最優(yōu)解為的最優(yōu)解為 (3.53.5，2)2)，z z1 1=1

17、4.5=14.5將整數(shù)解化為將整數(shù)解化為一個(gè)分枝的可一個(gè)分枝的可行域的極點(diǎn)行域的極點(diǎn)x x1 1x x2 2OO圖圖4-44-4 0 x,x3x2x5.4x5.0 x14x3x2.t.sx2x3zmax2112212121L L1111：L L11 11的最優(yōu)解為的最優(yōu)解為(3(3，2)2)，z z11 11=13=13L L1212的最優(yōu)解為的最優(yōu)解為(4(4，1)1)，z z1212=14=14L L1212：0 x4x2x5.4x5.0 x14x3x2.t.sx2x3zmax212212121其中其中11 11zz1212 0 x,x2x5.4x5.0 x14x3x2.t.sx2x3zm

18、ax212212121L L1 1：L L2 2的最優(yōu)解為的最優(yōu)解為(2.5(2.5，3)3)，z z2 2=13.5=13.521優(yōu)講課堂第三步第三步:比較與剪枝比較與剪枝L L0 0 x x1 1=3.25 =3.25 x x2 2=2.5=2.5z=14.75z=14.75L L1 1x x1 1=3.5 x=3.5 x2 2=2=2z=14.5z=14.5L L2 2x x1 1=2.5 x=2.5 x2 2=3=3z=13.5z=13.5L L1212x x1 1=4 x=4 x2 2=1=1z=14z=14L L1111x x1 1=3 x=3 x2 2=2=2z=13z=13x

19、x2 2 2 2x x2 2 3 3x x1 1 3 3x x1 1 4 4UB=14.5UB=14.5LB=0LB=0UB=14.75UB=14.75LB=0LB=0UB=14UB=14LB=14LB=1422優(yōu)講課堂A A問(wèn)題為問(wèn)題為MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 x1,x2 都為整數(shù)都為整數(shù)MaxZ=40 x1+90 x29x1+7x2567x1+20 x2 70 x1,x20 B B問(wèn)題為問(wèn)題為23優(yōu)講課堂 問(wèn)題問(wèn)題B x1=4.81,x2=1.82 Z=356Z=356 Z=0 問(wèn)題問(wèn)題B1 x1=4,x2=2.1 Z=349

20、 問(wèn)題問(wèn)題B 2 x1=5,x2=1.57 Z=341x14x15Z=349 Z=0 x22x23問(wèn)題問(wèn)題B3 x1=4,x2=2 Z=340問(wèn)題問(wèn)題B4 x1=1.42 x2=3 Z=327Z=341Z=340 x21x22問(wèn)題問(wèn)題B5 x1=5.44 x2=1 Z=308Z*=340問(wèn)題問(wèn)題B6 無(wú)可行無(wú)可行解解Z=340Z=34024優(yōu)講課堂整數(shù)解整數(shù)解整數(shù)解整數(shù)解非整數(shù)解非整數(shù)解非整數(shù)解非整數(shù)解無(wú)可行解無(wú)可行解無(wú)可行解無(wú)可行解此整數(shù)解即最優(yōu)解此整數(shù)解即最優(yōu)解無(wú)可行解無(wú)可行解整數(shù)解整數(shù)解較優(yōu)的一個(gè)為最優(yōu)解較優(yōu)的一個(gè)為最優(yōu)解整數(shù)解整數(shù)解問(wèn)題問(wèn)題1停止分枝停止分枝(剪枝剪枝)，其整數(shù)解為，其

21、整數(shù)解為下界，對(duì)問(wèn)題下界，對(duì)問(wèn)題2繼續(xù)分枝繼續(xù)分枝非整數(shù)解，目標(biāo)函非整數(shù)解，目標(biāo)函數(shù)優(yōu)于問(wèn)題數(shù)優(yōu)于問(wèn)題1問(wèn)題問(wèn)題1繼續(xù)分枝繼續(xù)分枝無(wú)可行解無(wú)可行解取較優(yōu)的一個(gè)繼續(xù)分枝，得三個(gè)分枝，取較優(yōu)的一個(gè)繼續(xù)分枝，得三個(gè)分枝，再比較再比較非整數(shù)解非整數(shù)解此整數(shù)解即最優(yōu)解此整數(shù)解即最優(yōu)解整數(shù)解，目標(biāo)函數(shù)整數(shù)解，目標(biāo)函數(shù)值優(yōu)于問(wèn)題值優(yōu)于問(wèn)題1非整數(shù)解非整數(shù)解問(wèn)題問(wèn)題2繼續(xù)分枝繼續(xù)分枝非整數(shù)解非整數(shù)解此整數(shù)解即最優(yōu)解此整數(shù)解即最優(yōu)解整數(shù)解整數(shù)解無(wú)可行解無(wú)可行解無(wú)可行解無(wú)可行解無(wú)可行解無(wú)可行解789465321說(shuō)說(shuō) 明明問(wèn)題問(wèn)題2問(wèn)題問(wèn)題1序號(hào)序號(hào)情況情況 2,5,82,5,8 找到最優(yōu)解找到最優(yōu)解關(guān)注關(guān)注是否是

22、否整數(shù)整數(shù)解解是否是否整數(shù)整數(shù)解解目標(biāo)目標(biāo)值值是否是否整數(shù)整數(shù)解解目標(biāo)目標(biāo)值值25優(yōu)講課堂基本思想基本思想：先求出先求出相應(yīng)的線性規(guī)劃相應(yīng)的線性規(guī)劃最優(yōu)解，最優(yōu)解，若此解不符合整數(shù)條件，若此解不符合整數(shù)條件，那么其目標(biāo)函數(shù)的值就是整數(shù)規(guī)劃問(wèn)題最優(yōu)值的那么其目標(biāo)函數(shù)的值就是整數(shù)規(guī)劃問(wèn)題最優(yōu)值的上界上界，而任意滿足整數(shù)條件的可行解的目標(biāo)函數(shù)值而任意滿足整數(shù)條件的可行解的目標(biāo)函數(shù)值將是其將是其下界下界（定界定界），），然后將相應(yīng)的線性規(guī)劃問(wèn)題進(jìn)行分枝，然后將相應(yīng)的線性規(guī)劃問(wèn)題進(jìn)行分枝，分別求解后續(xù)的分枝問(wèn)題。分別求解后續(xù)的分枝問(wèn)題。如果后續(xù)分枝問(wèn)題的最優(yōu)值如果后續(xù)分枝問(wèn)題的最優(yōu)值小于上述下界小于上述

23、下界,則剪掉此枝則剪掉此枝;如果后續(xù)某一分枝問(wèn)題的最優(yōu)解滿足整數(shù)條件，如果后續(xù)某一分枝問(wèn)題的最優(yōu)解滿足整數(shù)條件，且其最優(yōu)值大于上述下界，且其最優(yōu)值大于上述下界，則用其取代上述下界，繼續(xù)考慮其它分枝，則用其取代上述下界，繼續(xù)考慮其它分枝，直到最終求得最優(yōu)的整數(shù)解直到最終求得最優(yōu)的整數(shù)解.26優(yōu)講課堂 且全為整數(shù)且全為整數(shù)0 x,x1x3x651x9x14xxZmax2121212127優(yōu)講課堂LP1x1=1,x2=7/3Z(1)10/3LPx1=3/2,x2=10/3Z(0)29/6LP2x1=2,x2=23/9Z(2)41/9x11x12LP3x1=33/14,x2=2Z(3)61/14LP4無(wú)可無(wú)可行解行解x22x23LP7x1=2,x2=2Z(7)4LP8x1=3,x2=1Z(8)4x12x1328優(yōu)講課堂