运筹学课件4.7-最小费用流问题

1、第五节 最小费用流问题,什么是最小费用流问题？ 求解最小费用流的赋权图法 求解最小费用流的复合标号法,一、什么是最小费用流,给定网络N=(V,A,c,b)和经过网络的流量v，求流在网络上的最佳分布，使总费用最小。,二、求解最小费用流的赋权图法,增广链费用，最小费用增广链。 对于最小费用可行流，沿最小费用增广链调整流，可使流增加，并保持流费用最小。 给定初始最小费用可行流，求最小费用增广链，若存在，则沿该增广链调整网络流，直到达到给定的网络流或不存在增广链为止，后一种情况为最小费用最大流。 若给定网络流超过最大流，则不可能实现。,如何求最小费用增广链？,生成最小费用可行流的剩余网络： 将饱和弧反

2、向 将非饱和非零流弧加一反向弧 零流弧不变 所有正向弧的权为该弧的费用，反向弧的权为该弧费用的相反数 剩余网络又叫长度网络，本教材叫做赋权图。 最小费用增广链对应剩余网络的最短路,最小费用流的实例,第一次剩余网络最短路,第一次调整网络流,第二次剩余网络最短路,第二次调整网络流,第三次剩余网络的最短路,第三次调整网络流,剩余网络已不存在最短路,已获最小费用最大流,最小费用最大流 若规定网络流为7，则第二次调整量应为2，而不是3。见图。 最小费用与网络流的关系是凸的，即随着流的增加，单位流的费用在增加。请见下页的图。,三、求解最小费用流的复合标号法,将求最短路的标号法和求最大流的标号法相结合，即在

3、求增广链的标号后加上一个距离标号，成为一组三标号，距离标号应采用修正标号法。并采用T标号和P标号的记法。,三、求解最小费用流的复合标号法,(1)类似于求解最大流的标号法 每一个顶点的标号包括三个部分： 第一个标号表明流的源头，称为流标号，它表示该标号是从前面哪一个顶点过来的； 第二标号表明到该顶点为止的增广链可能增加流量的大小，称为增量限制标号； 第三个标号是沿此增广链到该顶点的总费用，称为费用标号。,三、求解最小费用流的复合标号法,(2)类似于求解最短路的标号法 每一个顶点有两种标号： T标号，用T(v)表示； P标号，用P(v)表示。 由T标号变成P标号的原则也同求最短路一样，要比较T标号

4、中第三个标号（即费用标号）的大小。,三、求解最小费用流的复合标号法,(3)进行第一次迭代时，网络中各弧的流量为零。 假定网络中各弧的费用均为正值，则求最短路可以采用Dijkstra标号法。 此后的迭代中，由于构成增广链的弧可能是负费用值，因此要采用Ford算法。,三、求解最小费用流的复合标号法,修正如下： 标号过程中，永久标号和临时标号一样是可以改变的。对任一顶点而言，它有可能反复变成T标号和P标号，顶点每次变成P标号，标号过程都要从该顶点重新开始。 所有顶点变为P标号，算法停止。,三、求解最小费用流的复合标号法,正向弧是非饱和弧：,反向弧是非零流弧：,三、求解最小费用流的复合标号法,下面以前例为例来说明符合标号的应用。,第一次迭代,第二次迭代,=P,第三次迭代,最后结果,提示思考,最短路问题、最大流问题可以看作最小费用流的特殊情况，请分析如何将最小费用流问题化成最短路问题和最大流问题？ 运输问题和指派问题可