运筹学_分支定界法课件

1、运筹学_分支定界法,（一）、基本思路,考虑纯整数问题：,整数问题的松弛问题：,第三节 分枝定界法,运筹学_分支定界法,考虑纯整数问题：,整数问题的松弛问题：,判断题：整数问题的最优函数值总是小于或等于其松弛问题的最优函数值。,运筹学_分支定界法,例一：用分枝定界法求解整数规划问题（用图解法计算）,记为（IP）,（二）、例题,运筹学_分支定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=12/5, x2=3 Z(21) 17.4,LP22 无可 行解,LP2

2、11 x1=2, x2=3 Z(211) 17,LP212 x1=3, x2=5/2 Z(212) 15.5,x11,x12,x23,x24,x12,x13,运筹学_分支定界法,例一：用分枝定界法求解整数规划问题（用图解法计算）,记为（IP）,解：首先去掉整数约束，变成一般线性规划问题,记为（LP）,运筹学_分支定界法,用图解法求（LP）的最优解，如图所示。,x1,x2,3,3,运筹学_分支定界法,x1,x2,3,3,(18/11,40/11),x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是（IP）最大值的上限。,运筹学_分支定界法,LP x1=18/1

3、1, x2=40/11 Z(0) 19.8,运筹学_分支定界法,x1,x2,3,3,(18/11,40/11),对于x118/111.64， 取值x1 1， x1 2 对于x2 =40/11 3.64，取值x2 3 ，x2 4,x118/11, x2 =40/11 Z(0) =218/11(19.8) 即Z 也是（IP）最大值的上限。,先将（LP）划分为（LP1）和（LP2）,取x1 1, x1 2,运筹学_分支定界法,现在只要求出（LP1）和（LP2）的最优解即可。,先将（LP）划分为（LP1）和（LP2）,取x1 1, x1 2，有下式：,运筹学_分支定界法,LP1 x1=？, x2=？

4、Z(1) ？,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=？, x2=？ Z(2) ？,x11,x12,运筹学_分支定界法,x1,x2,3,3,先求（LP1）,如图所示。,1,1,A,运筹学_分支定界法,x1,x2,3,3,先求（LP1）,如图所示。,1,1,B,A,此时B 在点取得最优解。 x11, x2 =3, Z(1)16,运筹学_分支定界法,LP1 x1=？, x2=？ Z(1) ？,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=？, x2=？ Z(2) ？,x11,x12,运筹学_分支定界法,LP1 x1=1, x2=

5、3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=？, x2=？ Z(2) ？,x11,x12,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,求（LP2） ,如图所示。,运筹学_分支定界法,x1,x2,3,3,1,1,在C 点取得最优解。 即x12, x2 =10/3, Z(2) 56/318.7,B,A,C,求（LP2） ,如图所示。,运筹学_分支定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=？, x2=？ Z(2) ？,x11,x12,运筹学_分支

6、定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.7,x11,x12,找到整数解，此枝停止计算,运筹学_分支定界法,在C 点取得最优解。 即x12, x2 =10/3, Z(2) 56/318.7,x1,x2,3,3,1,1,B,A,C,求（LP2） ,如图所示。,Z2 Z116 原问题可能有比（16）更大的最优解，但 x2 不是整数，故利用 x2 3 ， x2 4 加入条件。,运筹学_分支定界法,（LP）划分为（LP1）和（LP2）,x1 1, x1 2,运筹学_分支定界法

7、,对于LP2,加入条件： x23, x24 有下式：,只要求出（LP21）和（LP22）的最优解即可。,运筹学_分支定界法,x11,x12,x24,x23,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.7,LP21 x1=？, x2=？ Z(21) ？,LP22 x1=？, x2=？ Z(22) ？,找到整数解，此枝停止计算,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,先求（LP21）,如图所示。,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,先求（

8、LP21）,如图所示。,D,此时D 在点取得最优解。 即 x112/5=2.4, x2 =3, Z(21)87/5=17.4,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,D,求（LP22），如图所示。 无可行解，不再分枝。,运筹学_分支定界法,x11,x12,x24,x23,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.7,LP21 x1=？, x2=？ Z(21) ？,LP22 x1=？, x2=？ Z(22) ？,找到整数解，此枝停止计算,运筹学_分支定界法,

