网络最大流问题__运筹学__胡运权__清华大学出版社

《网络最大流问题__运筹学__胡运权__清华大学出版社》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图与网络优化北京化工大学经济管理学院公路系统中的车辆流§4网络最大流问题控制系统中的信息流供水系统中的水流金融系统中的现金流问题背景网络最大流问题—问题的提出网络中存在流量限制时，求解一条线路使得从起点与终点之间可通过的流量最大。v1v2v3v4v5v61084653531117例：上图为V1到V6的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V1运到V6的产品数量最多。设有网络D=(V,A,C)，其中C={cij}，cij为弧(vi,vj)上的容量，现在D上要通过一个流f={fij}，fij为弧(vi,vj)上的流量。问题：

2、如何安排fij，可使网络D上的总流量最大？v2v1v3v4v5v681041755311635312213362一、一般提法：二、最大流问题的模型maxv=v（f）容量约束平衡约束s.t.v2Vsv3v4v5Vt81041755311635312213362注：满足两约束条件的流f称为可行流，v(f)称为该可行流的流量试分析下图是否是可行流?v2v1v3v4v5v681041755311635312113362三、基本概念与定理1.弧按流量分为饱和弧fij=cij非饱和弧fij

3、6810417553116353122133622.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱和，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v6810417553116353122133622.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v6810417553116353122133622.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，

4、u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v6810417553116353122133612.增广链f为一可行流，u为vs至vt的链，令u+={正向弧}，u-={反向弧}。若u+中弧皆非饱，且u-中弧皆非零，则称u为关于f的一条增广链。v2v1v3v4v5v6810417553116353320153623.截集与截量把V分成两部分：VA和VB(VA∩VB=φ,VA∪VB=V)且vs∈VA、vt∈VB，则弧集(VA,VB)称为D的截集。截集上的容量和称为截量，记为C(VA,VB)

5、。v1vsv2v3v4vt81041755311635312213362{(vs,v2),(v1,v2),(v1,v3),(v1,v4)}；截量为：C(VA,VB)=8+4+5+3=20例若VA={vs,v1}，则截集为：4.流量与截量的关系任一可行流的流量都不会超过任一截集的截量因v(f)=f(VA,VB)-f(VB,VA)≤f(VA,VB)≤C(VA,VB)）v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）最大流最小截定理：网络的最大流量等于最小截量。例.如图所示的网络中，弧旁数字为(cij,f

6、ij)v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）确定所有的截集；（2）求最小截集的容量；（3）证明图中的流为最大流；v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①VA={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①VA={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②VA={vs,v1

7、}，截集为{(vs,v2),(v1,vt)}，截量为：7v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①VA={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②VA={vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7③VA={vs,v2}，截集为{……}，截量为：7v1vsv2v3vt（2，2）（4，3）（3，1）（1，0）（3，3）（5，2）（2，2）（1）所有的截集：①VA={vs}，截集为{(vs,v1),(vs,v2)}，截量为：6②VA=

8、{vs,v1}，截集为{(vs,v2),(v1,vt)}，截量为：7③VA={vs,v2}，截集为{……}，截量为：7④Va={vs,v3}，截集为{……}，截量为：12v1vs