分枝定界法和割平面法ppt课件.ppt

《分枝定界法和割平面法ppt课件.ppt》由会员分享，可在线阅读，更多相关《分枝定界法和割平面法ppt课件.ppt（55页珍藏版）》请在三一办公上搜索。

1、整数规划,整数规划的数学模型设置逻辑变量建立整数规划模型分配问题与匈牙利法分枝定界法、割平面法应用举例,从数学模型上看整数规划似乎是线性规划的一种特殊形式，求解只需在线性规划的基础上，通过舍入取整，寻求满足整数要求的解即可。但实际上两者却有很大的不同，通过舍入得到的解（整数）也不一定就是最优解，有时甚至不能保证所得到的解是整数可行解。,3 分枝定界法,例：设整数规划问题如下,首先不考虑整数约束,得到线性规划问题（一般称为松弛问题）,3 分枝定界法,用图解法求出最优解x13/2, x2 = 10/3且有z = 29/6,x1,x2,3,3,(3/2,10/3),现求整数解(最优解):如用“舍入取

2、整法”可得到4个点即(1, 3) (2, 3) (1, 4) (2, 4).显然,它们都不可能是整数规划的最优解.,按整数规划约束条件,其可行解肯定在线性规划问题的可行域内且为整数点.故整数规划问题的可行解集是一个有限集,如图所示.,因此,可将集合内的整数点一一找出,其最大目标函数的值为最优解,此法为完全枚举法. 如上例:其中(2, 2) (3,1)点为最大值,z = 4.,目前,常用的求解整数规划的方法有： 分枝定界法和割平面法； 对于特别的01规划问题采用隐枚举法和匈牙利法。,3 分枝定界法,01整数规划求解隐枚举法求解举例,解:(1) 先用试探的方法找出一个初始可行解,如x1x20,x3

3、1.满足约束条件,选其作为初始可行解,目标函数z02. (2) 附加过滤条件,以目标函数作为过滤约束： 4x13x22x3 = 2原模型变为：,（3）求解 求解过程如表46所示。,基本思路,考虑纯整数问题,整数问题的松弛问题,3 分枝定界法,容易求解,第一步: 先不考虑整数约束,解A的松弛问题B,可能得到以下情况之一:若B没有可行解,则A也没有可行解,停止计算.若B有最优解,并符合A的整数条件,则B的最优解即为A的最优解,停止计算.若B有最优解,但不符合A的整数条件,转入下一步.为讨论方便,设B的最优解为：,3 分枝定界法,第二步:定界 记A的目标函数最优值为z*,以z(0)作为z* 的上界,

4、记为 =z(0).再用观察法找的一个整数可行解X,并以其相应的目标函数值z作为z*的下界,记为zz,也可以令z,则有:,4 分枝定界法,第三步:分枝 在以上界 所对应的解 中,任选一个不符合整数条件的变量,例如 (不为整数),以 表示不超过 的最大整数.构造两个约束条件 将这两个约束条件分别加入问题B中,形成两个子问题B1和B2,再对这两个子问题进行求解.,3 分枝定界法,第四步: 修改上、下界,按照以下两点规则进行 在各分枝问题中,找出目标函数值最大者 作为新的上界; 从已符合整数条件的分枝中,找出目标函 数值最大者作为新的下界.,3 分枝定界法,如此反复进行,直到得到 为止,即得最优解 X

5、* .,第五步：比较与剪枝 各分枝的目标函数值中,若有小于 者,则剪掉此枝,表明此子问题已经探清,不必再分枝了;否则继续分枝。,3 分枝定界法,用分枝定界法解整数规划问题（图解法）,例：考虑下面的整数规划问题,3 分枝定界法,用图解法求解上述线性规划问题B,转下页.,第一步：寻找替代问题并求解.,容易求解,图解法分析：,、 、 、 、 、 、 、 、 、 、 、0 1 2 3 4 5 6 7 8 9 10,8 -7 -6 -5 -4 -3 -2 -1 -,B,不是A问题解但,分枝：,0 1 2 3 4 5 6 7,4321,B,接下来求出（B1）和（B2）的最优解即可。,分枝后原B问题转化成B

