网络模型 Network Modeling Operations Research 运 筹 学

Presentation on theme: "网络模型 Network Modeling Operations Research 运 筹 学"— Presentation transcript:

1 网络模型 Network Modeling Operations Research 运 筹 学
            运 筹 学   Operations  Research 网络模型 Network Modeling 1 最小(支撑)树问题 Minimal (Spanning)Tree Problem 2 最短路问题 Shortest Path Problem 3 最大流问题 Maximal Flow Problem 4 旅行售货员与中国邮路问题 Traveling Salesman and China Carrier Problem

2 实例1： 著名的哥尼斯堡七桥问题 18世纪的哥尼斯堡城中有一条河，河的两岸与河中的两个小岛有7座桥彼此联接，问一个步行者能否通过每座桥一次且仅一次就能返回原出发地？ C A B D B C A D 问题转化为：能否从任何一个顶点(A，B，C，D)出发，恰好 经过每条边一次而返回原地？ 1736年欧拉证明了否定的答案。

3 实例2： 下图是一张石油流向管网示意图，A 表示石油开采
地，H 为石油汇集站，B，C，D，E，F 表示可供选择的石 油流动加压站，数字为两地距离（管长），问如何选择管线， 使将油从 A 送到 H 所需油管最短？ A B C D E F H 6 2 8 4 12 3 1

4 图的基本概念: 一个图G是由n个元素的非空集合V和V中给定的q个无序对构成的集合所组成的二元组，记作G = (V, E), 其中V={v1,v2, ··· ,vn}称为图G 的顶点集，V中的元素称为顶点； E={e1,e2, ··· ,eq}称为图G 的边集或弧集，E中的元素称为边，若边 是有方向的，我们称之为弧。 图可分为有向图与无向图，我们先讨论无向图的情况：

5 无向图概念 (5) 以点v为端点的边的个数称为v的度. 表示为: d(v)

6 定理1: 图G=(V,E)中,所有点的次之和是边数的两倍, 即:
定理2: 任意一图中, 奇点的个数为偶数. 证明:设 V1--奇点的集合, V2--偶点的集合 偶数 偶数 偶数

7 多重图：含有多重边的图称为多重图 简单图：无环无多重边的图称为简单图 子 图： 子图。 支撑子图。 有向图： 由一些点和连接这些点的弧(带有方向箭头)组成的图形 注意：有向图中 链：设G=(V, E)为无向图，称由点和边交替组成的序列 为连接vi1和vit的一条链，可简记为

8 圈: 当一条链的两个端点重合 (即vi1＝vit)时，则称之为圈。
连通图：若无向图中任何两点间至少存在一条链，则称之为连通 图;否则称之为不连通图。 不连通图 连 通 图 赋权图：若图G 的每一条边(弧)都赋予一个系数wij，则称G为赋 权无向(有向)图，赋权图记为G=(V, E, W).

9 Minimal (Spanning)Tree Problem
1 最小(支撑)树问题 Minimal (Spanning)Tree Problem

10 树(Tree): 一个无圈且连通的无向图称为树图, 简称树。
1 最小树问题 Minimal tree problem 1.1 树的概念 树(Tree): 一个无圈且连通的无向图称为树图, 简称树。 树的性质：（1）一棵树的边数等于点数减1； （2）在树中任意两个点之间添加一条边就形成圈； （3）在树中去掉任意一条边图就变为不连通。 支撑树(Spanning Tree )：在一个连通图G中，取部分边连接G的所有点组成的树称为G的支撑树(Spanning Tree )或部分树。 v1 v2 v3 v4 v5 v6 4 3 2 1 图1 7 v1 v2 v3 v4 v5 v6 4 3 2 1 图2 7

11 最小部分树可以直接用作图的方法求解，常用的方法有： 破圈法、 加边法 破圈法：任取一圈，去掉圈中最长边，直到无圈。
1 最小树问题 Minimal tree problem 1.2 最小部分树 将网络图G边上的权看作两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C(T)。 G的所有部分树中长度最小的部分树称为最小部分树(或最小支撑树)，简称为最小树。 最小部分树可以直接用作图的方法求解，常用的方法有： 破圈法、 加边法 破圈法：任取一圈，去掉圈中最长边，直到无圈。

12 注：当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小树有可能不唯一，但最小树的长度相同
1 最小树问题 Minimal tree problem 【例1】用破圈法求图1的最小树。 v1 8 v3 7 v5 5 4 5 8 1 2 v2 3 6 v6 v4 图 4 图1 图4就是图1的最小部分树，最小树长为 C(T)= =15。 注：当一个圈中有多个相同的最长边时，不能同时都去掉，只能去掉其中任意一条边。最小树有可能不唯一，但最小树的长度相同

13 × 加边法：取图G的n个孤立点｛v1，v2，…， vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边） v1
1 最小树问题 Minimal tree problem 加边法：取图G的n个孤立点｛v1，v2，…， vn}作为一个支撑图，从最短边开始往支撑图中添加，见圈回避，直到连通（有n－1条边） v1 v3 v5 v1 v3 v5 1 5 v2 v4 v6 8 4 3 7 2 6 5 4 5 2 1 × v2 3 v6 v4 图6－5 Min C(T)=15 在图6－5中，如果添加边[v1, v2]就形成圈｛v1, v2, v4｝，这时就应避开添加边[v1, v2]，添加下一条最短边[v3, v6]。破圈法和加边法得到树的形状可能不一样，但最小树的长度相等

