第7章网络分析-中国人民大学出版社.ppt

管理运筹学-管理科学方法 第7 章 网络分析 OR:SM * * * 中国人民大学出版社 谢家平 编著 Sub title 学习要点 理解图论中结点、边、链、弧、路径的概念 了解树的概念、最小树的求解方法及其应用 掌握最短路的标号算法及网络选址中的应用 理解网络流的概念及其网络瓶颈的识别方法 正确理解最小费用流的调整改进思路和方法 18世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？ 第7 章 网络分析 陆地A 陆地B 岛D 岛C A · D · · B · C 1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。 第一节 图论的概念 一、图的内涵 1、图的定义 · v1 · v4 v2· · v3 e1 e2 e3 e4 e5 e6 · v1 · v4 v2· v3 · e1 e2 e3 e4 e5 e6 · v1 · v2 · v3 · v4 e1 e2 e3 e4 e5 e6 图论的图与一般几何图形或代数函数图形是完全不同的 图论中的图:由一些点和连接点的线所组成的“图形” 点和线的位置是任意的 线的曲直、长短与实际无关，代表的只是点与点之间的相互关系 例：表示苏州v1 、杭州v2 、上海v3 、南京v4仓储网点之间的物流运输线路关系 第一节 图论的概念 一、图的内涵 2、图的分类 不带箭头的连线称为“边”，如公路运输线路； 带箭头的连线称为“弧”，如供排水的管道运输线路。 1、无向图 由点和边的集合所构成 由点和弧的集合所构成 2、有向图 链：无向网络中，前后相继点和边的交替序列称为一条链。 圈：闭合的链称为一个圈。 路径：有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。 回路：闭合的路径称为一个回路。 第二节 最小树问题 一、最小树的涵义 1、树的定义 无圈的连通图就是一棵树。 所谓连通图是指网络中任意两个结点之间都至少有一条链相连。 2、树的性质 [性质1] 任何树至少有一个悬挂结点。 [性质2] 树中任意两点之间有且只有一条链。 [性质3] 树中任意两个不相邻的结点之间增加一条边，则形成唯一的圈。 [性质4] 如果树的结点是m个，则边的个数为m-1个。 [性质5] 在树中任意去掉一条边，将得到一个不连通图。 3、最小树 把一棵树各边的权数总和，称为该树的树权。 权数总和为最小的那棵支撑树，称为最小支撑树，简称最小树。 第二节 最小树问题 二、最小树的求法 1、破圈法 从无向网络中任选一个圈，去掉圈中权数最大的边，便破一圈；如果最大权数的边不止一条，则任选其一去掉。如此反复操作，直至网络中不含圈为止。此时的支撑树就是最小树。 2、闭圈法 从无向网络中，开始选取权数最小的一条边，再选权数为次小的一条边；如此进行，总从剩余边中选取权数最小者，但前提是与已经选择的边不要构成圈；如果最小权数的边不止一条，则任选一条。 第二节 最小树问题 二、最小树的求法 例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，已知办公室之间的走线距离，应如何铺设网线才能使网线总长为最短？ 最短网线总长度为最小树权之和2+3+4+6+6=21 · v3 e2 8 2 3 5 4 6 6 6 8 v1 v4 v2 v3 v5 v6 第三节 最短路问题 一、双标号算法 狄克斯特拉(Dijkstra)算法 路权：弧(vi, vj)的权为wij；路权是路p中各条弧权之和 最短路：在所有从vs到vt 的路p中，求一条路权最短的路 算法说明： 1959年提出，目前公认的最短路算法 适合于求解所有弧权wij ≥0的最短路问题 算法假设：有向图D是完备图 图D中任意两点vi , vj 之间，恰有两条弧(vi , vj)和(vj , vi) 若vi→vj 不存在弧, 可设想一条从vi →vj 的弧, 权wij=+∞； 若vi → vj 有重复的弧，则保留弧权最小的弧 第三节 最短路问题 一、双标号算法 1、标号法的基本思路 基本思路: 从始点vs 出发，逐步探寻，给每个点标号； 标号分永久标号P(vk)和临时标号T(vk) 两种： 永久标号P(vk) 是从点 vs → vk 的最短路权 临时标号T(vk) 是从点 vs → vk 最短路权的上界 算法的每一步从临时标号集中选最小者变为永久标号； 经过逐次改变，就可以得到从点vs 到各点的最短路。 标号形式： 单标号法是对每一点赋予一个路权标号 双标号法是对每一点赋予两个标号：路