6、1和B2两个子问题.,图解法分析：,0 1 2 3 4 5 6 7,4321,再分枝：,4321,0 1 2 3 4 5 6 7,是问题A解但,不是问题A解而 剪枝,分枝后原B1问题转化成B11和B12两个子问题.,图解法分析：,分枝定界的全过程：,分支定界的全过程：,练习：用分枝定界法求解整数规划问题 （图解法）,x11,x12,x22,x23,x12,x13,解:用单纯形法解上述问题,如表所示,获得最优解：,初始表,最终表,用分枝定界法求解整数规划问题(单纯形法),x1=13/4 x2=5/2 z(0) =59/414.75 选 x2 进行分枝,即增加两个约束,2 x2 3 有下式:,分别

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

8、解,问题已探明,停止计算.,考虑LP4：,树形图如下：,LP1x1=7/2, x2=2Z(1)29/2=14.5,LPx1=13/4, x2=5/2Z(0) 59/4=14.75,LP2x1=5/2, x2=3Z(2)27/2=13.5,LP3x1=3, x2=2Z(3) 13,LP4x1=4, x2=1Z(4) 14,x22,x23,x13,x14,练习：用分枝定界法求解整数规划问题 （单纯形法）,先将问题转化成标准型：,上述松弛问题的单纯形表：,LP1x1=1, x2=3w(1) 16,LPx1=18/11, x2=40/11w(0) 19.8,LP2x1=2, x2=10/3w(2) 1

9、8.5,LP3x1=12/5, x2=3w(3) 17.4,LP4无可行解,LP5x1=2, x2=3w(5) 17,LP6x1=3, x2=5/2w(6) 15.5,x11,x12,x23,x24,x12,x13,1958由Gomory提出的一种求解整数规划问题的方法基本思想： 依次引进线性约束条件(称Gomory约束或割平面) 切割掉问题的部分非整数解 直到使问题的目标函数值达到最优的整数点成为缩小后可行域的一个顶点,4 割平面法,第一步：把问题中所有约束条件的系数均化为整数,用单纯形法求解该整数规划对应的松弛问题. 若松弛问题没有可行解,则原整数问题也没有可行解,停止计算. 若松弛问题有

10、最优解,并符合原整数问题的整数条件,则该最优解即为原整数问题的最优解,停止计算. 若松弛问题有最优解,但不符合原整数问题的整数条件,转入下一步.,4 割平面法,第二步：从松弛问题的最优解中,任选一个不为整数的分量xr,将最优单纯形表中该行的系数 和 分解为整数部分和小数部分之和,并以该行为源行,按下式作割平面方程：,的小数部分,的小数部分,4 割平面法,第三步：将所得的割平面方程作为一个新的约束条件置于最优单纯形表中（同时增加一个单位列向量）,用对偶单纯形法求出新的最优解。若表中得到的解仍为非整数解,重复第二步.,4 割平面法,例1：用割平面法求解整数规划问题,解：将上述问题的松弛问题记为,续

11、：,增加松弛变量x3和x4 ,得到LP1的初始单纯形表和最优单纯形表：,系数和常数项分解成整数和小数部分,此题的最优解为： ,但不是整数最优解,需引入割平面. 以x2 为源行生成割平面:,例1续：,现将生成的割平面条件加入松弛变量，然后加到表中：,此时, ,仍不是整数解. 继续以x1为源行生成割平面,得到Gomory约束为：,例1续：,将生成的割平面条件加入松弛变量,然后加到下表中:,例1续：,至此得到最优表,其最优解为 X= (1 , 1) , z = 1, 这也是原整数问题的最优解。,由以上解题过程可见,表中含有分数元素且算法过程中始终保持对偶可行性,因此算法也称为分数对偶割平面法。,例1续：,例2：用割平面法求解整数规划问题,4 割平面法,初始表,最终表,先给出其松弛问题的初始单纯形表和最终 单纯形表：,以x2为源行得到的割平面方程：,引入松弛变量s1 后得到下式,将此约束条件加到上表中,继续求解。,例2续：,得到整数最优解，即为整数规划的最优解，而且此整数规划有两个最优解： X= (0, 4), z = 4, 或 X= (2, 2), z = 4。,作业：P145 4.9P147 4.15,结束！,