3
最小费用流问题
定义7.2 （容量-费用网络中的流(flow) 的定义同前一章） 流x的（总）费用定义为
c( x)
( i , j )A
c
ij
xij
线性费用网络
di , i V (7.1)
(7.2)
最小费用流问题就是在网络中寻找总费用最小的可行流.
min c( x)
( i , j )A
运 输 问 题
凸 规 划
狭义模型
广义模型
9
7.2 消圈算法与最小费用路算法
单源单汇网络 可行流x的流量（或流值）为v=v（x）= ds = - dt
如果我们并不给定ds 和dt , 则网络一般记为N=（s, t,V,A,C,U）
容量可行且转运点流量守恒的流称为s-t可行流，有时为了方 便也称为可行流. 最小费用流问题就是在网络N=(s,t,V,A,C,U)中计算流值为v的 最小费用流x 或者当不给定流值时, 计算流值最大的最小费用流x (此时流x 称为最小费用最大流).
增益除了可以发生在弧上，类似地可以考虑增益发生在节点上
8
7.1.2 最小费用流模型的特例及扩展
最 问 短 路 题 最 小 费 用 流 问 题
带 增 益 的 最小费用流 问 题 凹费用网络 的最小费用 流 问 题 凸费用网络 的最小费用 流 问 题 线 规 问 性 划 题
最 问
大
流 题
指 派 问 题
如果再令所有弧上的(单位流量)的费用为“弧长”, 则此时的最 小费用流问题就是第五章讨论过的最短路问题.
在第五章我们正是用这样的方式对最短路问题进行建模的
5
7.1.2 最小费用流模型的特例及扩展
例 - 最大流问题st Nhomakorabea设s为起点,t为终点,增加弧(t,s), 令
cts 1, u ts
12
7.2.1 消圈算法(cycle-canceling algorithm)
定理7.1 可行流x为最小费用流的充要条件是N(x)中不存在负费 用增广圈.
必要性是显然的. 反证法证明充分性：
0
设x0为不同于的可行流，但费用低于x的费用，即
v( x) v( x ) v
c( x) c( x 0 )
复杂度？
Step0可借用最大流算法 ，复杂度为O(n2m)
任何可行流的费用不可能超过mCU
设数据是整数, 每次消去一个负圈至少使费用下降一个单位 设数据是整数, 消去负圈的STEP1~2最多执行O(mCU )次 N(x)中找负圈可用最短路算法(如Bellman-Ford算法，O(m n ) ) 则该算法的复杂度为O(n m 2CU), 不是多项式时间算法. 如按一些特定次序消圈, 可得到一些多项式时间算法
r
至少存在一个费用为 负的增广圈. 矛盾
13
7.2.1 消圈算法: Klein (1967)等
STEP 0 . 在网络N=(s,t,V,A,C,U)中计算流值为v的可行流 x. STEP 1. 在残量网络N(x)中判别负圈. 若无负圈, 则已经找到了最 小费用流，结束；否则转STEP 2. STEP 2. 沿找到的负圈增广流量, 转STEP 1.
1
最小费用流问题的例子
公路交通网络：车辆路线确定
S
T
1辆车
最短路问题
多辆车:车流
最小费用流问题
许多实际问题都可以转化为最小费用流问题
2
7.1.1 最小费用流问题
定义7.1 在流网络N=(V,A，L,U,D) 上增加如下的权函数： C： A R为弧上的权函数，弧（i，j）对应的权 C（i，j）记 为cij ，称为弧（i，j）的单位流量的成本或费用（cost）; 此时网络可称为容量-费用网络 (一般仍可简称为网络),记为 N=(V,A,C，L,U,D).
c x
ij ij
s.t.
ij j:( i , j )A
x

