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

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

2、則繼續(xù)選擇一個(gè)非整數(shù)的變量，繼續(xù)將這個(gè)子問題分解為兩個(gè)更下一級(jí)的子問題。這個(gè)過繼續(xù)將這個(gè)子問題分解為兩個(gè)更下一級(jí)的子問題。這個(gè)過程稱為程稱為“分支（分支（Branch）”。 01.maxXIxbAXstCXZrr0.maxXIxbAXstCXZrr運(yùn)籌學(xué)教程 。 運(yùn)籌學(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運(yùn)籌學(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運(yùn)籌學(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運(yùn)籌學(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運(yùn)籌學(xué)教程說明:求極小問題時(shí)，求極小問題時(shí)，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ù)值大于上界，則停止分值大于上界，則停止分。運(yùn)籌學(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運(yùn)籌學(xué)教程 運(yùn)籌學(xué)教程第四節(jié)第四節(jié) 0101型整數(shù)規(guī)劃型整數(shù)規(guī)劃TnTTnTTnjjjjjjjjnAAAAxxAEAExAAEEEEx）選擇（）選擇（選擇選擇有兩種選擇每項(xiàng)有限要素變量描述。種選擇，用每項(xiàng)要素有問題含有較多的要素，當(dāng)決策不選取方案當(dāng)決策選取方案選取某個(gè)特定方案,.1,)0,.,1 , 1 (:,.1,) 1,.,1 , 1 (),.(, 0, 1,.2, 1102, 0, 11運(yùn)籌學(xué)教程一、一、01規(guī)劃數(shù)學(xué)模型規(guī)劃數(shù)學(xué)模型例：固定費(fèi)用問題有三種資源被用于生產(chǎn)三種產(chǎn)品，資源量、產(chǎn)品單件費(fèi)用、資源消耗量以及生產(chǎn)產(chǎn)品的固定費(fèi)用。要求制定一個(gè)生產(chǎn)計(jì)劃，總收益最大。消耗產(chǎn)品1

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

9、且為整數(shù)）種產(chǎn)品（不生產(chǎn)第）種產(chǎn)品（生產(chǎn)第分析：jj jjjjjjjjjj運(yùn)籌學(xué)教程例例 含有相互排斥的約束條件的問題含有相互排斥的約束條件的問題設(shè)工序設(shè)工序B的每周工時(shí)約束條件為的每周工時(shí)約束條件為0.3x1+0.5x2150,式式(1)現(xiàn)有一新的加工方式現(xiàn)有一新的加工方式,相應(yīng)的每周工時(shí)約束條件為相應(yīng)的每周工時(shí)約束條件為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)式成立式成立;多余的約束多余的約束運(yùn)籌學(xué)教程例例 選址問題選址問題 某公司在城市的東、西、南三區(qū)建立門市部。擬議某公司在城市的東、西、南三區(qū)建立門市部。擬議 中有中有 7 個(gè)位置（地點(diǎn)）個(gè)位置（地點(diǎn)）Ai（i=1，2，7）可供選擇。）可供選擇。公司規(guī)定公司規(guī)定 在東區(qū)，由在東區(qū)，由 A1，A2，A3 三個(gè)點(diǎn)中至多選兩個(gè)；三個(gè)點(diǎn)中至多選兩個(gè)； 在南區(qū)，由在南區(qū)，由 A4，A5 兩個(gè)點(diǎn)中至少選一個(gè)；兩個(gè)點(diǎn)中至少選一個(gè)； 在西區(qū)，由在西區(qū)，由 A6，A7 兩個(gè)點(diǎn)中至少選一個(gè)。兩個(gè)點(diǎn)中至少選一個(gè)。

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

12、3213221321321321orxxxdxxcxxbxxxaxxxstxxxZ整數(shù)規(guī)劃例：求解運(yùn)籌學(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運(yùn)籌學(xué)教程01,5358462173.73min4321421432143214321orxxxxxxxxxxxxxxxstxxxxZ01,5358462173.37min4321421432143213412orxxxxxxxxxxxxxxxstxxxxZ運(yùn)算運(yùn)算36次次運(yùn)算運(yùn)算30次次運(yùn)籌學(xué)教程練習(xí)練習(xí)1:使用分支定界法求解整數(shù)規(guī)劃使用分支定界法求解整數(shù)規(guī)劃且為整數(shù), 0,212605.2max2121212121xxxxxxxxstxxz松弛問題的最優(yōu)解松弛問題的最優(yōu)解X=(2.75,2.25)T運(yùn)籌學(xué)教程Cj21000CBXBbX1X2X3X4X51X22.25 011.50-0.250X40.500-210.52X12.75 10-0.500.25Cj-zj00