9、x11,x12,x24,x23,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.7,LP21 x1=2.4, x2=3 Z(21) 17.4,LP22 无可 行解,找到整数解，此枝停止计算,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,（LP21）,如图所示， 在D点取得最优解。 即 x112/5=2.4, x2 =3, Z(3)87/5=17.4,D,x12.4不是整数，可继续分枝。即 x12， x1 3,运筹学_分支定界法,运筹学_分支定界法,在（LP21）的基础

10、上继续分枝。加入条件x12， x1 3有下式：,只要求出（LP211）和（LP212）的最优解即可。,运筹学_分支定界法,x12,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=2.4, x2=3 Z(21) 17.4,LP22 无可 行解,LP211 x1=？, x2=？ Z(211) ？,LP212 x1=？, x2=？ Z(212) ？,x11,x12,x23,x24,x13,找到整数解，此枝停止计算,运筹学_分支定界法,先求（LP211）,x1,3,3,

11、1,1,B,A,C,D,x2,运筹学_分支定界法,先求（LP211）,x1,3,3,1,1,B,A,C,D,E,x2,如图所示，此时E 在点取得最优解 即 x12, x2 =3, Z(211)17,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,D,E,求（LP212）,运筹学_分支定界法,x1,x2,3,3,1,1,B,A,C,D,E,求（LP212）,F,如图所示。此时 F在点取得最优解。 x13, x2 =2.5, Z(212)31/2=15.5,运筹学_分支定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,

12、LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=2.4, x2=3 Z(21) 17.4,LP22 无可 行解,LP211 x1=2, x2=3 Z(211) 17,LP212 x1=3, x2=5/2 Z(212) 15.5,x11,x12,x23,x24,x12,x13,找到整数解，此枝停止计算,找到整数解，此枝停止计算,运筹学_分支定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=2.4, x2=3 Z(21) 17.4,LP

13、22 无可 行解,LP211 x1=2, x2=3 Z(211) 17,LP212 x1=3, x2=5/2 Z(212) 15.5,x11,x12,x23,x24,x12,x13,找到最优解,找到整数解，此枝停止计算,找到整数解，此枝停止计算,运筹学_分支定界法,LP1 x1=1, x2=3 Z(1) 16,LP x1=18/11, x2=40/11 Z(0) 19.8,LP2 x1=2, x2=10/3 Z(2) 18.5,LP21 x1=2.4, x2=3 Z(21) 17.4,LP22 无可 行解,LP211 x1=2, x2=3 Z(211) 17,LP212 x1=3, x2=5/

14、2 Z(212) 15.5,x11,x12,x23,x24,x12,x13,至此，原问题（IP）的最优解为： x1=2， x2 =3, Z* = Z(211) 17 以上的求解过程可以用一个树形图表示如右：,运筹学_分支定界法,练习：用分枝定界法求解整数规划问题 （图解法）,运筹学_分支定界法,x11,x12,x22,x23,x12,x13,运筹学_分支定界法,解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。,初始表,最终表,例二、用分枝定界法求解整数规划问题（单纯形法）,运筹学_分支定界法,x1=13/4 x2=5/2 Z(0) =59/4=14.75 选 x2 进行分枝，即增加两

15、个约束， x2 2 , x2 3 有下式：,分别在(LP1)和(LP2)中引入松弛变量x5和x6 ，将新加约束条件加入上表计算。即 x2+ x5= 2 , x2+x6=3 得下表:,运筹学_分支定界法,x1=7/2, x2=2 Z(1) =29/2=14.5 继续分枝，加入约束 x1 3, x1 4,LP1,运筹学_分支定界法,LP2,x1=5/2, x2=3 Z(2) =27/2=13.5 Z(2) Z(1) 先不考虑分枝,运筹学_分支定界法,接(LP1)继续分枝，加入约束 x1 3， x1 4 有下式：,分别引入松弛变量x7 和 x8 ，然后进行计算。,运筹学_分支定界法,x1=3, x2=2 Z(3) =13 找到整数解，问题已探明，停止计算。,LP3,运筹学_分支定界法,x1=4, x2=1 Z(4