解0—1规划的隐枚举法.doc_第1页
解0—1规划的隐枚举法.doc_第2页
解0—1规划的隐枚举法.doc_第3页
全文预览已结束

下载本文档

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

文档简介

(5) 解 01 规划的隐枚举法解 01 规划的隐枚举法有其独特的工作程序，具体过程如下。a. 模型转化为求极小的问题b. 变量替换。极小问题模型的目标函数中所有变量系数为负的01变量，可利用变量替换xk=1xk (xk 是引入的新的01变量)，将目标函数中所有变量系数化为正数。c. 目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整。d. 按目标函数值由小到大的顺序依次排列可能的解，并予以可行性检验。e. 发现求极小问题的最优解并停止。f. 转化为原问题的最优解。例4 用隐枚举法求解下列01规划问题Max Z=3x12x25x32x43x5x1 x2 x32x4 x547x1 3x34x43x5811x16x2 3x4 5x53xj =0, 1, j=1, 2, 3, 4, 5. 解： 转化为求极小的问题Min Z=3x12x25x32x43x5x1 x2 x32x4 x547x1 3x34x43x5811x1 6x2 3x4 5x53xj =0, 1, j=1, 2, 3, 4, 5. 令x1=1x1, x2=1x2, x5=1x5, 带入极小问题模型中，得Min Z=3 x12 x25x32x43 x58x1 x2 x32x4 x517x1 3x34x43x5211x1 6x2 3x45x57xj =0, 1, j= 3, 4; xj =0, 1, j= 1, 2, 5. 目标函数中变量按系数大小排列，约束条件中变量排列顺序也相应调整，得Min Z=5x33 x13 x52 x22x48 x3 x1 x5x22x4 1 3x3 7x1 3x5 4x42 11x1 5x56x2 3x47 xj =0, 1, j= 3, 4; xj =0, 1, j= 1, 2, 5. 按目标函数值由小到大的顺序排列可能的解，并予以可行性检验。计算表格如下可能的解Z是否满足约束是否可行解备注x3x1x5x2x4000008 否 000016 否 000106 否 001005是010005否 000114是 停止 表4.1 最优解为x5=1, x1=x2=x3=x4=0. 所以原问题的最优解为：x1
人人文库> 全部分类> 应用文书 > 工作计划

温馨提示

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

最新文档

评论

0/150

提交评论