运筹学-分支定界法课件.ppt

1、（一）、基本思路（一）、基本思路 11max (1.2)()0,(1.2)njjjnijjijjZc xa xbimIPxjn且为整数考虑纯整数问题：考虑纯整数问题：11max (1.2)()0,(1.2)njjjnijjijjZc xa xbimLPxjn整数问题的松弛问题：整数问题的松弛问题：第三节第三节 分枝定界法分枝定界法且为整数且为整数)2 . 1( , 0)2 . 1( )(max11mjxmibxaIPxcZjnjijijnjjj考虑纯整数问题：考虑纯整数问题：)2 . 1( , 0)2 . 1( )(max11mjxmibxaLPxcZjnjijijnjjj整数问题的松弛问题：

2、整数问题的松弛问题：判断题：整数问题的最优判断题：整数问题的最优函数值总是小于或等于其函数值总是小于或等于其松弛问题的最优函数值。松弛问题的最优函数值。例一：用分枝定界法求解整数规划问题（用图解法计算）例一：用分枝定界法求解整数规划问题（用图解法计算）121212112max5 256 30 4,0Zxxxxxxxxx 且全为整数记为（记为（IP）（二）、例题（二）、例题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无可无可行解行解

3、LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13例一：用分枝定界法求解整数规划问题（用图解法计算）例一：用分枝定界法求解整数规划问题（用图解法计算）121212112max5 256 30 4,0Zxxxxxxxxx 且全为整数记为（记为（IP）解：首先去掉整数约束，变成一般线性规划问题解：首先去掉整数约束，变成一般线性规划问题121212112max5 256 30 4,0Zxxxxxxxxx 记为（记为（LP）用图解法求用图解法求（LP）的最的最优解，如图所示。优解，如图所示。x1x23312121

4、2112max5 256 30 4,0Zxxxxxxxxx 12 2xx 14x 125630 xx125xxZx1x233(18/11,40/11) x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最大值的上限。最大值的上限。121212112max5 256 30 4,0Zxxxxxxxxx 12 2xx 14x 125630 xx125xxZLPx1=18/11, x2=40/11Z(0) 19.8x1x233(18/11,40/11)对于对于x118/111.64， 取值取值x1 1， x1 2对于对于x2 =40/11 3.64，取值

5、取值x2 3 ，x2 4 x118/11, x2 =40/11 Z(0) =218/11(19.8)即即Z 也是也是（IP）最大值的上限。最大值的上限。先将先将（LP）划分为（）划分为（LP1）和）和（LP2）, ,取取x1 1, x1 212 2xx 14x 125630 xx125xxZ1212121112max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且为整数1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且为整数 现在只要求出（现在只要求出（LP1）和（）和（LP2）的最优解即可。）的最优解即可。先将先将（LP）划分为（）划分

6、为（LP1）和（）和（LP2）, ,取取x1 1, x1 2，有下式：有下式：LP1x1=？, x2=？Z(1) ？LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12x1x233 先求先求（LP1）, ,如图所示。如图所示。11A1212121112max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZx1x233 先求先求（LP1）, ,如图所示。如图所示。11BA此时此时B 在点取得最优解。在点取得最优解。x11, x2 =3, Z(1)16121212111

7、2max5 256 30(1) 4 1,0ZxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZLP1x1=？, x2=？Z(1) ？LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12x1x23311BA求求（LP2） ,如图所示。如图所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且为整数12 2xx 14x

8、125630 xx125xxZx1x23311在在C 点取得最优解。点取得最优解。即即x12, x2 =10/3, Z(2) 56/318.7BAC求求（LP2） ,如图所示。如图所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZLP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=？, x2=？Z(2) ？x11x12LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x

9、2=10/3Z(2) 18.7x11x12找到整数解，找到整数解，此枝停止计算此枝停止计算在在C 点取得最优解。点取得最优解。即即x12, x2 =10/3, Z(2) 56/318.7 x1x23311BAC求求（LP2） ,如图所示。如图所示。1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且为整数 Z2 Z116 原问题可能有比（原问题可能有比（16）更大的最优解，）更大的最优解，但但 x2 不是整数，故利用不是整数，故利用 x2 3 ， x2 4 加入条件。加入条件。12 2xx 14x 125630 xx125xxZ1212121112max5

10、 256 30(1) 4 1,0ZxxxxxxIPxxxx 且为整数1212121112max5 256 30(2) 4 2,0ZxxxxxxIPxxxx 且为整数（LP）划分为（）划分为（LP1）和（）和（LP2）, ,x1 1, x1 2对于对于LP2,加入条件：加入条件： x23, x24 有下式：有下式：12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且为整数12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且为整数只要求出（只要求出（LP21）和（）和（LP22）的最优解即可。）的最优解

11、即可。x11x12x24x23LP1x1=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) ？找到整数解，找到整数解，此枝停止计算此枝停止计算x1x23311BAC先求先求（LP21）, ,如图所示。如图所示。12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZx1x23311BAC先求先求（LP21）, ,如图所示。如图所

