最小费用最大流问题的解决方法

最小费用最大流问题的解决方法

解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。
然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。
由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。
在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图 1 网络G 是具有最小 费用的流，边旁参数为c(e),f(e),w(e），而图 2 即为该网络流 的增流网络G′。增流网络的顶点和原网络相同。按以下原则建 立增流网络的边：若G中边（u，v）流量未饱，即f(u,v) < e(u,v），则G ' 中建边（u,v），赋权w ' (u,v)=w(u,v）；若G中边（u,v）已有流量，即f(u,v）〉0，则G′中建边（v,u），赋权w′（v,u) =-w(u,v）。建立增流网络后，即可在此网络上求源点至汇点的最短路径，以此决定增流路径，然后在原网络上循此路径增流。这里，运用的仍然是最大流算法的增流原理，唯必须选定最小费用的增流链增流。
计算中有一个问题需要解决。这就是增流网络G ′中有负权边，因而不能直接应用标号法来寻找x至y的最短路径，采用其它计算有负权边的网络最短路径的方法来寻找x至y的最短路径，将 大大降低计算效率。为了仍然采用标号法计算最短路径，在每次建立增流网络求得最短路径后，可将网络G的权w(e）做一次修正，使再建的增流网络不会出现负权边，并保证最短路径不至于因此而改变。下面介绍这种修改方法。当流值为零，第一次建增流网络求最短路径时，因无负权边，当然可以采用标号法进行计算。为了使以后建立增流网络时不出现负权边，采取的办法是将 G中有流边（f(e)>0）的权w(e）修正为0。为此， 每次在增流网络上求得最短路径后，以下式计算G中新的边权w(u,v）：
w(u,v)=L(u)-L(v)+w(u,v) (*)
式中 L(u),L(v) -- 计算G′的x至y最短路径时u和v的标号值。第一次求最短径时如果（u,v）是增流路径上的边， 则据最短 路径算法一定有 L(v)=L(u)+w ' (u,v)=L(u)+w(u,v）， 代入（*）式必有
w″（u,v)=0。
如果（u,v）不是增流路径上的边，则一定有：
L(v）≤L(u)+w(u,v）， 代入（*）式则有 w ”(u,v）≥0。
可见第一次修正w(e）后，对任一边，皆有w(e）≥0， 且有流 的边（增流链上的边），一定有w(e)=0。以后每次迭代计算，若 f(u,v)>0，增流网络需建立（v,u）边，边权数w ' (v,u)=-w(u,v) =0，即不会再出现负权边。 此外，每次迭代计算用（*）式修正一切w(e）， 不难证明对每一条x至y的路径而言，其路径长度都同样增加L(x)-L(y）。因此，x至y的最短路径不会因对w(e）的修正而发生变化。
【计算步骤】
⒈ 对网络G=[V,E,C,W]，给出流值为零的初始流。
⒉ 作伴随这个流的增流网络G′=[V′，E′，W′]。G′的顶点同G：V′=V。若G中f(u,v)0，则G′中建边（v,u），w′（v,u)=-w(u,v）。
⒊ 若G′不存在x至y的路径，则G的流即为最小费用最大流， 停止计算；否则用标号法找出x至y的最短路径P。
⒋ 根据P，在G上增流：对P的每条边（u,v），若G存在（u,v），则（u,v）增流；若G存在（v,u），则（v,u）减流。增（减）流后，应保证对任一边有c(e）≥ f(e）≥0。
⒌ 根据计算最短路径时的各顶点的标号值L(v），按下式修 改G一切边的权数w(e):
L(u)-L(v)+w(e）→w(e）。
⒍ 将新流视为初始流，转2。