当前位置：文档之家 › 运筹学第六章图与网络分析(ppt文档)

运筹学第六章图与网络分析(ppt文档)

  • 格式：ppt
  • 大小：1.34 MB
  • 文档页数：37

下载文档原格式

  / 37

合集下载

运筹学-6网络计划精品PPT课件

运筹学-6网络计划精品PPT课件

图2
14
图3
5)网络图中不能有缺口和回路 在网络图中，除始点和终点外，其它各个结点的前后都
应有弧相连接，即图中不能有缺口，使网络图从始点经 任何路线都可到达终点。否则，将使某些工序失去与其 紧后（或紧前）工序应有的联系。
在本章讨论的网络图中不能有回路，即不能有循环现 象。否则将使组成回路的子工程永远不能完工。在如下 网络图4中出现的情况是错误的。
EFTj= ESTj+ tj
一项工作的结束时间应等于其开始时间加
12
1) 方向、时序与结点编号
网络图是有向图，按照工艺流程的顺序，规定工序从左向右排列。 网络图中的各个结点都有一个时间(某一个或若干个工序开始或结 束的时间),一般按各个结点的时间顺序编号。为了便于修改编号及 调整计划,可以在编号过程中留出一些编号
2)紧前工序与紧后工序
例如,在图1中,只有在a 工序结束以后,b、c、d、e工序才能开始。a 工序是b、c、d、e 等工序的紧前工序,而b、c、d、e等工序则是工 序a 的紧后工序
这种计划借助于网络表示各项工作与所需要的时间，以 及各项工作的相互关系。通过网络分析研究工程费用与 工期的相互关系。并找出在编制计划时及计划执行过程 中的关键路线。这种方法称为关键路线法（Critical Path Method）简称CPM。
• 工程计划与甘特图
不易表现工程全貌 不便于对各项工作的安排进行筹划和推敲 不能识别影响进度的关键工作 不能反映一项工作不能按进度完成时对工程进度的影
99-7-5
2 拟拟拟拟拟拟拟拟拟拟拟拟拟
99-7-12
3 拟拟拟拟
99-7-13
99-7-22
4 拟拟拟拟拟拟拟
99-7-23

运筹学 图与网络分析PPT学习教案

运筹学 图与网络分析PPT学习教案

ij
min{ V1到Vj中间最多经过t-2个点 P1j（t-1）=
P1j（t-2）
+wij}
终止原则：
1）当P1j（k）= P1j（k+1）可停止，最短路P1j*= P1j（k） 2）当P1j（t-1）= P1j（t-2）时，第1再9页多/共迭59页代一次P1j（t） ，若P1j（t） =
P1j（t-1） ，则原问题无解，存在负回路。
图与网络模型Graph Theory
最短路问题
v1，u1 =（M，W，G，H）； v2，u2 =（M，W，G）；
v3，u3 =（M，W，H）；
v4，u4 =（M，G，H）；
v5，u5 =（M，G）。
此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。
v1
v2
v3
v4
v5
u5
u4
例： 求下图所示有向图中从v1到各点 的最短路。
2 v1
v2
4
5 -2 v3 6
-3 4
v4
7
v6 -3 2
v5
3
4
v8
-1
v7
第20页/共59页
wij
d(t)(v1,vj)
v1 v2 v3 v4 v5 v6 v7 v8 t=1 t=2 t=3 t=4 t=5 t=6
v1 0 2 5 -3
0 0 0 00 0
参加的游客众多，游客甚至不惜多花机票钱暂转取道它地也愿参加
此游。旅行社只好紧急电传他在全国各地的办事处要求协助解决此
问题。很快，各办事处将其已订购机票的情况传到了总社。根据此
资料，总社要作出计划，最多能将多少游客从成都送往北京以及如
何取道转机。下面是各办事处已订购机票的详细情况表：

管理运筹学 图与网络分析PPT教案

管理运筹学 图与网络分析PPT教案

