第八章 整数线性规划(ILP).ppt_第1页
第八章 整数线性规划(ILP).ppt_第2页
第八章 整数线性规划(ILP).ppt_第3页
第八章 整数线性规划(ILP).ppt_第4页
第八章 整数线性规划(ILP).ppt_第5页
已阅读5页，还剩28页未读， 继续免费阅读

下载本文档

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

文档简介

1、第7章整数线性规划(ILP)在前面讨论的线性规划问题中，最优解可能是分数或小数，但特定问题的答案往往是整数。我们把这些线性规划问题称为整数线性规划问题，整数规划是近20年发展起来的规划论之一。1，在数值线性规划问题的建议整数计划中，如果所有变量都限制为非负整数，则称为纯整数计划，如果部分变量限制为整数，则称为混合整数计划，整数计划的特殊情况是01计划，他的变量是整数线性规划问题示例1，投资决策问题一个部门在未来5年内可以投资的只有询问投资项目选择方法，才能最大限度地提高总利润。将总收益设置为z，将上述问题的数学模型：解决方案：投资决策变量设置为，显然上述决策变量只能采取0或1整数规划问题，这些

2、整数规划问题称为01规划。决策变量0或1牙齿约束可以用非线性约束代替。2，某工厂想寄集装箱甲两个茄子的货物。每个箱子的体积、重量、可用利润和托运的限制如下表所示。询问两个茄子货物各寄多少箱，利润最大吗？解释：甲方设置为两个茄子货物的托运箱数，总利润z，上述问题的数学模型：3，旅行推销员问题(货物和负担问题)，第一个限制表示每个城市准确进入一次，第二个限制表示每个城市正确离开一次，第三个限制显然这是混合整数编程问题。2，求解整数线性规划问题的解算平面法，(1)基本思想提供整数规划，首先求出相应的线性规划问题，(2)剖切平面法解决ILP问题的一般步骤，3，求解整数线性规划问题的分支定界法实现方法首

3、先考虑变量的整数要求例如，如果最佳解决方案不满足整数要求，则将原始问题分成两部分。每个部分都添加了新的约束，以减少原始线性规划问题的可执行域。通过不断分解，逐渐接近满足要求的最优解，直到得到最优解。牙齿过程包括分支和边界两个茄子重要阶段。(2)按照用茄子划分方法解决ILP问题的一般步骤，分支划分方法的基本思想，总结了用分支划分方法解决整数规划问题的一般步骤。这里举例说明了目标函数值最大化问题。提出整数规划可以先找到相应的线性规划问题，分支定界法可用于解决纯整数规划问题，也可用于查找混合整数规划问题。20世纪60年代初，Land和Dong牙齿Dakin修改的优点是方法灵活，电脑解决非常容易。所以现在已经成为解决净水计划的重要方法之一，成功地解决了净水计划问题、生产日程问题、旅行推销员问题、工厂位置问题、背包问题、分配问题等问题。分支法优于宫相法。因为，仅在一些可执行的整数解中寻找最佳解，计算量小于宫商法，但变量数多的话，计算工作量也相

人人文库> 全部分类> 生活休闲 > 励志创业

温馨提示

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

最新文档

评论

0/150

提交评论