购买

¥ 10.0

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 运筹学应用实例

运筹学应用实例.ppt

运筹学应用实例

华仔
2019-06-06 0人阅读 举报 0 0 暂无简介

简介:本文档为《运筹学应用实例ppt》,可适用于自然科学领域

sect应用举例例:比赛安排问题有五名运动员参加游泳比赛下表给出了每位运动员参加的比赛项目问如何安排比赛才能使每位运动员都不连续地参加比赛?解:如果两项比赛没有同一名运动员参加把这两项紧排在一起为了解决这个问题只需找到一条包含所有顶点的初等链。如:{vvvvv}是一条初等链对应的比赛是:m自由泳m仰泳m蛙泳m碟泳m自由泳。用顶点vvvvv表示五项比赛项目用一条边把代表这两个项目的顶点连接起来。这样得到下图此问题的方案不唯一。例线路铺设问题下图是一个城镇的地图现在要在该城镇的各地点铺设管道已知各点相互之间的铺设费用(单位:千元)如何设计铺设线路使各地互通的总铺设费用最少?解:求各边相通且总费用最少的方案实际上求最小树保证了各点之间连通且费用最少。其总费用为:千元例设备更新问题某单位使用一台生产设备在每年年底单位领导都要决策下年度是购买新设备还是继续使用旧设备。若购置新设备需要支付一笔购置费如果继续使用旧的则要支付一定的维修费用。一般说来维修费随设备使用年限的延长而增加。根据以往的统计资料已经估算出设备在各年年初的价格和不同使用年限的年维修费用分别示于表和表。表表解:为解决好这一问题建立下述网络模型并用最短路法求解。令:vimdash第i年年初购进一台新设备i=,,,,,v指第五年年末。(vivj)mdash第i年年初引进新设备一直使用到第j年年初。Wijmdash第i年年初购进的新设备一直使用到第j年年初这段期间的全部费用。求解得v到v得最短路径为:vvv最短路长为。设备更新的计划是:第一年初购置一台新设备使用到第二年末第三年初购置一台新设备使用到第五年末总费用为。例房屋设计问题下图是某建筑物的平面图要求在建筑物的内部从每一房间都能走到别的所有房间问至少要在墙上开多少门?试给出一个开门的方案。把每一房间看作一个顶点如果两房间相邻(有共同的隔墙)则用边把对应的两个顶点连起来这样就得到一个无向图如图。从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。解:图的任意一个连通的生成子图在它的所有边对应的隔墙上开门即可达到要求。令所有边的权为为了使开的门尽可能少就要使这个连通子图的生成子图的边尽可能少即求图的最小生成树。开门方案最小生成树对应的开门方案如图所示共开个门。例:选址问题有六个居民点vvvvvv拟定建一夜校已知各点参加学习的人数为、、、、、人其道路如图所示试确定学校位于哪一个居民点才能使学习者所走的总路程最少?(图中边旁的数字为路段长度)解:首先计算各点对间的最短路每个学习者为使所走的路程最短应走最短路。迭代得到最短距离矩阵D和相应的中间点矩阵C如下:考虑各点的学习人数对矩阵D的每一行乘以相应各点的人数得到:最短路程为即夜校应设在v点由C得到相应路径。VhelliphellipV:VVVVVhelliphellipV:VVVVhelliphellipV:VVVhelliphellipV:VVVhelliphellipV:VVV例:网络运输容量问题有三个仓库运送某种产品到四个市场上去仓库的供应量是、和件市场需求量是、、和件。仓库与市场之间的线路上的容量如下表所示(容量零表示两点之间无直接的线路可通)。确定现有线路容量是否能满足市场的需求。若不能应修改哪条线路的容量。用点AAA表示三个仓库点BBBB表示四个市场若仓库与市场间有线路可通则在对应点间连一条弧弧的容量就是线路的容量。增设一发点S连接S与Ai容量为Ai的供应量增设一收点T连接Bi与T容量为Bi的需求量得到如下的网络。问题转化成求S到T的最大流问题。由于最大流量为,而市场总需求量为,所以现有线路容量不能满足市场的需求。由上图得到市场B的需求量不能满足而仓库A的供应量尚有余量所以考虑将弧(AB)容量增至可满足市场的需要。例:分派问题某飞行队有名正驾驶员和名副驾驶员。由于种种原因某些正、副驾驶员不能同时飞行某些则可以如下表所示(*表示可同机飞行)每架飞机出航时需要正、副驾驶员各一人问最多能有几架飞机同时出航?应如何安排正、副驾驶员?用顶点AAAAA表示位副驾驶员BBBBB表示位正驾驶员若正、副驾驶员可同机飞行则在对应的点之间连一条弧方向由A指向B增设一个起点S和终点T得到下图各弧的容量均为。则问题转化成求S到T的最大流问题。fmax=知道最多能有架飞机同时出航。分配方案为:ABABABAB例:桥梁切断问题如下图A、B、C、D、E、F分别表示陆地和岛屿若河的两岸分别被敌对两方部队占领问至少切断哪几座桥梁才能阻止对方部队过河?陆地、河流及桥梁示意图解:将ABCDEF分别用一个点表示相互之间有桥相连的连一条弧弧的容量就是两点间的桥梁数设一个方向得到网络图如下:割是分离A和F的弧的集合,若切断一个割的所有弧对应的桥梁,就可切断A和F之间的线路。切断最小割包含的弧对应的桥梁是切断A和F之间线路的桥梁数最少的方法。由上图得知:已标号点为ABC而DEF不能获得标号从而知道该最大流对应的最小割为{(AE)(CD)(CF)}因此切断AECDCF三座桥梁即可阻止对方部队过河。由最大流最小割定理分离A和F的最小割容量等于由A到F的最大流量例:生产计划问题某工厂与客户签定合同,当月起连续三个月每月末向客户提供某种产品。该厂三个月的生产能力、单位产品生产成本及客户需求见下表。已知单位产品每积压一个月需支付存储费元。在签定合同时工厂有该产品的库存量个工厂希望在第三个月末完成合同后还能存储该产品个。问工厂应如何安排生产计划使在满足上述条件的情况下总的费用最小?月份正常生产能力加班生产能力需求量单位产品正常生产成本单位产品加班生产成本解:构造网络图如下Xmdashmdash工厂处于正常生产状态Xmdashmdash工厂处于加班生产状态Vjmdashmdash第j个月生产产品的存储与供货点。增设起点S和终点T。这样问题就转化为求从S到T的最小费用最大流问题。结束!

VIP尊享8折文档

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/28

运筹学应用实例

¥10.0

会员价¥8.0

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利