运筹学应用实例课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学应用实例课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 应用 实例 课件
- 资源描述:
-
1、4.7 应 用 举 例 例1:比赛安排问题有五名运动员参加游泳比赛,下表给出了每位运动员参加的比赛项目,问如何安排比赛,才能使每位运动员都不连续地参加比赛?运动员运动员 50m仰泳仰泳 50m蛙泳蛙泳 100m蝶泳蝶泳 100m自由泳自由泳 200m自由泳自由泳 A *B *C *D *E *解:如果两项比赛没有同一名运动员参加,把这两项紧排在一起v1v2v3v4v5为了解决这个问题,只需找到一条包含所有顶点的初等链。如:v4,v1,v2,v3,v5是一条初等链,对应的比赛是:100m自由泳,50m仰泳,50m蛙泳,100m碟泳,200m自由泳。用顶点v1,v2,v3,v4,v5表示五项比赛项
2、目用一条边把代表这两个项目的顶点连接起来。这样得到下图此问题的方案不唯一。例 2.线路铺设问题下图是一个城镇的地图,现在要在该城镇的各地点铺设管道,已知各点相互之间的铺设费用(单位:千元),如何设计铺设线路,使各地互通的总铺设费用最少?3578479812547610251解:求各边相通且总费用最少的方案,实际上求最小树,保证了各点之间连通且费用最少。35472514其总费用为:31千元例3.设备更新问题某单位使用一台生产设备,在每年年底,单位领导都要决策下年度是购买新设备还是继续使用旧设备。若购置新设备,需要支付一笔购置费;如果继续使用旧的,则要支付一定的维修费用。一般说来,维修费随设备使用
3、年限的延长而增加。根据以往的统计资料,已经估算出设备在各年年初的价格和不同使用年限的年维修费用,分别示于表1和表2。年份年份 1 2 3 4 5 购置费购置费 10 10 11 12 13 使用年限使用年限 0-1 1-2 2-3 3-4 4-5 维修费维修费 5 6 8 11 15 表1表2解:为解决好这一问题,建立下述网络模型,并用最短路法求解。令:vi 第 i 年年初购进一台新设备,i=1,2,3,4,5,6 v6 指第五年年末。(vi,vj)第 i年年初引进新设备一直使用到第 j 年年初。Wij 第 i 年年初购进的新设备一直使用到第 j 年年初这段 期间的全部费用。v41515214
4、02921302216294055182317v1v6v5v3v2求解得v1到v6得最短路径为:v1-v3-v6,最短路长为51。设备更新的计划是:第一年初购置一台新设备,使用到第二年末,第三年初购置一台新设备,使用到第五年末,总费用为51。例4.房屋设计问题下图是某建筑物的平面图,要求在建筑物的内部从每一房间都能走到别的所有房间,问至少要在墙上开多少门?试给出一个开门的方案。ABCDEFIHGJKIABCJKHDGEF把每一房间看作一个顶点,如果两房间相邻(有共同的隔墙),则用边把对应的两个顶点连起来,这样就得到一个无向图,如图。从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。解
5、:图的任意一个连通的生成子图,在它的所有边对应的隔墙上开门,即可达到要求。令所有边的权为1,为了使开的门尽可能少,就要使这个连通子图的生成子图的边尽可能少,即求图的最小生成树。开门方案最小生成树IBACDEFKJHG对应的开门方案如图所示,共开10个门。ABCDEFIHGJK例5:选址问题有六个居民点v1,v2,v3,v4,v5,v6,拟定建一夜校,已知各点参加学习的人数为25、20、30、10、35、45人,其道路如图所示,试确定学校位于哪一个居民点,才能使学习者所走的总路程最少?(图中边旁的数字为路段长度)v1v3v5v6v4v22746811363解:首先计算各点对间的最短路,每个学习者
6、为使所走的路程最短,应走最短路。V1 V2 V3 V4 V5 V6 D0=V1V2V3V4V5V6 0 2 7 2 0 4 6 8 7 4 0 1 3 6 1 0 1 6 8 3 1 0 3 6 3 0V1 V2 V3 V4 V5 V6V1V2V3V4V5V6C0=1 1 1 1 1 1 2 2 2 2 2 23 3 3 3 3 34 4 4 4 4 45 5 5 5 5 56 6 6 6 6 6 迭代得到最短距离矩阵D0和相应的中间点矩阵C0如下:V1 V2 V3 V4 V5 V6 D6=V1V2V3V4V5V60 2 6 7 8 92 0 4 5 6 96 4 0 1 2 57 5 1 0
展开阅读全文