分枝定界法和割平面法

1、分枝定界法和割平面法 从数学模型上看整数规划似乎是线从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。不能保证所得到的解是整数可行解。3 分枝定界法分枝定界法例：设整数规划问题如下例：设整数规划问题如下 且为整数0,13651914max21212

2、121xxxxxxxxz 首先不考虑整数约束首先不考虑整数约束,得到线性规划问题（一般称为松弛问题）得到线性规划问题（一般称为松弛问题）0,13651914zmax21212121xxxxxxxx3 分枝定界法分枝定界法用图解法求出最优解用图解法求出最优解x13/2, x2 = 10/3且有且有z = 29/6x1x233(3/2,10/3) 现求整数解现求整数解(最优解最优解):如用如用“舍入取整法舍入取整法”可得可得到到4个点即个点即(1, 3) (2, 3) (1, 4) (2, 4).显然显然,它们都不可它们都不可能是整数规划的最优解能是整数规划的最优解. 按整数规划约束条件按整数规划

3、约束条件,其可行解肯定在线其可行解肯定在线性规划问题的可行域内且为整数点性规划问题的可行域内且为整数点.故整数规故整数规划问题的可行解集是一个有限集划问题的可行解集是一个有限集,如图所示如图所示. 因此因此, ,可将集合内的整数点一一找出可将集合内的整数点一一找出, ,其最大目标函数的值为最优解其最大目标函数的值为最优解, ,此法为完此法为完全枚举法全枚举法. . 如上例如上例: :其中其中(2, 2) (3,1)点为最大值点为最大值, ,z = 4. . 目前目前, ,常用的求解整数规划的方法有：常用的求解整数规划的方法有： 分枝定界法和割平面法；分枝定界法和割平面法； 对于特别的对于特别的

4、0 01 1规划问题采用隐枚举法和匈规划问题采用隐枚举法和匈牙利法。牙利法。3 分枝定界法分枝定界法 0 01 1整数规划求解整数规划求解 隐枚举法求解举例隐枚举法求解举例或12312312323123m a x z = 4 x+ 3 x+ 2 x2 x- 5 x+ 3 x = 3s .tx+ x = 1x , x, x= 01 解解:(1) 先用试探的方法找出一个初始可行解先用试探的方法找出一个初始可行解,如如x1x20,x31.满足约束条件满足约束条件,选其作为初始可行解选其作为初始可行解,目标函目标函数数z02. (2) 附加过滤条件附加过滤条件,以目标函数作为过滤约束：以目标函数作为过

5、滤约束： 4x13x22x3 = 2 原模型变为：原模型变为：或123 12312323123123m a x z = 4 x+ 3 x+ 2 x2 x- 5 x+ 3 x = 3(2 )x+ x = 1(3 )4 x+ 3 x+ 2 x = 2(4 )x , x, x= 01（3 3）求解）求解 求解过程如表求解过程如表4 46 6所示。所示。点点过滤条件过滤条件约束约束z值值 4x13x22x32 （0，0，0）T （0，0，1）T 2（0，1，0）T （0，1，1）T 5 4x13x22x35 （1，0，0）T （1，0，1）T （1，1，0）T 7 4x13x22x37 （1，1，1）

6、T 9 基本思路基本思路 11:max(min) z, (1,). .0,(1, )njjjnijjijjAc xa xbimstxjn 且为整数考虑纯整数问题考虑纯整数问题11:max min, (1,). .0(1, )njjjnijjijjBzc xa xbimstxjn 整数问题的松弛问题整数问题的松弛问题3 分枝定界法分枝定界法容易求解 第一步第一步: 先不考虑整数约束先不考虑整数约束,解解A的松弛问题的松弛问题B,可能得到以下情况之一可能得到以下情况之一:若若B没有可行解没有可行解,则则A也没有可行解也没有可行解,停止计算停止计算.若若B有最优解有最优解,并符合并符合A的整数条件的