v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第27页/共83页
支撑树的权：如果T=(V,E)是G的一个支撑树，则称E中所 有边的权之和为支撑树T的权，记为w(T)。即
w(T )
wij
[vi ,v j ]T
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
上例中支撑树的权为 3+7+5+2+2+3+4=26
第34页/共83页
v1
2
A
4
v6
3
7
3
v2
5
v5
5
6
2
4
5
v3 2 v4
7
v7
第35页/共83页
课堂练习：1.分别用三种方法求下图的最小支撑树
v2
7
v5
5
2
3
4
v1
4
5
v4 3
1
1
v7
7
4
v3
v6
第36页/共83页
2. 某农场的水稻田用堤埂分割成很多小块。为了 用水灌溉，需要挖开一些堤埂。问最少挖开多少条 堤埂，才能使水浇灌到每小块稻田？
水源
第37页/共83页
作业 P221： 第3题
第38页/共83页
§3 最短路问题
1. 问题的提出 2. 最短路问题的Dijkstra算法 3. 求任意两点之间最短距离的矩阵算法

第六章图与网络分析

第六章图与网络分析

e3
v3
若链中所有的顶点也互不相同,这样的链称为路.
e4
v4
起点和终点重合的链称为圈. 起点和终点重合的路称为回路.
若图中的每一对顶点之间至少存在一条链, 称这 样的图为连通图, 否则称该图是不连通的. 第10页
完全图，偶图
任意两点之间均有边相连的简单图, 称为完全图. K n
K2
K3
K4
2 | E | Cn
第20页
6.2树图和图的最小部分树问题 Minimal tree problem 6.2.1树的概念
若图中的每一对顶点之间至少存在一条链, 称这样的图 为连通图. 树图(简称树Tree)： 无圈的连通的图，记作T(V, E)
组织机构、家谱、学科分支、因特网络、通讯网络及高压线路 网络等都能表达成一个树图 。
第13页
有向图 G ： (V,E)，记为 G=(V,E)
G 的点集合： V {v1 , v2 ,...,vn } G 的弧集合： E {eij } 且 eij 是一个有序二元组 (vi , v j ) ，记
为 eij (vi , v j ) 。下图就是一个有向图，简记 G 。 若 eij (vi , v j ) ，则称 eij 从 v i 连向 v j ，点 v i 称为 eij 的尾，v j 称为 eij 的头。 v i 称为 v j 的前继， v j 称为 v i 的后继。 基本图：去掉有向图的每条弧上的方向所得到的无向图。
有向图 G (V , E ) 的关联矩阵：一个 | V | | E | 阶矩阵
B (bik ) ，
1, 当 弧ek以 点i为 尾 其中 bik 1, 当 弧ek以 点i为 头 0, 否 则

运筹学课件—网络分析

运筹学课件—网络分析

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)

第六章运筹学图与网络

第六章运筹学图与网络

A
7
2
2
5
S
4
B
5
D
5
1
C
3
4
E
1
7
T
第三节 最短路(Shortest path)问题 最短路问题是指在给定的网络(有向图和无向图) 中,找出任意两点间距离最短的一条路,这里的距 离是权值的代表.最短路问题可应用于选址,管道 铺设时的选线,设备更新,投资等方面. 本节介绍从某一点到其他各点之间最短距离的 Dijkstra算法和网络图上任意两点的最短距离的 矩阵算法.
对起点和终点相重合的链称为圈.起点和终点重 合的路称为回路.在一个图中,如果任意两点间 至少存在一条链,则称该图为连通图,否则为不 连通的.
1 v5 , e8 , v3 , e3 , v1 , e2 , v2 , e4 , v3 , e7 , v4 2 v5 , e8 , v3 , e7 , v4
图的最小部分树(最小生成树):设 G2 是一个图,如 果 G1 是 G2 的支撑子图(部分图),且 G1 是一个树, 则称 G1 是 G2 的部分树.树的各条边称为树枝.在 图的每条边上赋予权值的图称为赋权图. 在 G2 中一般含有许多部分树,其中树枝总长为 最小的部分树,称为该图的最小部分树.
部分树
min2 7,4 5,4 3,4 4 7 LSE , 对E标号, 将边[ B, E ]改
与已标号点相邻的未标 号点是D, T .计算 LSP minLSA d AD , LSB d BD , LSE d ED , LSE d ET [ E , D]改为红色; 只有T未标号, 计算LSP minLSD d DT , LSE d ET min8 5,7 7 13 LST , 对T标号, 将边[ D, T ] 改为红色, 计算结束.图中红线为S到T的最短路, T点旁的数值 13为最短路的长度 .

