运筹学-分支定界法培训讲学

（一）、基本思路

考虑(kǎolǜ)纯整数问题：整数(zhěngshù)问题的松弛问题：第三节分枝(fēnzhī)定界法第一页，共50页。考虑(kǎolǜ)纯整数问题：整数问题(wèntí)的松弛问题(wèntí)：判断题：整数问题(wèntí)的最优函数值总是小于或等于其松弛问题(wèntí)的最优函数值。第二页，共50页。例一：用分枝定界法求解整数规划问题(wèntí)（用图解法计算）记为（IP）（二）、例题(lìtí)

第三页，共50页。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úkě)行解LP211x1=2,x2=3Z(211)

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

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃第四页，共50页。例一：用分枝定界法求解(qiújiě)整数规划问题（用图解法计算）记为（IP）解：首先去掉整数约束，变成一般(yībān)线性规划问题记为（LP）第五页，共50页。用图解法求（LP）的最优解，如图所示。x1x2⑴⑵33⑶第六页，共50页。x1x2⑴⑵33(18/11,40/11)⑶x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限(shàngxiàn)。第七页，共50页。LPx1=18/11,x2=40/11Z(0)

＝19.8第八页，共50页。x1x2⑴⑵33(18/11,40/11)⑶对于(duìyú)x1＝18/11≈1.64，取值x1≤1，x1≥2对于(duìyú)x2=40/11≈3.64，

取值x2≤3，x2≥4x1＝18/11,x2=40/11Z(0)=218/11≈(19.8)即Z也是（IP）最大值的上限(shàngxiàn)。先将（LP）划分(huàfēn)为（LP1）和（LP2）,取x1≤1,x1≥2第九页，共50页。现在(xiànzài)只要求出（LP1）和（LP2）的最优解即可。先将（LP）划分(huàfēn)为（LP1）和（LP2）,取x1≤1,x1≥2，有下式：第十页，共50页。LP1x1=？,x2=？Z(1)

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

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

＝？x1≤1x1≥2第十一页，共50页。x1x2⑴⑵33⑶

先求（LP1）,如图所示。11A第十二页，共50页。x1x2⑴⑵33⑶

先求（LP1）,如图所示。11BA此时(cǐshí)B在点取得最优解。x1＝1,x2=3,Z(1)＝16第十三页，共50页。LP1x1=？,x2=？Z(1)

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

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

＝？x1≤1x1≥2第十四页，共50页。LP1x1=1,x2=3Z(1)

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

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

＝？x1≤1x1≥2第十五页，共50页。x1x2⑴⑵33⑶11BA求（LP2）

,如图所示。第十六页，共50页。x1x2⑴⑵33⑶11在C点取得(qǔdé)最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7BAC求（LP2）

,如图所示。第十七页，共50页。LP1x1=1,x2=3Z(1)

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

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

＝？x1≤1x1≥2第十八页，共50页。LP1x1=1,x2=3Z(1)

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

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

＝18.7x1≤1x1≥2找到整数(zhěngshù)解，

此枝停止计算第十九页，共50页。在C点取得(qǔdé)最优解。即x1＝2,x2=10/3,Z(2)＝56/3≈18.7x1x2⑴⑵33⑶11BAC求（LP2）

,如图所示。∵Z2>Z1＝16∴原问题可能(kěnéng)有比（16）更大的最优解，

但x2不是整数，故利用x2≤3，x2≥4加入条件。第二十页，共50页。（LP）划分(huàfēn)为（LP1）和（LP2）,x1≤1,x1≥2第二十一页，共50页。对于LP2,加入(jiārù)条件：x2≤3,x2≥4有下式：只要求(yāoqiú)出（LP21）和（LP22）的最优解即可。第二十二页，共50页。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)

＝？找到整数解，

