《运筹学研究生辅导课件》最短路最大流练习题.doc
文本预览下载声明
7 求图7.58中各图从到各点的最短路．
，k=5.
i=2
)，
令
对已经标号v3，（v3,v7）∈S,但v7已经标号。对已经标号v11，有（v10,v11）∈S,则T(v11)修改为P(v10)+w10-11=15+4=19,λ(v11)=10,所以P(v11)=19,
S9={ v1,v2,v5,v9,v4,v6,v8,v7,v3,v10,v11}
d(v1,v2)=2, 最短路为（v1,v2）;
d(v1,v5)=3, 最短路为（v1,v2,v5）;
d(v1,v9)=4, 最短路为（v1,v2,v5,v9）;
d(v1,v7)=14 ,最短路为（v1,v2,v5,v9,v6,v7）;
d(v1,v8)=11, 最短路为（v1,v2,v5,v9,v8）;
d(v1,v4)=8, 最短路为（v1,v2,v4）或（v1,v4）;
d(v1,v6)=10, 最短路为（v1,v2,v5,v9,v6）;
d(v1,v3)=15, 最短路为（v1,v2,v4,v3）或（v1,v4,v3）;
d(v1,v10)=15, 最短路为（v1,v2,v5,v9,v6,v7,v10）;
d(v1,v11)=19, 最短路为（v1,v2,v5,v9,v6,v7,v10,v11）;
结果标在图7.58(a’)上。
解 结果见图7.58(b’).
求图7.62中各图从到的最大流．
两家工厂和生产同一种商品，商品通过图7.63表示的网络送到．求从工厂到市场所能运送的最大总量．
解 加上点，点同时给中间点加上名称，令所有弧的可行流都为0，如图7.63(1)所示，
（1）标号过程
用标号法找出增广链.(0,+),(,30),(,18),(,7),(,7),因已标号,故转入调整过程.
(2)调整过程
按点的第一标号找到一条增广链,如图7.63(2)中粗箭头表示.
按照=7,在上调整
由于本题图形复杂,调整过程次数过多,这里不再一步步进行计算,把进行几步计算后的结果直接写在图7.63(3)上.
3
4
1
4
8
2
3
5
6
7
9
4
5
5
3
2
1
5
7
(a)
(3,2)
(3,2)
(10,4)
(2,2)
(1,1)
(4,3)
(3,2)
(4,3)
(4,2)
(5,3)
(8,3)
(7,6)
(b)
图7.62
(s,7)
(1,3)
(3,0)
(5,3)
(4,4)
(1,0)
(7,1)
(2,3)
(1,4)
(4,4)
(8,2)
(2,2)
(3,0)
(6,2)
(7,2)
(0,+∞)
(9,2)
(4,0)
(5,4)
(5,4)
(3,0)
(2,2)
(1,0)
(5,0)
(7,4)
(5,1)
(a’)
(3,3)
(3,3)
(10,7)
(s,3)
(2,2)
(1,1)
(4,4)
(3,3)
(0,+∞)
(4,4)
(4,4)
(5,5)
(8,7)
(7,7)
(b’)
图7.62
7
4
2
9
1
7
3
1
5
6
8
2
2
1
4
6
1
1
1
9
2
3
(a)
4
4
8
7
3
2
2
3
2
5
6
4
5
5
1
5
3
2
2
6
4
2
(b)
P(19,10)
P(14,6)
P(10,9)
P(4,5)
P(3,2)
P(8,1)
P(0,0)
4
2
9
1
7
3
1
5
6
显示全部