10-图及网络分析.ppt

2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 min {8+6,6+4,3+8}=min {14,10,11}=10 [2,v1] [1,v1] [0,v1] [3,v1] [3,v4] [6,v7] [8,v2] [10,v5] 给v3标号[8,v2]; 2 3 7 1 8 4 5 6 6 1 3 4 10 5 2 7 5 9 3 4 6 8 2 1到8的最短路径为{1，4，7，5，8}，长度为10。 [2,v1] [1,v1] [0,v1] [3,v1] [3,v4] [6,v7] [8,v2] [10,v5] 分析：可行的购置方案（更新计划）是很多的，例如： 1）每年购置一台新的，则对应的费用为： 10+12+13+14+15 +4+4+4+4+4 = 84 2)第一年购置新的，一直用到第五年年底，则总费用为： 10+4+6+9+12+19 = 60 显然不同的方案对应不同的费用。 设备在各年年初的价格 第1年 第2年 第3年 第4年 第5年 10 12 13 14 15 使用不同时间（年）的设备所需要的维修费用 使用年数 0-1 1-2 2-3 3-4 4-5 维修费用 4 6 9 12 19 例：求5年内，哪些年初购置新设备，使5年内的总费用最小。 例：设备更新问题 设备在各年年初的价格 第1年 第2年 第3年 第4年 第5年 10 12 13 14 15 使用不同时间（年）的设备所需要的维修费用 使用年数 0-1 1-2 2-3 3-4 4-5 维修费用 4 6 9 12 19 v1 v2 v3 v4 v5 v6 20 29 41 60 22 31 43 23 32 24 14 16 17 18 19 求费用最小的设备更新计划. 方法：将此问题用一个赋权 有向图来描述，然后求这个 赋权有向图的最短路。 求解步骤： 1、画赋权有向图： 设点Vi 表示第i年初 边(Vi ,Vj )表示第i 年初购买 新设备用到第j年初（j-1年底） 边上的权数Wi j 表示相应费用 则5年的一个更新计划相当于 从V1 到V6的一条路。 2、求解 :标号法 W12 =10+4=14 W13 =10+4+6=20 W14 =10+4+6+9=29 W15 =10+4+6+9+12=41 W16 =10+4+6+9+12+19=60 W23 =12+4=16 W24 =12+4+6=22 W25 =12+4+6+9=31 W26 =12+4+6+9+12=43 W34 =13+4=17 W35 =13+4+6=23 W36 =13+4+6+9=32 W45 =14+4=18 W46 =14+4+6=24 W56 =15+4=19 例：设备更新问题 设备在各年年初的价格 第1年 第2年 第3年 第4年 第5年 10 12 13 14 15 使用不同时间（年）的设备所需要的维修费用 使用年数 0-1 1-2 2-3 3-4 4-5 维修费用 4 6 9 12 19 v1 v2 v3 v4 v5 v6 20 29 41 60 22 31 43 23 32 24 14 16 17 18 19 求费用最小的设备更新计划. 使用Dijkstra算法求出： 最优路线：V1?V3?V6 即第1年初购置，第3年初更新，第5年末结束。 总费用：52 13 9 4 5 6 5 5 5 4 4 9 10 四.网络系统的最大流问题 　在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等。 如图所示的网络，每一个弧旁边的权就是对应的容量（最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。 设一个赋权有向图D=（V, E）,在V中指定一个发点vs 和一个收点vt ,其它的点叫做中间点。 对于D中的每一个弧（vi , vj）∈E ,都有一个非负数cij,叫做弧的容量。 网络D上的流，是指定义在弧集合E上的一个函数 其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 （