5.2分支定界法(精)

1、5.2分支定界法一、基本思路maxZ=CXrAX=b（A） XRX為整數(shù)先求解松弛問題（B）。設(shè)最優(yōu)解XJ它不符合 整數(shù)要求，則選一個分量分支。分支（C）（D）稱為后繼問題。maxZ=CXAX=b可以看出，兩個后繼問題可行域中包含原 整數(shù)規(guī)劃的所有可行解。在原松弛問題的可 行域中，滿LX；jx；Z0/以它作為新的下界取代Z。,如果其他分支的目標(biāo) 函數(shù)值比Z還小，則這些分支（稱為枯枝）不必再繼續(xù)分支。 比如問題（5）的目標(biāo)函數(shù)值是327.12 Zx=340,所以 它是枯枝剪去。而問題（3）目標(biāo)函數(shù)值比Z丄大.繼續(xù)分枝 成（6）、（7）。（6）是枯枝，（7）不可行（樹葉）不 需再分枝。問題（4）的

2、解就是IP問題的最優(yōu)解。(I)4.8091.817355加分支定界法的求解過程42.15- 11.428JL.廠5.444J21無解無解LX分枝定界法一般步驟：1)求整數(shù)規(guī)劃的松弛問題最優(yōu)解；若松弛問題無可行解-無可行解；若松抱問題的最優(yōu)解滿足箱數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解否則轉(zhuǎn)下一步&2)分支與定界：任意選一個非整數(shù)解的變ftxi,在松弛問題中加上約束：xi(xi+l組成兩個新的松弛問題，稱為分枝.新的松弛問題具有待征：當(dāng)原問題 是求最大值時，目標(biāo)值是分枝問題的上界：當(dāng)原問題是求最小值時，目 標(biāo)值聶分枝問題的下界.檢査所有分枝的解及目標(biāo)函數(shù)值，若某分枝的解是整數(shù)并且目標(biāo)函數(shù)值 大于(

3、 (nwQ等于其它分枝的目標(biāo)值，則將其它分枝剪去不再計算，若 還存在非整數(shù)解并且目標(biāo)值大于(nww)整數(shù)解的目標(biāo)值,襦要繼續(xù)分枝， 再檢査，宜到得到最優(yōu)解.分支定界法優(yōu)點：(1)、任何模型均可用;(2) .思路簡單.靈活;(3)、速度快；(4) .適合上機。分枝定界法注意事項:(1).分枝變量選擇原則：1按目標(biāo)函數(shù)系數(shù)：選系數(shù)絕對值最大者變雖先分.對目標(biāo)值升降影響最大。2選與整數(shù)值相差最大的非整數(shù)變量先分枝。(3)按使用者經(jīng)驗，對各整數(shù)變量排定重要性 的優(yōu)先順序。(2)、分枝節(jié)點選擇：1深探法(后進(jìn)先出法)；最后打開的節(jié)點最先選，盡快找到整數(shù)解。整數(shù)解質(zhì)量可能不高。2廣探法：選目標(biāo)函數(shù)當(dāng)前最大

4、值節(jié)點，找到的整數(shù) 解質(zhì)量高。慢。用圖解法求松弛問題的最優(yōu)解，如圖所示。X；-18/11, x2=40/11Z=-218/ll(-19.8)即Z也是垠小值的下限J對=40/11 =3.64取(fix24minZNxIP例5.6用分枝定界法求解整數(shù)規(guī)劃問題解：首先去抻整數(shù)約束，變成一般線性規(guī)劃問題（原整數(shù)規(guī)劃 問題的松馳問題）對xl= 18/ll1.64.取值X 218/11,40/11)先將（LP劃分為（LP1）和（LP2），取xl 5xt+6x：M 30斗M4minZ=斗一5心Xg x22 25xt+6x230在IP2中分別再加入條件：X24得卜式兩支：分別求出LP21和LP22的垠優(yōu)解先求

5、LP21,如圖所示。 此時D在點収得最優(yōu)解.即x1= 12/52.4/x2=3,Z（2i）=87/5174 Z=16但X = 12/5仆尼於放，可繼續(xù)分枝即3SXS2求LP22,如圖所示.無可行解. 故不再分枝。 在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件3xxZ（2如對LP212繼續(xù)分解其最小 值也不會低T15.5問minZxt X5Xj +6X2 30&4些2 2（212）V 勺minZ=-5x分別求出（LP211）和（LP212）的最優(yōu)解題探 明,剪枝。原整數(shù)規(guī)劃問 題的最優(yōu)解為： XX = = 2 2x x2 2=3, |Z*=17以上的求解過 程可以用一個 樹形圖表示如 右：X

6、jlLPJTRA/ILx40/U Z（o）=-19.8LP1 = 1. x.=32f=-16X23x3X24LP22無可行解LP212=3 x、=：5/2井LP211x產(chǎn)2小產(chǎn)3Z（2ii）- - 17練習(xí)用分枝定界法求解解：先求對應(yīng)的松弛問題(記為LP0)用圖解法得到最優(yōu)解X=(3.57/7.14)/Z=35.7/如下圖所示。LP21:X=(4.33/6)/maxZ=4xt+3x.兀2 2 7不可行211:X0Xol6cX0選擇目標(biāo)值最大的分桂2進(jìn)行分枝，増加約芽 心S6及427.顯於N7不可行.得到線性規(guī)2 5x.S2,3114 5maxZ=4x, +3x:Uxl+Jlx, $10lx+15x25丄，24 x:6,