运筹学网络分析

地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、 地理位置、地理实体、地理区域，譬如，山顶、河流汇聚点、车站、 码头、村庄、城镇等——点 码头、村庄、城镇等 点 它们之间的相互联系，譬如，构造线、河流、交通线、 它们之间的相互联系，譬如，构造线、河流、交通线、供电与通讯 线路、人口流、物质流、资金流、信息流、技术流等 线路、人口流、物质流、资金流、信息流、技术流等——点与点的 点与点的 连线。 连线。 一个由基本流域单元组成的复杂的流域地貌系统， 一个由基本流域单元组成的复杂的流域地貌系统，如果舍弃各种复 杂的地貌形态，各条河流 杂的地貌形态，各条河流——线，河流分岔或汇聚处 线 河流分岔或汇聚处——点，流域 点 地貌系统——水系的基本结局（树）。 水系的基本结局（ 地貌系统 水系的基本结局
（4 ）环 的两个端点相同， 若e的两个端点相同，即u＝v，则称为环。 的两个端点相同 ＝ ，则称为环。 （5）多重边 若连接两个端点的边多于一条以上， 若连接两个端点的边多于一条以上，则称为 多重边。 多重边。 （6）多重图 含有多重边的图，称为多重图。 含有多重边的图，称为多重图。 （7）简单图 无环、无多重边的图，称为简单图。 无环、无多重边的图，称为简单图。
（13）基础图 13）
从一个有向图D＝（ ， ） 从一个有向图 ＝（V，A）中去掉所有边上的箭头所 ＝（ 得到的无向图，就称为D 的基础图，记之为G（ ）。 得到的无向图，就称为 的基础图，记之为 （D）。
（14）截 14）
如果从图中移去边的一个集合将增加亚图的数目时， 如果从图中移去边的一个集合将增加亚图的数目时， 被移去的边的集合就称为截。 被移去的边的集合就称为截。
需要说明的是——图的定义只关注点之间是否 图的定义只关注点之间是否 需要说明的是 连通，而不关注点之间的连结方式。 连通，而不关注点之间的连结方式。对于任何一个 图的画法并不唯一。 图的画法并不唯一。

一、树的概念及性质 例：已知有五个城市，要在它们之间架设电话线，要 求任何两个城市都可以互相通话（允许通过其它城市） ，并且电话线的根数最少。
v2
v3
v1
v5
v4
9
1.树的定义 ：连通且不含圈的无向图称为树。 次为1的点称为树叶，次大于1的点称为分枝点，树的边称 为树枝。
v2 v4 v2 v1 v4
d1 j = min( d1i wij )
i
设任一点vi到任一点 vj都有一条弧，如果（vi, vj）不是弧，则添 22 加弧（vi, vj），令wij=+∞
迭代过程：
①初始条件： t=1,d1j(1)=w1j (j=1,2,…,n) ，如果 v1 与 vj间 无边，其最短路长记为+∞ ②t=2,3,…
3
悬挂边：悬挂点的关联边
定理1：图G=(V,E)中，所有点的次之和是边数 的两倍，即
Σd(v)=2q vV
定理2：任一图中，奇点的个数为偶数。
给定一个图G=(V,E)，一个点边的交错序列(vi1, ei1, vi2, ei2,…,vik-1,eik-1,vik)，如果满足eit=[vit,vit+1] (t=1,2,…,k1)，则称为一条联结vi1和vik的链，记为(vi1,vi2,…,vik)， 称点vi2, vi3,…,vik-1为链的中间点。
2．最小支撑树（最小树）
具有最小权的支撑树称为最小支撑树。
13
3．求最小支撑树的方法
（1）避圈法 在图中选一条权数最小的边，在以后的每步中，总从未被选 取的边中选一条权数最小的边，并使之与已选取的边不构成圈（ 权数相同时，任选一条），直到选够n-1条边为止。
3
2
4 1 5

