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

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

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

x1=28/9，x2=25/9，Z1=293/9第二步,定界過程這個解不滿足整數約束，這時目標函值Z1是整數規(guī)劃的目標上界；因為x1=x2=0是整數規(guī)劃問題的可行解，所以下界為0。第三步,分枝過程將不滿足整數約束的變量x1進行分枝，x1稱為分枝變量，構造兩個新的約束條件：

x1≤[28/9]=3，x1≥[28/9]+1=444.3分枝定界法這樣就把相應的線性規(guī)劃的可行域分成兩個部分，如圖所示。??????????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取整數x1,x2取整數54.3分枝定界法求解相應的線性規(guī)劃的最優(yōu)解問題2相應的線性規(guī)劃的最優(yōu)解：x1=3，x2=20/7，Z2=226/7問題3相應的線性規(guī)劃的最優(yōu)解：x1=4，x2=1，Z3=29第四步，定界過程LP3的解滿足整數約束，不必再分枝，它的目標函數值是29，大于原有下界0，則新的下界為29；現有上界為未分枝子問題中目標函數最大值，即為226/7。LP2的解仍不滿足整數約束的要求，它的目標函數值226/7大于現有下界，則應繼續(xù)分枝。第五步，分枝過程將不滿足整數約束的變量x2進行分枝，構造兩個新的約束條件：

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取整數x1,x2取整數x2=2

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

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

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取整數x1,x2取整數x2=2

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

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

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取整數x1,x2取整數??????????5x1+7x2=352x1+x2=9x1x2123125344x1=4x1=3x2=3x1=2x2=2

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

x1=2，x2=3，Z8=27問題9相應的線性