信息技术——网络研究与网络计划.docVIP

第六章网络分析与网络计划 网络分析是图论的一个应用分支．它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题．在现实生活和生产实践中，网络分析方法有很广泛的应用．如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等．由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段． 网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluation and review technique，简称PERT)和关键路径方法(critical path method或critical path analysis，简称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．无向图 一个图定义为一个有序二元组（，），记为： ＝（，） 其中，V是一个有限非空的集合，其元素称为G的结点或顶点，简称点，而V称为G的结点集或顶点集，简称点集，一般表示为： ＝{，，…，} 而E称为G的边集，表示为： ＝{，，…，} 其中由中元素对(，)所构成．如果(，)是无序对，则称为无向图．中元素称为的无向边，一般表示为 ＝(，) 对于给定的图可以作出其几何图． 例6-3 无向图＝（，），其中点集＝{，，，，}， ＝{，，，，，，,}，边与顶点的关联情况由表6-1给出． 表6-1 边与顶点的关联情况 (，) (,) (,) (,) (,) (,) (,) (,) (,) 根据表6-1，可作其几何图，如图6-3所示．在作几何图时，仅要求表示出顶点、边以及它们间的关联关系，而对顶点的位置以及边的曲直、长短都没有任何规定． 图6-3 基于无向图的结构特点，我们给出下列一些术语： 平行边——若两条不同的边与具有相同的端点，则称与为的平行边．图6-3中与是平行边，因为它们的端点均为、． 简单图——若无平行边，则称图为简单图． 完备图——图中任两个顶点间恰有一条边相关联，为完备图． 2．有向图 设顶点的非空集合＝（，，…，），边的集合＝（，，…，）．如果中任一条边是的一个有序元素对(，)(这里，≠)，则称为有向边集，中元素称为有向边或弧，记为 ＝(，) 其中为的起点，为的终点