2022年网络规划与网络计划技术 .pdf
《2022年网络规划与网络计划技术 .pdf》由会员分享,可在线阅读,更多相关《2022年网络规划与网络计划技术 .pdf(47页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1 第六章网络规划与网络计划技术网络规划是图论的一个重要内容,也是近几十年来运筹学领域中发展迅速、且十分活跃的一个分支 . 由于它对实际问题的描述具有直观性,使网络规划在工程设计和管理中得到广泛应用, 已成为对各种系统进行分析、研究、 管理的重要工具. 网络规划的内容十分丰富,本章主要介绍了在路径问题、网络流问题等领域中的一些应用方法,如:最小树问题、 最大流问题和最小费用流问题. 网络计划技术是指计划评审法和关键路径法,它们是五十年代在美国彼此独立发展起来的一种组织生产和进行计划管理的科学方法. 网络计划技术的基本原理是利用网络图来表达工程的进度安排及其组成的各项活动之间的制约关系,计算各项
2、活动的有关时间参数,使管理者对工程的全局能有全面、清晰的了解, 从而制定工程进展的日程计划以求得完工期、资源和成本的优化方案. 1 图与网络的基本概念一、图什么是图?首先我们通过下面的几个例子来认识什么是图. 例 6.1 哥尼斯堡七桥问题哥尼斯堡( konigsberg )城域有一个普雷格尔(Pregel )河系,由旧河、新河及其交汇而成的大河组成,它把该城分成了一岛三岸共四块陆地,陆地之间有七座桥连通,如图6-1(a).这个城里的居民当时热衷于这样一个问题:从岸上任一地方开始,能否通过每座桥一次且仅仅一次就能回到原地.1736 年欧拉发表了图论方面的第一篇论文,将此难题化成了一个数学问题:
3、用点表示两岸或小岛,用点之间的联线表示陆地之间的桥,这样就得到了图6-1(b) 所示的一个图. 从而原问题就变为:在图6-1(b) 中,是否能从某一点出发只经过各条边一次且仅仅一次而又回到出发点,即一笔画问题. 在图 6-1(b) 中,虽然没有画出两岸、岛屿的大小形状和桥的长短,但保持了陆地间的关联情况. (a) (b) 图 6-1 例 6.2 在一群人中,他们分别是赵、钱、孙、李、周、吴、陈七人,对他们之间相互认识的关系,我们用图6-2 来表示 . ABDC()v1()v3()v2()v4DCAB大 河新 河旧 河名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -
4、- - - - - - - - - 名师精心整理 - - - - - - - 第 1 页,共 47 页 - - - - - - - - - 2 图 6-2 图 6-3 从上面的例子可以看到图可以很好地描述、刻画反映对象之间的特定关系. 一般情况下图中点的相对位置如何、点与点之间联线的长短曲直,对于反映对象之间的关系并不是很重要,如例6.2 也可以用图6-3 来表示 . 可见图论中的图是对现实现实的具体事物及其相互关系的一种抽象表示,它比地图、 天文图、 电路图、 几何图等更抽象,也更具随意性, 因而它是帮助人们认识客观事物的一种更一般的工具 . 所谓图就是点和边的集合. 图的定义如下:一个图G
5、为一个有序二元组(V,E) ,记为G = (V,E)其中,V是一个有限非空的集合,其元素称为G的结点或顶点,简称点,而V成为G的结点集,简称点集,一般表示为V = v1, v2, , vn ;E是由V中的无序对(vi,vj)所构成的一个集合,其元素称为G的边,一般表示为ei j=(vi, vj) ,而E称为G的边集 . 例 6.3用图表示哥尼斯堡七桥问题. 哥尼斯堡七桥问题的图G表示如下:G = (V,E)其中:点集V = v1, v2, v3, v4 边集 E=e14, e14, e42, e42, e13, e43, e23 边e14 = (v1, v4) ,e14 = (v1, v4)
6、,e42 = (v4, v2) ,e42 = (v4, v2) e13 = (v1,v3) ,e43 = (v4, v3) ,e23 = (v2, v3) 为了便于叙述,以图6-4 为例,介绍有关术语与概念. 图 6-4 1、端点和关联边对于eij = (vi, vj),则称vi, vj是eij的端点,eij是vi, vj的关联边 . 在图 6-4 中,v1, v3是e13的端点,e23是v2, v3的关联边 . 2、相邻相邻的概念包括了点相邻与边相邻两种. 若点vi, vj都有同一条关联边,则称点vi与钱 ()v2陈 ()v7李 ()v4孙 ()v3赵 ()v1e1 2e3 4e24吴 ()
7、v6周 ()v5e13e6 7v5v2v3v6v7v1e13e1 2e23e3 4v4e6 7e13e13e24e22e4 5e34e12v1v3v5v2v4e2 3名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页,共 47 页 - - - - - - - - - 3 vj相邻;若两边具有同一个端点,则称该两边相邻. 在图 6-4 中,点v2, v3相邻,边e13, e13, e23, e34相邻 . 3、重边、简单图若一条边的两个端点是同一点,则称该边为环. 图 6-4 中e
8、22称为环 . 若两个端点之间有多条边,则称这些边为多重边. 图 6-4 中的e13, e13为多重边 . 没有环和多重边的图称为简单图. 如图 6-2 、 6-3. 4、次、奇点、偶点、孤立点、悬挂点和悬挂边点v的关联边的数目称为点v的次,记为d (v);若d (v) 为奇数的点称为奇点;若d(v)为偶点的点称为偶点;次为 0 的点为孤立点; 次为 1 的点为悬挂点; 悬挂点的关联边称为悬挂边 . 在图 6-4 中,d (v3) = 4 ,d (v1) = 3;由于存在环e22,所以d (v2) = 5;点v5为悬挂点,边e45为悬挂边 . 5、链、开链、闭链、简单链、初等链和圈在图 G=
9、(V, E )中,设Vvvvkiii,10,Eeeekjjj,21. 若),(1tiijVVett,t = 1, 2, k,则交替序列,2110kkijjijiveevev称为一条从0iv至kv1的链,简记为kiiivvv,10. 在中,0iv称为始点,kiv称为终点;若始点与终点相同,则称为闭链;若始点与终点是不同的点,则称为开链;若链中的边都不相同,则为简单链;若链中的边都不相同,也没有相同的结点,则链称为初等链 . 若在初等链中,始点与终点相同,即kiivv0则初等链称为圈 . 在图 6-4 中,链43211vvvv是初等链,链342312vvvvv是简单链 . 6、连通图在一个图中,若
10、任意两点之间至少存在一条链,则该图就称为连通图,否则称为不连通图 . 如图 6-1(b) 、6-4 为连通图,而图6-2 、6-3 为不连通图 . 7、子图、真子图、支撑子图设有图G = (V,E)和图) , (EVG. (1) 若EEVV,,则称G是G的子图;(2) 若EEVV,,则称G是 G的真子图;(3) 若EEVV,,则称G是 G的支撑子图 . 在图 6-5 中, (a) 、(b) 、(c) 、(d) 是图 (a) 的子图, (a) 、(b) 、(c) 是(a) 的支撑子图 .因为 (d) 比(a) 少了一个点v3,所以 (d) 不是支撑子图. (a) (b) (c) (d) 图 6-
11、5 v1v5v4v2e1v6v3v1v5v6v4v2v3v4v2v3v4v2v1v5v6v1v5v6名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页,共 47 页 - - - - - - - - - 4 二、有向图、无向图1、有向图、无向图在例 6.2 中,若我们将“相互认识”的关系改成“认识”的关系,那么只用两点之间的联线就很难表示清楚他们之间的关系了. 若引用一个带箭头的联线,我们称之为弧,记为a.在图 6-6 中,弧a51表示周认识赵, 而赵并不认识周. 图 6-6 反映
12、了例6.2 中七个人的 “认识”关系 . 在图中,赵、钱“相互认识”,可以用两条反向的弧a12、a21表示 . 图 6-6 我们把像图6-2 那样由点和边构成的图称为无向图,简称图,记为G = (V, E) ,V, E的含义前面已述. 像图 6-6 那样由点和弧构成的图称为有向图D. 一个有向图D定义为一个有序二元组(V, A) ,记为D = (V, A) ,其中(1) V = v1, v2, , vn是结点集;(2) A是由V中元素的有序对(vi, vj)所构成的一个集合,其元素称为D的有向边或弧,一般表示为aij(vi, vj) ,而A称为D的弧集 . 有序对(vi, vj)是指当vivj
13、时, (vi, vj)与(vj, vi)不同 . 弧aij =(vi, vj)在图中表示为一条从始点vi指向终点vj的箭线 . 2、基础图、路、回路若在有向图D中,将所有弧都用边来替代,所得到的一个无向图称为该有向图的基础图,记为G(D). 如图 6-7(b) 就是 6-7(a) 的基础图 . 基础图G(D)中的链和圈就是有向图D的链和圈 . 若交替序列,2110kkjijijievevev是有向图D = (V, A)的一条链,且有ktvvatttiij,2,1,1v3v1v4v2v3v1v4v2(a) (b) 图 6-7 钱 ()v2李 ()v4赵 ()v1周 ()v5陈 ()v7吴 ()v
14、6孙 ()v3a51a1 2a21a3 4a24a3 1a45a56a76a67名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页,共 47 页 - - - - - - - - - 5 则称是有向图D的一条从0iv到kiv的路,记为kiiivvv,10若0iv=kiv,则称为有向图D中的一条回路;否则称为开路. 对于无向图G来说,链和路(闭链和回路)这两个概念是一致的. 概括地说,一条路必定是一条链,然而在有向图中,一条链未必是一条路. 在图6-6 中,v1, v2, v4, v
15、5, v6, v7是一条链,也是一条路,而v1, v3, v4, v5, v6, v7是一条链但不是一条路. 三、网络设在图G= (V, E)中,每一条边e都有相应的一个权值)(e,则称G为赋权图,)(e称为边e的权 . 图 6-8 是一个赋权图 . 图 6-8 .3)(),(;2)(),(;5)(),(;1)(),(;3)(),(;2)(),(;4)(),(;1)(),(355335455445255225344334244224233223133113122112evveevveevveevveevveevveevveevve可见,赋权图不仅指出各点之间的邻接关系,而且也表示各点之间的数量
16、关系,所以赋权图在图的理论及其应用方面有着重要的地位. 同样,对于有向图D = (V, A)中,每一条弧aij都有相应的一个权值)(ija,则称D为赋权有向图,)(ija称为弧的权,简记为ij(权可以表示距离、费用和时间等). 图 6-9是一个赋权有向图,这是某地区的交通运输的公路分布、走向及相应费用示意图.箭头表示走向,箭头旁边的数字表示费用. 图 6-9 在实际工作中,有很多问题的可行解方案都可通过一个赋权有向图表示,例如:物流渠道的设计、物资运输路线的安排、排水管道的铺设等. 所以,赋权图被广泛应用于解决工程技术及科学管理等领域的最优化问题. 通常,我们把赋权图称为网络,赋权有向图称为有
17、向网络,赋权无向图称为无向网络.v1v2v3v4v511223345v1v2v5v7v6v3v4544482332221名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页,共 47 页 - - - - - - - - - 6 网络分析内容主要涉及网络优化问题,即最小树问题、 最短路问题、 最大流问题、 最小费用最大流问题、网络计划问题等等. 2 最小支撑树问题一、树树是图论中的一个重要概念. 所谓树就是一个无圈的连通图. 如图6-10 中的 (a) 就是一棵树,而 (b) 因为有
18、圈(v3, v4, v5, v3) ,所以 (b) 就不是树, (c) 也不是树,因为(c) 不是连通图 . 一个家族的家谱,一个单位的组织结构,一个城镇的自来水管道等等,都可以用树来表示 . (a) (b) (c) 图 6-10 二、最小支撑树若图G的一个支撑图T是树,则称T为图G的一棵支撑树. 在图 6-11 中给出了图G的几个支撑树T1, T2, T3. 图 G T1 T2 T3图 6-11 设) ,(EVT是网络(赋权图)G = (V, E)的一棵支撑树,E中的所有边的权数之和称为支撑树T 的权数,记为ijTvvjiT),()(. 如果支撑树T*的权数)(*T是G的所有支撑树的权中最小
19、者,即)(min)(*TT则称T*是G的最小支撑树,简称最小树. 那么,如何找出网络最小树呢?这就是最小树问题. 三、最小支撑树的求法求最小树通常用以下两种方法:1、破圈法:在给定的连通图G中,任取一圈,去掉圈中权最大的一条边(若有多条边的权最大,则去掉任意一条边);在 G的余图中再任取一圈,去掉圈中权最大的一条边;重v1v2v4v4v6v6v6v7v7v7v5v3v5v5v1v2v4v1v2v3v3名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页,共 47 页 - - - -
20、 - - - - - 7 复取圈,直到余图中不再有圈为止,此时即可得到图G的最小树 . 例 6.4用破圈法求图6-8 的最小树 . 解:求解过程如图6-12 示. 具体步骤如下:(1) 在图 6-8 中,任选一图v1v2v3v1,在该圈中由于边(v1, v3)的权413最大,所以去掉边(v1, v3) ,得图 6-12(a). (2) 在图 6-12(a) 中,任选一圈 v2, v3, v4, v2 ,在该圈中由于边 (v2, v3)的权223最大,所以去掉边(v2, v3) ,得圈 6-12(b). (3) 在图6-12(b) 中,任选一圈 v2, v3, v4, v5, v2,在该圈中由于
21、边(v2, v5)的权525最大,所以去掉边(v2, v5) ,得圈 6-12(c). (4) 在图6-12(c) 中,只有一圈 v3, v4, v5, v3,去掉权为最大的边(v3, v5) ,得图6-12(d). 在图 6-12(d) 中,由于已没有圈,故已得图6-8 的最小树 . (a) (b) (c) (d) 图 6-12 2、避圈法( kruskal算法) :在给定的连通图G中,取权值最小的一条边(若有多条边权值最小,则任取一条边),在余下的边中选一条权值最小的边(要求此边与已选中的边不构成圈);重复取边,直到不存在与选边能构成圈的边为止,此时,已选边与结点构成的图T就是连通图G的最
22、小树 . 例 65 用避圈法求图6-8 的最小树 . 解:求解过程过如6-13 示. 具体步骤如下:(1) 在图6-8 中,有边(v1, v2) 、 (v3, v4)的权为最小权值1,任取一边(v1, v2) ,得图 6-13(a) ,在图中(v1, v2)用粗线表示. (2) 在余下的边中,边(v3, v4)权最小,权值为1,并与(v1, v2)不构成圈,故选取(v3, v4) ,得图 6-13(b). (3) 在余下的边中,边(v2, v3) 、 (v4, v5)的权最小,权值为2,任取一边(v4, v5).边(v1, v2) 、 (v3, v4) 、 (v4, v5)没有构成圈,得图6-
23、13(c). (4) 在余下的边中,取最小权边(v2, v3) ,得图 6-13 (d). 在余下的边中, (v2, v4)与(v3, v5)的权值最小,但取它们之间的任一条边,都会构成圈,故此时已得到最小树,v1v2v3v4v51122335v1v2v3v4v5112235v1v2v3v4v511223v1v2v3v4v51122名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页,共 47 页 - - - - - - - - - 8 如图 6-13(d) 中,粗线所标出. (a
24、) (b) (c) (d) 图 6-13 3 最短路问题最短路问题一般可描述如下:在一个网络中,给定一个始点vs和一个终点vt,求出一条路,使得路长最短(即路的所有边权数之和最小). 许多实际问题都可以通过求解最短路解决.如两地之间的货物运输路线、管道铺设; 再如设备更新问题也可转化为最短路问题. 一、 Dijkstra标号法本节先介绍求最短路的一种算法:狄克斯屈标号法(E.D.Dijkstra). 该法是狄克斯屈在 1959 年提出的,适用于所有权数均为非负(即一切ij0)的网络,能够求出网络的任一点vs到其他各点的最短路,为目前求这类网络最短路的最好算法. Dijkstra算法是一种标号法
25、,它的基本思路是从起点vs出发,逐步向外探寻最短路,执行过程中给每一个顶点vj标号(jjl ,).其中j是正整数,它表示顶点vj获得此标号的前一点的下标;lj表示从起点vs到vj点的最短路,即权之和(称为固定标号,记为P标号)或表示从起点vs到点的最短路的权的上界(称为临时标号,记为T标号) . Dijkstra算法将所有点集分为两类:P标号点和T标号点 . 一个点vj的标号只能是上述两种标号之一 . 若为T标号, 则需视情况修改,而一旦成为P标号, 就固定不变了 . 开始将起点vs设为P标号点,而其余点设为T标号点,方法的每一步是去修改T标号,并且把某一个具有T标号的点变为具有P标号点,从而
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年网络规划与网络计划技术 2022 网络 规划 计划 技术
限制150内