运筹学胡运权第五版(第6章)课件

运筹学胡运权第五版(第6章)课件
零图： 边集为空集的图。
运筹学胡运权第五版(第6章)
2、图的阶：即图中的点数。 例如 右图为一个五阶图
3、若图中边e= [vi,vj] ,则vi,vj称 为e的端点，
e称为vi,vj的关联边。 若vi与vj是一条边的两个端
点，则称vi与vj相邻； 若边ei与ej有公共的端点，
则称ei与ej相邻。
e8
1、图(graph)：由V,E构成的有序二元组，用以表示对 某些现实对象及其联系的抽象，记作 G=｛V,E｝。 其中V称为点集，记做V=｛v1,v2,···,vn｝
E称为边集，记做E=｛e1,e2,···,em｝
点(vertex)：表示所研究的对象，用v表示； 边(edge)：表示对象之间的联系，用e表示。 网络图(赋权图)： 点或边具有实际意义(权数)的图， 记做N。
路：点不能重复的链。
圈：起点和终点重合的链。
回路：起点和终点重合的路。
连通图：任意两点之间至少存在一条链的图。
完全图：任意两点之间都有边相连的简单图。
n阶完全图用Kn表示，边数=
C 2 n(n 1)
n

2
注意：完全图是连通图，但连通图不一定是完全图。
运筹学胡运权第五版(第6章)
v1 e4
v4 e5 v5
依次下去，vn必然与前面的某个点相邻，图中有圈，矛盾！
注意：树去掉悬挂点和悬挂边后余下的子图还是树。
运筹学胡运权第五版(第6章)
（2）n阶树必有n-1条边。
证明（归纳法）： 当n=2时，显然；
设n=k-1时结论成立。 当n=k时，树至少有一个悬挂点。
去掉该悬挂点和悬挂边，得到一个k-1阶的树，它有 k-2条边，则原k阶树有k-1条边。
7、已知图G1=｛V1,E1｝, G2={V2,E2}, 若有V1V2，E1E2，则称G1是G2的一个子图； 若V1=V2，E1E2且 E1≠E2 ，则称G1是G2的一个部分图。

Chap.6-图与网络分析解析

Chap.6-图与网络分析解析

V10
V11
V12
将奇点两两 相连，变成 偶点
2
4
2
V7
欧拉图
V13
4 V9 每条边上最多重复一次
在图G的每个回路上，有重复的边的长度不超过回路总 长的一半
Copyrights © 2006 - powered by nerdpal @ HIT
中国邮路问题
V1 4 V4 4 5 4 V10
4 V2
5 V3
× 1 V5 ×
2 V6 V7 2
2
1
×
V11
×
5 V8× 4
V12 ×
2
×
4 V13
× 4 7 V9 在图G的每个回路上，有重复的边的长度不超过回路总长的一半
Copyrights © 2006 - powered by nerdpal @ HIT
中国邮路问题
V1 4 V4 4 5 4 V10
t
v4 9(9) 如图，在链（s,v1,v2,v3,v4,t)中，μ+={(s,v1),(v1,v2),(v4,t)}, μ- ={(v3, v2),(v4,v3)}. v2
Copyrights © 2006 - powered by nerdpal @ HIT
§5 网络最大流
增广链，如果链μ满足以下条件：
(i , j ) Î E n n
å
wij x ij ì ï 1 ï ï ï = í- 1 ï ï ï 0 ï ï î E. , i = 1 , i = n , i ¹ 1, n
s.t .
邋x ij
j=1
j=1
x ji
x ij 澄 0, (i, j )
Copyrights © 2006 - powered by nerdpal @ HIT

