下面先是汉语-----
【MCMF问题及数学模型】
在介绍最大流问题时，我们列举了一个最大物资输送流问题。如果这个问题的已知条件还包括每条边运送单位物资的费用，那么怎样运送，才能得到最大运输量，并且输送费用最少？这便是所谓最小费用最大流问题。
在最大流的有关定义的基础上，若每条有向边除权数c(e)（表示边容量）外还有另外一个权数w(e)（表示单位流所需费用），并且已求得该网络的最大流值为F， 那么最小费用最大流问题，显然可用以下线性规划模型加以描述：
Min ∑ w(e)f(e)
e∈E
满足 0≤f(e)≤c(e) ，对一切e∈E
f+(v)=f-(v) ，对一切v∈V
f+(x)=F （最大流约束）
（或f-(y)=F )
【算法思路】
解决最小费用最大流问题，一般有两条途径。一条途径是先用最大流算法算出最大流，然后根据边费用，检查是否有可能在流量平衡的前提下通过调整边流量，使总费用得以减少？只要有这个可能，就进行这样的调整。调整后，得到一个新的最大流。
然后，在这个新流的基础上继续检查，调整。这样迭代下去，直至无调整可能，便得到最小费用最大流。这一思路的特点是保持问题的可行性（始终保持最大流），向最优推进。另一条解决途径和前面介绍的最大流算法思路相类似，一般首先给出零流作为初始流。这个流的费用为零，当然是最小费用的。然后寻找一条源点至汇点的增流链，但要求这条增流链必须是所有增流链中费用最小的一条。如果能找出增流链，则在增流链上增流，得出新流。将这个流做为初始流看待，继续寻找增流链增流。这样迭代下去，直至找不出增流链，这时的流即为最小费用最大流。这一算法思路的特点是保持解的最优性（每次得到的新流都是费用最小的流），而逐渐向可行解靠近（直至最大流时才是一个可行解）。
由于第二种算法和已介绍的最大流算法接近，且算法中寻找最小费用增流链，可以转化为一个寻求源点至汇点的最短路径问题，所以这里介绍这一算法。
在这一算法中，为了寻求最小费用的增流链，对每一当前流，需建立伴随这一网络流的增流网络。例如图 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)的修正而发生变化。
【计算步骤】
1. 对网络G=[V,E,C,W]，给出流值为零的初始流。
2. 作伴随这个流的增流网络G′=[V′,E′,W′]。
G′的顶点同G：V′=V。
若G中f(u,v)＜c(u,v)，则G′中建边(u,v)，w(u,v)=w(u,v)。
若G中f(u,v)＞0，则G′中建边(v,u)，w′(v,u)=-w(u,v)。
3. 若G′不存在x至y的路径，则G的流即为最小费用最大流，
停止计算；否则用标号法找出x至y的最短路径P。
4. 根据P，在G上增流： 对P的每条边(u,v)，若G存在(u,v)，则(u,v)增流；若G存在(v,u)，则(v,u)减流。增（减）流后，应保证对任一边有c(e)≥ f(e)≥0。
5. 根据计算最短路径时的各顶点的标号值L(v)，按下式修 改G一切边的权数w(e):
L(u)-L(v)+w(e)→w(e)。
6. 将新流视为初始流，转2。
-----------------
======================
下面是英文-----
【MCMF problems and the mathematical model】
Maximum flow problem in the introduction, we listed one of the largest flow of goods delivery. If this issue also includes the known conditions of delivery of each unit while the cost of goods, then how to transport, to get the most traffic, and transportation costs to a minimum? This is the so-called maximum flow problem minimum cost.
The maximum flow based on the definition, if each side of a first-priority claim to the number of c (e) (that the edge capacity) but also have another weights w (e) (that the unit cost flow), and has been seeking a maximum flow of the network value of F, then the minimum cost maximum flow problem, it is clear the following linear programming model can be used to describe:
Min ∑ w (e) f (e)
e ∈ E
Satisfy 0 ≤ f (e) ≤ c (e), for all e ∈ E
f + (v) = f-(v), for all v ∈ V
f + (x) = F (maximum flow constraints)
(Or f-(y) = F)
】 【Algorithm ideas
Solve the minimum cost maximum flow problem, there are two general ways. Way is to use a maximum flow algorithm to calculate the maximum flow, and then based on the cost side, check whether it is possible to balance the flow by adjusting the flow side, so that to reduce the total cost? As long as there is a possibility, on such adjustments. After adjusting for a new maximum flow.
Then, on the basis of the new flow to continue to check and adjust. This iteration continues until no adjustment may be, they will have the minimum cost maximum flow. The characteristics of this line of thought is to maintain the feasibility of the problem (always maintain maximum flow), to promote optimal. Solution to another and in front of the maximum flow algorithm, introduced a similar line of thought, first of all, given the general flow as the initial flow of zero. The cost of the flow to zero, of course, is the smallest cost. And then find a source to the Meeting Point by flow chain, but by the requirements of this chain must be a stream flow of all chain costs by a minimum. If we can find out by flow chain, the chain in the flow by increasing flow, a new flow. The flow will be treated as the initial flow, continue to search for links by increasing stream flow. This iteration continues, until found by flow chain, then the flow is the minimum cost maximum flow. Idea of the characteristics of this algorithm is to maintain the optimal solution of (each of the new fees are the smallest stream flow), but gradually close to the feasible solution (up to maximum flow is a feasible solution when).
As a result of the second algorithm and has introduced close to the maximum flow algorithm and the algorithm by finding the minimum cost flow chain, can be turned into a source to find the shortest path to the Meeting Point, so this algorithm here.
In this algorithm, in order to seek to increase the minimum cost flow chain, the current flow of each, accompanied by the need to establish a network flow by the flow network. For example, Figure 1 is a network G of minimum cost flow, next to parameters c (e), f (e), w (e), and Figure 2 is the network flow by the flow network G '. By the peak-flow network and the same as the original network. By the following principles in accordance with the establishment of the network edge flow: If G in the edge (u, v) is not enough traffic, that is, f (u, v)
Calculation, there is a need to address the problem. This is the stream network by G 'the right to have a negative side, thus labeling law can not be directly applied to find x to y of the shortest path, using the right of other negative side computing network approach to the shortest path x to y to find the shortest path, will greatly reduce the computational efficiency. In order to still use the labeling method to calculate the shortest path, each flow set up by the network to achieve the shortest path, the network G can be the right of w (e) an amendment to do so by the stream to build the network will not be a negative right side, and guarantee the shortest path does not change. This modified method described below.
When the flow value is zero, the first built by the shortest path for flow network, the result of non-negative right side, of course, can be used to calculate labeling law. In order to increase flow network after the establishment of a negative time is not right side of the approach taken is to have stream G edge (f (e)> 0) the right to w (e) amendment to 0. To this end, each time a flow network obtained by the shortest path, the following computing G in the right side of the new w "(u, v):
w "(u, v) = L (u)-L (v) + w (u, v) (*)
Where L (u), L (v) - calculation of G 'of the shortest path x to y when u and v the value of the label. For the first time if the shortest path (u, v) is the flow path by the edge, then, according to the shortest path algorithm must have L (v) = L (u) + w '(u, v) = L (u) + w (u, v), substituting into (*) type must
w "(u, v) = 0.
If (u, v) rather than by the side of flow path, it must have:
L (v) ≤ L (u) + w (u, v),
Into the (*)-type, there w (u, v) ≥ 0.
Shows that the first amendment to w (e), against either side, there are w (e) ≥ 0, and a stream side (by side chain flow), there will be w (e) = 0. Calculated after each iteration, if f (u, v)> 0, by the need to establish the network flow (v, u) edge, edge weights w '(v, u) =- w (u, v) = 0, that is, the right will not be a negative side.
In addition, the calculation of each iteration with (*) fixes all the w (e), it is not difficult to prove that to each path x to y, its all the same to increase the path length L (x)-L (y). Therefore, x and y will not be the shortest path to w (e) the amendment changes.
】 【Calculation steps
1. On the network G = [V, E, C, W], given the initial value is zero flow streams.
2. Be accompanied by this stream flow network G '= [V', E ', W'].
G 'the vertex-G: V' = V.
If G in f (u, v)
3. If G 'does not exist the path x to y, then G is the minimum cost flow of maximum flow,
To stop calculation; otherwise labeling method used to find x to y of the shortest path P.
4. According to P, the increased flow in G: each edge of P of (u, v), if G exists (u, v), then (u, v) by flow; if G exists (v, u), while (v, u) by flow. Increase (decrease) in flow should be on either side to ensure that there is c (e) ≥ f (e) ≥ 0.
5. According to the calculation of the shortest path at the time of peak value of the label L (v), press the G-type modification of all the edge weights w (e):
L (u)-L (v) + w (e) → w (e).
6. The new stream as the initial flow to 2
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024