第三節(jié) 分支定界法

1、運籌學(xué)教程 （Branch and Bound， 簡稱簡稱B&B） 0.maxXbAXstCXZ運籌學(xué)教程 E D C B Sub1 Sub2 Ir Xr Ir+1 A X2O X1分枝分枝運籌學(xué)教程 Sub1Sub2 由于這兩個子問題的可行域都是原線性規(guī)劃問題可行域的由于這兩個子問題的可行域都是原線性規(guī)劃問題可行域的子集，這兩個子問題的最優(yōu)解的目標(biāo)函數(shù)值都不會比原線子集，這兩個子問題的最優(yōu)解的目標(biāo)函數(shù)值都不會比原線性規(guī)劃問題的最優(yōu)解的目標(biāo)函數(shù)值更大。如果這兩個問題性規(guī)劃問題的最優(yōu)解的目標(biāo)函數(shù)值更大。如果這兩個問題的最優(yōu)解仍不是整數(shù)解，則繼續(xù)選擇一個非整數(shù)的變量，的最優(yōu)解仍不是整數(shù)解，

2、則繼續(xù)選擇一個非整數(shù)的變量，繼續(xù)將這個子問題分解為兩個更下一級的子問題。這個過繼續(xù)將這個子問題分解為兩個更下一級的子問題。這個過程稱為程稱為“分支（分支（Branch）”。 01.maxXIxbAXstCXZrr0.maxXIxbAXstCXZrr運籌學(xué)教程 。 運籌學(xué)教程整數(shù)規(guī)劃問題的求解方法整數(shù)規(guī)劃問題的求解方法分支定界法圖解整數(shù)規(guī)劃分支定界法圖解整數(shù)規(guī)劃 松弛問題松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0該整數(shù)規(guī)劃松弛問題的解為：該整數(shù)規(guī)劃松弛問題的解為：（X1 ，X2 ）= （3/2 ，10/3）Z1 = 29/

3、6運籌學(xué)教程松弛問題松弛問題 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 ， X2 0（3/2 ，10/3）Z1 = 29/6B1 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 1 X1 ， X2 0B2：解：解（1，7/3 ）Z21 = 10/3B1：解：解（2，23/9 ）Z11 = 41/912運籌學(xué)教程（3/2 ，10/3）Z1 = 29/6B1 Max Z = X1

4、+ X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X1 ， X2 0B2：解：解（1，7/3 ）Z21 = 17/3B1：解：解（2，23/9 ）Z11 = 41/9B11 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 3 X1 ， X2 0B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解：解（33/14，2 ）Z12 = 61/14運籌學(xué)教程（3/2 ，10/3）Z1 = 29/6B2：解：解（1，7/3 ）Z21

5、 = 10/3B12 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 2 X2 2 X1 ， X2 0B12：解：解（33/14，2 ）Z12 = 61/14B121 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 X1 3 X2 2 X1 ， X2 0B122 Max Z = X1 + X2 14X1 + 9X2 51 - 6X1 + 3X2 1 2 X1 2 X2 2 X1 ， X2 0B121：解：解（3，1 ）Z121 = 4B122：解：解（2，2 ）Z122 = 4B1：解：解（2，23/9 ）Z

6、11 = 41/9運籌學(xué)教程說明:求極小問題時，求極小問題時，LP問題的解是問題的解是IP問題的下界。每次分問題的下界。每次分后的子后的子問題最優(yōu)解的目標(biāo)函數(shù)值都大于或等于分問題最優(yōu)解的目標(biāo)函數(shù)值都大于或等于分前的最優(yōu)值。如分前的最優(yōu)值。如分中得到整數(shù)解，則最小的整數(shù)解為上界。如分中得到整數(shù)解，則最小的整數(shù)解為上界。如分的目標(biāo)函數(shù)的目標(biāo)函數(shù)值大于上界，則停止分值大于上界，則停止分。運籌學(xué)教程AX1=3/2,X2=10/3Z=29/6BX1=2,X2=23/9Z=41/9CX1=1,X2=7/3Z=10/3無可行解DX1=33/14,X2=2Z=61/14FX1=2,X2=2Z=4EX1=3,X

