《最大流与最小费用流.ppt》由会员分享，可在线阅读，更多相关《最大流与最小费用流.ppt（36页珍藏版）》请在三一办公上搜索。
1、第3节 最大流与最小费用流,最大流问题及其求解方法最小费用流及其求解方法,一、最大流问题及其求解方法,（一）最大流问题,最大流问题 设有向网络N（V，A），在发点Vs 有一批货，要通过网络上的弧运输到收点Vt 去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij 辆，分析：如何组织运输才能使从Vs到Vt 在单位时间内通过的车辆达到最多？上面描述的这类问题，称为最大流问题。,最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。,例：如图10.3.1中，有一批物资需要用汽车尽快从发点运到收点，弧（i，j）上所标的数字表示该条道路在单
2、位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从调到。,线性规划方法,点出发的车辆数应该与点到达的车辆数相同，除和以外的各中间点，进的车辆数应该与离去的车辆数应该相同。,xij 是通过弧(i，j)的车辆数。,（10.3.1）,（10.3.4）,（10.3.5）,（10.3.6）,（10.3.2）,（10.3.3）,对所有弧（i，j），应满足约束 满足（）（）的解称为从到的一个可行流。我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的 f 最大。若从收点到发点连接一条假想弧(7，1)，设它的容量c71=，那么 对点：对点：最大流问题的目标为,线性规划
3、方法,（10.3.7）,（10.3.8）,（10.3.9）,（10.3.10）,所以，对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=的假想弧（t，s）后，最大流问题就成为：容量约束 平衡条件 目标函数,线性规划方法,（10.3.11）,（10.3.12）,（10.3.13）,（二）求最大流的方法：弧标号法,尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法弧标号法，求解上述最大流问题。,(1)为了便于弧标号法的计算，首先需要将最大流问题（譬如图10.3.1）重新改画成为图10.3.2的形式。,在图10.
4、3.2中，每条弧 上标有两个数字，其中，靠近点 i 的是，靠近点 j 的是。如 表示从到的最大通过量是5（百辆），从到的最大通过量是0；表示从到和从到都可以通过2（百辆）；等等。,(2)求最大流的基本步骤：标号法求最大流的过程，就是对图10.3.2反复地进行修改的过程，其计算步骤如下：步骤1.从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。步骤2.在选定的路上，找到最小的容许量cij定为P。,步骤3.对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-P，对于与路反向的弧，将cij修改为
5、cij+P。修改完毕后再转入步骤1。步骤4.用原图中各条弧上起点与终点数值减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。,第1次修改：从发点s到收点t找一条路，使得这条路上的所有弧前面的约束量。从图10.3.2中可以看出，显然，就是满足这样的条件的一条路。,下面，我们用弧标号法求解图10.3.2中的最大流。,在路中,，所以取。,在路中，修改每一条弧的容量,通过第1次修改，得到图。,返回步骤，进行第2次修改。,第2次修改：选定，在这条路中，由于，所以，将 改为2，改为0，改为5，、改为3。修改后的图变为图。,返回步骤继续做第3次修
6、改。,第3次修改：取，在这条路中，由于 所以将 改为0，改为5，改为0，改为4，改为1，改为2，改为3,c75改为5。修改后的图变为图。,返回步骤，继续做第4次修改。,，,第4次修改：选定，在这条路中，由于 P=c67=1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76 改为7。修改后的图为变为图10.3.6。,返回步骤，继续做第5次修改。,第5次修改：选定,在这条路中，由于 P=c65=1，所以将c14和c46均改为3，c65改为0，c57改为2，c41、c64、c56均改为2，c75改为6。修改后的图变为图10.3.7。,需要注意的是，由图10.3.7中
7、可以看出，弧 本来在图10.3.2中是无容量可通过的，但经过几次修改，由 变成，即此时从到还可通过1（百辆），而从到，可以通过6（百辆）的容量，这说明，修改过程实际上是把计划中从到的通过车辆数减少了。,第6次修改：,取，在这条路中，由于P=c35=1，所以将 c14和 c46均改为2，c63改为5,c35改为0，c57改为1，c41、c64、c53均改为3，c36改为2，c75改为7。修改后的图变为图10.3.8。,在图10.3.8中，从发点到收点，再也不存在连通的起点容量都大于零的弧了，所以图10.3.8为最大流图。,转入步骤，用原图中各条弧上发点与收点数值减去修改后的图上各点的数值，将得到
8、正负号相反的两个数，将这个数标在弧上，并将从正到负的方向用箭头表示,这样就得到最大流量图。例如原来弧 是，现在是，相减为5，那边为正，我们就记作。这样，就得到图10.3.9，即最大流量图。依这样的调度方式，可以从发点s调运14（百辆）汽车到收点t。,图10.3.9 最大流量图,(3)最大流算法的讨论：,从上面的标号计算过程可以看出，一个图成为最大流图的条件是从发点到收点的每一条路上总存在某个起点容量为零的弧，我们称这样的路为饱和路；如果从s到t有一条路，它上面每条路的起点容量都大于零，则称为非饱和路。由此可以得到一个结论：一个图是最大流图的充分必要条件是不存在从s到t的非饱和路。,将网络中的点
9、分成两组，一组包括发点，称为发集，一组包括收点t，称为收集，连接 到 的所有弧称为截集，截集中各弧在 旁的容量和称为截集的容量。,例如，在图10.3.2中，,我们取，则截集为(2,5),(3,5),(1,4),(3,6),(3,4)，它的容量为3+3+5+7+3=21；若在图中，取，则截集为(2,5),(3,5),(6,5),(6,7)，其容量为0+1+1+0=2等等。在将网络分成发集与收集的所有分法中，容量最小的截集称为最小截集。可以证明：,设f是网络N的一个可行流，那么，网络N的最小截集的容量（）等于网络最大流 与f 的差，即,（10.3.14）,式中：称为可行流 f 的余量。,显然，当=
10、0时，就得到了最大流。因此，进一步可以得到：在网络N中，设f是从发点到收点的一个可行流，那么，f是最大流的充分必要条件是网络N的最小截集的容量为零。从 到 的最大流的流量等于分离 与 的最小截集的容量。,这表明，从 到，最小截集的弧是网络中的“卡脖子”线路，要获得最大流量，必须在最小截集的各弧上达到满载。,最大流fmax的大小是确定的，但最大流的路线可以不唯一。在上例中，如果从不同的路开始来修改图，也可能得到另外一个最大流图（图10.3.10）。,对于不同的最大流图（譬如图10.3.9与图10.3.10），它们必有以下性质：对于网络的最小截集上的弧，它们的流量是相同的。对于由最小截集分开的V1
11、和V2内，它们的流量可能不同，但都是相差一个或几个不饱和回路上的量，如图10.3.9与图10.3.10，相差的是回路上一个值为2的流量。,二、最小费用流及其求解方法,（一）最小费用流问题,如果在考虑网络上流量的同时，还要使得所安排流量的费用或者代价达到最小，就是所谓的最小费用流问题。,在上例中，如果单位车辆数通过某一条弧要付出一定的代价，其代价如图。,现在要从发点调动若干车辆到收点去，约束条件为图10.3.1，代价条件为图10.3.11，要使所花费的代价达到最小，用公式表示，就是要在（10.3.1）（10.3.7）式的约束条件下，找到一个可行流f 的流量,（10.3.15）,使其代价最小，即,
12、（10.3.16）,式中：指单位车辆数通过弧 的代价。,图10.3.11 代价条件,图10.3.1 约束条件,（二）求解最小费用流问题,求最小费用流的步骤和求最大流的步骤几乎完全一致，只是在步骤（1）中，选一条非饱和路时，应选代价和最小的路，即最短路。例如，在图10.3.11中，从到的最短路是，代价为7，在这条最短非饱和路上取 后，变成容量为零，在下一次选择最短路时应将视为断路来选取最短非饱和路。另外，选取路后，的弧成为容量大于零的弧，可分别标上它们的代价值为-3，-3，-1，是，的相反数。,在求最小费用流过程中，可以依上述方法不断重复求最大流的步骤来进行，当流量达到 时就可以停止，这时求出的是最小费用流。当然，如果，就需要将步骤进行到最后，直到不存在非饱和路存在为止。,按照这种方法，可以将约束条件由图10.3.1所示，代价函数为图10.3.11所示的最小费用流问题的求解算法，可以用表10.3.1表示，这里设。,表10.3.1 最小费用流的求解过程,将各条路的流量相加，就得到最小费用流，如图10.3.12所示。,图10.3.12 最小费用流,这个最小费用流的总代价为,
