运筹学3.2割平面算法.ppt

《运筹学3.2割平面算法.ppt》由会员分享，可在线阅读，更多相关《运筹学3.2割平面算法.ppt（19页珍藏版）》请在优知文库上搜索。

1、 3.2 割平面算法OR第三章 整数线性规划1958 R.E.Gomory 提出割平面提出割平面(cutting plane)的概念的概念理论依据理论依据:IP与与LP之间的关系之间的关系,即前述的即前述的“conv(S)”结论结论基本思想基本思想:考虑纯考虑纯IP:Tnmins.t.0c xAxbxxZ放弃该约束放弃该约束 Tmins.t.0c xAxbx称为称为(IP)的的松弛问题松弛问题Abc、均均为为整整值值0()P()IPOR第三章 整数线性规划但原但原(IP)的任一可行解均未被切割掉的任一可行解均未被切割掉 否则否则,对对()增加一个线性约束增加一个线性约束(几何上为超平面几何上为

2、超平面,故故称为割平面条件称为割平面条件)0P用单纯形法或别的方法求解用单纯形法或别的方法求解(IP)的松弛问题的松弛问题(),得其最优解得其最优解 ,0P0 x若若 为整数向量为整数向量STOP,亦为亦为(IP)的最优解的最优解.0 x0 x该割平面条件将该割平面条件将()的可行域割掉一部分的可行域割掉一部分,且使这个非整数且使这个非整数向量向量 恰好在被割掉的区域内恰好在被割掉的区域内0P0 x 新的新的 松弛问题松弛问题改进的松弛问题改进的松弛问题1()P费用减小费用减小0 x1x2xOR第三章 整数线性规划按上述增加约束、逐步迭代的过程中按上述增加约束、逐步迭代的过程中,若某步所得的松

3、弛若某步所得的松弛LP问题问题无可行解无可行解无界无界原问题原问题(IP)亦不可行亦不可行原问题原问题(IP)或不可行或无界或不可行或无界STOP割平面法为一种松弛方法割平面法为一种松弛方法!关键关键:如何生成割平面如何生成割平面,不同的构造方法将产生不同的算法不同的构造方法将产生不同的算法.OR第三章 整数线性规划0 x0 xGomory 分数割平面算法分数割平面算法0P0 x 设用单纯形法求解设用单纯形法求解(IP)的松弛问题的松弛问题()所得的最优基本所得的最优基本可行解为可行解为 :1mBB,BAA基基1mBB,xx基基变变量量下标集合记为下标集合记为 ,而非基变量下标集为而非基变量下

4、标集为SS迭代终止时目标函数、各个约束条件对应的典式分别为迭代终止时目标函数、各个约束条件对应的典式分别为:ijj0j SBijjij S,1,zxzxa xbim0B0jj00,xz abz0B0jj0j Sxa xb0,1,im若对所有的若对所有的 ,均为整数均为整数i0,1,im b0 xSTOP!已经是已经是(IP)的最优解的最优解OR第三章 整数线性规划否则否则,至少存在某一个至少存在某一个 ,使得使得 不是整数不是整数.:0lllmb Bjjj Slllxa xb诱导诱导(生成生成)方程方程jjjj,01,01,llllllllbbffaafajS 由变量的非负性由变量的非负性jj

5、jjj Sj Sllaxa x生成方程变为生成方程变为:Bjjj Slllxaxb左边取值必为整数值左边取值必为整数值Bjjj Slllxaxb 从诱导方程中减去该不等式从诱导方程中减去该不等式 OR第三章 整数线性规划jjjj Sllllaaxbb jjj Sllf xfjjj Sllf xsf 引进松弛变量引进松弛变量S对应于生成行对应于生成行l 的的Gomory割平面条件割平面条件系数为分数系数为分数 分数割平面分数割平面()Th.:将割平面将割平面()加到松弛问题加到松弛问题()中并没有割掉原中并没有割掉原IP问问 题的任何整数可行点题的任何整数可行点.当当 不是整数时不是整数时,则对

6、应新的则对应新的 松弛问题有一个原始基本不可行解和对偶可行解松弛问题有一个原始基本不可行解和对偶可行解.0Plb用对偶单纯形法求解用对偶单纯形法求解!OR第三章 整数线性规划Proof:由上述推导过程由上述推导过程,割平面割平面()是原是原(IP)的整数约束推出来的整数约束推出来的的,所以它不会切割掉任何整数可行解所以它不会切割掉任何整数可行解.它对应的是新松弛问题的一个原始基本解它对应的是新松弛问题的一个原始基本解,但不可行但不可行.可选松弛变量可选松弛变量S作为对应所增加新约束条件的基变量作为对应所增加新约束条件的基变量,它它与原来的基变量与原来的基变量 一起必可构成新松弛问题的基变量一起

7、必可构成新松弛问题的基变量.1mBB,xx当当 不是整数时不是整数时,新松弛问题的基本解中有新松弛问题的基本解中有lb0lf 0lSf OR第三章 整数线性规划Gomory 割平面算法计算步骤割平面算法计算步骤:0PS 1:(用单纯形法用单纯形法)求解整数规划问题求解整数规划问题(IP)的松弛问题的松弛问题()0 x0P若若()没有最优解没有最优解,STOP!(IP)也没有最优解也没有最优解.若若()有最优解有最优解 ,如果如果 是整数向量是整数向量,STOP!为为(IP)的最优解的最优解.否转否转 S 2.0P0 x0 xS 2:任选任选 的一个非整数值分量的一个非整数值分量 ,按上述方式按

