运筹学最大最小,运筹学最大流最小费用问题谁会( 二 ) _生活百科

计算中有一个问题需要解决。这就是增流网络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.