运筹学 0-1整数规划.ppt_第1页
运筹学 0-1整数规划.ppt_第2页
运筹学 0-1整数规划.ppt_第3页
运筹学 0-1整数规划.ppt_第4页
运筹学 0-1整数规划.ppt_第5页
已阅读5页，还剩13页未读， 继续免费阅读

下载本文档

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

文档简介

一 相互排斥的计划例4 6某公司拟在市东 西 南三区中建立门市部 有例7个点Ai i 1 2 7 可供选择 要求满足以下条件 1 在东区 在A1 A2 A3三个点中至多选两个 2 在西区 A4 A5两个点中至少选一个 3 在南区 A6 A7两个点为互斥点 4 选A2点必选A5点 若Ai点投资为bi万元 每年可获利润为ci万元 投资总额为B万元 试建立利润最大化的0 1规划模型 第四节0 1整数规划 解 设决策变量为 建立0 1规划模型如下 解 设决策变量为 建立0 1规划模型如下 在东区 在A1 A2 A3三个点中至多选两个 2 在西区 A4 A5两个点中至少选一个 3 在南区 A6 A7两个点为互斥点 4 选A2点必选A5点 例4 7某产品有A1和A2两种型号 需要经过B1 B2 B3三道工序 单位工时和利润 各工序每周工时限制见表所示 问工厂如何安排生产 才能使总利润最大 B3工序有两种加工方式B31和B32 产品为整数 二 互排斥的约束条件 解 设A1 A2产品的生产数量分别为x1 x2件 在不考虑B31和B32相互排斥的情况下 问题的数学模型为 工序B3只能从两种加工方式中选择一种 那么约束条件 1 和 2 就成为相互排斥的约束条件 为了统一在一个问题中 引入0 1变量 则数学模型为 一般地 在建立数学模型时 若需从p个约束条件中选择q个约束条件 则可以引入p个0 1变量 那么约束条件组 三 固定成本问题 例4 8某公司制造小 中 大三种尺寸的容器 所需资源为金属板 劳动力和机器设备 制造一个容器所需的各种资源的数量如下表所示 不考虑固定费用 小 中 大号容器每售出一个其利润分别为4万元 5万元 6万元 可使用的金属板有500吨 劳动力有300人 月 机器有100台 月 另外若生产 不管每种容器生产多少 都需要支付一笔固定费用 小号为100万元 中号为150万元 大号为200万元 问如何制定生产计划使获得的利润对大 解 设x1 x2 x3分别为小号容器 中号容器 大号容器的生产数量 不考虑固定费用 则问题的数学模型为 若考虑固定费用就必须引入0 1变量 则该问题的数学模型为 0 1整数规划是一种特殊形式的整数规划 这时的决策变量xi只取两个值0或1 一般的解法为隐枚举法 例一 求解下列0 1规划问题 0 1整数规划求解方法 解 对于0 1规划问题 由于每个变量只取0 1两个值 一般会用穷举法来解 即将所有的0 1组合找出 使目标函数达到极值要求就可求得最优解 但此法太繁琐 工作量相当大 而隐枚举法就是在此基础上 通过加入一定的条件 就能较快的求得最优解 例二 求解下列0 1规划问题 例二 求解下列0 1规划问题 例三 求解下列0 1规划问题 令y1 x5 y2 x4 y3 x2 y4 x3 y5 x1得到下式 所以 Y 0
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论