vV1 vV2 vV
由于2m为偶数, 而 d (v )是若干个偶数之和, 也是偶数.
vV2
所以 d (v )必为偶数,即 | V1 | 是偶数.
有向图中,以vi为始点的边数称为点vi的出次, 用d (vi )表示, 以vi为终点的边数称为点vi的入次, 用d (vi )表示, vi点的出次与入次之和就是该点的次.
六、第10章 图与网络分析
图与网络的基本知识 树及最小树问题 最短路问题 最大流问题 最小费用最大流问题
(Graph Theory and Network Analysis)
A
C
D
问题：一个游者怎样才 能一次连续走过这七座 桥且每座桥只走一次， 回到原出发点。
A
B
哥尼斯堡“七桥”难 题 欧拉用A,B,C,D四点表示河的 两岸和小岛，用两点间的联 线表示桥。七桥问题变为： 从A,B,C,D任一点出发，能否 通过每条边一次且仅一次， 再回到该点?
无路可通.那么加上一边( u, v )也不会形成圈, 与已知矛盾. 再证每舍去一边便不连通.若T中有一边( u, v ), 舍去( u, v )后
图T ( u, v )仍然连通, 那么T T ( u, v )由于无圈是一棵树
但T 加一边( u, v )后就是T 仍无圈, 与( 4)中树每加一新边必
从T中去掉(v , u)边及u点不会影响T的连通性, 得图T , T 为树 只有k 1个顶点, 所以有k 2条边, 再把(v , u)，u加上去,可知
当T 有k个顶点时有k 1条边.
( 2) (3)
只需证明T 是连通图.
l
反证法.设T 不连通, 可以分为l个连通分图( l 2), 设第i个
e4

第5章 图论与网络分析
网络分析
➢ 图的基本概念 ➢最小支撑树问题 ➢ 最短路径问题 ➢网络最大流问题
图论起源：哥尼斯堡七桥问题
A
A
C
D
C
D
B
B
问题：一个散步者能否从任一块陆地出发;走过七 座桥;且每座桥只走过一次;最后回到出发点
结论：每个结点关联的边数均为偶数
§1 图的基本概念
1图
由点和边组成;记作G=V;E;其中 V=v1;v2;……;vn为结点的集 合;E=e1;e2;……;em 为边的集合; 点表示研究对象 边表示研究对象之间的特定关系
例 ： G1为不连通图; G2为连通图
G1
G2
5 支撑子图
图G=V;E和G'=V ' ;E ';若V =V ' 且E ' E ;则 称G' 为
G的支撑子图;
例 ：G2为G1的支撑子图
v5
v5
v1
v4 v1
v4
v2
v3
G1
v2
v3
G2
例 ： G2 是G1 的子图；
v2
e1 v1
e6 e7
e2
v3
e8 e9
两条以上的边都是权数最大的边;则任意去掉其 中一条： ③若所余下的图已不含圈;则计算结束;所余下的图 即为最小支撑树;否则;返问①;
例 求上例中的最小支撑树
v1
5
v2
7.5 4
5.5
3
v5
2
解：
v3 3.5 v4 v1
5
v2
75 4
55
3
v5
2
v3 3 5 v4
算法2避圈法：从某一点开始;把边按权从小到大 依次添入图中;若出现圈;则删去其中最大边;直至 填满n1条边为止n为结点数 ;

运筹学
赵明霞山西大学经济与管理学院
2
第八章 图与网络分析
图与网络的基本概念 树 最短路问题 最大流问题 最小费用最大流问题
3
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题哈密尔顿回路：经过每点且仅一次 货郎担问题、快递送货问题
例8-9
28
基本步骤标号T(j)→P(j)

29
2017/10/26
30
最长路问题例8-10（7-9）设某台新设备的年效益及年均维修费、更新净费用如表。试确定今后5年内的更新策略，使总收益最大。
役龄项目
0
1
2
3
4
5
效益vk(t)
5
4.5
4
3.75
3
2.5
14
15
柯尼斯堡七桥问题
欧拉回路：经过每边且仅一次 厄尼斯堡七桥问题、邮路问题 充要条件：无向图中无奇点，有向图每个顶点出次等于入次
16
第二节 树
树是图论中的重要概念，所谓树就是一个无圈的连通图。
图8-4中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。
7
G=(V,E)关联边(m)：ei端（顶）点(n)：vi, vj点相邻(同一条边)： v1, v3边相邻(同一个端点)：e2, e3环：e1多重边： e4, e5
8
简单图：无环无多重边
多重图：多重边
9
完全图：每一对顶点间都有边（弧）相连的简单图
10
次（d）：结点的关联边数目d(v3)=4，偶点d(v2)=3，奇点d(v1)=4d(v4)=1，悬挂点e6, 悬挂边d(v5)=0，孤立点
（一）线性(整数)规划法

