求解整数规划算法.doc_第1页
求解整数规划算法.doc_第2页
求解整数规划算法.doc_第3页
全文预览已结束

下载本文档

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

文档简介

求解整数规划算法分枝定界法原理步骤：将要求解的整数规划问题称为I L，与它相应的线性规划问题称为问题L。 解问题L，可能得到以下情况之一： （a）L没有可行解，这时I L也没有可行解（b）L有最优解，且解变量都是整数，因而它也是I L的最优解，则停止；（c）L有最优解，但不符合I L中的整数条件，记它的目标函数值为，若记为I L的最优目标函数值，则必有 迭代：第一步：分枝：在L的最优解中任选一个不符合整数条件的变量，设其值为，构造两个约束条件：和。将这两个条件分别加入问题L，将L分成两个后继问题L1和L2。求解L1和L2。定界：以每个子问题的求解结果，与其它问题的解的结果一道，找出最优目标函数值最小者作为新的下界，替换，从已符合整数条件的各分枝中，找出目标数值为最小者作为新的上界，即有。第二步比较与剪枝：各分枝的最优目标函数中若有大于者，则剪掉这一枝；若小于，且不符合整数条件，则重复第一步骤，一直到最后得到最优目标函数值为止，从而得最优整数解。割平面算法求解整数规划模型这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量是整数的条件，但增加线性约束条件使得由原可行域中切割掉一部分，这部分只包含非整数解，但没切割掉任何整数可行解。这个方法就是指怎样找到适当的割平面，使切割后最终得到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。0-1型整数规划一、解决的主要问题背包问题P35,售货员问题P34,投资组合问题P33,投资决策问题P33,飞机排队P31，（资料）集合覆盖和布点问题P212运筹学基础，与生产方式有关的固定成本问题P213运筹学基础1 如果决策i为是或有0 如果决策i为否或无二、模型建立：假设现有m种资源对可供选择的n个项目进行投资的数学模型为：求一组决策变量使其中
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

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

最新文档

评论

0/150

提交评论