14 1.图的有关概念 2.树、支撑树、最小支撑树的概念 3.掌握求最小树的方法： （1）破圈法 （2）加边法 下一节：最短路问题 1 最小树问题
Minimal tree problem 1.图的有关概念 2.树、支撑树、最小支撑树的概念 3.掌握求最小树的方法： （1）破圈法 （2）加边法 下一节：最短路问题

15 2 最短路问题 Shortest Path Problem

16 最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。
2 最短路问题 Shortest Path Problem 2.1最短路问题的网络模型 最短路问题，就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。 最短路问题在实际中具有广泛的应用，如管道铺设、线路选择等问题，还有些如设备更新、投资等问题也可以归结为求最短路问题 求最短路有两种算法： 一是求从某一点至其它各点之间最短离的狄克斯屈拉(Dijkstra)算法； 另一种是求网络图上任意两点之间最短路的Floyd(弗洛伊德)矩阵（表格）算法。

17 【例3】图6中的权cij表示vi到vj的距离(费用、时间)，从v1 修一条公路或架设一条高压线到v7，如何选择一条路线使距离
2 最短路问题 Shortest Path Problem 【例3】图6中的权cij表示vi到vj的距离(费用、时间)，从v1 修一条公路或架设一条高压线到v7，如何选择一条路线使距离 最短，建立该问题的网络数学模型。 14 ② ⑤ 11 9 6 2 3 10 ① ③ 8 ⑦ 6 7 5 12 16 ④ ⑥ 5 图6

18 【解】 设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：
2 最短路问题 Shortest Path Problem 【解】 设xij为选择弧(i，j)的状态变量，选择弧(i，j)时xij＝1，不选择弧(i，j)时xij＝0，得到最短路问题的网络模型：

19 2.2 有向图的狄克斯屈拉(Dijkstra)标号算法
2 最短路问题 Shortest Path Problem 2.2 有向图的狄克斯屈拉(Dijkstra)标号算法 先求有向图的最短路，设网络图的起点是vs , 终点是vt , 以vi为起点vj 为终点的弧记为(i，j ), 距离为cij ≥0, vi到vj 的最短路记为Pij , 最短路长记为Lij. 点标号：b(j) —起点vs到点vj的最短路长； 弧标号：k(i，j)=b(i)+cij， 步骤：(1) 起点的标号: b(s)＝0; (2) 找出所有起点vi已标号终点vj未标号的弧, 集合为 B={(i，j) | vi已标号，vj未标号}，如果这样的弧不存在或vt已标号则计算结束； (3) 计算集合B中弧的标号: k(i，j)=b(i)+cij (4)选一个点标号 , 在终点vl 处标号b(l) 返回到第(2)步。

20 【例6.4】用Dijkstra算法求图6－6 所示v1到v7的最短路及最短路长
2 最短路问题 Shortest Path Problem 【例6.4】用Dijkstra算法求图6－6 所示v1到v7的最短路及最短路长 6 18 14 20 ② ⑤ 11 18 9 6 6 9 2 29 3 10 10 ① ③ 8 ⑦ 24 29 6 7 9 16 5 12 14 32 12 16 ④ ⑥ 5 17 16 12 图6 v1 到v7的最短路为：p17=｛v1, v2, v3, v5, v7｝，最短路长为L17=29

21 (2) Dijkstra算法可以求任意两点的最短路，只要将两个点看作是路线的始点和终点，然后进行标号；
2 最短路问题 Shortest Path Problem 注: (1) Dijkstra算法可以求某一点 vi 到其他各点 vj 的最短路，只要将 vj 看作是路线的终点，使得 vj 得到标号，如果某个点 vj 不能标号，说明 vi 不可到达 vj ; (2) Dijkstra算法可以求任意两点的最短路，只要将两个点看作是路线的始点和终点，然后进行标号； (3) 最短路可能不惟一，但最短路长相等; (4) Dijkstra算法的条件是弧长非负，问题是求最小值，对于最大值问题无效。

22 2.3 无向图最短路的求法 无向图最短路的求法只将上述步骤 (2) 改动一下即可。 点标号：b(i) —起点vs到点vi的最短路长； 边标号：k(i, j)=b(i)+cij ， 步骤：(1)令起点的标号；b(s)＝0。 (2)找出所有一端vi已标号另一端vj未标号的边集合 B={[i，j]}, 如果这样的边不存在或vt已标号则计算结束； (3)计算集合B中边标号：k[i，j]=b(i)+cij (4)选一个点标号: 返回到第(2)步。

23 【例5】求图10所示v1到各点的最短路及最短距离
2 最短路问题 Shortest Path Problem 【例5】求图10所示v1到各点的最短路及最短距离 4 11 6 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 12 16 18 18 4 9 6 8 3 12 8 5 24 18 6 12 3 2 24 10 2 6 图6-10 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。

24 2.有向图、无向图一点到各点最短路的Dijkstra算法
2 最短路问题 Shortest Path Problem 1.最短路的概念及应用。 2.有向图、无向图一点到各点最短路的Dijkstra算法 下一节：最大流问题

25 作业：用Dijkstra算法计算v0到v8的最短路径，要求写出步骤
2 最短路问题 Shortest Path Problem 作业：用Dijkstra算法计算v0到v8的最短路径，要求写出步骤 图6

26 作业：用Dijkstra算法计算v0到v8的最短路径，要求写出步骤
2 最短路问题 Shortest Path Problem 作业：用Dijkstra算法计算v0到v8的最短路径，要求写出步骤 图6

27 作业：某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如下图，图中v1,…,v7 表示7个学院办公室，请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。
3 1 7 2 8 5 4 10 v7 v6 v5 v4 v2 v3 图11-14