12、示。D此时此时D 在点取得最优解。在点取得最优解。即即 x112/5=2.4, x2 =3, Z(21)87/5=17.412121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZx1x23311BACD求求（LP22），），如图所示。如图所示。无可行解，不再分枝。无可行解，不再分枝。12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且为整数12 2xx 14x 125630 xx125xxZx11x12x24x23LP1x1=1, x2=3Z(1

13、) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.7LP21x1=？, x2=？Z(21) ？LP22x1=？, x2=？Z(22) ？找到整数解，找到整数解，此枝停止计算此枝停止计算x11x12x24x23LP1x1=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无可无可行解行解找到整数解，找到整数解，此枝停止计算此枝停止计算x1x23311BAC（LP21）, ,如图所示，如图所

14、示， 在在D点取点取得最优解。得最优解。即即 x112/5=2.4, x2 =3, Z(3)87/5=17.4Dx12.4不是整数，可继续分枝。不是整数，可继续分枝。即即 x12， x1 312 2xx 14x 125630 xx125xxZ12121211212max5 256 30 4(21) 2 3,0ZxxxxxxxIPxxxx 且为整数12121211212max5 256 30 4(22) 2 4,0ZxxxxxxxIPxxxx 且为整数在在（LP21）的基础上继续分枝。加入条件）的基础上继续分枝。加入条件x12， x1 3有下式：有下式：121212112112max5 256

15、30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且为整数121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且为整数只要求出（只要求出（LP211）和（）和（LP212）的最优解即可。）的最优解即可。x12LP1x1=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无可无可行解行解LP211x1=？, x2=？Z(211) ？LP212x1=？, x2=？Z(212) ？x1

16、1x12x23x24x13找到整数解，找到整数解，此枝停止计算此枝停止计算先求先求（LP211）x13311BACD121212112112max5 256 30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且为整数x212 2xx 14x 125630 xx125xxZ先求先求（LP211）x13311BACDE121212112112max5 256 30 4(211) 2 3 2,0ZxxxxxxxIPxxxxx 且为整数x2如图所示，此时如图所示，此时E 在点取得最优解在点取得最优解即即 x12, x2 =3, Z(211)1712 2xx 14x 125630 xx1

17、25xxZx1x23311BACDE求求（LP212）121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且为整数12 2xx 14x 125630 xx125xxZx1x23311BACDE求求（LP212）F121212112112max5 256 30 4(212) 2 3 3,0ZxxxxxxxIPxxxxx 且为整数如图所示。此时如图所示。此时 F在点取在点取得最优解。得最优解。x13, x2 =2.5, Z(212)31/2=15.5 12 2xx 14x 125630 xx125xxZLP1x1=1, x2=3Z(1) 16

18、LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=2.4, x2=3Z(21) 17.4LP22无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13找到整数解，找到整数解，此枝停止计算此枝停止计算找到整数解，找到整数解，此枝停止计算此枝停止计算LP1x1=1, x2=3Z(1) 16LPx1=18/11, x2=40/11Z(0) 19.8LP2x1=2, x2=10/3Z(2) 18.5LP21x1=2.4, x2=3

