管理运筹学管理科学方法重点.pptxVIP

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