(6.2.1)--06_2分支定界法.pdf
分枝定界解法1、算法依据:对于目标函数值来讲，整数规划的最优解不会更优于相应线性规划问题的最优解。整数规划与其松弛问题:当放弃整数约束时得到的线性规划称为整数规划的松弛问题。整数规划的可行域是松弛问题的可行域，反之不成立。基本思想:设有最大化整数规划问题A,相应的线性规划问题为B.从解B开始,若最优解不符合A的条件,那么B的最优目标函数值必是A的最优目标函数值Z*的上界,记为,而A的任意可行解对应的目标函数值将是Z*的一个下界Z,分支定界法就是将B可行域分为子区域(分支)方法,逐步减少上界和增大下界,最终求得Z*。分枝定界法就是将问题的可行域分成子区域（分枝）。具体步骤:1、先不考虑整数约束，解(IP)的松弛问题(LP)，可能得到以下情况之一：.若(LP)没有可行解，则(IP)也没有可行解，停止计算。.若(LP)有最优解，并符合(IP)的整数条件，则(LP)的最优解即为(IP)的最优解，停止计算。.若(LP)有最优解，但不符合(IP)的整数条件，转入下一步。为讨论方便，设(LP)的最优解为：2、定界：记(IP)的目标函数最优值为Z*,以Z(0)作为Z*的上界，记为 Z(0)。再用观察法找的一个整数可行解 X，并以其相应的目标函数值 Z作为Z*的下界，记为Z Z，也可以令Z，则有：Z Z*3、分歧：在(LP)的最优解 X(0)中，任选一个不符合整数条件的变量，例如xr=（不为整数），以表示不超过的最大整数。构造两个约束条件xr 和 xr 1将这两个约束条件分别加入问题(IP)，形成两个子问题(IP1)和(IP2)，再解这两个问题的松弛问题(LP1)和(LP2)。4、修改上、下界：按照以下两点规则进行。.在各分枝问题中，找出目标函数值最大者作为新的上界；.从已符合整数条件的分枝中，找出目标函数值最大者作为新的下界。5、比较与剪枝：各分枝的目标函数值中，若有小于Z 者，则剪掉此枝，表明此子问题已经探清，不必再分枝了;否则继续分枝。如此反复进行，直到得到ZZ*为止，即得最优解X*。情况 2,4,5 找到最优解情况 3 在缩减的域上继续分枝定界法情况 6 问题 1 的整数解作为界被保留，用于以后与问题 2 的后续分枝所得到的解进行比较，结论如情况 4或5分枝问题解可能出现的情况例1:解：先不考虑x1,x2为非负整数的条件，得最优解:x13/2，x2=10/3，z0=29/6。它不符合整数条件，Z0作为Z*的上界。显然，(0,0)是问题A的一个整数可行解。0z*29/6S132x254x1123对S分枝：先注意其中一个非负整数变量的解。如：x1形成分枝问题S1和S2，分别得最优解Z1和Z2这时没有得到全部变量都是整数的解。因Z1Z2，故先考察S1这一枝。且41/929/6,故0Z*41/9x13/2，x2=10/3，z0=29/6。构造约束：X12 和 X11132x254zx1123S2S1)310,23(A)37,1(C)923,2(B S1问题S2问题对S1分枝：形成分枝问题S11和S12，得解D构造约束：X23 和 X22132x254zx1123S11无可行域，无可行解。因61/1441/9,故0Z*61/1411)310,23(AS2S12)2,1433(D对S12分枝：形成分枝问题S121和S122，得解E和F构造约束：X13 和 X12132x254zx1123D:x1=33/14,x2=2,Z3=61/14解E和F的变量皆为整数，故4Z*61/14)310,23(AS2S121)1,3(E)2,2(FS122对于分枝S2，最优值Z210/3，小于4，所以不必讨论。因4与61/14之间只有4一个整数，故4为所求整数规划问题目标函数的最优值。最优解为(3,1)(2,2)。分枝定界法是计算机求解整数规划，进行迭代的基础。原理3200CBXBbx1x2x3x40 x3921109/20 x414230114/2-Z03200解:用单纯形法解对应的(LP)问题,如表所示,获得最优解。初始表最终表例、用分枝定界法求解整数规划问题（单纯形法）3200CBXBbx1x2x3x43x113/4103/4-1/42x25/201-1/21/2-Z-59/400-5/4-1/4x1=13/4 x2=5/2 Z(0)=59/414.75选 x2 进行分枝，即增加两个约束，2 x23 有下式：分别在(LP1)和(LP2)中引入松弛变量x5和x6，将新加约束条件加入上表计算。即 x2+x5=2,x2+x6=3 得下表:x1=7/2,x2=2 Z(1)=29/2=14.5继续分枝，加入约束3 x14LP132000CBXBbx1x2x3x4x53x113/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/23x113/4103/4-1/402x25/201-1/21/200 x6-1/200-1/21/21-Z-59/400-5/4-1/40 x1=5/2,x2=3 Z(2)=27/2=13.5 Z(2)Z(1)先不考虑分枝LP232000CBXBbx1x2x3x4x63x113/4103/4-1/402x25/201-1/21/200 x6-30-1001-Z-59/400-5/4-1/403x15/21001/23/22x23010010 x31001-1-2-Z-27/2000-3/2-5/2接(LP1)继续分枝，加入约束 4 x1 3，有下式：分别引入松弛变量x7 和 x8，然后进行计算。x1=3,x2=2 Z(3)=13找到整数解，问题已探明，停止计算。LP3CBXBbx1x2x3x4x5x73x17/2101/20-1/202x220100100 x4100-11-200 x73100001-Z-29/200-3/20-1/203x17/2101/20-1/202x220100100 x4100-11-200 x7-1/200-1/201/21-Z-29/200-3/20-1/203x131000012x220100100 x420001-3-20 x310010-1-2-Z-130000-2-33x17/2101/20-1/202x220100100 x4100-11-200 x8-1/2001/20-1/21-Z-29/200-3/20-1/20 x1=4,x2=1 Z(4)=14找到整数解，问题已探明，停止计算。LP4CBXBbx1x2x3x4x5x83x17/2101/20-1/202x220100100 x4100-11-200 x8-4-100001-Z-29/200-3/20-1/203x1410000-12x210110020 x4300-310-40 x5100101-2-Z-1400-200-1树形图如下：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)14x22x23x13x14
