[管理学]第11章 图与网络优化.ppt

W12 =11+5=16 W13 =11+5+6=22 W14 =11+5+6+8=30 W15 =11+5+6+8+11=41 W16 =11+5+6++8+11+18=59 13 (5) 9 (3) 4 (1) 5 (3) 6(3) 5 (2) 5 (2) 5 (0) 4 (2) 4 (1) 9 (5) 10 (1) 课堂练习：求下图所示网络中的最大流，弧旁数为 13 (11) 9 (9) 4 (0) 5 (5) 6(6) 5 (5) 5 (4) 5 (4) 4 (4) 4 (3) 9 (9) 10 (7) 截集1 截集2 最小截量为：9+6+5=20 70（70） 70（50） 130（100） 150（130） 150（150） 50（20） 50（50） 120（30） 100（100） ∞ （120 ） ∞ （230 ） ∞ （150 ） ∞ （200 ） 练习：求下图所示网络的最大流 *11.4.3 求解网络最大流问题的LINGO程序 由可行流的定义可推导出最大流的数学规划表达式如下 从上面的表达式可以看出，最大流问题其实就是一种规划问题，因此可以采用LINGO软件进行求解。下面用例子说明如何用LINGO软件求解最大流问题。 (11-4) (11-5) 例11.12 (续例11.10 最大流问题） 现需要将城市s的石油通过管道运送到城市t，中间有4个中转站，城市与中转站的连接以及管道的容量如下图所示，求从城市s到城市t的最大流。 解：相应的LINGO程序清单如下 MODEL: 1]sets: 2]nodes/s,1,2,3,4,t/; 3]arcs(nodes,nodes)/s,1 s,2 1,2 1,3 2,4 3,2 3,t 4,3 4,t/:c,f; 4]endsets 5]data: 6]c=8 7 5 9 9 2 5 6 10; 7]enddata 8]max=@sum(arcs(i,j)|i #eq# 1:f(i,j)); 9]@for(nodes(i)|i #ne# 1 #and# i #ne# @size(nodes): 10] @sum(arcs(i,j):f(i,j))-@sum(arcs(j,i):f(j,i))=0); 11]@for(arcs:@bnd(0,f,c)); END 程序的第9-10行表示约束(11-4)，第11行表示有界约束(11-5)。在以上的程序清单中并未单独列出发点和收点的约束，其实它们已经隐含在了目标函数及其他约束条件之中了。 LINGO软件的计算结果（只保留流量)如下： Global optimal solution found. Objective value: 14.00000 Total solver iterations: 3 Variable Value Reduced Cost F( S, 1) 7.000000 0.000000 F( S, 2) 7.000000 0.000000 F( 1, 2) 2.000000 0.000000 F( 1, 3) 5.000000 0.000000 F( 2, 4) 9.000000 -1.000000 F( 3, 2) 0.000000 0.000000 F( 3, T) 5.000000 -1.000000 F( 4, 3) 0.000000 1.000000 F( 4, T) 9.000000 0.000000 因此，该网络的最大流为14，F的值对应弧上的流，如图11-26所示