《第4节 网络最大流问题》由会员分享，可在线阅读，更多相关《第4节 网络最大流问题（43页珍藏版）》请在金锄头文库上搜索。
1、图与网络优化周荣喜 北京化工大学经济管理学院公路系统中的车辆流4 4 网络最大流问题网络最大流问题控制系统中的信息流供水系统中的水流金融系统中的现金流问题背景网络最大流问题问题的提出n网络中存在流量限制时，求解一条线路使 得从起点与终点之间可通过的流量最大。v1v2v3v4v5v61084653531117例：上图为V1到V6的一交通网，权表示相应运输线的最大 通过能力，制定一方案，使从V1运到V6的产品数量最多。设有网络D=(V, A, C)，其中C=cij， cij为弧(vi,vj)上的容量，现在D上要通过一个流f=fij， fij为弧(vi,vj)上的流量。问题：如何安排fij，可使网络
2、D上的总流量最大？v2v1v3v4v5v681041755311635312213362一、一般提法：二、最大流问题的模型二、最大流问题的模型max v=v（f） 容量约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362注：满足两约束条件的流f称为可行流，v(f)称为该可行流的流量试分析下图是否是可行流试分析下图是否是可行流? ?v2v1v3v4v5v681041755311635312113362三、基本概念与定理三、基本概念与定理1. 1. 弧按流量分为弧按流量分为饱和弧 fij=cij非饱和弧 fij0，则给vj标(-vi，l(vj)，其中nvi成为
3、标号而已检查过的点，重复上述步骤，一旦vt被标号，表明得到一条从vs到vt的增广链，转入 2.调整过程n如果所有标号已检查过，而标号不能进行下去，则算法 结束，这时可行流为最大流。网络最大流问题标号法n1.标号过程n2.调整过程利用反向追踪法找出增广链。调整量为= l(vt)去掉所有的标号，对新的可行流f*重新进行标号过程。步骤： (1)给vs标号为0,+，流出未饱和弧(vs , vj) ,给vj标号vs ,j,其中j=csj- fsj或流入非零弧 (vj , vs) ,给vj标号-vs, j ,其中j=fsj例例. . 图中网络弧旁数字为图中网络弧旁数字为(cij, ,fij)，用标号法求最
4、大流。0,+vs, 4选与vs关联的v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）（3,0）(2)把节点集V分为VA：已标号点集VB：未标号点集v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0 , +vs, 4（3,0）考虑所有弧(vi , vj)或(vj , vi) ,其中vi VA, vj VB，若该弧为流出未饱弧,则给vj标号vi , j,其中j=mini, cij- fij流入非零弧,则给vj标号-vi , j ,其中j= mini, fij(3)-v1 , 1v2Vsv
5、1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0 , +vs , 4（3,0）(4)v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0 , +vs , 4-v1 , 1重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号,且无法再标号,此时的流为最大流,此时的截集为最小截。（3,0）v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0 , +vs, 4-v1, 1(4) 重复（2）,（3）
6、，依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号,且无法再标号,此时的流为最大流,此时的截集为最小截。v2 , 1（3,0）V3(4) 重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标号,且无法再标号,此时的流为最大流,此时的截集为最小截。v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0, +vs, 4-v1, 1v2, 1（3,0）v4, 1(4) 重复（2）,（3），依次进行的结局可能为vt已标号，得到一条增广链u(反向追踪)，转（5）；vt未标
7、号,且无法再标号,此时的流为最大流,此时的截集为最小截。v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0, +vs, 4-v1, 1v2 , 1（3,0）v4 , 1v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0, +vs, 4-v1, 1v2, 1（3,0）-v2, 1v4 , 1(5)调整。取，令，得新流,转(1)。v2Vsv1v4v3Vt（3,3）（5,1）（1,1）（2,2）（1,1）（5,3）（2,1）（4,3）0, +vs, 4-v1, 1-v2, 1（3,0）-v
8、2, 1v4, 1v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）调整v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）0 ,+vs, 3v2Vsv1v4v3Vt（3,3）（5,2）（1,0）（2,2）（1,1）（5,4）（2,1）（4,4）（3,0）0, +vs , 3此时标号无法进行，当前流为最大流，最大流量为5 ；最小截为(vs,v2), (v1,v3)，截量为：5有三个发电站v1,v2,v3，发电能力分别为15、10和 40兆瓦，经输电网可把电力送到8号地区
9、，电网能力如 图所示。求三个发电站输到该地区的最大电力。v2v1v3v4v5v6v7v8401530154510 151020v010 154010101515150 10 1010101525课堂练习例1、图中A、B、C、D、E、F分别表示陆地和岛屿， 表示桥梁及其编号。河两岸分别互为敌对的双方 部队占领，问至少应切断几座桥梁（具体指出编号）才能达 到阻止对方部队过河的目的。试用图论方法进行分析。ABDEFC实际应用分析：转化为一 个网络图，弧的 容量为两点间的 桥梁数。则问题为求最 小截。A BDEFC ABCDEF211111222222分析：转化为一 个网络图，弧的 容量为两点间的 桥
10、梁数。则问题为求最 小截。答案：最小截为AE、 CD、CFA BDEFC ABCDEF211111222222例2、有一批人从我国A城赴俄罗斯B城，可能的旅 行路线如图：边防队拟建立足够数量检查站以便使每辆汽车至少 必经过一个检查站，建立检查站的费用根据各路段条 件有所不同（如图数字所示），求最小费用解。aAAbcdefg4 682325738 4 3764（分析：最小截问题）例3、过纽约ALBANY的北-南高速公路，路况通过能 力如下图所示，图中弧上数字单位：千辆/小时。求（1）该路网能承受的北-南向最大流量；（2）若要扩充通过能力，应在那一组路段上扩充， 说明原因。 2143562 366241331进入Albany（北）离开Albany（南）课堂作业P207 7.12与7.13
