信息技术--网络分析与网络计划（DOC 62页）

第六章网络分析与网络计划网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段．网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programmeevaluationandreviewtechnique，简称PERT)和关键路径方法(criticalpathmethod或criticalpathanalysis，简称CPM、CPA)．网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支．本章在引入有关图的一些基本概念的基础上，介绍最小生成树、网络最短路、最大流、最小费用最大流等网络分析模型及其解法；并对网络计划图（统筹图）的制作、作业时间参数计算、关键线路方法和计划评审技术等网络计划基本技术和方法进行初步介绍．第一节图的基本概念一、图现实世界中有许多具体事物及关系可以用图形来抽象表示．例如，路线关系、工序安排、区位规划等都可以用图来表达．我们先通过几个直观的例子，来认识什么是图．例6-1歌尼斯堡七桥问题哥尼斯堡(Konigsbergs)城域有一个普雷格尔河系，由新河、旧河及其交汇而成的大河组成，它把该城分成了一岛三岸共四块陆地，陆地之间有七座桥连通，如图6-1(a)所示．当时城内居民在散步时热衷于这样一个问题：从某陆地出发，能否走遍七桥且每桥只过一次而最终回到原出发地．图6-1（a）图6-1（b）欧拉在1736年解决了这一问题．他用四个点表示四块陆地，用相应两点间的边表示桥，从而建立了该问题的图的模型，见图6-1(b)．于是问题归结为：在这个连通多重图中，能否找出一条回路，过每边一次且仅仅一次．欧拉在求解该问题时，把图6-1（a）所示的实际问题抽象为图6-1（b）所示图形．例6-2比赛安排问题5个球队之间安排赛事．其中a球队分别与b，c，d球队有赛事；b球队还与c球队，d球队还与e球队有赛事．综上，这5个球队之间的比赛关系可用图6-2(a)来表示，也可用图6-2(b)来反映．图6-2（a）图6-2（b）以上两例都忽略了问题的具体细节，而把问题的关键性质或关系抽象为图的形式．例6-1中两岸和岛的形状及桥的曲直都被忽略，但陆地间的关联情况却得到保持．例6-2中把比赛关系抽象为连接关系．简单些说，一个图代表了某些对象集合之间的关系，而图论是主要研究这些对象在上述表示法中的许多可能的性质中的某些性质．详细些说，一个图指的是一些点以及连接这些点的一些线的总体．这种连接方式可以具有许多特征，而图论本质上就是研究这种特征的．注意，这里所讲的图并不是解析几何与微积分书中常见的图，在那里，点的位置，线的长度和斜率是它的重要部分．而在图论中，这些都是不重要的，而重要的只是哪些点之间有线相连．有时，连接的先后次序也是重要的．二、几个基本概念1．无向图一个图G定义为一个有序二元组（V，E），记为：G＝（V，E）其中，V是一个有限非空的集合，其元素称为G的结点或顶点，简称点，而V称为G的结点集或顶点集，简称点集，一般表示为：V＝{1v，2v，…，nv}而E称为G的边集，表示为：E＝{1e，2e，…，ne}其中e由V中元素对(iv，jv)所构成．如果(iv，jv)是无序对，则G称为无向图．E中元素e称为G的无向边，一般表示为e＝(iv，jv)对于给定的图可以作出其几何图．例6-3无向图G＝（V，E），其中点集V＝{1v，2v，3v，4v，5v}，E＝{1e，2e，3e，4e，5e，6e，7e,8e}，边与顶点的关联情况由表6-1给出．表6-1边与顶点的关联情况e1e2e3e4e5e6e7e8e(iv，jv)(1v,2v)(1v,5v)(2v,4v)(1v,4v)(4v,3v)(5v,4v)(1v,5v)(2v,3v)根据表6-1，可作其几何图，如图6-3所示．在作几何图时，仅要求表示出顶点、边以及它们间的关联关系，而对顶点的位置以及边的曲直、长短都没有任何规定．图6-3基于无向图G的结构特点，我们给出下列一些术语：平行边——若两条不同的边e与'e具有相同的端点，则称e与'e为G的平行边．图6-3中2e与7e是平行边，因为它们的端点均为1v、3v．简单图——若G无平行边，则称图G为简单图．完备图——图G中任两个顶点间恰有一条边相关联，G为完备图．2．有向图设顶点的非空集合V＝（1v，2v，…，nv），边的集合A＝（1a，2a，…，na）．如果A中任一条边ija是V的一个有序元素对(iv，jv)(这里，iv≠jv)，则称A为有向边集，A中元素ija称为有向边或弧，记为ija＝(iv，jv)其中iv为ija的起点，jv为ija的终点．V和A组成了一个有向图，记作D＝（V，A）例6-4给有向图D＝（V，A），其中V＝（1v，2v，3v，4v），A＝（1a，2a，…，7a），边与顶点的关联情况如表6-2所给．表6-2边与顶点的关联情况a1a2a3a4a5a6a7a8a(iv，jv)(2v,1v)(1v,2v)(3v,2v)(3v,2v)(2v,4v)(3v,4v)(2v,4v)(1v,3v)根据表6-2也可作出有向图，如图6-4（a）图6-4(a)图6-4(b)图6-4（c）有向图区别于无向图的关键，在于它的边（或弧）是有方向的，图6-4（a）中边上的箭头所指即边的方向．在有向图中(iv，jv)≠(jv，iv)．类似于无向图，有向图G也有下列术语：平行边——不同的弧a与'a(iv，jv)的起点与终点都相同．图6-4（a）中3a、4a是平行边，而1a、2a却不是，1a＝(2v,1v)；而2a＝(1v,2v)．简单图——无平行边的有向图称为简单图．完备图——图中任两个顶点iv与jv间，恰有两条有向边(iv，jv)及(jv，iv)，则称该有向图D为完备图．基本图——把有向图D的每条边除去方向就得到一个相应的无向图G，称G为D的基本图．例如图6-4（b）是图6-4（a）的基本图．3．同构对于无向图和有向图，如果图G＝（V，E）和G'＝(V'，E')的顶点集合V和V'，以及边集E和E'之间在保持关联性质的条件下一一对应，则图G和G'同构．例如图6-2(a)、(b)所示的两个图看似不同，其实是同构图．由于同构的图被认为是相同的，这就给我们在网络规划中建立网络模型带来许多方便，当我们用几何图来反映和分析实际问题的内在关系而构建网络模型时，点的位置可以任意布置，边的长短曲直也可任意，故而我们尽量设计那种反映问题清晰、简练的几何图．4．链、路和连通性给定一个无向图G＝（V，E），其中的一个点与边的交错序列1iv，1ie，2iv，2ie，…，1ikv，1ike，ikv，如果序列中所有ite都满足ite＝（itv，1itv），（t＝1，2，…，k－1），则称交错序列为联结1iv和ikv的链，记为＝（1iv，1ie，2iv，2ie，…，1ikv，1ike，ikv）或简记为（1iv，2iv，…，1ikv，ikv）和（1ie，2ie，…，2ike，1ike）当k＞0，且1iv＝ikv，则链的起点等于终点，称为闭链．闭链中除起点和终点外没有相同的结点和边，则该闭链称为圈．当1iv≠ikv，时称为开链．若开链中所有结点均不相同，称为初等链．例如图6-5中：图6-51＝（1v，2v，4v，3v，2v，1v）是闭链，但不是圈；2＝（1v，2v，3v，1v）是闭链，同时也是圈；3＝（1v，2v，4v，3v，2v）是开链；4＝（1v，2v，4v，3v）是初等链．对于有向图D＝（V，A），可以通过其相应的基本图来定义它的链．但由于有向图中弧是有方向的，可能出现链中的弧的方向与链的方向不一致的情况．如果链中所有弧的方向与链的方向一致，则称该链为单向路，简称路．显然，在有向图中链和路的概念并不一致，而在无向图中两者没有区别．如果路的起点和终点相同，则称为回路．对于无向图而言闭链和回路概念一致．在图6-4（a）中：1＝（1a，3a，8a）是链，但不是路；2＝（8a，3a，1a）是链，同时也是路和回路．在D中任意两个结点vi1和vik，从vi1到vik存在路，则称vi1可达vik．若D中任意两结点间存在链，则称D为连通图．若D中任意两结点间相互可达，则称D为强连通图．对于无向图而言连通图等价于强连通图．例如图6-4（a）所示的是强连通图，因为1v、2v、3v、4v都是相互可达的．如果我们将图中弧8a删去，如图6-4（c）所示，则成为一般的连通图．因为这时1v、3v不能相互可达．5．网络一个图连同定义在其边集上的实函数一起称为一个网络．网络一般是连通图．定义在边集上的实函数称为边的权数记为ijw＝w(iv，jv)它与边(iv，jv)具有一一对应关系，可以用以表达网络上的各种有关性质，如路长、流量、费用等等．网络的图解即在每条边旁标上相应的权数．若一网络的每条边都是无向边，则称为无向网络，记为N＝（G，w）或N＝(V，E)若一网络的每条边都是有向边，则称为有向网络，记为N＝（D，w）或N＝(V，A)若一网络中既有无向边，也有有向边，则称为混合网络．所谓网络分析，简单地说，即对网络进行定性和定量分析，以便为实现某种优化目标而寻求最优方案．这方面的典型问题有：最小树问题，最短路问题，中心问题，重心问题，最大流问题，最小费用最大流问题，最短回路问题，网络计划问题，等等．第二节最小树问题一、树的基本概念1．子图、真子图、生成子图设有图G＝(V，E)和图G'＝(V'，E')，如果V'V，E'E，则称G'为G的子图，并记为G'G，而G则为G'的原图．当子图的边集或点集不同于原图时，即G'≠G时，称子图G'为G的真子图，记为G'G．当子图的点集等于原图的点集时，则称子图G'为原图G的生成子图或支撑子图．在图6-6中，（a），（b），（c），（d）均是（a）的子图；（a），（b），（c）是（a）的真子图；（a），（b），（c）均是（a）的生成子图．由于（d）比（a）少一个点，所以（d）不是（a）的生成子图．图6-62．树无圈且连通的无向图称为树．树一般记为T．作为树定义还可以有以下几种表述：(1)T连通且无圈或回路；(2)T无圈且有n－1条边（如果有n个结点）；(3)T连通有n－1条边；(4)T无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)T连通，但去掉T的任意一条边，T就不连通了；(6)T的任意两个结点之间恰有一条初等链．二、最小生成树及其算法1．最小生成树如果T是无向图G的生成子图，同时T又是树，则称T是G的生成树或支撑树．例如图6-7（b），（c）是（a）的生成树．图6-7一个网络图可以有多个生成树．记N的所有生成树的集合为：T＝{kT|k＝1，2，…，L}设iT＝（V，kE）是网络图N＝（G，w）的一棵生成树，则边集kE中所有边的权数之和称为树kT的权数，记为w（kT）＝Ekeew)(若*T∈T，使w（*T）＝TTkmin{w（kT）}则称*T为网络N的一棵最小生成树，简称最小树．2．最小树的求法定理8-1如果把网络N的点集V分割成两个不相交的非空集合S和_S，则联结S和_S的最小边必包含于N的最小树内．根据定理8-1，可以给出求最小树的两种方法，这就是避圈法与破圈法，分述如下：(1)避圈法其计算步骤如下：①从网络N中任选一点iv，令S＝{iv}，_S＝V\{iv}；②从联结S与_S的边中选取最小边，不妨设为(iv，jv)，则它必包含于最小树内；③令S∪{jv}S，_S\{jv}_S；④若_S＝，则停止，已选出的诸边即给出最小树；否则返②．例6-5试求图6-8所示网络的最小