网络优化课件.ppt

文档介绍：该【网络优化课件 】是由【yzhlya】上传分享，文档一共【76】页，该文档可以免费在线阅读，需要了解更多关于【网络优化课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。网络优化
NetworkOptimization

清华大学数学科学系谢金星
办公室:理科楼2206#(电话:62787812)
Email:******@
/~jxie
清华大学课号:70420133(研)
第7章最小费用流问题(MinimumCostFlowProblem)第1讲
1
许多实际问题都可以转化为最小费用流问题
S
T
最小费用流问题的例子
公路交通网络:车辆路线确定
最短路问题
最小费用流问题
1辆车
多辆车:车流
2
=(V,A,L,U,D)上增加如下的权函数:
C:AR为弧上的权函数,弧(i,j)对应的权C(i,j)记为cij,称为弧(i,j)的单位流量的成本或费用(cost);
此时网络可称为容量-费用网络(一般仍可简称为网络),记为N=(V,A,C,L,U,D).

di>0:供应点(supplynode)或源(source)、起始点或发货点
di<0:需求点(demandnode)或汇(sink)、终止点或吸收点
di=0:转运点(transshipmentnode)或平衡点、中间点
可以把L0的网络转化为L=0的网络进行研究(思考?)
除非特别说明,假设L=0,网络简记为N=(V,A,C,U,D).
3
(容量-费用网络中的流(flow)的定义同前一章)
流x的(总)费用定义为
通常又称为转运问题(transshipmentproblem)或容量受限的转运问题(capacitatedtransshipmentproblem).
最小费用流问题就是在网络中寻找总费用最小的可行流.
最小费用流问题

经典的最小费用流问题:单源单汇(起点s,终点t),寻找从s流到t的给定流量(或最大流量、最小流量等)的最小费用流.
线性费用网络
思考:经典问题与一般问题有什么关系?是否等价?
4
例-最大流问题
设s为起点,t为终点,增加弧(t,s),
令

s
t
而令所有其他弧上的费用为0,
所有顶点上的供需量(外部流量)全为0.
6
例-运输问题(transportationProblem)
又称Hitchcock问题(Hitchcock,1941年)
完全二部图
只有源和汇
没有中间转运点
S
T

如果每条弧上还有容量(上下限)的限制,则称为容量受限的运输问题(capacitatedtransportationproblem).
有解的必要条件
可以不失一般性
指派问题(assignmentproblem)
7

最小费用流问题
指派
问题
运输
问题
最大流
问题
最短路
问题
带增益的
最小费用流问题
线性
规划
问题
凹费用网络的最小费用流问题
凸费用网络的最小费用流问题
狭义模型
广义模型
凸
规
划
9
单源单汇网络
可行流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称为最小费用最大流).

最小费用最小流?
10

=(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)定义如下:(residualnetwork,或增量网络或辅助网络)
讨论算法复杂度时,假定:
弧(i,j)A时,弧(j,i)A;cij=-cji
A(x)=A(允许容量为0的弧仍然保留在网络中就可以了)
其中称,uij(x)为弧(i,j)上的残留容量(residualcapacity).
11
定义W的费用为
对于N(x)中的任何一个有向圈W,它一定对应于原网络N中的一个增广圈(增广弧构成的圈);
通过沿W对当前流x进行增广,可以获得流值相等的s-t可行流y.
消圈算法的思想
则当增广的流量为时
只要N中存在费用为负数的增广圈W,即C(W)<0,则可以通过沿W对当前流x进行增广,获得流值相等但费用更小的s-t可行流y.
12