第三节最大流与最小费用流

《第三节最大流与最小费用流》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三节最大流与最小费用流一、最大流问题及其求解方法（一）最大流问题最大流问题——设有向网络N（V，A），在发点Vs有一批货，要通过网络上的弧运输到收点Vt去，受运输条件限制，每条弧aij在单位时间内通过的车辆数不能超过cij辆，分析：如何组织运输才能使从Vs到Vt在单位时间内通过的车辆达到最多？上面描述的这类问题，称为最大流问题。最大流问题广泛地应用在交通运输、供水、油管供油、邮电通讯，也可以用在生产安排，管理优化等实际问题上。例：如图10.3.1中，有一批物资需要用汽车尽快从发点①运到收点⑦，弧（i，j）上

2、所标的数字表示该条道路在单位时间内最多能通过的车辆数（单位：百辆），问如何调运，才能使单位时间里有最多的车辆从①调到⑦。425136756385577113223图10.3.1┍┑线性规划方法┕┙点①出发的车辆数应该与点⑦到达的车辆数相同，除①和⑦以外的各中间点，进的车辆数应该与离去的车辆数应该相同。xij是通过弧(i，j)的车辆数。（10.3.1）（10.3.4）（10.3.5）（10.3.6）（10.3.2）（10.3.3）对所有弧（i，j），应满足约束满足（10.3.1）～（10.3.7）的解

3、称为从①到⑦的一个可行流，我们的目的：在所有可行流中求出一个方案，使得这个可行流得到的f最大。若从收点到发点连接一条假想弧(7，1)，设它的容量c71=∞，那么对点①：对点⑦：最大流问题的目标为┍┑线性规划方法┕┙（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

4、.13）（二）求最大流的方法：弧标号法尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法——弧标号法，求解上述最大流问题。①为了便于弧标号法的计算，首先需要将最大流问题（譬如图10.3.1）重新改画成为图10.3.2的形式。图10.3.22416357st650230081023730071000055在图10.3.2中，每条弧上标有两个数字，其中，靠近点i的是，靠近点j的是。如①②表示从①到②的最大通过量是5（百辆），从②到①的最大通过量是

5、0；②③表示从②到③和从③到②都可以通过2（百辆）；等等。图10.3.22416357st650230081023730071000055②求最大流的基本步骤：弧标号法求最大流的过程，就是对图10.3.2反复地进行修改的过程，其计算步骤如下：步骤1.从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。步骤2.在选定的路上，找到最小的容许量cij定为P。步骤3.对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为ci

6、j-P，对于与路反向的弧，将cij修改为cij+P。修改完毕后再转入步骤1。步骤4.用原图中各条弧上起点与终点数值减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。第一次修改：（1）从发点s到收点t找一条路，使得这条路上的所有弧前面的约束量。从图10.3.2中可以看出，显然，①—③—⑥—⑦就是满足这样的条件的一条路。下面，我们用弧标号法求解图10.3.2中的最大流。（2）在路①—③—⑥—⑦中,,,,所以取。（3）在路①—③—⑥—⑦中，修改每一条弧的

7、容量：通过第1次修改，得到图10.3.3。2416357st050230081623130611600055图10.3.3返回步骤（1），进行第2次修改。第二次修改：选定①—②—⑤—⑦，在这条路中，由于，所以，将改为2，改为0，改为5，、、改为3。修改后的图变为图10.3.4。2416357st023203051623133611600055图10.3.4返回步骤（1），继续做第3次修改。第三次修改：取①—②—③—⑤—⑦，在这条，由于，所以将改为0，改为5，改为0，改为4，改为1，改为2，改为3，改为5。修改

8、后的图变为图10.3.5。2416357st005003231641135611600055图10.3.5返回步骤（1），继续做第4次修改。第四次修改：选定①—④—⑥—⑦，在这条路中，由于P=c67=1，所以将c14改为4,c41改为1,c46改为4,c64改为1,c67改为0，c76改为7。修改后的图为变为图10.3.6。2416357st005003231641135701611044图10.3