19、Z(21) 17.4LP22无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=5/2Z(212) 15.5x11x12x23x24x12x13找到找到最优最优解解找到整数解，找到整数解，此枝停止计算此枝停止计算找到整数解，找到整数解，此枝停止计算此枝停止计算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无可无可行解行解LP211x1=2, x2=3Z(211) 17LP212x1=3, x2=

20、5/2Z(212) 15.5x11x12x23x24x12x13 至此，原问至此，原问题（题（IP）的最优）的最优解为：解为： x1=2， x2 =3, Z* = Z(211) 17以上的求解过程以上的求解过程可以用一个树形可以用一个树形图表示如右：图表示如右： 且全为整数且全为整数0,13651914max21212121xxxxxxxxZ练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （图解法）（图解法）LP1x1=1, x2=7/3Z(1) 10/3LPx1=3/2, x2=10/3Z(0) 29/6LP2x1=2, x2=23/9Z(2) 41/9x11x12LP

21、21x1=33/14, x2=2Z(21) 61/14LP22无可无可行解行解x22x23LP211x1=2, x2=2Z(211) 4LP212x1=3, x2=1Z(212) 4x12x13且且为为整整数数0,143292)(23max21212121xxxxxxIPxxZ3200CB XB b x1x2x3x40 x3921109/20 x414230114/2-Z032003200CB XB b x1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4 -1/4解解:用单纯形法解对应的用单纯形法解对应的(LP)问题问题,如表所示如表所示,

22、获得最优解。获得最优解。初始表初始表最终表最终表例二、用分枝定界法求解整数规划问题（单纯形法）例二、用分枝定界法求解整数规划问题（单纯形法） x1=13/4 x2=5/2 Z(0) =59/4=14.75 选选 x2 进行分枝，即增加两个约束，进行分枝，即增加两个约束， x2 2 , x2 3 有下式：有下式：且且为为整整数数0,2 14329 2) 1(23max212212121xxxxxxxIPxxZ且且为为整整数数0,3 14329 2)2(23max212212121xxxxxxxIPxxZ 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ，将新加约束条

23、件加入上表计算。，将新加约束条件加入上表计算。即即 x2+ x5= 2 , x2+x6=3 得下表得下表:32000CB XB b x1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200 x5201001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x5-1/2001/2 -1/21-Z-59/400-5/4-1/403x17/2101/20-1/22x22010010 x4100-11-2-Z-29/200-3/20-1/2x1=7/2, x2=2 Z(1) =29/2=14.5继续分枝，加入继续分

24、枝，加入约束约束 x1 3, x1 4LP132000CB XB b x1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/2 1/21-Z-59/400-5/4-1/403x15/21001/23/22x230100-10 x31001-1-2-Z-27/2000-3/2-5/2LP2x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝先不考虑分枝接接(LP1)继续分枝，加

25、入约束继续分枝，加入约束 x1 3， x1 4 有下式：有下式：且且为为整整数数0,3 2 14329 2)3(23max2112212121xxxxxxxxIPxxZ且且为为整整数数0,4 2 14329 2)4(23max2112212121xxxxxxxxIPxxZ分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。CB XB b x1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x410

26、0-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-3 x1=3, x2=2 Z(3) =13找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP3CB XB b x1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x8-1/

27、2001/20-1/21-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100-101-2-Z-1400-200-1 x1=4, x2=1 Z(4) =14找到整数解，找到整数解，问题已探明，问题已探明，停止计算。停止计算。LP4树形图如下：树形图如下：LP1x1=7/2, x2=2Z(1)29/2=14.5LPx1=13/4, x2=5/2Z(0) 59/4=14.75LP2x1=5/2, x2=3Z(2)27/2=13.5LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14121212112max5 256 30 4,0Zxxxxxxxxx 且全为整数练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （单纯形法）（单纯形法）