最大流与最小费用流.pptVIP

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

性

规

划

方

法┕┙点①出发的车辆数应该与点⑦到达的车辆数相同，除①和⑦以外的各中间点，进的车辆数应该与离去的车辆数应该相同。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=∞，那么对点①：对点⑦：最大流问题的目标为1┍┑线

性

规

划

方

法┕┙2（10.3.7）3（10.3.8）4（10.3.9）5（10.3.10）6所以，对于发点为Vs，收点为Vt的网络N（V，U），当增加一条约束为cts=∞的假想弧（t，s）后，最大流问题就成为：容量约束平衡条件目标函数┍┑线

性

规

划

方

法┕┙（10.3.11）12345（10.3.13）（10.3.12）求最大流的方法：弧标号法尽管最大流问题可以用线性规划模型描述，但是我们一般并不用求解线性规划的方法求最大流，而是用一种更为简便明了的图上作业法——弧标号法，求解上述最大流问题。为了便于弧标号法的计算，首先需要将最大流问题（譬如图10.3.1）重新改画成为图10.3.2的形式。在图10.3.2中，每条弧上标有两个数字，其中，靠近点i的是，靠近点j的是。如①②表示从①到②的最大通过量是5（百辆），从②到①的最大通过量是0；②③表示从②到③和从③到②都可以通过2（百辆）；等等。求最大流的基本步骤：标号法求最大流的过程，就是对图10.3.2反复地进行修改的过程，其计算步骤如下：从发点s到收点t选定一条路，使这条路通过的所有弧Vij的前面约束量cij都大于0，如果找不到这样的路，说明已经求得最大流，转步骤4。在选定的路上，找到最小的容许量cij定为P。010203对选定的路上每条弧的容量作以下修改，对于与路同向的弧，将cij修改为cij-P，对于与路反向的弧，将cij修改为cij+P。修改完毕后再转入步骤1。用原图中各条弧上起点与终点数值减去修改后的图中对应点的数值，得到正负号相反的两个数，并将从正到负的方向用箭头表示。这样，就得到一个最大流量图。从发点s到收点t找一条路，使得这条路上的所有弧前面的约束量。从图10.3.2中可以看出，显然，①—③—⑥—⑦就是满足这样的条件的一条路。下面，我们用弧标号法求解图10.3.2中的最大流。在路①—③—⑥—⑦中,,,，所以取。第1次修改：在路①—③—⑥—⑦中，修改每一条弧的容量返回步骤①，进行第2次修改。通过第1次修改，得到图。第2次修改：选定①—②—⑤—⑦，在这条路中，由于，所以，将改为2，改为0，改为5，、、改为3。修改后的图变为图。返回步骤①继续做第3次修改。0102第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次修改：