资源描述：
《数学模型3-2最大流问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、最大流问题•所谓最大流问题就是在一定的条件下，要求流过网络的物流、能量流或信息流等流量为最大的问题，在最大流问题中一般有如下约定：–网络有一个起点v和一个终点vst–网络是有向网络，即流有方向性。–在网络各条弧上都有一个权，表示允许流过的最大流量。若以ω表示由v到v的弧上允许流过ijij的最大流量，以x表示实际流过该弧的流量，ij则–网络中，除起点v和终点v之外的任何顶点，流st入量总和应该等于流出量的总和。最大流问题的数学模型v27v415114vsvt35910v6v35可行流•可行流：是指
2、所有弧上流量满足容量限制，所有中间点满足平衡条件的流；•零流是可行流。•从零流到最大流：Ford-Fulkerson方法。Ford-Fulkerson方法原理•依据最大流问题的要求，为网络分配一个可行流，可以取零流。•若这一可行流的流量就是最大流量，则问题已经解决；•若不是最大流量，则增加流量获得流量更大的可行流。Ford-Fulkerson方法流图求一个初始可行流是判断初始可行流是否最优结束不是求使目标得到改善的可行流Ford-Fulkerson方法关键•关键问题：如何增加流量？怎样判断是否需
3、要增加流量？•借助一个概念：伴随增量网络伴随增量网络•给定网络G=(V,E,W),W=(ω(e))和可行流Φ={φ(e)},对应的伴随增量网络G0=(V0,E0)如下定义，•顶点集合V0=V；•边集定义，任意e=[vv]∈E,ij–若该边非饱和，即φ(e)<ω(e)，增加正向边e0=[v,v],权ω0(e0)=ω(e)-φ(e)，称之为正向弧。ij–若该边非零流弧，即φ(e)≠0,增加逆向边e0=[v,v],权ω0(e0)=φ(e)，称之为逆向弧。jiv7,7v2415,1011,94,4vsv
4、t3,15,210,7逆向弧上正向弧上9,6的权表示v6,3v的权表示35已经分担可以增加v7v24的负荷。的负荷潜109力。54322vt21vs33763vv353流量增广链•伴随增量网络中若存在从v到v的路径，则st可以调整流量。•对应于原网络，一条从v到v的某个初等st链，称之为流量增广链，满足如下性质。–其上的正向弧均为非饱和弧。–其上的逆向弧均为非零流弧。–v到增广链上任一点也有增广链（v可达）;ss–增广链上任一点到v也有增广链（可达v）;ttFord-Fulkerson方法步骤•
5、算法的步骤：–①为网络分配初始流xij–②根据伴随增量网络寻求增广链，若不存在，则已最优,否则–③在增广链上调整流量，产生新的可行流。–重复②、③两步，直到最优。v7,7v2415,1011,94,4vsvt3,15,210,79,6v6,3v35v7v2410943252vt21vs33763vv353v7v2410943252vt21vs33763vsvv35333vt增大流量33vv35v7,7v2415,1011,94,4vsvt3,15,210,109,9v6,6v35v7,7v241
6、5,1011,94,4vsvt3,15,210,109,9v6,6v35v7v2410954322vv2ts1910vv365v7v2410954322vv2ts1910vv36553v142增大流量1vsvtv3v7,7v2415,1111,104,4vsvt3,05,310,109,9v6,6v35v7,7v2415,1111,104,4vsvt3,05,310,109,9v6,6v35v7v24111044231vv3ts910vv365算法讨论•算法只对整数容量适用。•最大流解不唯一。如
7、下图v2vv7,742v47,715,1111,1015,1111,11vs4,45,3vvs4,43,0t5,4vt3,09,910,109,910,9v36,6v5v36,5v5FF算法理论依据•借助于一个概念：切割。•给定某个可行流φ={φ(e=[v,v])
8、e∈ijiE(G)}，切割定义为：(P,Q),PUQ=V(G),v∈P,v∈Q.st集合流量与容量•给定集合(P,Q)，仍用(P,Q)表示起点在P中，终点在Q中的有向边的集合。定义集合P与Q之间的流和容量如下流量与切割关系•对任一可行
9、流φ={φ(e=[v,v]
10、e∈E(G)}和iji分割(P,Q)，PUQ=V(G)，v∈P，v∈stQ。其流量是P到Q的流与Q到P的流之差，即v7,7v2415,1011,94,4vsvt3,1将集合P中节点的5,29,610,7流(包括流进和流v36,3v5出的)相加，即可证明公式。流量公式说明•对P中所有点对流量定义公式求和，可以得到流量公式。•物理意义：从源流到汇的量通过P与Q的联系流过。净流量为从P流过Q的总量与Q流过P的总量之差。流量公式说明•流量公式意义：网络流量以分割的容量为上界。
