文档介绍：第六章网络分析与网络计划
,,如何制订管理计划或设备购置计划,使收益最大或费用最小;在组织生产中,如何使各工序衔接好,使生产任务完成得既快又好;在交通网络中,,方法简便,容易掌握的特点,因此得到迅速的发展,且广泛地应用在各个领域,成为经济活动中许多管理决策的优化问题的重要手段.
网络计划方法是上世纪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)
,用相应两点间的边表示桥,从而建立了该问题的图的模型,见图6-1(b).于是问题归结为:在这个连通多重图中,能否找出一条回路,,把图6-1(a)所示的实际问题抽象为图6-1(b)所示图形.
例6-2 比赛安排问题
,c,d球队有赛事;b球队还与c球队,,这5个球队之间的比赛关系可用图6-2(a)来表示,也可用图6-2(b)来反映.
图6-2(a)
图6-2(b)
以上两例都忽略了问题的具体细节,-1中两岸和岛的形状及桥的曲直都被忽略,-,一个图代表了某些对象集合之间的关系,,,,这里所讲的图并不是解析几何与微积分书中常见的图,在那里,点的位置,,这些都是不重要的,,连接的先后次序也是重要的.
二、几个基本概念
一个图定义为一个有序二元组(,),记为:
=(,)
其中,V是一个有限非空的集合,其元素称为G的结点或顶点,简称点,而V称为G的结点集或顶点集,简称点集,一般表示为:
={,,…,}
而E称为G的边集,表示为:
={,,…,}
其中由中元素对(,)(,)是无序对,,一般表示为
=(,)
对于给定的图可以作出其几何图.
例6-3 无向图=(,),其中点集={,,,,},
={,,,,,,,},边与顶点的关联情况由表6-1给出.
表6-1 边与顶点的关联情况
(,)
(,)
(,)
(,)
(,)
(,)
(,)
(,)
(,)
根据表6-1,可作其几何图,如图6-,仅要求表示出顶点、边以及它们间的关联关系,而对顶点的位置以及边的曲直、长短都没有任何规定.
图6-3
基于无向图的结构特点,我们给出下列一些术语:
平行边——若两条不同的边与具有相同的端点,-3中
与是平行边,因为它们的端点均为、.
简单图——若无平行边,则称图为简单图.
完备图——图中任两个顶点间恰有一条边相关联,为完备图.
设顶点的非空集合=(,,…,),边的集合=(,,…,).如果中任一条边是的一个有序元素对(,)