整数规划解法_第1页
整数规划解法_第2页
整数规划解法_第3页
整数规划解法_第4页
整数规划解法_第5页
已阅读5页，还剩17页未读， 继续免费阅读

下载本文档

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

文档简介

1、1,2.2 整数规划解法,(一)、整数规划的解： 可行域为其相应线性规划问题的可行域的子集,例1、,LP:X=(4.8,0) maxZ=96 ILP:X=(4,1) maxZ=90,2,(1)、四舍五入法 可估近似解，例中X=(4,0), Z=80 80 Z* 96 0Z*- 8016,(2)、穷举法 当100个01变量，计算机，几亿年,3,分枝定界法 割平面法 隐枚举法,(二)、常用方法,4,(三)、分枝定界法,基本思路,(B)为(A)的松弛问题。,5,6,maxZ=40X1 + 90X2,例：,7,解：先解(1)的松弛问题,选X1分枝,8,选(2)继续分枝,9,10,分枝定界法一般步骤：,

2、(1)、(A), 先解(A)的松弛问题(B),(2)、 (B)无可行解(A)无可行解。 (B)最优解符合(A)要求，停。 (B)最优解不符合(A)要求，转(3)。,(3)、估整数解S0 ，作下界,(4)、选(B)解中不符合整数条件的分量Xj (Xj = bj )分枝，作(B)的后续问题(C)、(D)。 (C)： (B）加约束Xj bj (D)：(B)加约束Xj bj +1,11,(6)、全部枝剪完，停,12,优点：,(1)、任何模型均可用；,(2)、思路简单、灵活；,(3)、速度快；,(4)、适合上机。,13,分枝定界法注意事项：,(1)、分枝变量选择原则： 按目标函数系数：选系数绝对值最大者

3、变 量先分。 对目标值升降影响最大。 选与整数值相差最大的非整数变量先分枝。 按使用者经验，对各整数变量排定重要性 的优先顺序。,14,(2)、分枝节点选择：, 广探法： 选目标函数当前最大值节点，找到的整数 解质量高。慢。, 深探法(后进先出法)： 最后打开的节点最先选，尽快找到整数解。 整数解质量可能不高。,15,01问题的分枝定界法（背包问题),松弛问题(B)为,16,解:“单位重量价值大的先放”,17,18,隐枚举法,19,20,(二)、简单隐枚举法(max),原则： (1)、用试探法，求出一个可行解，以它的目标值作为当前最好值Z0 (2)、增加过滤条件Z Z0 (3)、将xi 按ci由小大排列,21,解：观察得解(x1 , x2 , x3 )=(1 ,0 ,0) Z0 =3

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论