7、整数条件,则则B的最优解即为的最优解即为A的最优解的最优解,停止计算停止计算.若若B有最优解有最优解,但不符合但不符合A的整数条件的整数条件,转入下一步转入下一步.为讨为讨论方便论方便,设设B的最优解为：的最优解为： .z), 1(,)0 , 0 ,(0)1)0(目标函数最优值为不全为整数mibbbXiTm3 分枝定界法分枝定界法第二步第二步: :定界定界 记记A的目标函数最优值为的目标函数最优值为z z* *, ,以以z z(0)(0)作为作为z z* * 的上界的上界, ,记为记为 =z=z(0)(0). .再用观察法找的一个整数可再用观察法找的一个整数可行解行解X X, ,并以其相应的目

8、标函数值并以其相应的目标函数值z z作为作为z z* *的下的下界界, ,记为记为z zz z, ,也可以令也可以令z z, ,则有则有: :z*zzz4 分枝定界法分枝定界法第三步第三步: :分枝分枝 在以上界在以上界 所对应的解所对应的解 中中, ,任选一个不符合整数条件的变量任选一个不符合整数条件的变量, ,例如例如 ( (不不为整数为整数),),以以 表示不超过表示不超过 的最大整数的最大整数. .构造构造两个约束条件两个约束条件 将这两个约束条件分别加入问题将这两个约束条件分别加入问题B B中中, ,形成形成两个子问题两个子问题B1B1和和B2,B2,再对这两个子问题进行求解再对这两

9、个子问题进行求解. .rbrbrb1rrrrxbxb和3 分枝定界法分枝定界法TmrbbbX)0 , 0 ,(1z 第四步第四步: : 修改上修改上、下界下界, ,按照以下两点规则按照以下两点规则进行进行 在各分枝问题中在各分枝问题中, ,找出目标函数值最大者找出目标函数值最大者 作为新的上界作为新的上界; ; 从已符合整数条件的分枝中从已符合整数条件的分枝中, ,找出目标函找出目标函 数值最大者作为新的下界数值最大者作为新的下界. .3 分枝定界法分枝定界法如此反复进行如此反复进行,直到得到直到得到 为止为止,即得即得最优解最优解 X* .第五步：比较与剪枝第五步：比较与剪枝 各分枝的目标函

10、数值中各分枝的目标函数值中,若有小于若有小于 者者,则剪则剪掉此枝掉此枝,表明此子问题已经探清表明此子问题已经探清,不必再分枝了不必再分枝了;否则继续分枝。否则继续分枝。 z3 分枝定界法分枝定界法*zzzv用分枝定界法解整数规划问题（图解法）例：考虑下面的整数规划问题3 分枝定界法分枝定界法12121212max40909756. .72070,0,zxxxxstxxx x且均取整数值用图解法求解上述线性规划问题B,转下页.v 第一步：寻找替代问题并求解.容易求解12121212:max40909756. .72070,0,Azxxxxstxxx x且均取整数值12121212:max409

11、09756. . 72070,0Bzxxxxstxxx x图解法分析： 、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 108 -7 -6 -5 -4 -3 -2 -1 -B12( 0 ):4.811.82356Bxxz不是A问题解但 ( 0 )zz356, 0zz定界：0,7020756799040max21212121xxxxxxxxz分枝： 12(0):4.811.82356Bxxzz4:11xB5:12xB356,0zz0,7020756799040max21212121xxxxxxxxz 0 1 2 3 4 5 6 7 43214:11xB2BB12

12、12121121: max40909+75672070. . 4,0Bzxxxxxxs txxx0,5 70 2075679.9040max:2211212121xxxxxxxtsxxzB接下来求出（接下来求出（B1）和（）和（B2）的最优解即可。）的最优解即可。v 分枝后原B问题转化成B1和B2两个子问题.图解法分析： 0 1 2 3 4 5 6 7 43214:11xB34910.200.4:)1(211zxxB34157.100.5:)2(212zxxB34903560zzzz和和修改上下界：2B12(0):4.811.82356Bxxz14x 15x 再分枝： 432134000.20

13、0.4:)11(2111zxxB32700.342.1:)12(2112zxxB 0 1 2 3 4 5 6 7 341340zz定界：是问题A解但 zz)11(12B11BzzxxB34910. 200. 4:)1(21123x22x不是问题A解而 剪枝 zz)12(121212121211: max40909+75672070. . 4 3,0Bzxxxxxxs txxxx0,2 4 70 2075679.9040max:122121212121xxxxxxxxtsxxzBv 分枝后原B1问题转化成B11和B12两个子问题.图解法分析： 0 1 2 3 4 5 6 7 432130800.

14、144.5:)21(2121zxxB无可行解:22B34157.100.5:2212zxxB12x22x341340zz21B分枝定界的全过程：35682.181.4:)0(21zxxB34910.200.4:)1(211zxxB34157.100.5:)2(212zxxB34000.200.4:)11(2111zxxB32700.342.1:)12(2112zxxB356,0zz3490zz341340zz41x51x22x32x分支定界的全过程：30800.144.5:)21(2121zxxB无可行解:22B12x22x34910.200.4:)1(211zxxB34157.100.5:)