7、2=1Z=4運籌學(xué)教程 運籌學(xué)教程第四節(jié)第四節(jié) 0101型整數(shù)規(guī)劃型整數(shù)規(guī)劃TnTTnTTnjjjjjjjjnAAAAxxAEAExAAEEEEx）選擇（）選擇（選擇選擇有兩種選擇每項有限要素變量描述。種選擇，用每項要素有問題含有較多的要素，當(dāng)決策不選取方案當(dāng)決策選取方案選取某個特定方案,.1,)0,.,1 , 1 (:,.1,) 1,.,1 , 1 (),.(, 0, 1,.2, 1102, 0, 11運籌學(xué)教程一、一、01規(guī)劃數(shù)學(xué)模型規(guī)劃數(shù)學(xué)模型例：固定費用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件費用、資源消耗量以及生產(chǎn)產(chǎn)品的固定費用。要求制定一個生產(chǎn)計劃，總收益最大。消耗產(chǎn)品1

8、產(chǎn)品2產(chǎn)品3資源量A248500B234300C123100單件費用 456固定費用 100150200單件售價 81012產(chǎn)品資源運籌學(xué)教程解：xj是生產(chǎn)第j種產(chǎn)品的產(chǎn)量。總收益等于銷售減去所生產(chǎn)的產(chǎn)品的總費用。建立數(shù)學(xué)模型時，無法確定某種產(chǎn)品是否生產(chǎn)，不能確定相應(yīng)的固定費用是否發(fā)生，用0-1變量解決此問題。34,50,100,01010032300432500842.200150100654max0, 00, 1321333222111321321321321321MMMxMyxyMxyMxyMxxxxxxxxxxstyyyxxxZxjxjyjjjjjjj件，例如根據(jù)第三個約束條的上界為或

9、且為整數(shù)）種產(chǎn)品（不生產(chǎn)第）種產(chǎn)品（生產(chǎn)第分析：jj jjjjjjjjjj運籌學(xué)教程例例 含有相互排斥的約束條件的問題含有相互排斥的約束條件的問題設(shè)工序設(shè)工序B的每周工時約束條件為的每周工時約束條件為0.3x1+0.5x2150,式式(1)現(xiàn)有一新的加工方式現(xiàn)有一新的加工方式,相應(yīng)的每周工時約束條件為相應(yīng)的每周工時約束條件為0.2x1+0.4x2120 ,式式(2)如果工序如果工序B只能選擇一種只能選擇一種,那么那么(1)和和(2)變成相互排斥的約束條件變成相互排斥的約束條件.不采用新加工方式采用新加工方式不采用原加工方式采用原加工方式BByBBy,1,0,1,02111204.02.0150

10、5.03.0.21221121yyMyxxMyxxst當(dāng)當(dāng)y1=1,y2=0;采用采用新工藝新工藝,(2)式成立式成立;多余的約束多余的約束運籌學(xué)教程例例 選址問題選址問題 某公司在城市的東、西、南三區(qū)建立門市部。擬議某公司在城市的東、西、南三區(qū)建立門市部。擬議 中有中有 7 個位置（地點）個位置（地點）Ai（i=1，2，7）可供選擇。）可供選擇。公司規(guī)定公司規(guī)定 在東區(qū)，由在東區(qū)，由 A1，A2，A3 三個點中至多選兩個；三個點中至多選兩個； 在南區(qū)，由在南區(qū)，由 A4，A5 兩個點中至少選一個；兩個點中至少選一個； 在西區(qū)，由在西區(qū)，由 A6，A7 兩個點中至少選一個。兩個點中至少選一個。

11、 如果選用如果選用 Ai 點，設(shè)備投資估計為點，設(shè)備投資估計為 bi 元，每年可獲元，每年可獲利潤估計為利潤估計為 ci元，但投資總額不能超過元，但投資總額不能超過 B 元。問公司選元。問公司選擇哪幾個點可使年總利潤最大？擇哪幾個點可使年總利潤最大？運籌學(xué)教程建立模型建立模型 引入引入 0-1 變量變量 1 當(dāng)當(dāng) Ai 點被選用點被選用 0 當(dāng)當(dāng) Ai 沒點被選用沒點被選用xi =（i=1，2，7）max z = cixi bixi B x1 + x2 + x3 2 x4 + x5 1 x6 + x7 1 xi = 0，或，或1運籌學(xué)教程01,)(24)(22)(24)(22.523max10

12、3213221321321321orxxxdxxcxxbxxxaxxxstxxxZ整數(shù)規(guī)劃例：求解運籌學(xué)教程解：求解過程可以列表表示：(x1,x2,x3)Z值 約束條件過濾條件abcd(0,0,0)0z 0(0,0,1)5z 5(0,1,0)-2(0,1,1)3(1,0,0)3(1,0,1)8z 8(1,1,0)1(1,1,1)6運籌學(xué)教程01,5358462173.73min4321421432143214321orxxxxxxxxxxxxxxxstxxxxZ01,5358462173.37min4321421432143213412orxxxxxxxxxxxxxxxstxxxxZ運算運算36次次運算運算30次次運籌學(xué)教程練習(xí)練習(xí)1:使用分支定界法求解整數(shù)規(guī)劃使用分支定界法求解整數(shù)規(guī)劃且為整數(shù), 0,212605.2max2121212121xxxxxxxxstxxz松弛問題的最優(yōu)解松弛問題的最優(yōu)解X=(2.75,2.25)T運籌學(xué)教程Cj21000CBXBbX1X2X3X4X51X22.25 011.50-0.250X40.500-210.52X12.75 10-0.500.25Cj-zj00