运筹学第6章：图与网路分析

运筹学第6章：图与网路分析

13
6.3 最短路问题
6.3.1 狄克斯特拉算法 (Dijkstra algorithm, 1959)
• 计算两节点之间或一个节点到所有节点之间的最短路
令 dij 表示 vi 到 vj 的直接距离(两点之间有边)，若两点之间 没有边，则令 dij = ，若两点之间是有向边，则 dji = ； 令 dii = 0，s 表示始点，t 表示终点





10 16 11 10 17 10 9.5 19.5 16 9.5 7 12 7 8 7 11 10 8 9 17 19.5 12 7 9
• • • • •
Prim算法是多项式算法 Prim算法可以求最大生成树 网路的边权可以有多种解释，如效率 次数受限的最小生成树—尚无有效算法 最小 Steiner 树—尚无有效算法
j dij i dik djk k
17
6.3.2 Floyd-Warshall 算法 (1962)
for i=1 to n do dii=; for all eij=0; for j=1 to n do for i=1 to n do if ij then for k=1 to n do if kj then begin dik=min{dik, dij+djk}; if dik>dij+djk then eik=j end;
7
6.2 树图与最小生成树
• 一般研究无向图 • 树图：倒臵的树，根(root)在上，树叶(leaf)在下 • 多级辐射制的电信网络、管理的指标体系、家谱、分 类学、组织结构等都是典型的树图
C1
根
C2
C3
C4

运筹学图与网络分析.pptx

运筹学图与网络分析.pptx
{a12,a14,a34}
{a26,a46 } φ
min{ li Wij | Vj J } lh Whk
iI
min{l1+W12, l1+W13, l1+W14}= min{0+3,0+2,0+5}=2= l1+W13 min{l1+W12, l1+W13, l3+W34}= min{0+3,0+5,2+1}=3= l1+W12, l3+W34 min{l2+W26, l4+W46}= min{3+7,3+5}=8= l4+W46
{ a57,a68 }
min{ li Wij | Vj J } lh Whk
iI
min{l1+W12, l1+W13, l1+W14}= min{0+2,0+6,0+3}=2= l1+W12 min{l1+W13, l1+W14, l2+W23, l2+W26}= min{0+6,0+3,2+3, 2+7}=3= l1+W14 min{l1+W13,l2+W23, l2+W26, l4+W45}= min{0+6,2+3,2+7,3+6}=5= l2+W23 min{l2+W26, l3+W35, l3+W36, l4+W45}= min{2+7,5+3,5+7,3+6}=8= l3+W35 min{l2+W26, l3+W36, l5+W56, l5+W57}= min{2+7,5+7,8+1,8+6}=9= l2+W26, l5+W56 min{ l5+W57, l6+W68}= min{8+6,9+4}=13= l6+W68

运筹学基础及应用(第五版),(第六章图与网络分析)