15、2(212zxxB34000.200.4:)11(2111zxxB32700.342.1:)12(2112zxxB3490zz341340zz22x32x340zz12*42340 xxz最 优 解 ：目 标 函 数 最 大 值且全为整数0,13651914. .max21212121xxxxxxtsxxz练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （图解法）（图解法）B1x1=1, x2=7/3z(1) 10/3Bx1=3/2, x2=10/3z(0) 29/6B2x1=2, x2=23/9z(2) 41/9x11x12B21x1=33/14, x2=2z(21)

16、61/14B22无可无可行解行解x22x23B211x1=2, x2=2z(211) 4B212x1=3, x2=1z(212) 4x12x130,29 / 6zz0,41/ 9zz0,61/14zz4,4zz112223214.xxxxz原问题的解为：或目标函数最大值为4,即max且为整数0,143292. .23max)(21212121xxxxxxtsxxzIP解解:用单纯形法解上述问题用单纯形法解上述问题,如表所示如表所示,获得最优解：获得最优解：初始表初始表最终表最终表v 用分枝定界法求解整数用分枝定界法求解整数规划问题规划问题(单纯形法单纯形法) x1=13/4 x2=5/2 z(

17、0) 选选 x2 进行分枝进行分枝,即增加两个约束即增加两个约束,2 x2 3 有下式有下式:且为整数0,2 14329 2. .23max) 1(212212121xxxxxxxtsxxZIP且为整数0,3 14329 2. .23max)2(212212121xxxxxxxtsxxZIP 分别在分别在(LP1)和和(LP2)中引入松弛变量中引入松弛变量x5和和x6 ,将新加约将新加约束条件加入上表计算束条件加入上表计算.即即 x2+ x5= 2 ,x2+x6=3 得下表得下表: 上例续：x1=7/2, x2=2 z(1) =29/2=14.5继续分枝继续分枝,加入约束加入约束 3 x1 4

18、 考虑LP1： 考虑LP2：x1=5/2, x2=3 Z(2) Z(2) Z(1) 先不考虑分枝先不考虑分枝接接(LP1)继续分枝继续分枝,加入约束加入约束 4 x1 3,有下式：有下式：且为整数0,3 2 14329 2. .23max)3(2112212121xxxxxxxxtsxxZIP且为整数0,4 2 14329 2. .23max)4(2112212121xxxxxxxxtsxxZIP分别引入松弛变量分别引入松弛变量x7 和和 x8 ，然后进行计算。，然后进行计算。 上例续： x1=3,x2=2 z(3) =13找到整数解找到整数解,问题问题已探明已探明,停止计算停止计算. 考虑L

19、P3： x1=4, x2=1 z(4) =14找到整数解找到整数解,问题问题已探明已探明,停止计算停止计算. 考虑LP4：树形图如下：树形图如下：LP1x1=7/2, x2=2Z(1)LPx1=13/4, x2=5/2Z(0) LP2x1=5/2, x2=3Z(2)LP3x1=3, x2=2Z(3) 13LP4x1=4, x2=1Z(4) 14x22x23x13x14且全为整数0,4 30 652 .5min)(211212121xxxxxxxtsxxzIP练习：用分枝定界法求解整数规划问题练习：用分枝定界法求解整数规划问题 （单纯形法）（单纯形法）且全为整数0,4 30 652 - .5ma

20、x)(211212121xxxxxxxtsxxwLP先将问题转化成标准型：先将问题转化成标准型： 上述松弛问题的单纯形表：上述松弛问题的单纯形表：LP1x1=1, x2=3w(1) 16LPx1=18/11, x2=40/11w(0) LP2x1=2, x2=10/3w(2) LP3x1=12/5, x2=3w(3) LP4无可无可行解行解LP5x1=2, x2=3w(5) 17LP6x1=3, x2=5/2w(6) x11x12x23x24x12x13v 1958由由Gomory提出的一种求解整数规划问题的方法提出的一种求解整数规划问题的方法v基本思想：基本思想：v 依次引进线性约束条件依次

21、引进线性约束条件(称称Gomory约束或割平面约束或割平面)v 切割掉问题的部分非整数解切割掉问题的部分非整数解v 直到使问题的目标函数值达到最优的整数点成为直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点缩小后可行域的一个顶点4 割平面法割平面法 第一步：把问题中所有约束条件的系数均化为第一步：把问题中所有约束条件的系数均化为整数整数, ,用单纯形法求解该整数规划对应的松弛问题用单纯形法求解该整数规划对应的松弛问题. 若松弛问题没有可行解若松弛问题没有可行解,则原整数问题也没有可行则原整数问题也没有可行解解,停止计算停止计算. 若松弛问题有最优解若松弛问题有最优解,并符合原整

22、数问题的整数条并符合原整数问题的整数条件件,则该最优解即为原整数问题的最优解则该最优解即为原整数问题的最优解,停止计算停止计算. 若松弛问题有最优解若松弛问题有最优解,但不符合原整数问题的整数但不符合原整数问题的整数条件条件,转入下一步转入下一步. 4 割平面法割平面法第二步：从松弛问题的最优解中第二步：从松弛问题的最优解中, ,任选一个不为整任选一个不为整数的分量数的分量x xr,r, ,将最优单纯形表中该行的系数将最优单纯形表中该行的系数 和和 分解为整数部分和小数部分之和分解为整数部分和小数部分之和, ,并以该行为源行并以该行为源行, ,按下式作割平面方程：按下式作割平面方程：rjarb

23、 nmjjrjrxff10 的小数部分的小数部分的小数部分的小数部分rjarb4 割平面法割平面法第三步：将所得的割平面方程作为一个新的约束第三步：将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列条件置于最优单纯形表中（同时增加一个单位列向量）向量）, ,用对偶单纯形法求出新的最优解。用对偶单纯形法求出新的最优解。若表中得到的解仍为非整数解若表中得到的解仍为非整数解, ,重复第二步重复第二步. .4 割平面法割平面法 例例1：用割平面法求解整数规划问题：用割平面法求解整数规划问题且为整数0,023623 . .max)(2121212xxxxxxtsxzIP解：将上述问题的松弛问题记为解：将上述问题的松弛问题记为0,023623 . .max:12121212xxxxxxtsxzLP 续续：增加松弛变量增加松弛变量x3和和x4 ,得到得到LP1的初始单纯形的初始单纯形表和最优单纯形表：表和最优单纯形表：系数和常数项分解成整数和小数部分 此题的最优解为：此题的最优解为： ,但不是整数最但不是整数最优解优解,需引入割平面需引入割平面. 以以x2 为源行生成割平面为源行生成割平面: 21414143xx 例例1续：续：2/ 3, 121 xx234141432xxx211)410()410(432xxx432414121