此枝停止(tíngzhǐ)计算第二十三页，共50页。x1x2⑴⑵33⑶11BAC先求（LP21）,如图所示。第二十四页，共50页。x1x2⑴⑵33⑶11BAC先求（LP21）,如图所示。D此时(cǐshí)D在点取得最优解。即x1＝12/5=2.4,x2=3,Z(21)＝87/5=17.4第二十五页，共50页。x1x2⑴⑵33⑶11BACD求（LP22），如图所示。无可行(kěxíng)解，不再分枝。第二十六页，共50页。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)

＝？找到整数解，

此枝停止(tíngzhǐ)计算第二十七页，共50页。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úkě)行解找到整数(zhěngshù)解，

此枝停止计算第二十八页，共50页。x1x2⑴⑵33⑶11BAC（LP21）,如图所示，在D点取得(qǔdé)最优解。即x1＝12/5=2.4,x2=3,Z(3)＝87/5=17.4Dx1＝2.4不是整数，可继续(jìxù)分枝。即x1≤2，x1≥3第二十九页，共50页。第三十页，共50页。在（LP21）的基础上继续(jìxù)分枝。加入条件x1≤2，x1≥3有下式：只要求(yāoqiú)出（LP211）和（LP212）的最优解即可。第三十一页，共50页。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úkě)行解LP211x1=？,x2=？Z(211)

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

＝？x1≤1x1≥2x2≤3x2≥4x1≥3＃找到整数解，

此枝停止(tíngzhǐ)计算第三十二页，共50页。先求（LP211）x1⑴⑵33⑶11BACDx2第三十三页，共50页。先求（LP211）x1⑴⑵33⑶11BACDEx2如图所示，此时(cǐshí)E在点取得最优解即x1＝2,x2=3,Z(211)＝17第三十四页，共50页。x1x2⑴⑵33⑶11BACDE求（LP212）第三十五页，共50页。x1x2⑴⑵33⑶11BACDE求（LP212）F如图所示。此时(cǐshí)F在点取得最优解。x1＝3,x2=2.5,Z(212)＝31/2=15.5第三十六页，共50页。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úkě)行解LP211x1=2,x2=3Z(211)

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

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃找到整数(zhěngshù)解，

此枝停止计算找到整数解，

此枝停止(tíngzhǐ)计算第三十七页，共50页。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úkě)行解LP211x1=2,x2=3Z(211)

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

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃找到最优解找到整数解，

此枝停止(tíngzhǐ)计算找到整数解，

此枝停止(tíngzhǐ)计算第三十八页，共50页。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úkě)行解LP211x1=2,x2=3Z(211)

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

＝15.5x1≤1x1≥2x2≤3x2≥4x1≤2x1≥3＃＃＃＃至此，原问题（IP）的最优解为：x1=2，x2=3,Z*=Z(211)＝17以上的求解过程(guòchéng)可以用一个树形图表示如右：第三十九页，共50页。练习(liànxí)：用分枝定界法求解整数规划问题

（图解法）第四十页，共50页。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无可行解x2≤2x2≥3＃LP211x1=2,x2=2Z(211)

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

＝4x1≤2x1≥3＃＃第四十一页，共50页。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解:用单纯形法解对应的(LP)问题(wèntí),如表所示,获得最优解。初始(chūshǐ)表最终(zuìzhōnɡ)表例二、用分枝定界法求解整数规划问题（单纯形法）

第四十二页，共50页。x1=13/4x2=5/2Z(0)=59/4=14.75选x2进行分枝，即增加两个(liǎnɡɡè)约束，x22≥,x2≤3有下式：分别(fēnbié)在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算。即x2+x5=2,－x2+x6=－3得下表:第四十三页，共50页。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继续分枝，加入(jiārù)约束x1≤3,x1≥4LP1第四十四页，共50页。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=3Z(2)=27/2=13.5∵Z(2)<Z(1)∴先不考虑(kǎolǜ)分枝第四十五页，共50页。接(LP1)继续分枝，加入(jiārù)约束x1≤3，≤x1≥4有下式：分别引入松弛(sōnɡchí)变量x7和x8，然后进行计算。第四十六页，共50页。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/203x131000012x220100100x420001-3-20x310010