《运筹》教学课件整数规划-割平面法_第1页
《运筹》教学课件整数规划-割平面法_第2页
《运筹》教学课件整数规划-割平面法_第3页
《运筹》教学课件整数规划-割平面法_第4页
《运筹》教学课件整数规划-割平面法_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

割平面法,一、基本思想,割平面,割平面法的基本思想：,若整数规划IP的松弛规划L0的最优解不是整数解，对L0增加一个约束条件，得线性规划L1，此过程缩小了松弛规划的可行解域，在切去松弛规划的最优解的同时，保留松弛规划的任一整数解，因此整数规划IP的解均在L1中，若L1的最优解为整数解，则得IP的最优解。若L1的最优解不是整数解，重复以上步骤，由于可行解域在不断缩小，且保留IP所有的整数解，总可以在有限次后得到IP的最优解.,问题：如何寻找割平面？,增加的约束方程须满足什么条件才能使：,1、割掉松弛规划的最优解,2、保留所有的整数解,二、割平面法,L0的最优单纯形表：,源方程,-对应于生成行i的割平面,L0的最优单纯形表：,生成行,对应于生成行i的割平面,非基变量,b,010.500-0.51,00-1.75103.255.5,00-10113,10-0.25000.751.5,00-0.500-1.5z-9,对应第2行的割平面：,对应第4行的割平面：,非基变量,如何求解？,s,s,000-fim+1-fim+j-fin1fi0,0000,对偶单纯刑法,四、割平面计算步骤：,第一步：,用单纯刑法解整数问题IP的松弛问题L0,若L0没有最优解，则IP没有最优解。停止,若L0有最优解X0:,(1)X0是整数解，,则X0也是IP的最优解，停止,(2)X0不是整数解，,转第二步,第二步：,求割平面方程,第三步：,将割平面加到L0得L1,第四步：,解L1,在L0的最优单纯型表中增加一行一列，得L1的单纯型表，,用对偶单纯刑法求解，,若其解是整数解，则该解也是原整数规划的最优解,否则将该解记为X0，返回第二步,例用割平面法求解IP,解：IP问题的松弛规划的标准型：,X5,000,X5,00-0.125-0.3751-0.75,100013,010.3330-0.6672,00-1.6670-4.667z-34,整数,最优值：Z=34,例：用割平面法求解,解：IP的松弛规划的标准型,X5,00-7/22-1/221-1/2,X5,000,1001/7-1/732/7,010013,000-1-8Z-59,非整数,1001/7-1/732/7,010013,000-1-8Z-59,X6000-1/7-6/71-4/7,X6,000
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论