運(yùn)籌學(xué)分支定界法演示

（優(yōu)選）運(yùn)籌學(xué)分支定界法目前一頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)考慮純整數(shù)問(wèn)題：整數(shù)問(wèn)題的松弛問(wèn)題：判斷題：整數(shù)問(wèn)題的最優(yōu)函數(shù)值總是小于或等于其松弛問(wèn)題的最優(yōu)函數(shù)值。目前二頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)例一：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）記為（IP）（二）、例題

目前三頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=12/5,x2=3Z(21)

＝17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)

＝17LP212x1=3,x2=5/2Z(212)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃目前四頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)例一：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（用圖解法計(jì)算）記為（IP）解：首先去掉整數(shù)約束，變成一般線(xiàn)性規(guī)劃問(wèn)題記為（LP）目前五頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)用圖解法求（LP）的最優(yōu)解，如圖所示。x1x2⑴⑵33⑶目前六頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33(18/11,40/11)⑶x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限。目前七頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LPx1=18/11,x2=40/11Z(0)

＝19.8目前八頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33(18/11,40/11)⑶對(duì)于x1＝18/11≈1.64，取值x1≤1，x1≥2對(duì)于x2=40/11≈3.64，

取值x2

≤3，x2

≥4x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限。先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2目前九頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)

現(xiàn)在只要求出（LP1）和（LP2）的最優(yōu)解即可。先將（LP）劃分為（LP1）和（LP2）,取x1≤1,x1≥2，有下式：目前十頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=？,x2=？Z(1)

＝？LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2目前十一頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶

先求（LP1）,如圖所示。11A目前十二頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶

先求（LP1）,如圖所示。11BA此時(shí)B

在點(diǎn)取得最優(yōu)解。x1＝1,x2=3,Z(1)＝16目前十三頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=？,x2=？Z(1)

＝？LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2目前十四頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2目前十五頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BA求（LP2）

,如圖所示。目前十六頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝56/3≈18.7BAC求（LP2）

,如圖所示。目前十七頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=？,x2=？Z(2)

＝？x1≤1x1≥2目前十八頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7x1≤1x1≥2找到整數(shù)解，

此枝停止計(jì)算目前十九頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)在C

點(diǎn)取得最優(yōu)解。即x1＝2,x2=10/3,Z(2)

＝56/3≈18.7x1x2⑴⑵33⑶11BAC求（LP2）

,如圖所示。

∵Z2>Z1＝16∴原問(wèn)題可能有比（16）更大的最優(yōu)解，

但x2不是整數(shù)，故利用x2≤3，x2≥4

加入條件。目前二十頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)（LP）劃分為（LP1）和（LP2）,x1≤1,x1≥2目前二十一頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)對(duì)于LP2,加入條件：x2≤3,x2≥4有下式：只要求出（LP21）和（LP22）的最優(yōu)解即可。目前二十二頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7LP21x1=？,x2=？Z(21)

＝？LP22x1=？,x2=？Z(22)

＝？找到整數(shù)解，

此枝停止計(jì)算目前二十三頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BAC先求（LP21）,如圖所示。目前二十四頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BAC先求（LP21）,如圖所示。D此時(shí)D在點(diǎn)取得最優(yōu)解。即x1＝12/5=2.4,x2=3,Z(21)＝87/5=17.4目前二十五頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BACD求（LP22），如圖所示。無(wú)可行解，不再分枝。目前二十六頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7LP21x1=？,x2=？Z(21)

＝？LP22x1=？,x2=？Z(22)

＝？找到整數(shù)解，

此枝停止計(jì)算目前二十七頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1≤1x1≥2x2≥4x2≤3LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.7LP21x1=2.4,x2=3Z(21)

＝17.4LP22無(wú)可行解找到整數(shù)解，

此枝停止計(jì)算目前二十八頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BAC（LP21）,如圖所示，

在D點(diǎn)取得最優(yōu)解。即x1＝12/5=2.4,x2=3,Z(3)＝87/5=17.4Dx1＝2.4不是整數(shù)，可繼續(xù)分枝。即x1≤2，

x1≥3目前二十九頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)目前三十頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)在（LP21）的基礎(chǔ)上繼續(xù)分枝。加入條件x1≤2，