8、上述方式 构造割平面方程构造割平面方程 .(0)lblm 0 xjjj Sllf xsf 0PS 3:将此割平面方程加到松弛问题将此割平面方程加到松弛问题()得新的松弛问题得新的松弛问题.用对偶单纯形法求解这个新的松弛问题用对偶单纯形法求解这个新的松弛问题.若其最优解为若其最优解为 整数向量整数向量,则则STOP,它亦为它亦为(IP)的最优解的最优解.否则否则,用这个最优解代替用这个最优解代替 ,转转S 2.0 xOR第三章 整数线性规划特点特点:割平面方程系数为分数割平面方程系数为分数迭代过程中保持对偶可行性迭代过程中保持对偶可行性且用对偶单纯形法求解且用对偶单纯形法求解分数对偶割平面算法分

9、数对偶割平面算法收敛性收敛性:按一定的规则按一定的规则(如字典序如字典序)选取诱导方程选取诱导方程用对偶单纯形算法时避免循环用对偶单纯形算法时避免循环分数对偶割平面算法可在有限步内收敛分数对偶割平面算法可在有限步内收敛(终止终止)P(L)2问题输入长度问题输入长度L的多项式的多项式OR第三章 整数线性规划分数割平面算法的缺点分数割平面算法的缺点:涉及分数涉及分数.计算机仅能以有限精度存贮各个参数的值计算机仅能以有限精度存贮各个参数的值,从而对无限从而对无限(不不)循环循环)小数就产生了误差小数就产生了误差.一次一次迭代一次一次迭代误差积累误差积累很难判定一个给定的元素是否为整数很难判定一个给定

10、的元素是否为整数但判定一个元素是否为整数却是生成割平面所必须的但判定一个元素是否为整数却是生成割平面所必须的!对偶性对偶性:导致在达到最优性以前未必可找到原始可行解导致在达到最优性以前未必可找到原始可行解算法通常需要很多次迭代算法通常需要很多次迭代若算法在中途停止若算法在中途停止,得不到原始问题的得不到原始问题的 既既也也可行解可行解整数解整数解结果毫无用处结果毫无用处!OR第三章 整数线性规划为克服上述不足为克服上述不足:对偶对偶原始原始整数割平面算法整数割平面算法整数割平面方程的导出整数割平面方程的导出:诱导方程诱导方程Bjjj Slllxa xb任意非零的任意非零的h乘以上式两边乘以上式

11、两边Bjjj Slllhxha xhb将各变量的系数分离成整数部分和小数部分将各变量的系数分离成整数部分和小数部分:000 BjjBjjjj Sj Sllllllllh xhaxhhxhahaxhbhbhb Bjjj Slllllh xhaxhbhbhb要求要求 均取整值均取整值Bj,lxx01 上式左边必为整数上式左边必为整数0OR第三章 整数线性规划 Bjjj Slllh xhaxhb诱导方程两边同乘以诱导方程两边同乘以h:Bjjj Slllh xh a xh b从中减去前一不等式从中减去前一不等式 jjjj Sllllh ahaxh bhb(一般一般)Gomory 割平面割平面h取值不同

12、取值不同,则可导出不同形式的割平面则可导出不同形式的割平面分数割平面分数割平面1h 1,1h令令jjjjBj Sj S1110lllllabxba xx引入松弛变量引入松弛变量0lS jjj SlllabSx整数割平面整数割平面OR第三章 整数线性规划导出有效不等式的方法导出有效不等式的方法:取整方法取整方法超加函数法超加函数法合并方法合并方法同余方法同余方法 3.3 分解算法OR第三章 整数线性规划思想思想:通过对原问题作适当的转换或变形通过对原问题作适当的转换或变形,以便化简、甚至以便化简、甚至 消去问题的某些复杂约束和消去问题的某些复杂约束和(或或)复杂变量复杂变量,从而将原从而将原 复

13、杂问题的求解变为对另一个或一系列相对简单问题复杂问题的求解变为对另一个或一系列相对简单问题 的求解的求解.最后真正求解的简单问题一般是原问题某种形式的最后真正求解的简单问题一般是原问题某种形式的LP 或纯整数规划松弛或纯整数规划松弛 亦可看成是一种松弛算法亦可看成是一种松弛算法通常的分解算法与松弛技术的结合通常的分解算法与松弛技术的结合.OR第三章 整数线性规划Lagrangian 松弛法松弛法:将约束分为简单约束和复杂约束将约束分为简单约束和复杂约束,再利用再利用Lagrangian 松弛消去复杂约束松弛消去复杂约束.利用利用Lagrangian 乘子将复杂约束乘子将复杂约束“转入转入”目标

14、目标Tnmins.t.c xAxbxZT1122nmaxs.t.c xA xbA xbxZ复杂约束复杂约束简单约束简单约束OR第三章 整数线性规划Benders 分解分解Lagrangian 松弛法的松弛法的“对偶对偶”形式形式 将变量分为复杂变量和简单变量将变量分为复杂变量和简单变量连续连续 y 整数整数 xOR:整数整数 x 连续连续 yTTnp:maxs.t.,MIPc xh yAxGybxZyR For example固定固定x LP多面体理论多面体理论Minkowski Th转换为仅有一个连续变量的混合整数规划转换为仅有一个连续变量的混合整数规划OR第三章 整数线性规划一般分解方法一般分解方法上述两个分解算法思想的联合使用上述两个分解算法思想的联合使用MIPTT1112121222nmaxs.t.0,0c xh yA xA ybA xA ybxExZy给定的上界向量给定的上界向量