第11章图与网络模型

18
§3 最小生成树问题
树是图论中的重要概念，所谓树就是一个无圈的连通图。
v1
v1
v1
v2
v3
v6
v5
v4
v7
v8
v9
(a)
v2
v3
v4
v5
v6
(b)
v8 v7
图11-11
v2
v8
v3
v4
v9
v5
v7
v6
(c)
图11-11中，(a)就是一个树，而(b)因为图中有圈所以就不 是树， (c)因为不连通所以也不是树。
4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其 值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号 （scd,c）,返回步骤2。
高级运筹学
17
第十一章 图与网络模型 回顾
解题关键：把实际问题抽象为图（对象对应点， 对象间的关系对应线）
高级运筹学
23 (41,1)
16
v2 16 v3 17 v4 17 v5 18
（16,1）
22
23
30
31
41
(53,3) (53,4)
v6
高级运筹学
12
§2 最短路问题
V1 （0,s）
59
41
22
30
23
(30,1)
16
V2
16 v3 17
（16,1） (22,1)
v4 17 (41,1)18 23 31 v5
解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6
各点的标号图如下：
(3,1)
(8,4)
v2
7
v6
（V01,s)
3 5
2
(3,3) 5 v4
21
31
5
(2,1)
v5
高 v级3 运 筹 学
7
§2 最短路问题
例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设
使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间
由点和弧构成的图，记作D=（V，A）。
连通图：
对无向图G，若任何两个不同的点之间，至少存在一条链，则G为 连通图。
回路：
若路的第一个点和最后一个点相同，则该路为回路。
赋权图：
赋权图对，一w个ij称无为向边图(Gvi的 ,vj每)上一的条权边。(vi,vj)，相应地有一个数wij，则称图G为
网络：
已知：设备每年年初的价格表
年份
1
2
3
4
5
年初价格
11
11
12
12
13
设备维修费如下表
使用年数 0-1
1-2
2-3
3-4
4-5
每年维修
5
6
8
11
18
费用
高级运筹学
10
§2 最短路问题
例3的解： 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的
(赵v1)
e2
(v3)孙
e1
e3
(v2)钱
(v5) 周
e4 (v4) 李
e5 (v6)吴
(v7)陈
图11-1
高级运筹学
2
§1 图与网络的基本概念
当然图论不仅仅是要描述对象之间关系，还要研究特定关 系之间的内在规律，一般情况下图中点的相对位置如何、点与 点之间联线的长短曲直，对于反映对象之间的关系并不是重要 的，如对赵等七人的相互认识关系我们也可以用图11-2来表示， 可见图论中的图与几何图、工程图是不一样的。
例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定 是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定 的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省 去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划， 使得五年内购置费用和维修费用总的支付费用最小。
高级运筹学
19
§3 最小生成树问题
给了一个无向图G=(V,E)，我们保留G的所有点，而删掉部分G的边或 者说保留一部分G的边，所获得的图G，称之为G的生成子图。在图11-12中， (b)和(c)都是(a)的生成子图。
如果图G的一个生成子图还是一个树，则称这个生成子图为生成树， 在图11-12中，(c)就是(a)的生成树。
公路的长度（单位：公里）。
V7 （乙地）
17
v2
5
6
15
6 v4
V1
（甲地）
43
10
4
4
2
v5
v6
v3
解：这是一个求无向图的最短路的问题。可以把无向图的每一边 （vi,vj）都用方向相反的两条弧（vi,vj）和（vj,vi）代替，就化为有向图， 即可用Dijkstra算法来求解。也可直接在无向图中用Dijkstra算法来求解。 只要在算法中把从已标号的点到未标号的点的弧的集合改成已标号的点 到未标号的点的边的集合即可。
高级运筹学
14
第十一章 图与网络模型 回顾
图：是由点和边构成，反映一些对象之间的关系。
(赵v1)
e2
(v3)孙
e1
e3
(v2)钱
(v5源自文库 周
e4 (v4) 李
e5 (v6)吴
(v7)陈
图11-1
高级运筹学
15
第十一章 图与网络模型 回顾
▪ 无向图：
由点和边构成的图，记作G=（V，E）。
有向图：
5
8
v6 4
v5
解：此问题实际上是求图11-14的最小生成树，这在例4中已经求得， 也即按照图11-13的(f)设计，可使此网络的总的线路长度为最短，为19 百米。
“管理运筹学软件”有专门的子程序可以解决最小生成树问题。
高级运筹学
23
§4 最大流问题
最大流问题：给一个带收发点的网络，其每条弧的赋权称 之为容量，在不超过每条弧的容量的前提下，求出从发点 到收点的最大流量。
v6 (f) v5
高级运筹学
22
§3 最小生成树问题
例5、某大学准备对其所属的7个学院办公室计算机联网，这个网络的可 能联通的途径如下图，图中v1,…,v7 表示7个学院办公室，请设计一个网 络能联通7个学院办公室，并使总的线路长度为最短。
图11-14
v2 1 v3
34
7
v1 3
v7 2
v4
10 3
v1
3
34 7 v7 2
v4
35
8
4
v6 (b) v5
v2 1 v3
v1
3
34 7 v7 2
v4
35 4
v6 (c) v5
v2 1 v3
v1
3
34 7 v7 2
v4
3
4 v6 (d) v5
v2 1 v3
v1
3
34 7 v7 2
v4
3
v2 1 v3
3
7
v1 3
v7 2
v4
3
v6 (e) v5
图11-13
e2
(v1) 赵
e1 e3
e4
(v2)钱 孙(v3) 李(v4)
周(v5)
图11-2
e5 吴(v6) 陈(v7)
高级运筹学
3
§1 图与网络的基本概念
如果我们把上面例子中的“相互认识”关系改为“认识”
的关系，那么只用两点之间的联线就很难刻画他们之间的关
系了，这是我们引入一个带箭头的联线，称为弧。图11-3就
在赋权的有向图D中指定一点，称为发点，指定另一点称为收点， 其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称 为网络。
高级运筹学
16
第十一章 图与网络模型 回顾
最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条 从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称 之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt 的距离。
是一个反映这七人“认识”关系的图。相互认识用两条反向
的弧表示。
a1 a2
(v2)钱
a7
a8
(赵v1)
a14 a15 a3
(v4) 李
a4
a9
(v3)孙
a5
a6
a12
a11
(v5) 周
a10
(v6)吴 a13
(v7)陈
图11-3
高级运筹学
4
§1 图与网络的基本概念
▪ 无向图：
由点和边构成的图，记作G=（V，E）。
第十一章 图与网络模型
§1 图与网络的基本概念 §2 最短路问题 §3 最小生成树问题 §4 最大流问题 §5 最小费用最大流问题
高级运筹学
1
§1 图与网络的基本概念
图论中图是由点和边构成，可以反映一些对象之间的关系。
例如：在一个人群中，对相互认识这个关系我们可以用图 来表示，图11-1就是一个表示这种关系的图。
网络：
在赋权的有向图D中指定一点，称为发点，指定另一点称为收点， 其它点称为中间点，并把D中的每一条弧的赋权数称为弧的容量，D就称 为网络。
高级运筹学
5
§2 最短路问题
最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条 从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称 之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt 的距离。
高级运筹学
24
§4 最大流问题
一、最大流的数学模型
例6 某石油公司拥有一个管道网络，使用这个网络可以把石油从采地运送 到一些销售点，这个网络的一部分如下图所示。由于管道的直径的变化， 它的各段管道（vi,vj）的流量cij（容量）也是不一样的。cij的单位为万加仑/ 小时。如果使用这个网络系统从采地 v1向销地 v7运送石油，问每小时能运 送多少加仑石油？
一、求解最短路的Dijkstra算法(双标号法）
步骤：
1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合
{(vi,vj)|vi I,vj J}
3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs 到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上 述的弧的集合不是空集，则转下一步。
一、求解最短路的Dijkstra算法(双标号法）
步骤：
1.给出点V1以标号(0,s)
2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合
{(vi,vj)|vi I,vj J}
3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs 到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上 述的弧的集合不是空集，则转下一步。
高级运筹学
8
§2 最短路问题
例2最终解得： 最短路径v1 v3 v5 v6 v7，每点的标号见下图
15 （0,s）
V1 （甲地） 10
(13,3) v2 3 V3
(10,1)
17
5 6
V4
(18,5) 4
2
4
V5
(14,3)
(22,6) V7 （乙地） 6 V(166,5)
高级运筹学
9
§2 最短路问题
有向图：
由点和弧构成的图，记作D=（V，A）。
连通图：
对无向图G，若任何两个不同的点之间，至少存在一条链，则G为 连通图。
回路：
若路的第一个点和最后一个点相同，则该路为回路。
赋权图：
赋权图对，一w个ij称无为向边图(Gvi的 ,vj每)上一的条权边。(vi,vj)，相应地有一个数wij，则称图G为
条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图
即为最小生成树，否则返回第1步。
高级运筹学
21
§3 最小生成树问题
例4 用破圈算法求图（a）中的一个最小生成树
v2 1 v3
v2 1 v3
v1
3
34 7 v7 2
v4
10
35 4
8
v6 (a) v5
30
41
v6 (53,3) (53,4)
最终得到下图，可知，v1到v6的距离是53，最短路径有两条： v1 v3 v6和 v1 v4 v6
高级运筹学
13
第十章 动态规划
动态规划：解决多阶段决策过程最优化问题 最解优决化思原路理：：多不阶管在段此最优策略单上阶的段某个状态以前的状 策成原如最何 优，子理对策：略该最。状优就态化是来说说原，，理以最后优的策所略有的决 任策 意必 子定 策构 略 都解是决最方优法的：。逆序解法 解资逆再整源决序 逆 个分的解 向 过配具法 逐 程、体： 个 的生问阶 最正产题段优向过找决将：出策待程最最方解最短佳案决优路决的。化径策问等、方题问装案划题载分，问成直题多到、个求库阶得存段、
4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其 值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号 （scd,c）,返回步骤2。
高级运筹学
6
§2 最短路问题
例1 求下图中v1到v6的最短路
v1
v2 3
52
21
v3
7 v4 5
3 5
v6
1 v5
最小生成树问题就是指在一个赋权的连通的无向图G中找出一个生成 树，并使得这个生成树的所有边的权数之和为最小。
(a)
图11-12
(b)
高级运筹学
(c)
20
§3 最小生成树问题
一、求解最小生成树的破圈算法 算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两
设备一直使用到第j年年初。
v1
v2
v3
v4
v5
v6
把所有弧的权数计算如下表：
1
2
3
4
5
6
1
16
22
30
41
59
2
16
22
30
41
3
17
23
31
4
17
23
5
18
6
高级运筹学
11
§2 最短路问题
(继上页) 把权数赋到图中，再用Dijkstra算法求最短路。
v1
（0,s）
59
22
30
41 (30,1)
(22,1)