运筹学3.2割平面算法

《运筹学3.2割平面算法》由会员分享，可在线阅读，更多相关《运筹学3.2割平面算法（19页珍藏版）》请在装配图网上搜索。

1、 3.2 割平面算法1958 R.E.Gomory 提出割平面(cutting plane)的概念理论依据 : IP与LP之间的关系, 即前述的“conv(S)”结论基本思想 :考虑纯IP :Tnmins.t.0c xAxbxxZ放弃该约束 Tmins.t.0c xAxbx称为( IP )的松弛问题Abc、 、均均为为整整值值0()P()IP但原( IP )的任一可行解均未被切割掉 否则, 对( )增加一个线性约束(几何上为超平面, 故称为割平面条件)0P用单纯形法或别的方法求解( IP )的松弛问题( ), 得其最优解 , 0P0 x若 为整数向量STOP, 亦为( IP )的最优解. 0

2、x0 x该割平面条件将( )的可行域割掉一部分, 且使这个非整数向量 恰好在被割掉的区域内0P0 x 新的 松弛问题改进的松弛问题1()P费用减小0 x1x2x按上述增加约束、逐步迭代的过程中, 若某步所得的松弛LP问题无可行解无界原问题( IP )亦不可行原问题( IP )或不可行或无界STOP割平面法为一种松弛方法 !关键 : 如何生成割平面, 不同的构造方法将产生不同的算法 .0 x0 xGomory 分数割平面算法0P0 x 设用单纯形法求解( IP )的松弛问题( )所得的最优基本可行解为 :1mBB,BAA基基1mBB,xx基基变变量量下标集合记为 , 而非基变量下标集为SS迭代终

3、止时目标函数、各个约束条件对应的典式分别为 :ijj0j SBijjij S,1,zxzxa xbim0B0jj00,xz abz0B0jj0j Sxa xb0,1,im若对所有的 , 均为整数i0,1,im b0 xSTOP ! 已经是( IP )的最优解否则, 至少存在某一个 ,使得 不是整数 .:0lllmb Bjjj Slllxa xb诱导(生成)方程jjjj, 01, 01,llllllllbbffaafajS 由变量的非负性jjjjj Sj Sllaxa x生成方程变为 :Bjjj Slllxaxb左边取值必为整数值Bjjj Slllxaxb 从诱导方程中减去该不等式 jjjj S

4、llllaaxbb jjj Sllf xfjjj Sllf xsf 引进松弛变量S对应于生成行l 的Gomory割平面条件系数为分数 分数割平面( )Th. : 将割平面()加到松弛问题( )中并没有割掉原IP问 题的任何整数可行点. 当 不是整数时, 则对应新的 松弛问题有一个原始基本不可行解和对偶可行解 .0Plb用对偶单纯形法求解 !Proof: 由上述推导过程, 割平面()是原( IP )的整数约束推出来的, 所以它不会切割掉任何整数可行解 .它对应的是新松弛问题的一个原始基本解, 但不可行 . 可选松弛变量S作为对应所增加新约束条件的基变量, 它与原来的基变量 一起必可构成新松弛问题

5、的基变量.1mBB,xx当 不是整数时, , 新松弛问题的基本解中有lb0lf 0lSf Gomory 割平面算法计算步骤 :0PS 1 : (用单纯形法)求解整数规划问题( IP )的松弛问题( )0 x0P若( )没有最优解, STOP ! ( IP )也没有最优解 .若( )有最优解 , 如果 是整数向量, STOP ! 为( IP ) 的最优解. 否转 S 2 .0P0 x0 xS 2 : 任选 的一个非整数值分量 , 按上述方式 构造割平面方程 .(0)lblm 0 xjjj Sllf xsf 0PS 3 : 将此割平面方程加到松弛问题( )得新的松弛问题. 用对偶单纯形法求解这个新

6、的松弛问题. 若其最优解为 整数向量, 则STOP, 它亦为( IP )的最优解. 否则, 用这个最优解代替 , 转S 2 .0 x特点 :割平面方程系数为分数迭代过程中保持对偶可行性且用对偶单纯形法求解分数对偶割平面算法收敛性 :按一定的规则(如字典序)选取诱导方程用对偶单纯形算法时避免循环分数对偶割平面算法可在有限步内收敛(终止)P(L)2问题输入长度L的多项式分数割平面算法的缺点 : 涉及分数. 计算机仅能以有限精度存贮各个参数的值,从而对无限(不)循环)小数就产生了误差 .一次一次迭代误差积累很难判定一个给定的元素是否为整数但判定一个元素是否为整数却是生成割平面所必须的 ! 对偶性 :

7、导致在达到最优性以前未必可找到原始可行解算法通常需要很多次迭代若算法在中途停止, 得不到原始问题的 既也可行解整数解结果毫无用处 !为克服上述不足 :对偶原始整数割平面算法整数割平面方程的导出 :诱导方程Bjjj Slllxa xb任意非零的h乘以上式两边Bjjj Slllhxha xhb将各变量的系数分离成整数部分和小数部分 :000 BjjBjjjj Sj Sllllllllh xhaxhhxhahaxhbhbhb Bjjj Slllllh xhaxhbhbhb要求 均取整值Bj,lxx01 上式左边必为整数0 Bjjj Slllh xhaxhb诱导方程两边同乘以h : Bjjj Slll

8、h xh a xh b从中减去前一不等式 jjjj Sllllh ahaxh bhb(一般) Gomory 割平面h取值不同, 则可导出不同形式的割平面分数割平面1h 1,1h令令jjjjBj Sj S1110lllllabxba xx引入松弛变量0lS jjj SlllabSx整数割平面导出有效不等式的方法 :取整方法超加函数法合并方法同余方法 3.3 分解算法思想 : 通过对原问题作适当的转换或变形, 以便化简、甚至 消去问题的某些复杂约束和(或)复杂变量, 从而将原 复杂问题的求解变为对另一个或一系列相对简单问题 的求解 . 最后真正求解的简单问题一般是原问题某种形式的LP 或纯整数规划

9、松弛 亦可看成是一种松弛算法通常的分解算法与松弛技术的结合 .Lagrangian 松弛法 :将约束分为简单约束和复杂约束, 再利用Lagrangian 松弛消去复杂约束 .利用Lagrangian 乘子将复杂约束“转入”目标Tnmins.t.c xAxbxZT1122nmaxs.t.c xA xbA xbxZ复杂约束简单约束Benders 分解Lagrangian 松弛法的“对偶”形式 将变量分为复杂变量和简单变量连续 y 整数 xOR : 整数 x 连续 yTTnp: maxs.t.,MIPc xh yAxGybxZyR For example固定x LP多面体理论Minkowski Th转换为仅有一个连续变量的混合整数规划一般分解方法上述两个分解算法思想的联合使用MIPTT1112121222nmaxs.t.0,0c xh yA xA ybA xA ybxExZy给定的上界向量