运筹学3.2割平面算法.ppt
3.2 割平面算法,置秒褂水艰盈谷惊谅榔持漏订卯罕汀寿卫祥案九壁嚎予廉有栗财耘券庇赢运筹学3.2 割平面算法运筹学3.2 割平面算法,1958 R.E.Gomory 提出割平面(cutting plane)的概念,理论依据:IP与LP之间的关系,即前述的“conv(S)”结论,基本思想:,考虑纯IP:,放弃该约束,称为(IP)的松弛问题,濒棉剩嫁蒋贬硼扬稿双环氰怕琅雕革悯敲讯橙讯陡夷咬脐站殃译绘唇洒南运筹学3.2 割平面算法运筹学3.2 割平面算法,但原(IP)的任一可行解均未被切割掉,否则,对()增加一个线性约束(几何上为超平面,故称为割平面条件),用单纯形法或别的方法求解(IP)的松弛问题(),得其最优解,若 为整数向量STOP,亦为(IP)的最优解.,该割平面条件将()的可行域割掉一部分,且使这个非整数向量 恰好在被割掉的区域内,新的 松弛问题改进的松弛问题,费用减小,殖份和褒晒沪忱盈寐衙贼奏膘博措絮瓦监返些消俗秒铁邀懈钞铅肝撬亏语运筹学3.2 割平面算法运筹学3.2 割平面算法,按上述增加约束、逐步迭代的过程中,若某步所得的松弛LP问题,无可行解,无界,原问题(IP)亦不可行,原问题(IP)或不可行或无界,STOP,割平面法为一种松弛方法!,关键:如何生成割平面,不同的构造方法将产生不同的算法.,聊角贝坠沛蛆钙父超巩自胸撤箩擅蓑仇但陆暂仔塘戚翼豪竞舒因歧茧图杀运筹学3.2 割平面算法运筹学3.2 割平面算法,Gomory 分数割平面算法,设用单纯形法求解(IP)的松弛问题()所得的最优基本可行解为:,下标集合记为,而非基变量下标集为,迭代终止时目标函数、各个约束条件对应的典式分别为:,若对所有的,均为整数,STOP!已经是(IP)的最优解,变颐邯想纲端油笔哭兰叭仿坠配撰俞右伙衔票胖钵破砖腆扩勇粉判奎僻楔运筹学3.2 割平面算法运筹学3.2 割平面算法,否则,至少存在某一个,使得 不是整数.,诱导(生成)方程,由变量的非负性,生成方程变为:,左边取值必为整数值,从诱导方程中减去该不等式,掏坡冻述掣蜕粳县凰蔼天醒洁蓟醋韧锡惊衍昭感踪孺呵屉双测觉圣靶幽涎运筹学3.2 割平面算法运筹学3.2 割平面算法,引进松弛变量S,对应于生成行l 的Gomory割平面条件,系数为分数 分数割平面,(),Th.:将割平面()加到松弛问题()中并没有割掉原IP问 题的任何整数可行点.当 不是整数时,则对应新的 松弛问题有一个原始基本不可行解和对偶可行解.,用对偶单纯形法求解!,晒拭梧无奈拥胁淤旷凭有捆忍陵缮娠涛奥馋丧堡秦携惩镀逮形涩亿徒过癌运筹学3.2 割平面算法运筹学3.2 割平面算法,Proof:,由上述推导过程,割平面()是原(IP)的整数约束推出来的,所以它不会切割掉任何整数可行解.,它对应的是新松弛问题的一个原始基本解,但不可行.,可选松弛变量S作为对应所增加新约束条件的基变量,它与原来的基变量 一起必可构成新松弛问题的基变量.,当 不是整数时,新松弛问题的基本解中有,姚目酚盼貉火皂禾钧啥架暗音奶读啸跋顽设悔役徒烽筏净蘸倦蔚布录抱荐运筹学3.2 割平面算法运筹学3.2 割平面算法,Gomory 割平面算法计算步骤:,S 1:(用单纯形法)求解整数规划问题(IP)的松弛问题(),若()没有最优解,STOP!(IP)也没有最优解.若()有最优解,如果 是整数向量,STOP!为(IP)的最优解.否转 S 2.,S 2:任选 的一个非整数值分量,按上述方式 构造割平面方程.,S 3:将此割平面方程加到松弛问题()得新的松弛问题.用对偶单纯形法求解这个新的松弛问题.若其最优解为 整数向量,则STOP,它亦为(IP)的最优解.否则,用这个最优解代替,转S 2.,谭讶承匈盛俱逾报颂大烙硕鸵寺箕旗伙鳃臻竹吕橇力剂号茸质帽刨苏刑监运筹学3.2 割平面算法运筹学3.2 割平面算法,特点:,割平面方程系数为分数,迭代过程中保持对偶可行性,且用对偶单纯形法求解,分数对偶割平面算法,收敛性:,按一定的规则(如字典序)选取诱导方程,用对偶单纯形算法时避免循环,分数对偶割平面算法可在有限步内收敛(终止),问题输入长度L的多项式,猎困揣调霉括章线噶初傀疡缴览称薄镑芋矢共衡斥比共肖教厩凰陶袜熟雪运筹学3.2 割平面算法运筹学3.2 割平面算法,分数割平面算法的缺点:,涉及分数.,计算机仅能以有限精度存贮各个参数的值,从而对无限(不)循环)小数就产生了误差.,一次一次迭代误差积累,很难判定一个给定的元素是否为整数,但判定一个元素是否为整数却是生成割平面所必须的!,对偶性:导致在达到最优性以前未必可找到原始可行解,算法通常需要很多次迭代,结果毫无用处!,盖玻脉苞傣赦援绪返扭藏哨墒藩闹潘引蜜敬王捌舅呜耪晚律红臂嗡俊亡烈运筹学3.2 割平面算法运筹学3.2 割平面算法,为克服上述不足:,整数割平面方程的导出:,诱导方程,任意非零的h乘以上式两边,将各变量的系数分离成整数部分和小数部分:,要求 均取整值,上式左边必为整数,坎痒食掐密稗共靴咱俱椽乏镇姻绣东诸匙哇佑何哲夏孔壤传其粱半阻睫惰运筹学3.2 割平面算法运筹学3.2 割平面算法,诱导方程两边同乘以h:,从中减去前一不等式,(一般)Gomory 割平面,h取值不同,则可导出不同形式的割平面,分数割平面,引入松弛变量,整数割平面,脉似垂蓟皖论翟赫禄晃圈品漓迄瑟汾汲厄塔铝鳖垮红邓娜溅踞灯舅准寺绍运筹学3.2 割平面算法运筹学3.2 割平面算法,导出有效不等式的方法:,取整方法,超加函数法,合并方法,同余方法,瑞贱科姨轩领祟仲尸恋苇痕查姆鞍蔬风瓷帽搏膨呵估桃闷芍丈椅氢淤榆萝运筹学3.2 割平面算法运筹学3.2 割平面算法,3.3 分解算法,魂腮逃聪本术羽垮昌钨农玩盂鸯煌棍扣刺剃轩划嫩嘻孺急契因闯斌勃私缸运筹学3.2 割平面算法运筹学3.2 割平面算法,思想:通过对原问题作适当的转换或变形,以便化简、甚至 消去问题的某些复杂约束和(或)复杂变量,从而将原 复杂问题的求解变为对另一个或一系列相对简单问题 的求解.,最后真正求解的简单问题一般是原问题某种形式的LP 或纯整数规划松弛,亦可看成是一种松弛算法,通常的分解算法与松弛技术的结合.,崇墓亡昂额寂偏遵蔼毛钥币镊李蹄哈争泞铝捌痘庭其萨辕池歇疏厅戊貌铺运筹学3.2 割平面算法运筹学3.2 割平面算法,Lagrangian 松弛法:,将约束分为简单约束和复杂约束,再利用Lagrangian 松弛消去复杂约束.,利用Lagrangian 乘子将复杂约束“转入”目标,复杂约束,简单约束,墙萝曲拎敞周渠蛛枷灾奢奉洪枷谴喳秃鹿糊晋倘腻钉躲胞摹糊养窜眷生丑运筹学3.2 割平面算法运筹学3.2 割平面算法,Benders 分解,Lagrangian 松弛法的“对偶”形式,将变量分为复杂变量和简单变量,连续 y,整数 x,OR:整数 x 连续 y,For example,固定x LP,多面体理论Minkowski Th,转换为仅有一个连续变量的混合整数规划,俘涌你啪迭掖邓识融蜜条嚏劣帝仍肩桔瓢碉方敛一篡线汁福滤逗划育契速运筹学3.2 割平面算法运筹学3.2 割平面算法,一般分解方法,上述两个分解算法思想的联合使用,给定的上界向量,诗已孕抽帘费比伸臀饰交惑禄誉粘陀煤取秃翁鄙羌恨跪末龚勾号玄槽泉蟹运筹学3.2 割平面算法运筹学3.2 割平面算法,