定义7：子图、生成子图（支撑子图）
图G1={V1、E1}和图G2={V2，E2}如果 V1 V2和E1 E2 称G1是G2的一个子图。
若有 V1＝V2，E1 E2 则称 G1是G2的一 个支撑子图（部分图）。
图8-2（a）是图 6-1的一个子图，图8-2 （b）是图 8-1的支撑子图，注意支撑子图 也是子图,子图不一定是支撑子图。 e1
v2 ▲如果链中所有的顶点v0，v1，…，vk也不相
e1 e2 e4 v1 e3
v3 e5
同，这样的链称初等链（或路）。
e6
▲如果链中各边e1,e2…,ek互不相同称为简单链。
e7
e8
▲当v0与vk重合时称为回路（或圈），如果边不 v4
v5
重复称为简单回路，如果边不重复点也不重复
则称为初等回路。
图8－1中， μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5}是一条链，μ1中因顶 点v3重复出现，不能称作路。
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
定理1 任何图中，顶点次数的总和等于边数的2倍。
v1
v3
v2
定理2 任何图中，次为奇数的顶点必为偶数个。
e1
e2 e4 v1 e3
v2
v3
e5
e6
e7
e8
v4
v5
定义4 有向图： 如果图的每条边都有一个方向则称为有向图
定义5 混合图： 如何图G中部分边有方向则称为混合图 ② ⑤ ④
定理4 有向连通图G是欧拉图，当且仅当G中每个顶点的出 次等于入次。
② 15
9 10

v3 : v2 ,lv3 v2 ,1
lv3 minlv2 , f32 min1,1 1
v3 vt : f3t 1 c3t
vt : v3 ,lvt v3 ,1
lvt minlv3 ,c3t f3t min1,1 1
二.调整
lvt 1
在u
上：f
s1
fs1 1 1 2
vi vk ,若fki 0,则v j不标号;若fki 0,则v j可标号
vk： vi ,lvk lvk minlvk , fki
.
.
. 可能结局：（1）标号中断，已得最大流
（2）v t 得到标号，得一条增广链
二. 调整过程：
. lvt 调整量
f ij
f ij f ij
vi ,v j u vi ,v j u
非零流
定义2：给定网络D (V , A,C ) 若将V V1 , V1 , Vs V1 , Vt V1
V1 V1 (空)，则称弧集（V1 , V1）为截集
定义3：截集（V1 , V1）所有弧容量之和为截量
C（V1 , V1）
C ij
(Vi ,Vj )(V1 ,V1 )
例1. V1 vs V1 v1,v2 ,v3 ,v4 ,vt
C （V1 , V1） C S1 C S2 5 3 8
2. V1 vs ,v1 ,v2 ,v3 ,v4V1 vt
C （V1 , V1） C4t C流量等于分离Vs ,Vt
的最小截量，则max( f ) minC(V1,V1 )
定理2：可行性f *是最大流，当且仅当不存
v2 (3,3)
(3,3)
vs
(1,1) (1,1)
(5,1)
v1 (2,2)

