V1V7最短路:V1V2V3V5V7;
此路上的最大流量为1，此路上流1。
v2 21
v5 10
10 32
10
v6 1
v7
v3
10
v1 至此V1V7已无通路，总流量6+6-2
=5+4+2-1=10。
v4
费用:123+22×1＝145
最最大小流费问用题
教材中的做法存在问题：如
1 v11
(P.226)。
最小费用最大流问题
作为LP问题用Excel的规划求解; 网络图论算法:分费用、流量两张图。
v2 3 62
4 v5 45
52 2
3v6 4
4 7 v7
6 v16
2 v3
3
8
1 v34 3 2
最小费用最大流问题
费用看6 作v2 边长的图4 中找V91v5 V7的最短路。
费用:56+16×1＝72
最小费用最大流问题
删边V1V4V3,路程图中找V1V7最短路。
v2
4
v5
6
6
5
10
4
7
6
0
v3 11
v6 4
v7
17
v1
6
v4 V1V7最短路:费V用1:56V+216×V15＝7V27
最小费用最大流问题
V1V7最短路:V1V2V5V7;
此路上的最大流量为3，此路上流3。
之间都有门可穿过。
(出入口如图示)。
4X4的呢？
安排问题一：文件存储
4段乐曲存在一条磁带上,查到并听完每首乐曲 的时间：设依次存的乐曲的长度为：a,b,c,d。
找到并听完第一首需时间a; 找到并听完第二首需时间a+b; 找到并听完第三首需时间a+b+c; 找到并听完第四首需时间a+b+c+d; 四共需时间：4a+3b+2c+d,平均找到并听完一首
运筹学 绍兴文理学院 工学院计算机系
第十章图与网络模型
Graph and Network Optimal
图与网络基本概念 最小生成树问题 最大流问题 最小费用最大流问题
最大流问题
作为LP问题用Excel的规划求解;
网络图论算法
0
v2 3 2
0 0
256810
0 v5 5 2 00
0
6
1 3
v16 4 3
1
02 20
0 v3
0
1
3
10
0v6 4 3 0 0v7
01
0125680
v4
2 0 最大流为:10，解为…
最最大小流费问用题
问题的提法：(P.225)； 问题的LP解法：(P.225); 问题的网络图论解法：费用 当路长找最短路，路中找最大 流，删边，…，反复寻找。
最小费用最大流问题
V1V7最短路:V1V4V3V6V7;
此路上的最大流量为2，此路上流2。
v2 3
v5
2
5
5 6 v13 1
2 20
v6 3 1
v7
v3
5
v4 3 1
费用:32+12×2＝56
最小费用最大流问题
删边V3V6,路程图中找V1V7最短路。
6 v2
4
9 v5
6 5
11
1
1
v2 1
V1V4最短路:V1V2V3V4 此路上流1。删去
1
三条边后，V1V4
2.1 再无通路了。
1 v4 显然最大流可以
1
是2,而不只是1。
1
请看图。
2.1 v31 此问题有Ford-Fulkerson算法。
排序与统筹 优先策略
(Greedy method 贪心算法)
安排问题(收衣服)：
0
v1
3
5
4
5 v3 2
7
v6 4
v7
16
5
Vv14 3V7最短路:V1V费4用:3V23+12V×52＝V576
最小费用最大流问题
V1V7最短路:V1V4V3V5V7;
此路上的最大流量为1，此路上流1。
v2 3
v5
2
54
6 6 v11 0
21
v6 1
v7
v3
6
v4 1 0
安排问题一：文件存储
一般地说：n段乐曲存在一条磁带上, 要使平均找到并听完一首乐曲所需的 时间最短,就应该尽量先存短的乐曲。 但这没考虑听这些乐曲的概率,最短 的存在最前面,但若人们听这首乐曲的 概率很小,那按乐曲长短安排存放次序 就不一定可取了。
等长的n段乐曲存在一条磁带上,要使 平均找到并听完一首乐曲所需的时间 最短,要尽量先存收听概率高的乐曲。
最小费用最大流问题
删边V4V6,路程图中找V1V7最短路。
v2
6
4
9 v5
6
1
0
v1
3
5
4
7
5 v3 3
v6 4
8
v7
11
1
2 8
v4 3
费用：10×1＝10
V1V7最短路:V1V4V7
最小费用最大流问题
V1V7最短路:V1V4V7;
此路上的最大流量为2，此路上流2。
v2 3
v5
2
5
3
6 v15 3
2 2
v6 3
v7
v3
3
v4 3 2 0
费用:10+11×2＝32
最小费用最大流问题
删边6Vv42 V7,路程4 图中找9 vV51V7最短5
4
7
5 v3 3
v6 4
8
v7
12
3
2
v4 3
费用:10+11×2＝32
V1V7最短路:V1V4V3V6V7
6
0
v1 3
5
4
7
5 v3 3
v6
6
4
v7
10
23 8
3
v4
V1V7最短路:V1V4 V6V7
最小费用最大流问题
V1V7最短路:V1V4 V6V7;
此路上的最大流量为1，此路上流1。
v2 3
v5
2
5
1
6 v16 5
2 2
v6 4 3
v7
v3
1
10 v4 3 2
费用：10×1＝10
乐曲所需的时间为f(a,b,c,d)=(4a+3b+2c+d)/4。 四首乐曲有4！=24种存放顺序,哪一种次序使f
最少？短的存在前：a<b<c<d的f(a,b,c,d)=min 否则如a<b,则顺序b,a,c,d将使f变大。理由是:
f(b,a,c,d)-f(a,b,c,d)=[4b+3a-(4a+3b)]/4=(b-a)/4>0
v2 3 0
v5
2
41
9
1
v6 1
v7
63 v1
v3
9
v4
费用:72+17×3＝123
最小费用最大流问题
删边V2V5,路程图中找V1V7最短路。
v2
6
v5
15
6
5
4
7
9
0
v311
v6 4
v7
22
v1
9
V1V7最短路:V1V2V3V5V7
v4
费用:72+17×3＝123
最小费用最大流问题
文件的存储； 任务的安排。
安排问题
满足某种要求的安排有没有？有的话,有多少？ 如有某个定量指标时,最优安排是否存在？是 否唯一？如存在,怎么找？这类问题是优化关 心的主题。如：著名
的八皇后问题。
存在性问题：设计 一个参观如右3X3的 展览馆的路线,使每 间展馆都到而且不重
复每东西或南北两间