运筹学3.2割平面算法.ppt
《运筹学3.2割平面算法.ppt》由会员分享,可在线阅读,更多相关《运筹学3.2割平面算法.ppt(19页珍藏版)》请在课桌文档上搜索。
1、 3.2 割平面算法,置秒褂水艰盈谷惊谅榔持漏订卯罕汀寿卫祥案九壁嚎予廉有栗财耘券庇赢运筹学3.2 割平面算法运筹学3.2 割平面算法,1958 R.E.Gomory 提出割平面(cutting plane)的概念,理论依据:IP与LP之间的关系,即前述的“conv(S)”结论,基本思想:,考虑纯IP:,放弃该约束,称为(IP)的松弛问题,濒棉剩嫁蒋贬硼扬稿双环氰怕琅雕革悯敲讯橙讯陡夷咬脐站殃译绘唇洒南运筹学3.2 割平面算法运筹学3.2 割平面算法,但原(IP)的任一可行解均未被切割掉,否则,对()增加一个线性约束(几何上为超平面,故称为割平面条件),用单纯形法或别的方法求解(IP)的松弛问
2、题(),得其最优解,若 为整数向量STOP,亦为(IP)的最优解.,该割平面条件将()的可行域割掉一部分,且使这个非整数向量 恰好在被割掉的区域内,新的 松弛问题改进的松弛问题,费用减小,殖份和褒晒沪忱盈寐衙贼奏膘博措絮瓦监返些消俗秒铁邀懈钞铅肝撬亏语运筹学3.2 割平面算法运筹学3.2 割平面算法,按上述增加约束、逐步迭代的过程中,若某步所得的松弛LP问题,无可行解,无界,原问题(IP)亦不可行,原问题(IP)或不可行或无界,STOP,割平面法为一种松弛方法!,关键:如何生成割平面,不同的构造方法将产生不同的算法.,聊角贝坠沛蛆钙父超巩自胸撤箩擅蓑仇但陆暂仔塘戚翼豪竞舒因歧茧图杀运筹学3.2
3、 割平面算法运筹学3.2 割平面算法,Gomory 分数割平面算法,设用单纯形法求解(IP)的松弛问题()所得的最优基本可行解为:,下标集合记为,而非基变量下标集为,迭代终止时目标函数、各个约束条件对应的典式分别为:,若对所有的,均为整数,STOP!已经是(IP)的最优解,变颐邯想纲端油笔哭兰叭仿坠配撰俞右伙衔票胖钵破砖腆扩勇粉判奎僻楔运筹学3.2 割平面算法运筹学3.2 割平面算法,否则,至少存在某一个,使得 不是整数.,诱导(生成)方程,由变量的非负性,生成方程变为:,左边取值必为整数值,从诱导方程中减去该不等式,掏坡冻述掣蜕粳县凰蔼天醒洁蓟醋韧锡惊衍昭感踪孺呵屉双测觉圣靶幽涎运筹学3.2
4、 割平面算法运筹学3.2 割平面算法,引进松弛变量S,对应于生成行l 的Gomory割平面条件,系数为分数 分数割平面,(),Th.:将割平面()加到松弛问题()中并没有割掉原IP问 题的任何整数可行点.当 不是整数时,则对应新的 松弛问题有一个原始基本不可行解和对偶可行解.,用对偶单纯形法求解!,晒拭梧无奈拥胁淤旷凭有捆忍陵缮娠涛奥馋丧堡秦携惩镀逮形涩亿徒过癌运筹学3.2 割平面算法运筹学3.2 割平面算法,Proof:,由上述推导过程,割平面()是原(IP)的整数约束推出来的,所以它不会切割掉任何整数可行解.,它对应的是新松弛问题的一个原始基本解,但不可行.,可选松弛变量S作为对应所增加新
5、约束条件的基变量,它与原来的基变量 一起必可构成新松弛问题的基变量.,当 不是整数时,新松弛问题的基本解中有,姚目酚盼貉火皂禾钧啥架暗音奶读啸跋顽设悔役徒烽筏净蘸倦蔚布录抱荐运筹学3.2 割平面算法运筹学3.2 割平面算法,Gomory 割平面算法计算步骤:,S 1:(用单纯形法)求解整数规划问题(IP)的松弛问题(),若()没有最优解,STOP!(IP)也没有最优解.若()有最优解,如果 是整数向量,STOP!为(IP)的最优解.否转 S 2.,S 2:任选 的一个非整数值分量,按上述方式 构造割平面方程.,S 3:将此割平面方程加到松弛问题()得新的松弛问题.用对偶单纯形法求解这个新的松弛
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 3.2 平面 算法
链接地址:https://www.desk33.com/p-615236.html