段表示。如： 1
2
①表示作业开始，②表示作业完成，箭线的长短与时间
长短无关。
2、事项（Event)
也称节点。是作业开始或完成的瞬时状态。只表示相关 作业的衔接点。用带标号的圆圈表示。如
这里
2
2
33
34
4
表示作业，则表示②,③,④结点。 3、路（Path)
从起点到终点的一条通路。
1）路长：路的总长度 2）关键路线：路长最长的路线 3）关键作业：关键路线上的作业
12 12
5
图9.8 某工程的网络图
二、项目按期完成的概率分析(续）
解 利用节点标号法，如图9.8所示。可得关键路线为： 1345，路长为32。即tm=32。此外，利用均方差计
算公式可得 c= 5.1 1）当T=35天时，z=(T – tm)/C=(35-32)/5.1 =0.5882 查正态分布表可得，
5
2
5
13
9
5
13
4
15
30
7
30
8
7
10
3
13
6
5
5
20 20
图9.13某方案的网络图
四、经济赶工分析（续）
表9.4 成本斜率表
正常
作业
时间
成本
（天） （元）
12
6
210
13
5
300
12 4
0
4
0
4
0
0 12
23 1
4
5
7
8
3
0
24 2
4
6
4
6
0
0 24
25 4
4

（8）考察V8点，只有一个T标号，T(V8)=15，令P(V8)=15)，记录路 径（V7，V8），计算结束。
反推得最V1至V8的最短路为V1→V2 →V5 →V7 →V8,路长15。
8.2 最短路问题
一、Dijkstra算法：求无负权网络最短路问题。
计算步骤：
（1）给Vs以P标号，P（Vs）=0，其余各点给T标号， T（Vi）=+∞；
且仅得一个圈。
4）图中边数为：p-1（p为顶点数）
8.1 图与网络基本知识
例8-4：一个班级的学生共计选修A、B、C、D、 E、F六门课程，其中一部分人同时选修D、C、A， 一部分人同时选修B、C、F，一部分人同时选修 B、E，还有一部分人同时选修A、B，期终考试 要求每天考一门课，六天内考完，为了减轻学生 负担，要求每人都不会连续参加考试，试设计一 个考试日程表。
（2）若Vi点为刚得到P标号的点，考虑点Vj: (Vi,Vj) 属于E，且Vj为T标号。则修改T(Vj)
T(Vj)=min[T(Vj),P(Vi)+lij]；
（3）比较所有T标号的点，把最小者改为P标号，即： P（Vi）=min[T(Vi)] 当存在两个以上最小者时，可同时改为P标号。
8.2 最短路问题
8.1 图与网络基本知识
三、有向图的有关概念:
有向图：
由点和弧组成。表示为：D=（V，A）
V--点集合 A--弧集合
始点和终点： 对弧a=(u，v)， u为a的始点，v为a的
终点。
链（道路）：
点弧交错序列。
圈（回路）：
如一条链中起点和终点重合。
初等链（道路）： 链中无重复的点和弧。
（3） 考察V5V6和V5V7两边： T(V6)=min[T(V6),P(V5)+l56]=min[+∞,8+5] =13 T(V7)=min[T(V7),P(V5)+l57]=min[+∞,8+6] =14

v6
v7
v8
考虑边（v1,v2),(v1,v6),(v4,v2),(v4,v7)
计算 min{0+2, 0+3, 1+10, 1+2}=min {2,3,11,3} =2
v2:[2,v1]
（4）A={v1,v2,v4}
[0,v1] [2,v1] 2 1 10 [1,v1] v4 5 v6 [3,v1] 4 2 v7
最短．
最小支撑树的求法
1 破圈法 2 避圈法
5.2.1 求解最小支撑树问题的破圈法
方法：去边破圈的过程。 步骤：1）在给定的赋权的连通图上任找 一 个圈。 2）在所找的圈中去掉一条权数最 大的边。 3）若所余下的图已不含圈，则计 算结束，余下的图即为最小支撑
树，否则返回 1）。
例１：用破圈法求右图
v1 1 5 4 v2 2 v4 3 v6
权和＝１５
5.3 最短路问题
问题：求网络中一定点到其它点的最短路。
5.3.1 最短路问题的Dijstra解法 方法：给vi点标号[αi,vk] 其中：αi：vi点到起点vs的最短距离 vk: vi的前接点
方法：(1) 给起点vs标号[0，vs]。 （2）把顶点集v分为互补的两部分A和Ā 其中：A：已标号点集 Ā：未标号点集 （3）考虑所有这样的边[vi, vj], 其中vi ∈A,vj ∈ Ā 挑选其中与vs距离最短的点vj标号 [min{αi+cij},vi]
[3，V1]
考虑边(v2,v3),(v2,v5),(v4,v7),(v6,v7)
计算 min { 2+6, 2+5, 1+2, 3+4}=min {8,7,3,7}=3
v7:[3,v4]