图与网络模型gai.ppt

I={v1,v2,v3},J={v4,v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v4),(v1,v5),(v1,v6),(v2,v4),(v2,v5),(v2,v6),(v3,v4),(v3,v5),(v3,v6)}并有s34=l3+c34=22+17=39,s35=l3+c35=22+23=45,s36=l3+c36=22+31=53, min(s14,s15,s16,s24,s25,s26,s34,s35,s36)=s14=30.给弧(v1,v4)的终点v4标以(30,1). I={v1,v2,v3,v4},J={v5,v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v5),(v1,v6),(v2,v5),(v2,v6),(v3,v5),(v3,v6),(v4,v5),(v4,v6)}并有s45=l4+c45=30+17=47,s46=l4+c46=30+23=53, min(s15,s16,s25,s26,s35,s36,s45,s46)=s15=41.给弧(v1,v5)的终点v5标以(41,1). I={v1,v2,v3,v4,v5},J={v6}.弧集{(vi,vj)|vi∈I,vj∈J}={(v1,v6),(v2,v6),(v3,v6),(v4,v6),(v5,v6)}并有s56=l5+c56=41+18=59, min(s16,s26,s36,s46,s56)=s36=s46=53.给弧(v3,v6)和(v4,v6)的终点v6标以(53,3)和(53,4). v1 v2 v3 v4 v5 v6 16 18 17 17 16 23 31 23 22 30 41 59 41 30 22 (0,s) (16,1) (30,1) (41,1) (53,4) (53,3) (22,1) §4 最大流问题 最大流问题： 给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。 4.1 最大流的数学模型 例：某石油公司拥有一个管道网络，使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化，他的各段管道(vi,vj)的流量cij也不一样，如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油，问每小时能运送多少加仑石油？ v1 v6 v3 v4 v5 v2 v7 6 1 2 2 3 2 3 6 5 4 2 设弧(vi,vj)上的流量为fij，网络上的总的流量为F，则上述问题的线性规划模型为： 目标函数：max F=f12+f14 约束条件：f12=f23+f25 f14=f43+f46+f47 f23+f43=f35+f36 f25+f35=f57 f36+f46=f67 f57+f67+f47=f12+f14 fij?cij,(i=1,2,...,6;j=2,...,7) fij?0,(i=1,2,...,6;j=2,...,7) 4.2 最大流问题网络图论的解法 对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上，cij表示从vi到vj容许通过的容量，0表示从vj到vi容许通过的容量。 vi vj vi vj vi vj cij vi vj 0 cji cij cij cji cij 求最大流的基本算法 找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路，则已求得最大流。 找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤①。 注意： 在步骤①中尽量选择包含弧数最少的路。 引例的Ford-Fulkerson标号算法：(贝尔曼-福特算法 ) 第一次迭代： 选择路为：v1?v4 ?v7.弧(v4,v7)的顺流容量为2，决定了pf=2，改进的网络流量如图所示： v1 v6 v3 v4 v5 v7 6 1 2 2 3 2 3 6 5 4 2 2 0 0 0 0 0 0 0 0 0 0 4 2 0 2 0 v2 第二次迭代： 选择路为：v1?v2 ?v5 ?v7.弧(v2,v5)的顺流容量为c25=3，决定了pf=3，