(运筹学.ppt
文本预览下载声明
第11章 图与网络分析 11.1 图与网络的基本知识 11.2.树与图的生成树 11.3.最短路线问题 11.4.最大流问题 11.5.最小费用最大流问题 11.6 计算机求解 最大流问题是一类应用极为广泛的问题,例如在交通运输网络中有人流、车流、货物流,供水网络中有水流,金融系统中有现金流,通讯系统中有信息流等等。这类网络的组成弧都具有确定的通过能力,称为容量;而实际通过弧的流量则因网络各弧容量配置关系,有些常常达不列容量值,因此研究实际能通过的最大流量问题,可以充分发挥网络的设备能力,并能明确为使最大流量增大应如何改造网络。 在一个网络模型中,如果给一个发点和收点在满足弧的能力约束下,决定最大的可能流,这样的问题就是最大流问题。 在实际的网络系统中,当涉及到有关流的问题的时候,我们往往不仅仅考虑的是流量,还经常要考虑费用的问题。比如一个铁路系统的运输网络流,即要考虑网络流的货运量最大,又要考虑总费用最小。最小费用最大流问题就是要解决这一类问题。 v2 v5 v3 v1 v4 v6 (8,6) (5,2) (5,1) (9,7) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,2) (+v2,2) (+v4,2) 在μ上进行流量?=2的调整,得可行流f ’ v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (+v1,1) (-v2,2) 对于调整后的可行流进行标号。 从v1开始,重新标号。 v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (1)给v1标上(-,∞);v1为标号而未检查的点。 (2)检查与v1相邻接且未标号的点 v2,v3。 弧(v1,v2)为饱和的正向弧,不满足标号条件,该点不标号 在弧(v1,v3)上,f13=1c13=2,故给v3标号 (+v1,l(v3)),其中 l(v3)=min[l(v1),f13]=min[∞,1]=1。 v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,1) (3)检查与v3相邻接且未标号的点。 在弧(v3,v2)上, f32=60,故(v3,v2)为非零流的反向弧, 给v2标号(-v3,l(v2)),其中 l(v2)=min[l(v3),f32]=min[1,6]=1。 v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,1) (-v3,1) v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,1) (+v2,2) (+v3,1) 在弧(v3,v4)上,f34=1c34=5,故给v4标号(+v3,l(v4)),其中 l(v4)=min[l(v3),(c34-f34)]=min[1,5-1]=1 在弧(v3,v5)上,f35=6c35=8,故给v5标号(+v3,l(v5)),其中 l(v5)=min[l(v3),(c35-f35)]=min[1,8-6]=1 (+v3,1) (4)检查与v4相邻接且未标号的点v6,弧(v4,v6) 为饱和的正向弧,不满足标号条件,该点不标号。 检查与v5相邻接且未标号的点v6,在弧(v5,v6)上,f56=0c56=7,故给v6标号(+v5,l(v6)), 其中l(v6)=min[l(v5),(c56-f56)]=min[1,7-0]=1 v6得到标号,标号过程结束。 v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,1) (-v2,1) (+v3,1) (+v3,1) (+v5,1) v2 v5 v3 v1 v4 v6 (8,8) (5,4) (5,1) (9,9) (2,1) (8,6) (7,0) (3,2) (6,4) (6,6) (-,∞) (+v1,1) (-v2,1) (+v3,1) (+v3,1) (+v5,1) (二)调整过程:从v6开始逆向追踪,找到增广链。 沿该可增广链,从v6倒推,增广链上的
显示全部