4.3-分枝定界法和割平面法

整数规划整数规划的数学模型设置逻辑变量建立整数规划模型分配问题与匈牙利法分枝定界法、割平面法应用举例从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。§3分枝定界法例：设整数规划问题如下且为整数0,13651914max21212121xxxxxxxxz首先不考虑整数约束,得到线性规划问题（一般称为松弛问题）0,13651914zmax21212121xxxxxxxx§3分枝定界法用图解法求出最优解x1＝3/2,x2=10/3且有z=29/6x1x2⑴⑵33(3/2,10/3)现求整数解(最优解):如用“舍入取整法”可得到4个点即(1,3)(2,3)(1,4)(2,4).显然,它们都不可能是整数规划的最优解.按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点.故整数规划问题的可行解集是一个有限集,如图所示.因此,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法.如上例:其中(2,2)(3,1)点为最大值,z=4.目前,常用的求解整数规划的方法有：分枝定界法和割平面法；对于特别的0－1规划问题采用隐枚举法和匈牙利法。§3分枝定界法0－1整数规划求解隐枚举法求解举例或12312312323123maxz=4x+3x+2x2x-5x+3x=44x+x+3x=3s.tx+x=1x,x,x=01解:(1)先用试探的方法找出一个初始可行解,如x1＝x2＝0,x3＝1.满足约束条件,选其作为初始可行解,目标函数z0＝2.(2)附加过滤条件,以目标函数作为过滤约束：4x1＋3x2＋2x3=2原模型变为：或12312312323123123maxz=4x+3x+2x2x-5x+3x=4(1)4x+x+3x=3(2)x+x=1(3)4x+3x+2x=2(4)x,x,x=01（3）求解求解过程如表4－6所示。点过滤条件约束z值④①②③4x1＋3x2＋2x3≥2（0，0，0）T×（0，0，1）T√√√√2（0，1，0）T√√×（0，1，1）T√√√√54x1＋3x2＋2x3≥5（1，0，0）T×（1，0，1）T√×（1，1，0）T√√√√74x1＋3x2＋2x3≥7（1，1，1）T√√√√9基本思路11:max(min)z,(1,,)..0,(1,,)njjjnijjijjAcxaxbimstxjn且为整数考虑纯整数问题11:maxmin,(1,,)..0(1,,)njjjnijjijjBzcxaxbimstxjn整数问题的松弛问题§3分枝定界法容易求解第一步:先不考虑整数约束,解A的松弛问题B,可能得到以下情况之一:若B没有可行解,则A也没有可行解,停止计算.若B有最优解,并符合A的整数条件,则B的最优解即为A的最优解,停止计算.若B有最优解,但不符合A的整数条件,转入下一步.为讨论方便,设B的最优解为：.z),,1(,)0,,0,,,((0)1)0(目标函数最优值为不全为整数mibbbXiTm§3分枝定界法第二步:定界记A的目标函数最优值为z*,以z(0)作为z*的上界,记为=z(0).再用观察法找的一个整数可行解X′,并以其相应的目标函数值z′作为z*的下界,记为z＝z′,也可以令z＝－∞,则有:z*zzz§4分枝定界法第三步:分枝在以上界所对应的解中,任选一个不符合整数条件的变量,例如(不为整数),以表示不超过的最大整数.构造两个约束条件将这两个约束条件分别加入问题B中,形成两个子问题B1和B2,再对这两个子问题进行求解.rb[]rbrb1rrrrxbxb和§3分枝定界法TmrbbbX)0,,0,,,,,(1z第四步:修改上、下界,按照以下两点规则进行在各分枝问题中,找出目标函数值最大者作为新的上界;从已符合整数条件的分枝中,找出目标函数值最大者作为新的下界.§3分枝定界法如此反复进行,直到得到为止,即得最优解X*.第五步：比较与剪枝各分枝的目标函数值中,若有小于者,则剪掉此枝,表明此子问题已经探清,不必再分枝了;否则继续分枝。z§3分枝定界法*zzz用分枝定界法解整数规划问题（图解法）例：考虑下面的整数规划问题§3分枝定界法12121212max40909756..72070,0,zxxxxstxxxx且均取整数值用图解法求解上述线性规划问题B,转下页.第一步：寻找替代问题并求解.容易求解12121212:max40909756..72070,0,Azxxxxstxxxx且均取整数值12121212:max40909756..72070,0Bzxxxxstxxxx图解法分析：、、、、、、、、、、、0123456789108-7-6-5-4-3-2-1-B12(0):4.811.82356Bxxz不是A问题解但(0)zz356,0zz定界：0,7020756799040max21212121xxxxxxxxz分枝：12(0):4.811.82356Bxxzz4:11xB5:12xB356,0zz0,7020756799040max21212121xxxxxxxxz0123456743214:11xB2BB1212121121:max40909+75672070..4,0Bzxxxxxxstxxx0,5702075679..9040max:2211212121xxxxxxxtsxxzB接下来求出（B1）和（B2）的最优解即可。分枝后原B问题转化成B1和B2两个子问题.图解法分析：0123456743214:11xB34910.200.4:)1(211zxxB34157.100.5:)2(212zxxB34903560zzzz和和修改上下界：2B12(0):4.811.82356Bxxz14x15x再分枝：432134000.200.4:)11(2111zxxB32700.342.1:)12(2112zxxB01234567341340zz定界：是问题A解但zz)11(12B11BzzxxB34910.200.4:)1(21123x22x不是问题A解而剪枝zz)12(121212121211:max40909+75672070..43,0Bzxxxxxxstxxxx0,24702075679..9040max:122121212121xxxxxxxxtsxxzB分枝后原B1问题转化成B11和B12两个子问题.图解法分析：01234567432130800.144.5:)21(2121zxxB无可行解:22B34157.100.5:2212zxxB12x22x341340zz21B分枝定界的全过程：35682.181.4:)0(21zxxB34910.200.4:)1(211zxxB34157.100.5:)2(212zxxB34000.200.4:)11(2111zxxB32700.342.1:)12(2112zxxB356,0zz3490zz341340zz41x51x22x32x分支定界的全过程：30800.144.5:)21(2121zxxB无可行解:22B12x22x34910.200.4:)1(211zxxB34157.100.5:)2(212zxxB34000.200.4:)11(2111zxxB32700.342.1:)12(2112zxxB3490zz341340zz22x32x340zz12*42340xxz最优解：目标函数最大值且全为整数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/9x1≤1x1≥2B21x1=33/14,x2=2z(21)＝61/14B22无可行解x2≤2x2≥3B211x1=2,x2=2z(211)＝4B212x1=3,x2=1z(212)＝4x1≤2x1≥30,29/6zz0,41/9zz0,61/14zz4,4zz112223214.xxxxz原问题的解为：或目标函数最大值为4,即max且为整数0,143292..23max)(21212121xxxxxxtsxxzIP3200CBXBbx1x2x3x40x3921109/20x414230114/2Z032003200CBXBbx1x2x3x43x113/4103/4-1/42x25/201-1/21/2Z59/400-5/4-1/4解:用单纯形法解上述问题,如表所示,获得最优解：初始表最终表用分枝定界法求解整数规划问题(单纯形法)x1=13/4x2=5/2z(0)=59/4≈14.75选x2进行分枝,即增加两个约束,2≥x2≥3有下式:且为整数0,2143292..23max)1(212212121xxxxxxxtsxxZIP且为整数0,3143292..23max)2(212212121xxxxxxxtsxxZIP分别在(LP1)和(LP2)中引入松弛变量x5和x6,将新加约束条件加入上表计算.即x2+x5=2,－x2+x6=－3得下表:上例续：32000CBXBbx1x2x3x4x53x113/4103/4-1/402x25/201-1/21/200x5201001Z59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x5-1/2001/2-1/21Z59/400-5/4-1/403x17/2101/20-1/22x22010010x4100-11-2Z29/200-3/20-1/2x1=7/2,x2=2z(1)=29/2=14.5继续分枝,加入约束3≥x1≥4考虑LP1：32000CBXBbx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200x6-30-1001Z59/400-5/4-1/403x113/4103/4-1/402x25/201-1/21/200x6-1/200-1/21/21Z59/400-5/4-1/403x15/21001/23/22x230100-10x31001-1-2Z27/2000-3/2-5/2考虑LP2：x1=5/2,x2=3Z(2)=27/2=13.5∵Z(2)Z(1)∴先不考虑分枝接(LP1)继续分枝,加入约束4≤x1≤3,有下式：且为整数0,32143292..23max)3(2112212121xxxxxxxxtsxxZIP且为整数0,42143292..23max)4(2112212121xxxxxxxxtsxxZIP分别引入松弛变量x7和x8，然后进行计算。上例续：CBXBbx1x2x3x4x5x73x1