整数规划教学课件PPT.ppt_第1页
整数规划教学课件PPT.ppt_第2页
整数规划教学课件PPT.ppt_第3页
整数规划教学课件PPT.ppt_第4页
整数规划教学课件PPT.ppt_第5页
已阅读5页，还剩75页未读， 继续免费阅读

下载本文档

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

文档简介

第4章 整 数 规 划 (Integer Programming),整数规划的模型,分支定界法,割平面法,01 整数规划,指派问题,知识回顾：线性规划模型,由前面学习可知，线性规划在生产实践中有重要作用，能够解决许多优化问题； 用单纯性算法能方便地对线性规划问题求解,已知： 两种货物装葙 每种货物装葙利润 体积限制 重量限制 决策变量:两种货物各多少箱 Max Z =利润最大？,但现在也有另一类现实问题：,思考：箱数？,实践中的其他问题举例,背包问题：背包的容积一定，现有多种物品待装，各物品的价值、体积已知，求最优配装方案，使得在不超过背包的容量的前提下装入物品的价值最大。 选址问题：某商场在全市有数个连锁店，拟建立n个仓库对所有连锁店供货，有数个地点作为被选点。问在何处建设仓库使得各仓库到所有连锁店的总距离最小。 投资决策问题：现有一定的资金，有数个可以考虑的投资项目。每个项目需要的资金和利润已知。问如何选择投资项目，使得获得的利润最大。,分析,以上问题的特点是：变量为整数 背包问题：对每一件物品进行取舍，装或者不装； 选址问题：对每一个被选点有两种选择，在这里建或者不在这里建； 投资决策问题：对每一个考虑的项目，投资或者不投资。 这类问题无法用线性规划求解！因为线性规划的解可能包含小数部分,（一）、整数规划问题实例,例一、合理下料问题 设用某型号的圆钢下零件A1, A2,Am 的毛坯。在一根圆钢上下料的方式有B1,B2, Bn 种，每种下料方式可以得到各种零件的毛坯数以及每种零件的需要量，如表所示。问怎样安排下料方式，使得即满足需要，所用的原材料又最少？,一、整数规划的模型,设：xj 表示用Bj (j=1.2n) 种方式下料根数 模型：,例二、某公司计划在m个地点建厂，可供选择的地点有A1,A2Am ，他们的生产能力分别是a1,a2,am（假设生产同一产品）。第i个工厂的建设费用为fi (i=1.2m),又有n个地点B1,B2, Bn 需要销售这种产品，其销量分别为b1.b2bn 。从工厂运往销地的单位运费为Cij。试决定应在哪些地方建厂，即满足各地需要，又使总建设费用和总运输费用最省？,设： xij 表示从工厂运往销地的运量(i=1.2m、j=1.2n), 1 在Ai建厂 又设 Yi （i=1.2m） 0 不在Ai建厂 模型：,例三、机床分配问题 设有m台同类机床，要加工n种零件。已知各种零件的加工时间分别为a1,a2,an ，问如何分配，使各机床的总加工任务相等，或者说尽可能平衡。,设： 1 分配第i台机床加工第j种零件； xij （i=1.2m,j=1.2n） 0 相
人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

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

最新文档

评论

0/150

提交评论