运筹学应用实例分解.ppt

* §4.7 应 用 举 例 例1：比赛安排问题 有五名运动员参加游泳比赛，下表给出了每位运动员参加的比赛项目，问如何安排比赛，才能使每位运动员都不连续地参加比赛？ 运动员 50m仰泳 50m蛙泳 100m蝶泳 100m自由泳 200m自由泳 A * B * * * C * * D * * E * * 解： 如果两项比赛没有同一名运动员参加，把这两项紧排在一起 v1 v2 v3 v4 v5 为了解决这个问题，只需找到一条包含所有顶点的初等链。 如：{v4，v1，v2，v3，v5}是一条初等链，对应的比赛是： 100m自由泳，50m仰泳，50m蛙泳，100m碟泳，200m自由泳。 用顶点v1，v2，v3，v4，v5表示五项比赛项目 用一条边把代表这两个项目的顶点连接起来。这样得到下图 此问题的方案不唯一。 例 2.线路铺设问题 下图是一个城镇的地图，现在要在该城镇的各地点铺设管道，已知各点相互之间的铺设费用（单位：千元），如何设计铺设线路，使各地互通的总铺设费用最少？ 3 5 7 8 4 7 9 8 12 5 4 7 6 10 2 5 1 解：求各边相通且总费用最少的方案，实际上求最小树，保证了各点之间连通且费用最少。 3 5 4 7 2 5 1 4 其总费用为：31千元 例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 年年初这段 期间的全部费用。 v4 15 15 21 40 29 21 30 22 16 29 40 55 18 23 17 v1 v6 v5 v3 v2 求解得v1到v6得最短路径为： v1-v3-v6，最短路长为51。 设备更新的计划是：第一年初购置一台新设备，使用到第二年末， 第三年初购置一台新设备，使用到第五年末，总费用为51。 例4.房屋设计问题 下图是某建筑物的平面图，要求在建筑物的内部从每一房间都能走到别的所有房间，问至少要在墙上开多少门？试给出一个开门的方案。 A B C D E F I H G J K I A B C J K H D G E F 把每一房间看作一个顶点，如果两房间相邻（有共同的隔墙），则用边把对应的两个顶点连起来，这样就得到一个无向图，如图。 从一个房间到另一房间相当于从这个顶点有一条链能到另一个顶点。 解： 图的任意一个连通的生成子图，在它的所有边对应的隔墙上开门，即可达到要求。 令所有边的权为1，为了使开的门尽可能少，就要使这个连通子图的生成子图的边尽