运筹学应用实例ppt课件.ppt

4 7应用举例 例1 比赛安排问题 有五名运动员参加游泳比赛 下表给出了每位运动员参加的比赛项目 问如何安排比赛 才能使每位运动员都不连续地参加比赛 1 解 如果两项比赛没有同一名运动员参加 把这两项紧排在一起 为了解决这个问题 只需找到一条包含所有顶点的初等链 如 v4 v1 v2 v3 v5 是一条初等链 对应的比赛是 100m自由泳 50m仰泳 50m蛙泳 100m碟泳 200m自由泳 用顶点v1 v2 v3 v4 v5表示五项比赛项目 用一条边把代表这两个项目的顶点连接起来 这样得到下图 此问题的方案不唯一 2 例2 线路铺设问题 下图是一个城镇的地图 现在要在该城镇的各地点铺设管道 已知各点相互之间的铺设费用 单位 千元 如何设计铺设线路 使各地互通的总铺设费用最少 3 解 求各边相通且总费用最少的方案 实际上求最小树 保证了各点之间连通且费用最少 其总费用为 31千元 4 例3 设备更新问题 某单位使用一台生产设备 在每年年底 单位领导都要决策下年度是购买新设备还是继续使用旧设备 若购置新设备 需要支付一笔购置费 如果继续使用旧的 则要支付一定的维修费用 一般说来 维修费随设备使用年限的延长而增加 根据以往的统计资料 已经估算出设备在各年年初的价格和不同使用年限的年维修费用 分别示于表1和表2 表1 表2 5 解 为解决好这一问题 建立下述网络模型 并用最短路法求解 令 vi 第i年年初购进一台新设备 i 1 2 3 4 5 6v6指第五年年末 vi vj 第i年年初引进新设备一直使用到第j年年初 Wij 第i年年初购进的新设备一直使用到第j年年初这段期间的全部费用 6 求解得v1到v6得最短路径为 v1 v3 v6 最短路长为51 设备更新的计划是 第一年初购置一台新设备 使用到第二年末 第三年初购置一台新设备 使用到第五年末 总费用为51 7 例4 房屋设计问题 下图是某建筑物的平面图 要求在建筑物的内部从每一房间都能走到别的所有房间 问至少要在墙上开多少门 试给出一个开门的方案 8 把每一房间看作一个顶点 如果两房间相邻 有共同的隔墙 则用边把对应的两个顶点连起来 这样就得到一个无向图 如图 从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点 解 图的任意一个连通的生成子图 在它的所有边对应的隔墙上开门 即可达到要求 9 令所有边的权为1 为了使开的门尽可能少 就要使这个连通子图的生成子图的边尽可能少 即求图的最小生成树 开门方案 最小生成树 对应的开门方案如图所示 共开10个门 10 例5 选址问题 有六个居民点v1 v2 v3 v4 v5 v6 拟定建一夜校 已知各点参加学习的人数为25 20 30 10 35 45人 其道路如图所示 试确定学校位于哪一个居民点 才能使学习者所走的总路程最少 图中边旁的数字为路段长度 11 解 首先计算各点对间的最短路 每个学习者为使所走的路程最短 应走最短路 迭代得到最短距离矩阵D0和相应的中间点矩阵C0如下 12 考虑各点的学习人数 对矩阵D6的每一行乘以相应各点的人数 得到 13 最短路程为520 即夜校应设在v4点 由C6得到相应路径 V1 V4 V1 V2 V3 V4V2 V4 V2 V3 V4V3 V4 V3 V4V5 V4 V5 V4V6 V4 V6 V5 V4 14 例6 网络运输容量问题 有三个仓库运送某种产品到四个市场上去 仓库的供应量是20 20和100件 市场需求量是20 20 60和20件 仓库与市场之间的线路上的容量如下表所示 容量零表示两点之间无直接的线路可通 确定现有线路容量是否能满足市场的需求 若不能 应修改哪条线路的容量 15 用点A1 A2 A3表示三个仓库 点B1 B2 B3 B4表示四个市场 若仓库与市场间有线路可通 则在对应点间连一条弧 弧的容量就是线路的容量 16 增设一发点S 连接S与Ai 容量为Ai的供应量 增设一收点T 连接Bi与T 容量为Bi的需求量 得到如下的网络 问题转化成求S到T的最大流问题 17 由于最大流量为110 而市场总需求量为120 所以现有线路容量不能满足市场的需求 由上图得到 市场B3的需求量不能满足 而仓库A3的供应量尚有余量 所以考虑将弧 A3 B3 容量增至50 可满足市场的需要 18 例8 分派问题 某飞行队有5名正驾驶员和5名副驾驶员 由于种种原因 某些正 副驾驶员不能同时飞行 某些则可以 如下表所示 表示可同机飞行 每架飞机出航时需要正 副驾驶员各一人 问最多能有几架飞机同时出航 应如何安排正 副驾驶员 19 用顶点A1 A2 A3 A4 A5表示5位副驾驶员 B1 B2 B3 B4 B5表示5位正驾驶员 若正 副驾驶员可同机飞行 则在对应的点之间连一条弧 方向由A指向B 增设一个起点S和终点T 得到下图 各弧的容量均为1 则问题转化成求S到T的最大流问题 20 21 fmax 4 知道最多能有4架飞机同时出航 分配方案为 A2 B1 A3 B4 A4 B2 A5 B5 22 例9 桥梁切断问题 如下图A B C D E F分别表示陆地和岛屿 若河的两岸分别被敌对两方部队占领 问至少切断哪几座桥梁才能阻止对方部队过河 陆地 河流及桥梁示意图 23 解 将A B C D E F分别用一个点表示 相互之间有桥相连的连一条弧 弧的容量就是两点间的桥梁数 设一个方向 得到网络图如下 割是分离A和F的弧的集合 若切断一个割的所有弧对应的桥梁 就可切断A和F之间的线路 切断最小割包含的弧对应的桥梁 是切断A和F之间线路的桥梁数最少的方法 24 由上图得知 已标号点为A B C 而D E F不能获得标号 从而知道该最大流对应的最小割为 A E C D C F 因此 切断AE CD CF三座桥梁 即可阻止对方部队过河 由最大流最小割定理 分离A和F的最小割容量等于由A到F的最大流量 25 例11 生产计划问题 某工厂与客户签定合同 当月起连续三个月每月末向客户提供某种产品 该厂三个月的生产能力 单位产品生产成本及客户需求见下表 已知单位产品每积压一个月需支付存储费2元 在签定合同时 工厂有该产品的库存量5个 工厂希望在第三个月末完成合同后还能存储该产品10个 问工厂应如何安排生产计划 使在满足上述条件的情况下 总的费用最小 月份 正常生产能力 加班生产能力 需求量 单位产品正常生产成本 单位产品加班生产成本 1