§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题 第7章 图与网络模型 §1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题
§4 最大流问题 最大流问题: 给了一个带收发点的网络,其每条弧的赋权称之为容量,在不超过每条弧的容量的前提下,求出从发点到收点的最大流量。
4.1 最大流的数学模型 例:某石油公司拥有一个管道网络,使用这个网络可以把石油从开采地运送到一些销售点。由于管道的直径的变化,他的各段管道(vi,vj)的流量cij也不一样,如下图所示。cij的单位为万加仑/小时。如果使用这个网络系统从开采地v1向销地v7运送石油,问每小时能运送多少加仑石油? v2 3 v5 5 2 2 6 2 v6 4 v3 v7 v1 6 3 1 2 v4
设弧(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 fijcij,(i=1,2,...,6;j=2,...,7) fij0,(i=1,2,...,6;j=2,...,7)
4.2 最大流问题网络图论的解法 对一条弧(vi,vj)的容量用一对数(cij,0)标在弧(vi,vj)上,cij表示从vi到vj容许通过的容量,0表示从vj到vi容许通过的容量。 cij cij vi vj vi vj cij cij cji vi vj vj vi cji
注意: 求最大流的基本算法 找出一条从发点到收点的路,在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路,则已求得最大流。 找出这条路上各条弧的最小的顺流的容量pf,通过这条路增加网络的流量pf。 在这条路上,减少每一条弧的顺流容量pf,同时增加这些弧的逆流容量pf,返回步骤①。 注意: 在步骤①中尽量选择包含弧数最少的路。
引例的Ford-Fulkerson标号算法:(贝尔曼-福特算法 ) 第一次迭代: 选择路为:v1v4 v7.弧(v4,v7)的顺流容量为2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 5 2 2 6 2 v6 4 v3 v7 v1 2 6 2 4 3 1 2 2 v4
选择路为:v1v2 v5 v7.弧(v2,v5)的顺流容量为c25=3,决定了pf=3,改进的网络流量如图所示: 第二次迭代: 选择路为:v1v2 v5 v7.弧(v2,v5)的顺流容量为c25=3,决定了pf=3,改进的网络流量如图所示: 3 v2 v5 2 3 3 5 2 3 3 2 6 2 v6 4 v3 v7 v1 2 2 5 4 3 1 2 v4
选择路为:v1v4 v6 v7.弧(v4,v6)的顺流容量为c46=1,决定了pf=1,改进的网络流量如图所示: 第三次迭代: 选择路为:v1v4 v6 v7.弧(v4,v6)的顺流容量为c46=1,决定了pf=1,改进的网络流量如图所示: v2 v5 3 2 3 2 2 3 3 2 v6 3 4 v3 1 v7 1 v1 5 2 6 4 3 3 1 2 3 v4
选择路为:v1v4 v3 v6 v7.弧(v3,v6)的顺流容量为c36=2,决定了pf=2,改进的网络流量如图所示: 第四次迭代: 选择路为:v1v4 v3 v6 v7.弧(v3,v6)的顺流容量为c36=2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 2 3 2 2 2 1 3 2 v6 3 4 v3 3 v7 2 v1 6 1 2 8 3 1 1 3 3 5 v4
选择路为:v1v2 v3 v5 v7.弧(v2,v3)的顺流容量为c23=2,决定了pf=2,改进的网络流量如图所示: 第五次迭代: 选择路为:v1v2 v3 v5 v7.弧(v2,v3)的顺流容量为c23=2,决定了pf=2,改进的网络流量如图所示: v2 v5 3 5 2 2 3 2 1 2 5 3 2 v6 3 2 1 v3 3 v7 v1 2 8 1 2 10 1 1 5 v4
最大流如图所示: v2 v5 3 2 2 5 5 v6 2 3 v3 v7 v1 10 1 2 2 5 v4