英语翻译如题.就这点分了,能帮忙的全部拿去,

英语翻译如题.就这点分了,能帮忙的全部拿去,
英语翻译
如题.就这点分了,能帮忙的全部拿去,

英语翻译如题.就这点分了,能帮忙的全部拿去,
下面先是汉语-----
【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.
-----------------
希望能满足您的要求----