第四章第3節(jié) 分枝定界法 2

第4章整數(shù)規(guī)劃與分配問題14.3分枝定界法分枝定界法(BranchandBoundMethod)基本思想：先求出整數(shù)規(guī)劃相應(yīng)的LP(即不考慮整數(shù)限制)的最優(yōu)解，若求得的最優(yōu)解符合整數(shù)要求，則是原LP的最優(yōu)解；若不滿足整數(shù)條件，則任選一個(gè)不滿足整數(shù)條件的變量來構(gòu)造新的約束，在原可行域中剔除部分非整數(shù)解。然后，再在縮小的可行域中求解新構(gòu)造的線性規(guī)劃的最優(yōu)解，這樣通過求解一系列線性規(guī)劃問題，最終得到原整數(shù)規(guī)劃的最優(yōu)解。24.3分枝定界法定界的含義：整數(shù)規(guī)劃是在相應(yīng)的線性規(guī)劃的基礎(chǔ)上增加變量為整數(shù)的約束條件，整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于相應(yīng)線性規(guī)劃的最優(yōu)解。對(duì)極大化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)最優(yōu)值是原整數(shù)規(guī)劃函數(shù)值的上界；對(duì)極小化問題來說，相應(yīng)線性規(guī)劃的目標(biāo)函數(shù)的最優(yōu)值是原整數(shù)規(guī)劃目標(biāo)函數(shù)值的下界。34.3分枝定界法例1maxZ=

6x1+5x22x1+x2≤95x1+7x2≤35x1,x2≥0x1,x2取整數(shù)第一步,不考慮變量的整數(shù)約束,求相應(yīng)LP(問題1)的最優(yōu)解：

x1=28/9，x2=25/9，Z1=293/9第二步,定界過程這個(gè)解不滿足整數(shù)約束，這時(shí)目標(biāo)函值Z1是整數(shù)規(guī)劃的目標(biāo)上界；因?yàn)閤1=x2=0是整數(shù)規(guī)劃問題的可行解，所以下界為0。第三步,分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，x1稱為分枝變量，構(gòu)造兩個(gè)新的約束條件：

x1≤[28/9]=3，x1≥[28/9]+1=444.3分枝定界法這樣就把相應(yīng)的線性規(guī)劃的可行域分成兩個(gè)部分，如圖所示。??????????5x1+7x2=352x1+x2=9x1x2123125344x1=3x1=4問題2：maxZ=

6x1+5x2問題3：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)54.3分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題2相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7問題3相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數(shù)約束，不必再分枝，它的目標(biāo)函數(shù)值是29，大于原有下界0，則新的下界為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為226/7。LP2的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值226/7大于現(xiàn)有下界，則應(yīng)繼續(xù)分枝。第五步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x2≤[20/7]=2，x2≥[20/7]+1=3

6??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=34.3分枝定界法問題4：maxZ=

6x1+5x2問題5：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≤2x2≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=374.3分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題4相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=3，x2=2，Z4=28問題5相應(yīng)的線性規(guī)劃的最優(yōu)解：x1=14/5，x2=3，Z5=159/5第六步，定界過程LP4的解滿足整數(shù)約束，不必再分枝，它的目標(biāo)函數(shù)值是28，小于原有下界29，則下界仍為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為159/5。LP5的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值159/5大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。第七步，分枝過程將不滿足整數(shù)約束的變量x1進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x1≤[14/5]=2，x1≥[14/5]+1=3

84.3分枝定界法問題6：maxZ=

6x1+5x2問題7：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≥3x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)x2=2

x2=3??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x1=294.3分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解：?jiǎn)栴}6相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=2，x2=25/7，Z6=209/7問題7相應(yīng)的線性規(guī)劃的最優(yōu)解：無最優(yōu)解第八步，定界過程LP7的無最優(yōu)解，不必再分枝，下界仍為29；現(xiàn)有上界為未分枝子問題中目標(biāo)函數(shù)最大值，即為209/7。LP6的解仍不滿足整數(shù)約束的要求，它的目標(biāo)函數(shù)值209/7大于現(xiàn)有下界29，則應(yīng)繼續(xù)分枝。第九步，分枝過程將不滿足整數(shù)約束的變量x2進(jìn)行分枝，構(gòu)造兩個(gè)新的約束條件：

x2≤3，x2≥4

104.3分枝定界法問題8：maxZ=

6x1+5x2問題9：maxZ=

6x1+5x22x1+x2≤92x1+x2≤95x1+7x2≤355x1+7x2≤35x1≤3x1≤3x2≥3x2≥3x1≤2x1≤2x2≤3x2≥4x1,x2≥0x1,x2≥0x1,x2取整數(shù)x1,x2取整數(shù)??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

x2=4114.3分枝定界法求解相應(yīng)的線性規(guī)劃的最優(yōu)解問題8相應(yīng)的線性規(guī)劃的最優(yōu)解：

x1=2，x2=3，Z8=27問題9相應(yīng)的線性