《运筹学3.2 割平面算法.ppt》由会员分享，可在线阅读，更多相关《运筹学3.2 割平面算法.ppt（19页珍藏版）》请在三一文库上搜索。
1、 3.2 割平面算法,1958 R.E.Gomory 提出割平面(cutting plane)的概念,理论依据 : IP与LP之间的关系, 即前述的“conv(S)”结论,基本思想 :,考虑纯IP :,放弃该约束,称为( IP )的松弛问题,但原( IP )的任一可行解均未被切割掉,否则, 对( )增加一个线性约束(几何上为超平面, 故 称为割平面条件),用单纯形法或别的方法求解( IP )的松弛问题( ), 得其最优解 ,若 为整数向量STOP, 亦为( IP )的最优解.,该割平面条件将( )的可行域割掉一部分, 且使这个非整数 向量 恰好在被割掉的区域内,新的 松弛问题 改进的松弛问题,
2、费用减小,按上述增加约束、逐步迭代的过程中, 若某步所得的松弛 LP问题,无可行解,无界,原问题( IP )亦不可行,原问题( IP )或不可行或无界,STOP,割平面法为一种松弛方法 !,关键 : 如何生成割平面, 不同的构造方法将产生不同的算法 .,Gomory 分数割平面算法,设用单纯形法求解( IP )的松弛问题( )所得的最优基本 可行解为 :,下标集合记为 , 而非基变量下标集为,迭代终止时目标函数、各个约束条件对应的典式分别为 :,若对所有的 , 均为整数,STOP ! 已经是( IP )的最优解,否则, 至少存在某一个 ,使得 不是整数 .,诱导(生成)方程,由变量的非负性,生
3、成方程变为 :,左边取值必为整数值,从诱导方程中减去该不等式,引进松弛变量S,对应于生成行l 的 Gomory割平面条件,系数为分数 分数割平面,( ),Th. : 将割平面()加到松弛问题( )中并没有割掉原IP问 题的任何整数可行点. 当 不是整数时, 则对应新的 松弛问题有一个原始基本不可行解和对偶可行解 .,用对偶单纯形法求解 !,Proof:,由上述推导过程, 割平面()是原( IP )的整数约束推出来 的, 所以它不会切割掉任何整数可行解 .,它对应的是新松弛问题的一个原始基本解, 但不可行 .,可选松弛变量S作为对应所增加新约束条件的基变量, 它 与原来的基变量 一起必可构成新松
4、弛问题的基变量.,当 不是整数时, , 新松弛问题的基本解中有,Gomory 割平面算法计算步骤 :,S 1 : (用单纯形法)求解整数规划问题( IP )的松弛问题( ),若( )没有最优解, STOP ! ( IP )也没有最优解 . 若( )有最优解 , 如果 是整数向量, STOP ! 为( IP ) 的最优解. 否转 S 2 .,S 2 : 任选 的一个非整数值分量 , 按上述方式 构造割平面方程 .,S 3 : 将此割平面方程加到松弛问题( )得新的松弛问题. 用对偶单纯形法求解这个新的松弛问题. 若其最优解为 整数向量, 则STOP, 它亦为( IP )的最优解. 否则, 用这个
5、最优解代替 , 转S 2 .,特点 :,割平面方程系数为分数,迭代过程中保持对偶可行性,且用对偶单纯形法求解,分数对偶割平面算法,收敛性 :,按一定的规则(如字典序)选取诱导方程,用对偶单纯形算法时避免循环,分数对偶割平面算法可在有限步内收敛(终止),问题输入长度L 的多项式,分数割平面算法的缺点 :, 涉及分数.,计算机仅能以有限精度存贮各个参数的值, 从而对无限(不)循环)小数就产生了误差 .,一次一次迭代 误差积累,很难判定一个给定的元素是否为整数,但判定一个元素是否为整数却是生成割平面所必须的 !, 对偶性 :导致在达到最优性以前未必可找到原始可行解,算法通常需要很多次迭代,结果毫无用
6、处 !,为克服上述不足 :,整数割平面方程的导出 :,诱导方程,任意非零的h乘以上式两边,将各变量的系数分离成整数部分和小数部分 :,要求 均取整值, 上式左边必为整数,诱导方程两边同乘以h :,从中减去前一不等式,(一般) Gomory 割平面,h取值不同, 则可导出不同形式的割平面,分数割平面,引入松弛变量,整数割平面,导出有效不等式的方法 :,取整方法,超加函数法,合并方法,同余方法, 3.3 分解算法,思想 : 通过对原问题作适当的转换或变形, 以便化简、甚至 消去问题的某些复杂约束和(或)复杂变量, 从而将原 复杂问题的求解变为对另一个或一系列相对简单问题 的求解 ., 最后真正求解
7、的简单问题一般是原问题某种形式的LP 或纯整数规划松弛, 亦可看成是一种松弛算法,通常的分解算法与松弛技术的结合 .,Lagrangian 松弛法 :,将约束分为简单约束和复杂约束, 再利用Lagrangian 松弛消去复杂约束 .,利用Lagrangian 乘子将复杂约束“转入”目标,复杂约束,简单约束,Benders 分解,Lagrangian 松弛法的“对偶”形式,将变量分为复杂变量和简单变量,连续 y,整数 x,OR : 整数 x 连续 y,For example,固定x LP,多面体理论 Minkowski Th,转换为仅有一个连续变量的混合整数规划,一般分解方法,上述两个分解算法思想的联合使用,给定的上界向量,