j:( j ,i )A
x
ji
0 xij uij ,
(i, j ) A
通常又称为转运问题(transshipment problem)或容量受限的 转运问题(capacitated transshipment problem).
最小费用最小流?
10
7.2 消圈算法与最小费用路算法
定义7.3 对网络N=(s,t,V,A,C,U)中给定的s-t可行流x，网络N关于流 x的残量网络N(x) = (s, t, V, A(x), C(x), U(x)) , 其中A(x), C(x) ，U(x) 定义如下：（residual network，或增量网络或辅助网络 ）
P W \ {(i, j )} 也是网 络中关于x的增广路, 且
s
i
j
P
t
C ( P W \ {(i, j )}) C ( P) C (W ) C ( P)
W
17
7.2.2 最小费用路算法 也称为连续最短路算法, 即Successive Shortest Path Algorithm), Jewell(1958), Iri(1960), Busacker & Gowen (1961) 独立提出的 STEP 0 . 取x为任一s-t可行流、且在同一流值的流中费用最小的 流 (如x=0). STEP 1. 若x的流值达到v, 结束；否则在残量网络N(x)中判别最 小费用路. 若无这样的路,则流值不可达到v, 结束；否则STEP 2. STEP 2. 沿该最小费用增广路增广流量(增广后的流值不超过v), 转STEP 1.
有解的必要条件 可以不失一般性
a b
iS i jT
j
指派问题(assignment problem)
a b
iS i jT
j
ai b j 1, | S || T |
7
7.1.2 最小费用流模型的特例及扩展
（1）当一定的流量流过一条弧时，该弧上导致的总费用与流量 大小成线性正比关系，这样的流网络一般称为线性费用网络. 如果当一定的流量流过一条弧时，该弧上导致的总费用不一定 与流量大小成线性正比关系，而是流量大小的一个凹（或凸） 函数，则这样的网络称为凹（或凸）费用网络，相应的最小费 用流问题称为凹（凸）费用网络上的最小费用流问题. （2）当流量流过一条弧时，流出该弧的流量（即流入该弧终点 的流量）与进入该弧的流量（即流出该弧起点的流量）相等. 如果当流量流过一条弧时，流出该弧的流量是进入该弧的流量 的一个线性函数，即流出该弧的流量是对进入该弧的流量按一 定比例进行放大或缩小的结果，则这样的流网络一般称为带增 益(或盈亏)的流网络（flow with gain network）.
消圈算法的思想
对于N(x)中的任何一个有向圈W, 它一定对应于原网络N中的一 个增广圈(增广弧构成的圈)； 通过沿W对当前流x进行增广，可以获得流值相等的s-t可行流y. 定义W的费用为
C (W )
( i , j )W
c
ij
( x)
则当增广的流量为时 c( y) c( x) C (W ) 只要N中存在费用为负数的增广圈W， 即C（W）<0，则可以通过沿W 对当 前流 x 进行增广，获得流值相等但 费用更小的s-t可行流y.
di >0:供应点(supply node)或源(source)、起始点或发货点
di <0:需求点(demand node)或汇(sink) 、终止点或吸收点 di ＝0:转运点(transshipment node)或平衡点、中间点 可以把L 0的网络转化为L=0的网络进行研究(思考？) 除非特别说明, 假设L=0,网络简记为N=(V,A,C，U,D).
而令所有其他弧上的费用为0, 所有顶点上的供需量(外部流量)全为0.
6
7.1.2 最小费用流模型的特例及扩展
例 -运输问题(transportation Problem) 又称Hitchcock问题（Hitchcock,1941年）
min s.t.
( i , j )A
S
T
c x
ij ij
(7.5) i S, j T , (i, j ) A. (7.6)
A( x) (i, j ) | (i, j ) A, xij u ij (i, j ) | ( j, i ) A, x ji 0
cij , cij ( x) c ji ,
u ij xij , u ij ( x) x ji ,
(i, j ) A, xij u ij , ( j , i ) A, x ji 0,
引理7.1 最小费用流问题存在可行流的必要条件

iV
d i 0.
经典的最小费用流问题：单源单汇(起点s，终点t)，寻找从s流 到t的给定流量(或最大流量、最小流量等)的最小费用流.
d s v, d t v
d i 0(i s, t )
4
思考： 经典问题与一般问题有什么关系？是否等价？
1 1 0 令 x1 =x0-x, 则 x 0, v( x ) v( x ) v( x) 0 ，即令x1为网络N中的循环流.
一个循环流一定可以表示为至多m个非零圈流之和，所以可以将x1表示为r个 非零圈流之和（ 1 r m ）。设对应的有向圈为Wk，
x {v(Wk ) | (i, j ) Wk }
网 络 优 化
Network Optimization
/netopt
清华大学课号：40420213（本），70420133（研）
第7章
最小费用流问题
(Minimum Cost Flow Problem) 第1讲
清华大学数学科学系 谢金星 办公室：理科楼1308# （电话：62787812） Email:jxie@ /faculty/~jxie