运筹学最小费用最大流问题ppt修复的

5-5最小费用最大流问题运筹学最小费用最大流问题ppt修复的第1页运筹学最小费用最大流问题ppt修复的第2页2、最小费用流对一费用容量网络，含有相同流量f可行流中，总费用最小可行流称为该费用容量网络关于流量f最小费用流，简称流量为f最小费用流。运筹学最小费用最大流问题ppt修复的第3页3、增广链费用当沿着一条关于可行流X增广链（流量修正路线）μ，以修正量ε=1进行调整，得到新可行流，则称C（）-C（X）为增广链μ费用。运筹学最小费用最大流问题ppt修复的第4页②增广链μ费用就是以单位调整量调整可行流时所付出费用；③当修正量ε=1时，此时，

①流量f()=f(X)+1；C()-C(X)=运筹学最小费用最大流问题ppt修复的第5页二、求解最小费用最大流问题对偶法1、求解路径：（1）一直保持网络中可行流是最小费用流，然后不停调整，使流量逐步增大，最终成为最小费用最大流；（2）一直保持可行流是最大流，经过不停调整使费用逐步减小，最终成为最大流量最小费用流。运筹学最小费用最大流问题ppt修复的第6页2、算法原理（1）定理若X是流量为f(X)最小费用流，μ是关于X全部增广链中费用最小增广链，那麽沿着μ去调整X得到新可行流就是流量为f()最小费用流。运筹学最小费用最大流问题ppt修复的第7页（2）实现思绪基于第一个求解路径，依据上述定理，只要找到最小费用增广链，在该链上调整流量，得到增加流量后最小费用流。循环往复直至求出最小费用最大流。＃运筹学最小费用最大流问题ppt修复的第8页

实施中关键结构增广费用网络图（即扩展费用网络图），借助最短路算法寻找最小费用增广链。增广费用网络图结构方法将网络中每一条弧（vi,vj）都变成一对方向相反弧，以形成四通八达“路”，权数定义以下：

运筹学最小费用最大流问题ppt修复的第9页零流弧上Wij=cij

原有弧（流量能够增加）∞后加弧（流量不能再降低）

饱和弧上wij=∞原有弧（流量不能再增加）

-cij

后加弧（流量能够降低）

非饱和且非零流

(0<xij<bij)弧上

cij

原有弧（流量能够增加）

-cij

后加弧（流量能够降低）

Wij=运筹学最小费用最大流问题ppt修复的第10页将上述思想加以简化，出现∞处对应弧不画，按下面方法详细结构增广费用网络图：

零流弧上，保持原弧不变，将单位费用作为权数，即wij=cij:

Vi

Vj(bij,cij)运筹学最小费用最大流问题ppt修复的第11页非饱和弧上，原有弧以单位费用作权数，后加弧（虚线弧）以单位费用负数作权数：ViVj（bij,cij）(bij,-cij)运筹学最小费用最大流问题ppt修复的第12页ViVj(bij,-cij)饱和弧上,去掉原有弧,添上后加弧(虚线弧),权数为单位费用负数：运筹学最小费用最大流问题ppt修复的第13页

于是，在容量网络中寻找最小费用增广链就相当于在增广费用网络图（扩展费用网络图）中寻找从发点到收点最短路。注意将找到最短路还原到原网络图中（虚线弧改成原图中反向弧）。运筹学最小费用最大流问题ppt修复的第14页3、步骤：第一步---用Ford-Fukerson算法求出该容量网络最大流量fmax；（本步骤作用是什麽？）第二步---取初始可行流为零流，其必为流量为0最小费用流运筹学最小费用最大流问题ppt修复的第15页

第三步---普通为第k-1次迭代，得一最小费用流X(k-1)

，对当前可行流结构增广费用网络图W(X(k-1))，用最短路算法求出从发点到收点最短路。（若不存在最短路，则X(k-1)即最小费用最大流，停顿迭代。不然，转下一步。）运筹学最小费用最大流问题ppt修复的第16页

第四步---将最短路还原成原网络图中最小费用