运筹学基础及应用(第五版),(第六章图与网络分析)
树枝总长最小的部分树，称为该图的最小部分树(也称最小支
撑树)。
定理1. 图中任一个点 i ，若 j 是与 i 相邻点中距离最近的， 则边 [ i , j ] 一定包含在该图的最小部分树中。
给图中的点和边赋以具体的含义和权值，我们称这样的
图为网络图（赋权图）
2020/3/27
6
图中的点用 v 表示，边用 e 表示，对每条边可用它所
联结的点表示，如图，则有：
e1 = [v1 , v1]，
e2 = [v1 , v2]或e2= [v2 , v1]
2020/3/27
用点和点之间的线所构成的图，反映实际生产和生 活中的某些特定对象之间的特定关系。通常用点表 示研究对象,用点与点之间的线表示研究对象之间 的特定关系。一般情况下，图中点的相对位置如何 ，点与点之间线的长短曲直，对于反映研究对象之 间的关系，显的并不重要，因此，图论中的图与几 何图，工程图等本质上是不同的。
§2．树图和最小部分树
树图（简称树，记作 T(V, E)）是无圈的连通图。（无圈， 无多重边）
一. 树的性质
性质1. 任何树中必存在次为1 的点。
次为1的点称为悬挂点，与之关联的边称为悬挂边。 性质2. 具有 n 个顶点的树恰有（n-1）条边。
性质3. 任何具有n 个点、(n - 1)条边连通图是树。
A D
C B
2020/3/27
3
为了寻找答案 ，1736年欧拉 把陆地缩为一点，把桥作为连接点 的边，将这个问题抽象成图形的一 笔画问题。即能否从某一点开始不 重复地一笔画出这个图形，最终回 到原点。欧拉在他的论文中证明了 这是不可能的，因为这个图形中每 一个顶点都与奇数条边相连接，不 可能将它一笔画出，这就是古典图 论中的第一个著名问题。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

