管理决策第七讲网络分析与应用.pptx

管理决策
曹媛媛 ******@
2
2021/3/5 星期五
第七讲 网络分析
图论(Graph Theory)
是运筹学的一个分支，已广泛应用在物理学、化学、控制论、信息论、科学管理、计算机等各个领域中。
网络分析（Network Analysis）
作为图论的一个重要内容，已成为对各种系统进行分析、研究和管理的重要工具。本章主要介绍运输问题、最短路问题、最小支撑树问题、最大流问题，以及网络计划评审与优化问题。
第七讲 网络分析
图与网络的基本概念
图论中的图，是反映现实世界中具体事物及其相互关系的一种抽象工具,它比地图、分子结构图、电路图等更抽象。
图的定义：简单的说，一个图是由一些点(Vertices)及点间的连线(Edges)所组成的。点可以作为现实世界中事物的抽象，而点间的连线表示事物间的关系。
无向图：如果一个图由点及边所构成，则称之为无向图 ，记为G=(V，E)。其中，V是一个有限非空的点集合，称为G的点集，一般表示为V={v1，v2，…，vn}；E是一个边集合，称为G的边集，一条连接vi和vj的边一般表示为一个无序对e=（vi，vj）。
有向图：如果一个图由点及弧所构成，则称之为有向图，记为D＝(V，A)。其中，V是点的集合；A是弧的集合，一条从vi连接到vj的弧一般表示为一个有序对a＝(vi，vj)。
第七讲 网络分析
图与网络的基本概念 ——无向图
例3-1 试用一个图来表示大连、北京、深圳、上海四城市之间的民航客机通航情况。
解： 设v1，v2，v3，v4分别表示大连、北京、深圳、上海四市，则他们之间的通航情况可表示为一个无向图：G=(V，E) 。
V={v1，v2，v3，v4}
E={e1，e2，e3，e4，e5，e6}
e1={v1，v2}，e2={v1，v3}，
e3={v1，v4}，e4={v2，v3}，
e5={v2，v4}，e6={v3，v4}
第七讲 网络分析
图与网络的基本概念 ——有向图
例3-2 有A、B、C、D四支篮球队，进行单循环比赛，比赛情况如表所示。试用一个图表示各队之间的胜负关系。
比赛球队
获胜球队
A——B
A
A——C
A
A——D
D
B——C
B
B——D
D
C——D
C
解：设v1，v2，v3，v4分别表示球队A、B、C、D，其相互间的胜负关系可表示为一个有向图： D=(V，A)，从vi连接到vj的弧表示vi代表的球队胜vj代表的球队。
其中
V={v1，v2，v3，v4}
A={a1，a2，a3，a4，a5，a6}
a1={v1，v2}，a2={v1，v3}，
a3={v4，v1}，a4={v2，v3}，
a5={v4，v2}，a6={v3，v4}
第七讲 网络分析
图与网络的基本概念
几个基本概念
若有e=（vi，vj），则称vi，vj是e的端点，也称点vi与vj相邻，称e是vi，vj的关联边。如图中，v1与v4是e5的端点，点v2与v3相邻，e6是v4与v5的关联边。
若一条边的两个端点相同，则称该边为环。如e7。
若两个端点之间不止一条边，则称具有多重边；一个无环也无多重边的图称为简单图。
第七讲 网络分析
图与网络的基本概念
几个基本概念
图G=(V，E)中，设 ； ；
；则交替序列 称为一条从
到 的链，简记为
若 ＝ 则称为闭链，否则称 为开链。
若 中的边均不相同，则称 为简单链；
若 中所有结点也均不同，则称 为初等链。
若一条闭链 中，除 ＝ 外，任意两点均不相同，则称 为一个圈。
若图G中，任意两点间至少存在一条链，则称图G为连通图，否则称为不连通图。
第七讲 网络分析
图与网络的基本概念
几个基本概念
如图， ＝v4v7v5v6v7v8是简单链，
＝v4v5v7v6v8是初等链， ＝v4v5v6v8v7v4是一个圈，
但 ＝v4v7v6v8v7v5v4仅为一条闭链，而不是圈。
左图是连通图，而右图是不连通图，因为v1与v4之间不存在链。
第七讲 网络分析
图与网络的基本概念
几个基本概念
设有图G=(V，E)和图G’=(V’，E’)，若V’＝V，E’ E，则