(运筹学.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倒推，增广链上的