§6.1 图的基本概念和模型
一、概念
（1）图：点V和边E的集合，用以表示对某种现实事物
的抽象。记作 G=｛V,E｝, V=｛v1,v2,···,vn｝, 点：表示所研究的事物对象； E=｛e1,e2,···,em｝
边：表示事物之间的联系。
e0
（2）若边e的两个端点重 合，则称e为环。
（3）多重边：若某两端点之 间多于一条边，则称为多重边。
D 8 64 5 0 15
E 7 53 4 1 0 6
T 14 11 9 10 5 6 0
i
dir（1）
r
drj（1）
j
⑷ 构造任意两点间最多可经过7个中间点到达的最短距 离矩阵 D（3）= dij（3）
其中
dij（3）=
min
r
{
dir（2）+
drj（2）
}
SABCDET
S 0 2 4 4 8 7 13
dir（0）
r i
drj（0）
j
⑶ 构造任意两点间最多可经过3个中间点到达的最短距 离矩阵 D（2）= dij（2）
其中
dij（2）=
min
r
{
dir（1）+
drj（1）}
SABCDET
S 0 2 4 4 8 7 14
A 2 0 2 3 6 5 11
B 4 20 1 43 9 D（2）= C 4 3 1 0 5 4 10
2. 破圈法：
⑴ 任取一圈，去掉其中一条最长的边， ⑵ 重复，至图中不存在任何的圈为止。
2. 破圈法
A
S
5 × B 5× D 5 T
C
4× E
最小部分树长Lmin=14
§6.3 最短路问题
1．求某两点间最短距离的D（Dijkstra）氏标号法
在图示的网络图中，从给定的点S出发，要到达目 的地T。问：选择怎样的行走路线，可使总行程最短？ 方法：Dijkstra（D氏）标号法——按离出发点的距离由 近至远逐渐标出最短距离和最佳行进路线。
e1 v1
e5
v0 e2
e3
v2
e4
e6 e7
v3
v4
（4）简单图：无环、无多重边的图称为简单图。
（5）链：点和边的交替序列，其中点可重复，但边不能 重复。
（6）路：点和边的交替序列，但点和边均不能重复。
（7）圈：始点和终点重合的链。
（8）回路：始点和终点重合的路。
（9）连通图：若一个图中，任意两点之间至少存在一条 链，称这样的图为连通图。 （10）子图，部分图：设图G1=｛V1,E1｝, G2={V2,E2}, 如果有V1V2，E1E2，则称G1是G2的一个子图；若 V1=V2，E1E2，则称G1是G2的一个部分图。 （11）次：某点的关联边的个数称为该点的次，以d(vi)表示。
⑵ 构造任意两点间直接到达、或者最多经过1个中间点到达的最 短距离矩阵D（1）= dij（1）
其中 dij（1）= mrin { dir（0）+ drj（0）} ，
例如
{ dSE（1）= min dSS（0）+dSE（0）, dSA（0）+dAE（0）, dSB（0）+dBE（0）, dSC（0）+dCE（0
√
建立模型：
解：项目作为研究对象，排序。 设 点：表示运动项目。 边：若两个项目之间无同一名运动员参加。
A
F
B
E
C
D
顺序： A—C—D—E—F—B A—F—E—D—C—B A—C—B—F—E—D
A—F—B—C—D—E
§6.2 树图和图的最小部分树
一、树图的概念 （1）树：无圈的连通图称为树图，简称为树。
第六章 图与网络分析
6.1 图的基本概念与数学模型 6.2 树图和图的最小部分树 6.3 最短路问题 6.4 中国邮路问题 6.5 网络最大流问题 6.6 网络模型的实际应用

第六章 图与网络分析
• 图是一种模型，如公路、铁路交通图， 通讯网络图等。
• 图是对现实的抽象，以点和线段的连 接组合表示。
A 2 0 2 3 6 5 11
B 4 20 1 43 9 D（3）= C 4 3 1 0 5 4 10
D 8 64 5 0 15
E 7 53 4 1 0 6
T 13 11 9 10 5 6 0
二、图的模型
例：有甲、乙、丙、丁、戊、己六名运动员报名参加A、 B、C、D、E、F六个项目的比赛。如表中所示，打“√”的 项目是各运动员报名参加比赛的项目。问：六个项目的比赛 顺序应如何安排，才能做到使每名运动员不连续地参加两项 比赛？
人
ABCDE F
甲 乙√ 丙 丁√ 戊 己
√
√
√
√
√
√
√
√
√
√
S
2
4
7
2 A
0 5
S
5 45 B
98
14
5
13
D
T
C
E
4
4
4
7
最短路线：S AB E D T
最短距离：Lmin=13
2．求任意两点间最短距离的矩阵算法
⑴ 构造任意两点间直接到达的最短距离矩阵D（0）= dij（0）
S A B D（0）= C D E T
SABCDET 0 25 4 2 02 7 5 20 1 5 3 4 1 0 4 75 0 15 3 41 0 7 5 7 0
二、最小部分树的求法 例：要在下图所示的各个位置之间建立起通信网络，
试确定使总距离最佳的方案。
1. 避圈法
A 5 S
5 B
5
D
T
C
E
4
最小部分树长Lmin=14
1. 避圈法：将图中所有的点分V为V两部分， V——最小部分树内点的集合 V——非最小部分树内点的集合
⑴ 任取一点vi加粗，令vi∈V， ⑵ 取V中与V相连的边中一条最短的边(vi,vj)， 加粗(vi,vj)，令vj∈V ⑶ 重复⑵ ，至所有的点均在V之内。
（2）树的特性：
① 树是边数最多的无圈连通图。在树中任加一条边，就会形成圈。 ② 树是边数最少的连通图。在树中任减一条边，则不连通。
（3）图的最小部分树：
定义：若G1是G2的一个部分图，且为树图，则称G1是 G2的一个部分树。
G2： A
5
7
65
B
C G1：A
5
7 4
6
3D B
C D
定义：树枝总长为最短的部分树称为图的最小部分树。 树枝：树图中的边称为树枝。
）,
dSD（0）+SdDE（A0） ,BdSE（C0）+ dDEE（0E）, dTST（0）+ dTE（0） } =8 S 0 24 4 98 A 2 0 2 3 7 5 12 B 4 2 0 1 4 3 10
D（1）= C 4 3 1 0 5 4 11 D 9 74 5 0 15 E 8 53 4 1 0 6 T 12 10 11 5 7 0