第章 图与网络模型.pptVIP

§4　最大流问题 二、最大流问题网络图论的解法 对网络上弧的容量的表示作改进。为省去弧的方向，如下图: (a)和 (b)、(c)和(d)的意义相同。 用以上方法对例6的图的容量标号作改进，得下图 * vi vj vi vj cij 0 （a） （b） cij cij vi vj （cji） （c） vi vj cij cji （d） 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 0 0 0 §4　最大流问题 求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 （3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 用此方法对例6求解： 第一次迭代：选择路为v1 v4 v7 。弧（ v4 , v7 ）的顺流容量为2， 决定了pf=2，改进的网络流量图如下图： * 6 3 5 2 2 2 4 1 2 6 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 0 0 0 4 2 0 2 §4　最大流问题 第二次迭代：选择路为v1 v2 v5 v7 。弧 （ v2 , v5 ）的顺流容量为3，决定了pf=3，改进的网 络流量图如下图： * 6 3 5 2 2 2 4 1 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 0 0 4 2 0 2 2 0 3 3 3 0 3 第三次迭代：选择路为v1 v4 v6 v7 。弧 （ v4 , v6 ）的顺流容量为1，决定了pf=1，改进的网 络流量图如下图： * 2 2 2 3 1 3 v1 v2 v5 v7 v4 v3 v6 0 0 0 0 0 0 4 2 0 2 2 0 3 3 3 3 3 0 1 §4　最大流问题 第四次迭代：选择路为v1 v4 v3 v6 v7 。弧 （ v3 , v6 ）的顺流容量为2，决定了pf=2，改进的网 络流量图如下图： * 2 2 2 3 3 v1 v2 v5 v7 v4 v3 v6 1 1 0 0 0 2 0 3 2 0 3 3 3 5 0 3 1 2 0 0 2 1 3 3 第五次迭代：选择路为v1 v2 v3 v5 v7 。弧 （ v2 , v3 ）的顺流容量为2，决定了pf=2，改进的网 络流量图如下图： * 2 2 v1 v2 v5 v7 v4 v3 v6 1 0 1 2 0 2 0 3 3 3 5 0 1 2 0 2 1 3 3 1 5 0 0 2 0 2 0 5 §4　最大流问题 经过第五次迭代后在图中已经找不到从发点到收点的一条路，路上的每一条弧顺流容量都大于零，运算停止。得到最大流量为10。 最大流量图如下图： * 2 2 v1 v2 v5 v7 v4 v3 v6 1 2 3 5 2 2 3 5 5 “管理运筹学软件”中还有专门的子程序用于解决最大流问题。 §5　最小费用最大流问题 最小费用最大流问题：给了一个带收发点的网络，对每一条弧 （vi,vj），除了给出容量cij外，还给出了这条弧的单位流量的费用bij，要 求一个最大流F，并使得总运送费用最小。 一、最小费用最大流的数学模型 例7 由于输油管道的长短不一，所以在例6中每段管道（ vi,vj ）除 了有不同的流量限制cij外，还有不同的单位流量的费用bij ，cij的单位为万 加仑/小时， bij的单位为百元/万加仑。如下图所示。从采地 v1向销地 v7运 送石油，怎样运送才能运送最多的石油并使得总的运送费用最小？求出最 大流量和最小费用。 * (6,6) (3,4) (5,7) (2,5) (2,4) （2,3） (4,4) (1,3) (2,8) （3,2） v1 v2 v5 v7 v4 v3 v6 (6,3) §5　最小费用最大流问题 * 这个最小费用最大流问题也是一个线性规划的问题。 解：我们用线性规划来求