XW-Ch6网络模型.pptVIP

* 【解】 对于不同的问题，寻求最佳服务点有不同的标准。像图6－14只有两点间的距离，可以采用“使最大服务距离达到最小”为标准，计算步骤如下。 第一步：利用Floyd算法求出任意两点之间的最短距离表(表6－3). 第二步：计算最短距离表中每行的最大距离的最小值，即 * v1 v2 v3 v4 v5 v6 v7 v8 Max Lij v1 0 6 9 5 14 4 6 18 18 v2 6 0 3 2 8 7 5 14 14 v3 9 3 0 5 7 10 8 13 13 v4 5 2 5 0 9 5 3 15 15 v5 14 8 7 9 0 12 10 6 14 v6 4 7 10 5 12 0 2 14 14 v7 6 5 8 3 10 2 0 12 12 v8 18 14 13 15 6 14 12 0 18 产量 80 50 70 40 30 35 60 65 表6－9中倒数第二列最小值为12，位于第7行，则v7为网络的中心，最佳服务点应设置在v7 6.2 最短路问题 Shortest Path Problem * 如果每个点还有一个权数，例如一个网点的人数、需要运送的物质数量、产量等，这时采用“使总运量最小”为标准，计算方法是将上述第二步的最大距离改为总运量，总运量的最小值对应的点就是最佳服务点。 6.2 最短路问题 Shortest Path Problem v1 v2 v3 v4 v5 v6 v7 v8 总运量 v1 0 6 9 5 14 4 6 18 3220 v2 6 0 3 2 8 7 5 14 2465 v3 9 3 0 5 7 10 8 13 2955 v4 5 2 5 0 9 5 3 15 2450 v5 14 8 7 9 0 12 10 6 3780 v6 4 7 10 5 12 0 2 14 2960 v7 6 5 8 3 10 2 0 12 2560 v8 18 14 13 15 6 14 12 0 5040 产量 80 50 70 40 30 35 60 65 * 下一节：最大流问题 6.2 最短路问题 Shortest Path Problem 1.最短路的概念及应用。 2.有向图、无向图一点到各点最短路的Dijkstra算法 3.任意两点最短路的Floyd算法 4.本节介绍了两个应用：设备更新问题和最佳服务点设置问题 作业：… 6.3 最大流问题 Maximal Flow Problem * 6.3 最大流问题 Maximal Flow Problem 6.3.1 基本概念 ① ② ③ ④ ⑤ ⑥ 8 14 5 6 3 3 8 10 7 6 ⑦ 3 4 网络图中定义了一个发点v1，称为源(source，supply node),定义了一个收点v7，称为汇(sink，demand node),其余点v2，v3，…，v6为中间点，称为转运点(transshipment nodes). 图中的权是该弧在单位时间内的最大通过能力，称为弧的容量(capacity). 最大流问题是在单位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量最大. 图 6 | 18 * 设cij为弧(i，j)的容量，是弧(i，j)单位时间内的最大通过能力； fij为弧(i，j)的流量，是弧(i，j)单位时间内的实际通过量. 流量的集合f={fij}称为网络的流. 发点到收点的总流量记为v=val(f)，v也是网络的流量。 图6－18最大流问题的线性规划数学模型为 6.3 最大流问题 Maximal Flow Problem * 满足下列3个条件的流fij 的集合 f ={ fij }称为可行流 发点vs流出的总流量等于流入收点vt的总流量 6.3 最大流问题 Maximal Flow Problem * 链：从发点到收点的一条路线(弧的方向不一定都同向)称为链。从发点到收点的方向规定为链的方向。 前向弧：与链的方向相同的弧称为前向弧。 后向弧：与链的方向相反的弧称为后向弧。 增广链: 设 f 是一个可行流，如果存在一条从vs到vt的链，满足： 1.所有前向弧上fijCij 2.所有后向弧上fij0 则该链称为增广链 ① ② ③ ④ ⑤ ⑥ 前向弧 后向弧 容量 流量 这是一条增广链 8 4 4 6 9 （5） (2) (3) (4) (6) 6.3 最大流问题 Maximal Flow Problem * 第二步：对点进行标号找一条增广链. （1）发点标号（∞） （2）选一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查： A．如果弧的方向向前(前向弧)并且有fijcij，则vj标号: