管理运筹学管理科学方法

管理运筹学-管理科学方法中国人民大学出版社谢家平编著1第7章网络分析Subtitle学习要点

理解图论中结点、边、链、弧、路径的概念了解树的概念、最小树的求解方法及其应用掌握最短路的标号算法及网络选址中的应用理解网络流的概念及其网络瓶颈的识别方法正确理解最小费用流的调整改进思路和方法218世纪，哥尼斯堡城中有一条普雷格尔河，河上有七座桥将河中的两个小岛与河岸连接起来。人们提出了这样的问题：一个散步者能否从某地出发，走遍七桥且每座桥恰好经过一次，最后回到原地？

第7章网络分析陆地A陆地B岛D岛CA·D

··B·C

1736年瑞士数学家欧拉将两岸和小岛抽象为四个点，将桥抽象为七条边，此问题归结为一笔画问题。3第一节图论的概念一、图的内涵

1、图的定义

·

v1·v4v2··

v3e1e2e3e4e5e6·v1·v4v2·v3·

e1e2e3e4e5e6·

v1·

v2·

v3·

v4e1e2e3e4e5e6图论的图与一般几何图形或代数函数图形是完全不同的图论中的图:由一些点和连接点的线所组成的“图形”点和线的位置是任意的线的曲直、长短与实际无关，代表的只是点与点之间的相互关系例：表示苏州v1

、杭州v2

、上海v3

、南京v4仓储网点之间的物流运输线路关系4第一节图论的概念一、图的内涵

2、图的分类

不带箭头的连线称为“边”，如公路运输线路；带箭头的连线称为“弧”，如供排水的管道运输线路。1、无向图由点和边的集合所构成由点和弧的集合所构成2、有向图链：无向网络中，前后相继点和边的交替序列称为一条链。圈：闭合的链称为一个圈。路径：有向网络图中，前后相继并且方向一致的点弧序列称为一条路径。回路：闭合的路径称为一个回路。5第二节最小树问题一、最小树的涵义

1、树的定义

无圈的连通图就是一棵树。所谓连通图是指网络中任意两个结点之间都至少有一条链相连。2、树的性质

[性质1]任何树至少有一个悬挂结点。[性质2]树中任意两点之间有且只有一条链。[性质3]树中任意两个不相邻的结点之间增加一条边，则形成唯一的圈。[性质4]如果树的结点是m个，则边的个数为m-1个。[性质5]在树中任意去掉一条边，将得到一个不连通图。

3、最小树把一棵树各边的权数总和，称为该树的树权。权数总和为最小的那棵支撑树，称为最小支撑树，简称最小树。6第二节最小树问题二、最小树的求法

1、破圈法

从无向网络中任选一个圈，去掉圈中权数最大的边，便破一圈；如果最大权数的边不止一条，则任选其一去掉。如此反复操作，直至网络中不含圈为止。此时的支撑树就是最小树。2、闭圈法从无向网络中，开始选取权数最小的一条边，再选权数为次小的一条边；如此进行，总从剩余边中选取权数最小者，但前提是与已经选择的边不要构成圈；如果最小权数的边不止一条，则任选一条。7第二节最小树问题二、最小树的求法

例：一家企业分别要在6间办公室铺设网线接入口，网线的可行走线方式如下图所示，已知办公室之间的走线距离，应如何铺设网线才能使网线总长为最短？最短网线总长度为最小树权之和2+3+4+6+6=21·

v3e2823546668v1v4v2v3v5v68第三节最短路问题一、双标号算法

狄克斯特拉(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第三节最短路问题一、双标号算法

1、标号法的基本思路

基本思路:从始点vs

出发，逐步探寻，给每个点标号；标号分永久标号P(vk)和临时标号T(vk)

两种：永久标号P(vk)

是从点vs

→

vk

的最短路权临时标号T(vk)

是从点vs

→vk

最短路权的上界算法的每一步从临时标号集中选最小者变为永久标号；经过逐次改变，就可以得到从点vs

到各点的最短路。

标号形式：单标号法是对每一点赋予一个路权标号双标号法是对每一点赋予两个标号：路标、路权10第三节最短路问题一、双标号算法

2、标号法的具体步骤

首先，给网络始点标上永久标号，给从网络始点出发的各弧（一步可达）的结点标上临时标号。第二，在所有临时标号中选择路权最小者，则将结点的临时标号变为永久标号，在标号下画横线。第三，接着考察刚刚获得永久标号的结点，修改从结点出发的各弧的点的临时标号。如果,则结点的临时标号不变；反之，就将结点的临时标号变为(,)，并划去其原有较大的标号。依此类推，当所有标号都是永久标号，则标号过程结束。

11第三节最短路问题一、双标号算法

3、标号法的算法举例例：用双标号法求下图网络最短路394732614128711012第三节最短路问题一、双标号算法

第一步：394732614128711013第三节最短路问题一、双标号算法

第二步：394732614128711014第三节最短路问题一、双标号算法

第三步：394732614128711015第三节最短路问题一、双标号算法

最终：依此类推，重复上述标号过程。得最短路。394732614128711016第三节最短路问题二、策略递推法

狄克斯特拉标号算法只适合所有弧权≥0的情况，当赋权有向图中存在负权（<0）时，标号算法失效。可以借助动态规划的递推方程，进行迭代寻求最短路递推法的基本思路

从到任一点的最短路权记为，根据最短路的特性，若是到的最短路，则一定是到的最短路，其路权为。故必定满足方程：

。17第三节最短路问题二、策略递推法

例：用递推算法求解下表中到其余各点的最短路

结点082∞∞∞803∞4∞23085∞∞∞8066∞45606∞∞∞66018第三节最短路问题二、策略递推法

最短路的函数迭代过程结点082∞∞∞803∞4∞23085∞∞∞8066∞45606∞∞∞660082∞∞∞052107∞052107130521071319第三节最短路问题二、策略递推法

各结点之间的最短距离矩阵结点052107135031041023085111010806674560613101166020第三节最短路问题三、最短路的应用

1、网络的中心所谓网络的中心是指一个网络中，选择某一点，使之其余各点到该中心点的距离之和为最小。例：如果要在下表中6个销售点中选一个作为仓库所在地，应该建在哪个经销点，使其余各销售点都离它较近？21第三节最短路问题三、最短路的应用

2、网络的重心引进点的权系数，将权系数与最短距离阵各列对应元素加权求和，再从中选择最小的即为网络重心。22第四节网络最大流一、相关概念与定理1、弧容量与容量网络对于有向图D=(V,A),，弧的容量表示弧的最大流通能力。在V中指定一点称为发点(记为vs)，另一点称收点(记为vt)，其余点叫中间点，这样的赋权有向图就称为一个容量网络，记N=(V,A,B)2、弧的流量与可行流

弧的实际通过量称为该弧的流量。弧集A上的流量集合称为网络上的流。满足下述条件的流称为可行流。

①容量限制：对每条弧，都有②平衡条件：中间点流出量=流入量23第四节网络最大流一、相关概念与定理3、前向弧与后向弧

4、饱和弧与非饱和弧

弧的流量与之容量比较：满足的弧称为饱和弧，弧的流量不能再扩充；满足的弧称为非饱和弧，弧的流量允许再被扩大。μ是从vs

到vt

的链，方向从vs

→vt

，则链μ上的弧分为两类前向弧：弧的方向与链μ的方向相同，记μ+

后向弧：弧的方向与链μ的方向相反，记μ-5、零弧与非零弧

满足的弧称为零弧。由于，所以弧的流量不能减小；满足的弧称为非零弧。弧的流量可以被减小，但要满足0。

24第四节网络最大流一、相关概念与定理6、流量可以扩充的路

设是一可行流，μ是从vs

到vt

的链，若链μ满足：①μ上的所有前向弧为非饱和弧，即满足，可以扩充流量②μ上的所有后向弧为非零弧，即满足，可以减少流量；则称是一条关于可行流的可扩充流量的路，亦称增广链。7、流量可以扩充的路

可行流中，网络发点的流出量（或网络收点的流入量）就是网络的流量。一个容量网络的诸可行流中，网络流量最大的可行流，称为最大流25第四节网络最大流二、求最大流标号法

1956年，福特和富尔克逊提出了寻求网络最大流的基本方法，称为福特-富尔克逊算法（Fold-FulkersonAlgorithm）。给定可行流X={xij}

，标号判断有无增广链①先给vs

标上(vs,+)，vs已标号尚未检查，其余未标号②取一个已标号但未检查的点vi进行检查，对未标号点vj

：前向弧(vi,vj)可以扩充流量(xij＜rij)vj尚未标号，则给vj

标号(vi，+)，vj

成为己标号尚未检查的点后向弧(vk,vi)可以减少流量(xki＞0)

vk尚未标号，则给vk

标号(vi,-)，vk成为己标号尚未检查的点vi成为已标号已检查的点，在其标号下划横线③检查收点vt

是否已标号：vt被标上号则找到增广链，进行流量调整；否则转第②步若所有标号都已检查，vt又未标号，则不存在增广链标号过程

26第四节网络最大流二、求最大流标号法

流量调整过程反向追踪找出vs

到vt

的增广链μ计算增广链μ上可调整的流量θ调整可行流的流量，得新的可行流xij

′抹去所有标号，对新的可行流X′

={xij′}，重新进入标号过程27第四节网络最大流二、求最大流标号法

例：下图表示了企业所处的供应市场（v1和v2）、配送中心（v3和v4、以及销售市场（v5、v6和v7）组成的网络，各弧上括号里的前一个数字表示弧的容量，后一个数字是目前的实际流量。试求这个供应-销售网络的最大流方案。

(4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)28第四节网络最大流二、求最大流标号法

供应-销售网络的可行流

(4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)29第四节网络最大流二、求最大流标号法

供应-销售网络的可扩充路

(4,3)(10,6)(15,9)(4,4)(5,5)(6,3)(6,6)(15,6)(12,12)(5,4)(10,8)(8,6)(+,∞)(+,4)(+,9)(-,3)(+,3)(+,3)(+,2)30第四节网络最大流二、求最大流标号法

调整后的可行流

最大流量为(4,1)(10,8)(15,11)(4,4)(5,5)(6,5)(6,6)(15,8)(12,12)(5,4)(10,10)(8,6)31第四节网络最大流三、网络的瓶颈识别1、截集-截量与最小截集

2、最大流-最小截量定理

网络中，任一可行流的流量恒不超过任一截集的截量，称为流量-截量定理。最小截量的大小影响总流量的提高

截集：对于网络N=(V,A,R)，将V分为两个非空集合S和S'，使发点vs∈S，收点vt∈S'

所有起点属于S而终点属于S'的弧的集合称为截集(S,S')截量：截集(S,S')中所有弧的容量之和r(S,S')最小截集：截量最小的截集32第五节最小费用流一、调整法求解步骤先不考虑费用问题，求得任一可行流X据此构造赋权有向图W(X)顶点是原网络N的顶点弧权根据可行流X确定弧(vi,vj)的流量可以增加，则照原方向画弧，标上费用bij弧(vi,vj)的流量可以减少，则照反方向画弧，标上费用-bij在赋权有向图W(X)中寻找负回路(总权为负值的回路)：若没有负回路，则得到最小费用流若存在负回路，则调整与负回路相对应的弧上的流量计算调整量θ，进行流量调整若弧(vi,vj)与负回路方向一致，则其流量调整为xij

+θ若弧(vi,vj)与负回路方向相反，则其流量调整为xij

-θ赋权有向