§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题

Presentation on theme: "§1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题"— Presentation transcript:

1 §1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题
第7章 图与网络模型 §1 图与网络的基本概念 §2 树图与最小生成树 §3 最短路问题 §4 最大流问题 §5 最小费用最大流问题

2 §4 最大流问题 最大流问题： 给了一个带收发点的网络，其每条弧的赋权称之为容量，在不超过每条弧的容量的前提下，求出从发点到收点的最大流量。

3 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

4 设弧(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)

5 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

6 注意： 求最大流的基本算法 找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于0。如果不存在这样的路，则已求得最大流。
找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 在这条路上，减少每一条弧的顺流容量pf，同时增加这些弧的逆流容量pf，返回步骤①。 注意： 在步骤①中尽量选择包含弧数最少的路。

7 引例的Ford-Fulkerson标号算法：(贝尔曼-福特算法 ) 第一次迭代：
选择路为：v1v4 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

8 选择路为：v1v2 v5 v7.弧(v2,v5)的顺流容量为c25=3，决定了pf=3，改进的网络流量如图所示：
第二次迭代： 选择路为：v1v2 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

9 选择路为：v1v4 v6 v7.弧(v4,v6)的顺流容量为c46=1，决定了pf=1，改进的网络流量如图所示：
第三次迭代： 选择路为：v1v4 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

10 选择路为：v1v4 v3 v6 v7.弧(v3,v6)的顺流容量为c36=2，决定了pf=2，改进的网络流量如图所示：
第四次迭代： 选择路为：v1v4 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

11 选择路为：v1v2 v3 v5 v7.弧(v2,v3)的顺流容量为c23=2，决定了pf=2，改进的网络流量如图所示：
第五次迭代： 选择路为：v1v2 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

12 最大流如图所示： v2 v5 3 2 2 5 5 v6 2 3 v3 v7 v1 10 1 2 2 5 v4