运筹学整数线性规划.pptx
《运筹学整数线性规划.pptx》由会员分享,可在线阅读,更多相关《运筹学整数线性规划.pptx(82页珍藏版)》请在咨信网上搜索。
1、第第1页页运运 筹筹 帷帷 幄幄 之之 中中决决 胜胜 千千 里里 之之 外外运运 筹筹 学学 课课 件件整数线性规划整数线性规划Integer Linear ProgrammingInteger Linear Programming第第2页页整整 数数 规规 划划n整数规划问题与模型整数规划问题与模型n整数规划算法整数规划算法n计算软件计算软件n应用案例应用案例第第3页页整数规划问题整数规划问题n实例实例n特点特点n模型分类模型分类第第4页页应用案例应用案例n投资组合问题投资组合问题n旅游售货员问题旅游售货员问题n背包问题背包问题第第5页页投资组合问题投资组合问题n背背 景景n实实 例例n模
2、模 型型第第6页页背背 景景n证券投资证券投资:把一定的资金投入到合适的:把一定的资金投入到合适的有价证券上以规避风险并获得最大的利有价证券上以规避风险并获得最大的利润。润。n项目投资项目投资:财团或银行把资金投入到若:财团或银行把资金投入到若干项目中以获得中长期的收益最大干项目中以获得中长期的收益最大。第第7页页案案 例例n某财团有某财团有 万元的资金,经出其考察选中万元的资金,经出其考察选中 个投资项目,每个项目只能投资一个。其个投资项目,每个项目只能投资一个。其中第中第 个项目需投资金额为个项目需投资金额为 万元,预计万元,预计5年后获利年后获利 ()万元,问应如何)万元,问应如何选择项
3、目使得选择项目使得5年后总收益最大?年后总收益最大?第第8页页模模 型型n变量变量每每个项目是否投资个项目是否投资n约束约束总总金额不超过限制金额不超过限制n目标目标总收益最大总收益最大第第9页页第第10页页旅游售货员问题旅游售货员问题n背景背景n案例案例n模型模型第第11页页背背 景景n旅游线路安排旅游线路安排 预定景点走且只走一次预定景点走且只走一次 路上时间最短路上时间最短n配送线路配送线路货郎担问题货郎担问题 送货地到达一次送货地到达一次 总路程最短总路程最短第第12页页案案 例例n有一旅行团从有一旅行团从 出发要遍游城市出发要遍游城市 ,已知从,已知从 到到 的旅费为的旅费为 ,问应
4、如何安排行程使总费用最,问应如何安排行程使总费用最小?小?第第13页页模模 型型n变量变量是是否从否从i第个城市到第第个城市到第j个城市个城市n约束约束 每个城市只能到达一次、离开一次每个城市只能到达一次、离开一次第第14页页n避免出现断裂避免出现断裂 每个点给个位势每个点给个位势 除了初始点外要求前除了初始点外要求前点比后点大点比后点大第第15页页n目标目标总总费用最小费用最小第第16页页第第17页页背包问题背包问题n背景背景n案例案例n模型模型第第18页页背背 景景n邮递包裹邮递包裹 把形状可变的包裹用尽量少的车辆运走把形状可变的包裹用尽量少的车辆运走n旅行背包旅行背包 容量一定的背包里装
5、尽可能的多的物品容量一定的背包里装尽可能的多的物品第第19页页实实 例例n某人出国留学打点行李,现有三个旅行包,容某人出国留学打点行李,现有三个旅行包,容积大小分别为积大小分别为1000毫升、毫升、1500毫升和毫升和2000毫升,毫升,根据需要列出需带物品清单,其中一些物品是根据需要列出需带物品清单,其中一些物品是必带物品共有必带物品共有7件,其体积大小分别为件,其体积大小分别为400、300、150、250、450、760、190、(单、(单位毫升)。尚有位毫升)。尚有10件可带可不带物品,如果不件可带可不带物品,如果不带将在目的地购买,通过网络查询可以得知其带将在目的地购买,通过网络查询
6、可以得知其在目的地的价格(单位美元)。这些物品的容在目的地的价格(单位美元)。这些物品的容量及价格分别见下表,试给出一个合理的安排量及价格分别见下表,试给出一个合理的安排方案把物品放在三个旅行包里。方案把物品放在三个旅行包里。第第20页页物品物品12345678910体积体积200350500430320120700420250100价格价格1545100705075200902030第第21页页问题分析问题分析n变量变量对对每个物品要确定是否带同时要确定每个物品要确定是否带同时要确定放在哪个包裹里,如果增加一个虚拟的包裹把放在哪个包裹里,如果增加一个虚拟的包裹把不带的物品放在里面,则问题就转
7、化为确定每不带的物品放在里面,则问题就转化为确定每个物品放在哪个包裹里。如果直接设变量为每个物品放在哪个包裹里。如果直接设变量为每个物品放在包裹的编号,则每个包裹所含物品个物品放在包裹的编号,则每个包裹所含物品的总容量就很难写成变量的函数。为此我们设的总容量就很难写成变量的函数。为此我们设变量为第变量为第i个物品是否放在第个物品是否放在第j个包裹中个包裹中第第22页页n约束约束包裹容量限制包裹容量限制必带物品限制必带物品限制选带物品限制选带物品限制第第23页页n目标函数目标函数未未带物品购买费用最小带物品购买费用最小第第24页页模模 型型第第25页页n特征特征变变量整数性要求量整数性要求n来源
8、来源 问题本身的要求问题本身的要求 引入的逻辑变量的需要引入的逻辑变量的需要n性质性质可可行域是离散集合行域是离散集合第第26页页第第27页页线性整数规划模型线性整数规划模型n一般整数规划模型一般整数规划模型n0-1整数规划模型整数规划模型n混合整数规划模型混合整数规划模型第第28页页一般整数规划模型一般整数规划模型第第29页页0-1整数规划模型整数规划模型第第30页页混合整数规划模型混合整数规划模型第第31页页算算 法法n与线性规划的关系与线性规划的关系n分支定界算法分支定界算法n割平面算法割平面算法n近似算法近似算法第第32页页与线性规划的关系与线性规划的关系整数规划整数规划放松的线性规划
9、放松的线性规划可行解是放松问题的可行解可行解是放松问题的可行解最优值大于等于放松问题的最优值最优值大于等于放松问题的最优值第第33页页第第34页页第第35页页注注 释释n最优解不一定在顶点上达到最优解不一定在顶点上达到n最优解不一定是放松问题最优解的邻近整最优解不一定是放松问题最优解的邻近整数解数解n整数可行解远多余于顶点,枚举法不可取整数可行解远多余于顶点,枚举法不可取第第36页页分支定界算法分支定界算法n算法思想算法思想n算法步骤算法步骤n算例算例n注释注释第第37页页算算 法法 思思 想想隐枚举法隐枚举法求解放松问题求解放松问题最优值比界坏最优值比界坏 最优解为整数最优解为整数最优值比界
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 整数 线性规划
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【可****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【可****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。