x1≥3有下式：只要求出（LP211）和（LP212）的最優(yōu)解即可。目前三十一頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1≤2LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22無(wú)可行解LP211x1=？,x2=？Z(211)

＝？LP212x1=？,x2=？Z(212)

＝？x1≤1x1≥2x2≤3x2≥4x1≥3＃找到整數(shù)解，

此枝停止計(jì)算目前三十二頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)先求（LP211）x1⑴⑵33⑶11BACDx2目前三十三頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)先求（LP211）x1⑴⑵33⑶11BACDEx2如圖所示，此時(shí)E

在點(diǎn)取得最優(yōu)解即x1＝2,x2=3,Z(211)＝17目前三十四頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BACDE求（LP212）目前三十五頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1x2⑴⑵33⑶11BACDE求（LP212）F如圖所示。此時(shí)F在點(diǎn)取得最優(yōu)解。x1＝3,x2=2.5,Z(212)＝31/2=15.5目前三十六頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)

＝17LP212x1=3,x2=5/2Z(212)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃找到整數(shù)解，

此枝停止計(jì)算找到整數(shù)解，

此枝停止計(jì)算目前三十七頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)

＝17LP212x1=3,x2=5/2Z(212)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃找到最優(yōu)解找到整數(shù)解，

此枝停止計(jì)算找到整數(shù)解，

此枝停止計(jì)算目前三十八頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=3Z(1)

＝16LPx1=18/11,x2=40/11Z(0)

＝19.8LP2x1=2,x2=10/3Z(2)

＝18.5LP21x1=2.4,x2=3Z(21)

＝17.4LP22無(wú)可行解LP211x1=2,x2=3Z(211)

＝17LP212x1=3,x2=5/2Z(212)

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃

至此，原問(wèn)題（IP）的最優(yōu)解為：

x1=2，

x2=3,

Z*=Z(211)

＝17以上的求解過(guò)程可以用一個(gè)樹(shù)形圖表示如右：目前三十九頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)練習(xí)：用分枝定界法求解整數(shù)規(guī)劃問(wèn)題

（圖解法）目前四十頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)LP1x1=1,x2=7/3Z(1)

＝10/3LPx1=3/2,x2=10/3Z(0)

＝29/6LP2x1=2,x2=23/9Z(2)

＝41/9x1≤1x1≥2LP21x1=33/14,x2=2Z(21)

＝61/14LP22無(wú)可行解x2≤2x2≥3＃LP211x1=2,x2=2Z(211)

＝4LP212x1=3,x2=1Z(212)

＝4x1≤2x1≥3＃＃目前四十一頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)3200CB

XB

b

x1x2x3x40x3921109/20x414230114/2-Z032003200CB

XB

b

x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4解:用單純形法解對(duì)應(yīng)的(LP)問(wèn)題,如表所示,獲得最優(yōu)解。初始表最終表例二、用分枝定界法求解整數(shù)規(guī)劃問(wèn)題（單純形法）

目前四十二頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)x1=13/4

x2=5/2Z(0)=59/4=14.75

選x2進(jìn)行分枝，即增加兩個(gè)約束，x2

2≥,x2≤3有下式：

分別在(LP1)和(LP2)中引入松弛變量x5和x6

，將新加約束條件加入上表計(jì)算。即x2+x5=2,－x2+x6=－3

得下表:目前四十三頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)32000CB

XB

b

x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2

-1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2-Z-29/200-3/20-1/2x1=7/2,x2=2Z(1)=29/2=14.5繼續(xù)分枝，加入約束

x1

≤3,x1≥4LP1目前四十四頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)32000CB

XB

b

x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/2

1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2,x2=3

Z(2)=27/2=13.5∵

Z(2)<Z(1)∴先不考慮分枝目前四十五頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)接(LP1)繼續(xù)分枝，加入約束

x1≤3，≤x1≥4

有下式：分別引入松弛變量x7和x8，然后進(jìn)行計(jì)算。目前四十六頁(yè)\總數(shù)四十九頁(yè)\編于五點(diǎn)CB

XB

b

x1x2x3x4x5x73x17/2101/20-1/202x220100100x4100-11-200x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100x4100-11-200x7-1/200-1/201/21-Z-29/200-3/20-1/203x1310000