3.2分枝定界法
分枝定界法的原理: 1、分枝对mx2=33x+20145 4x,+x≤16.5 松弛问 X,≥0 题的可 为整数 行域 松弛问题(L0) max=30x1+20x2 2x1+3x,≤14.5 s4x1+x2≤16.5 松弛问题的最优解: x,=3.5x=2.5 L212345678
一、分枝定界法的原理： 1、分枝 + + = + 为整数 对 1 2 1 2 1 2 1 2 1 2 , 0, 0 4 16.5 2 3 14.5 . max 30 20 x x x x x x x x st z x x + + = + 0, 0 4 16.5 2 3 14.5 . max 30 20 ( ) 1 2 1 2 1 2 1 2 0 x x x x x x st z x x 松弛问题 L ： x1 = 3.5, x2 = 2.5 松弛问题的最优解： · · · · · · · · · · · · · · · · · ·0 1 2 3 4 5 6 7 8 · 松弛问 题的可 行域 L1 L2
对(P)maxz=30x+20x2 松弛问题(Lo) 2x1+3x,≤14.5 maxz=30x1+20x2最优解: 4x1+x2≤16.5 2x1+3x2≤14.5 3.5 s t 4x1+x2≤165 ≥0,x,≥0 2.5 ≥0,x2≥0 x1,x2为整数 父问 )max=30x120x2(k2)mxz=30x1+20x2 子问题 2x1+3x2≤14.5 2x1+3x2≤145 4x1+x2≤165 st 4x1+x2≤16.5 <3 s t. ≥0,x2≥0 x1≥0,x2≥0 论1:(I)的最优解一定在某个子问题中 2:子问题的可行域c父问题的可行域 →子问题的最优解<父问题的最优值 3:子问题中的整数解都是(IP)的可行解
+ + = + 0, 0 4 16.5 2 3 14.5 . max 30 20 ( ) 1 2 1 2 1 2 1 2 0 x x x x x x st z x x 松弛问题 L ： + + = + 0, 0 3 4 16.5 2 3 14.5 . ( )max 30 20 1 2 1 1 2 1 2 1 1 2 x x x x x x x st L z x x + + = + 0, 0 4 4 16.5 2 3 14.5 . ( )max 30 20 1 2 1 1 2 1 2 2 1 2 x x x x x x x st L z x x 父问题 子问题 结论1 ：（IP）的最优解一定在某个子问题中 ≤ 父问题的最优值 + + = + 为整数 对（ ） 1 2 1 2 1 2 1 2 1 2 , 0, 0 4 16.5 2 3 14.5 . max 30 20 x x x x x x x x st IP z x x 2.5 3.5, 2 1 = = x x 最优解： 3 ：子问题中的整数解都是（IP）的可行解 子问题的最优解 2 ：子问题的可行域 父问题的可行域
2、定界 对整数规划问题Ⅰ max z= CX 及其松弛问题LP max z= CX aX=b ∫AX=b sX≥0 X≥0 x,为整数 1、(LP)的最优值是(P)的最优值的上界 2、若LP可以找到一个整数解X, 则CX是P最优值的下界
2、定界 = = 为整数 对整数规划问题 j x X AX b st z CX IP . 0 max = = 0 . max X AX b st z CX 及其松弛问题LP 1、（LP）的最优值是(IP)的最优值的上界 2、若LP可以找到一个整数解X， 则CX是IP最优值的下界
IP 2≤2,1≤Z或z≤Z 最优值z 若某个L的最优解X*是整数解 则x*是(P)的可行解,有CX*≤Z 松弛问题L0 即找到Z的下界CX*,关闭L 最优值z 讨论子问题Lk 若L的最优值Z≤CX*,剪枝 若L的最优值z>CX*: 最优值Z最优值z,()最优解X*是整数解 将下界改为CX*,,关闭Lk (2)最优解X*不是整数解 继续对L分枝 通过对(L0)分枝,使(P)的最优值上界=下界 的上界不断下降,下界不断上升 得最优值
IP 最优值ZI 松弛问题L0 L0 最优值Z L0 ZI Z L1 L2 L1 最优值Z L2 最优值Z L1 L0 Z Z L2 L0 Z Z 1 , ZI ZL L2 或ZI Z 通过对（L0）分枝，使（IP）的最优值 的上界不断下降， L3 L4 L5 L6 若某个Li 0 的最优解X * i 0 是整数解 则X * i 0 是(IP)的可行解 CX i ZI 0 ,有 * * , 0 若Lk 的最优值Zk CX i 即找到ZI 的下界 * , 将下界改为CX k 0 ,关闭Li (1)最优解X * k 是整数解 剪枝 若Lk 的最优值Zk CX * i 0 ： : 讨论子问题Lk 0 CX * i 关闭Lk , (2)最优解X * k 不是整数解 继续对Lk 分枝 下界不断上升， 上界=下界 得最优值
分枝定界法的基本思路: 通过对松弛问题的分枝, 不断降低(P)最优值的上界,提高下界, 当上界等于下界时,得到最优解
分枝定界法的基本思路： 不断降低（IP）最优值的上界，提高下界， 当上界等于下界时，得到最优解 通过对松弛问题的分枝
分枝定界法计算过程: 上界 讨论松弛问题L 1、L无最优解,则俨)无最优解结東 2、最优解X*=(x*01,x*m2…,x*n)最优值z0 (1)X*为整数解,则X*为)的最优解结束 (2)X*中至少有一个是分数,设x*01是分数:分枝 Xy 子问题L1 子问题L2 L无最优解,剪枝 2、最优解X*=( x11 最优值 (1)X*1为整数解,1为下界关闭 (2)X*中至少有一个是分数 继续分枝
分枝定界法计算过程： : 讨论松弛问题L0 1、L0无最优解，则(IP)无最优解 结束 0 0 1 0 2 0 2 X * (x * x * , , x * ), z 、最优解 = ， o n 最优值 (1)X * 0 为整数解 ，则X * 0 为(IP)的最优解 (2)X * 0 中至少有一个是分数， 结束 设x * 01 是分数 ：分枝 上界 : 子问题L1 : 子问题L2 1、L1无最优解，剪枝,z1 为下界 关闭 继续分枝 1 1 11 12 1 2 * ( * * , , * ), z X x x x n 最优值 、最优解 = ， (1)X * 1 为整数解 (2)X * 1中至少有一个是分数：
设口找到下界Z, 讨论子问题Lk: 若L的最优值zk≤CX*,剪枝 若L的最优值Z>CX*: (1)最优解X*是整数解 将下界改为CX*,,关闭L (2)最优解X*不是整数解 继续对L分枝 当所有的子问题均被关闭或剪枝后 目标函数值最大的整数解既为所求的最优解
* , 0 若Lk 的最优值Zk CX i 设已找到下界Zi 0 ： * , 将下界改为CX k (1)最优解X * k 是整数解剪枝 若Lk 的最优值Zk CX * i 0 ： : 讨论子问题Lk 关闭Lk , (2)最优解X * k 不是整数解 继续对Lk 分枝 当所有的子问题均被关闭或剪枝后 目标函数值最大的整数解既为所求的最优解
o:x1=3.5,x2=2.5,z0=155 松弛问题L: maxz=30x,+20x 2x1+3x,≤14.5 n4x1+x2≤16 0,x2≥0 440 130剪校(P)最优解:x1=3,x2=2 最优值:Z*=130 4x1+x2=165 2 130 285 关闭 2x1+3x2-14.5 1sx=2x=o剪枝 z=30X1+20 剪枝==1302无可行解最优解:=35x=25
+ + = + 1 2 为整数 1 2 1 2 1 2 1 2 , 0, 0 4 16.5 2 3 14.5 . max 30 20 x x x x x x x x st z x x + + = + 0, 0 4 16.5 2 3 14.5 . max 30 20 1 2 1 2 1 2 1 2 0 x x x x x x st z x x 松弛问题L ： · · · · · · · · · · · · · · · · · ·0 1 2 3 4 5 6 7 8 · : L0 x1 = 3.5，x2 = 2.5,z0 =155 : L1 3 440 , 6 17 3 1 1 2 = = = z x ，x 4x1+x2=16.5 2x1+3x2=14.5 2 3 2 1 = = x ：x 130 z3 = 关闭 3 4 11 1 2 x = ，x = 2 285 z4 = 3 z 2 7 2 1 2 x = ，x = 130 z5 = 无可行解 剪枝 2 1 4 1 2 x = ，x = z2 =130剪枝 3.5 2.5, 最优解：x1 = ，x2 = : L2 L3 L4 L5 剪枝 L6 * 130 ( ) 3 2 1 2 = = = Z IP x x 最优值： 的最优解：
课堂练习: max z=3x,+2x 2x,+ 2x,+3x<14 s t x1≥0,x,≥0 E.x 2 为整数 答案:最优解:x1=4,x2=1 最优值:Z*=14
课堂练习： + + = + 1 2 为整数 1 2 1 2 1 2 1 2 , 0, 0 2 3 14 2 9 . max 3 2 x x x x x x x x st z x x * 14 1 4 2 1 = = = Z x x 最优值： 答案：最优解：