最大流问题
更新时间:2024-03-30 22:29:01 阅读量: 综合文库 文档下载
网络最大流问题
一 产生背景
流量问题在实际中是一种常见的问题,在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流,城市给排水系统的水流问题,控制系统中的信息流问题,常见的人流,物流,水流,气流,电流,现金流等。在一定条件下,求解给定系统的最大流量,就是网络最大流问题.网络系统最大流问题是图与网络理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用。
二 基本概念与定理
设cij为弧(i,j)的容量,fij为弧(i,j)的流量。容量是弧(i,j)单位时间内的最大通过能力,流量是弧(i,j)单位时间内的实际通过量,流量的集合f={fij}称为网络的流。发点到收点的总流量记为v=v(f)。
设D=(V,A)是一有向图且对任意E均有容量cij =(vi,vj),记C={cij︱(vi,vj)∈A},此外D中只有一个源vs和汇vt( 即D中与vs相关联的弧只能以 vs为起点,与vt相关联的弧只能以 vt为终点),则称D=(V,A,C, vs,vt)为一网络。 引例1:图1给出了一张网络,其中:vs为源,vt为汇,弧旁的数字为该段弧的容量cij与流量fij,则显然有0≤fij ≤ cij 。
v2 (3,3) v4 (3,3) (5,5) vt (2,2) (2,2) (2,2) vt (6,4) (6,2) v1 (6,6) v3 图1
最大流问题可以建立如下形式的线性规划数学模型。图1最大流问题的线性规划数学模型为
1
maxv?fs1?fs2??fij??fij?0(i?s,t)?ji???0?fij?cij所有弧(i,j)
由线性规划理论知,满足式上式的约束条件的解{fij}称为可行解,在最大流问题中称为可行流。
可行流满足下列三个条件:
(1)0?fij?cjiijim(2?)fmj??f
vsvt(3v)??fsj??fit
条件(2)和条件(3)也称为流量守恒条件。
另外对有多个发点和多个收点的网络,可以另外虚设一个总发点和一个总收点,并将其分别与各发点、收点连起来(图*),就可以转换为只含一个发点和一个收点的网络。
S T
S* T* 图*
所以一般只研究具有一个发点和一个收点的网络
在图D中,从发点到收点的一条路线称为链,从发点到收点的方向规定为链的方向。与链的方向相同的弧称为前向弧,前向弧集合记为u+ ,与链的方向相反的弧称为后向弧,后向弧集合记为u-。
设f是一个可行流,如果存在一条从发点vs到收点vt到的链u满足: (1)所有前向弧上fij<cij
2
(2) 所有后向弧上fij>0 ,则称链u为增广链. 设S,T?V,S?T??,vs?S,vt?T则称
(S,T)??(vi,vj)|vi?S,vj?T?C(S,T)?
为图D的一个割集;称
(vi,vj)?(s,t)?c(vi,vj) 为割集(S,T)的容量。
显然对任意可行流f及任意割集(S,T)总有V(f)=C(S,T)。故有某个可行流f*及某一割集(S*,T*)使得V(f*)= C(S*,T*),则f*为D的最大流,(S*,T*)为最小容量割集。
定理1 图D上的可行流f*是最大流的充要条件是D上不存在关于f*的增广链。
三 求解网络最大流的方法(标号法)
标号法是一种图上迭代计算方法,该算法首先给出一个初始可行流,通过标号找出一条增广链,然后调整增广链上的流量,得到更大的流量。再用标号找出一条新的增广链,再调整直到标号过程不能进行下去为止,这时的可行流就是最大流。
标号法步骤如下:
第一步 找出一个初始可行流fij(0),例如所有弧的流量fij(0) =0. 第二步 对点进行标号找出一条增广链。 (1) 起点标号(∞)
(2) 选一个点vi已标号且另一端未标号的弧沿着某条链向收点检查
(a)如果弧是前向弧且有fij<cij,则vj标号
?j?ci?jf ij (b)如果弧是后向弧且有fij﹥0,则vj标号
?j?fij
当收点已得到标号时,说明已找到增广链,依据v的标号反向追踪得到一条增广链。当收点不能得到标号时,说明不存在增广链,计算结束
第三步 调整流量
(1) 求增广链上点的vi标号的最小值,得到调整量号
3
?j?min?jj
(2) 调整流量
?fij??(vi,vj)?u???f1??fij??(vi,vj)?u??fij(vi,vj)?u??
得到新的可行流f1,去掉所有标号,返回到第二步从发点重新标号寻找增广链,直到收点不能标号为止。 四 例题应用
例2:用标号法求网络最大流(图1),弧旁数字为(cij ,fij(0))。 解 (1) 标号过程。见图2。
?(v,v),(v,v)?u32 (2) 增广链为{vs,v1,v2,v3,vt} (注意21)。
(3)调整量θ=2调整后得图3。 (4) 二次标号过程。见图3。
标号无法进行下去,最大流流量V(f*)=3+6=9,最小割集(S*,T*), S*={vs}, T*={ v1,v2,v3,v4,vt}。
(-v1,2)
(3,3) vs (2,2) (2,2) (2,2) vt (v3,2)
v2 (3,3) v4 (5,5)
(0,+?) (6,4) (6,2) v1 (6,6) v3 (v1,2) (-v2,2)
图2
v2 (3,3) v4 (5,5)
(3,3) vs (2,0) (2,0) (2,2) vt
(0,+?) (6,6) (6,4)
v1 (6,6) v3 图3
4
例3:在下面的有向图中1是发点, 6是收点,求最大流. 2 1 4 4 2 1 2 4 2 6 5 6 3 3 5 图解法如下:
2(1,+4) 1 4(2,+1) 4 2 1(0,+inf) 2 4 2 6 (5,4) 5 6 3(5,+5) 3 5(2,+4)
2(5,-3) 1 4(5,+2) (4,4) 2 1(0,inf) 2 (4,4) 2 6(5,2) 5 (6,4) 3(1,+5) 3 5(3,+3)
5
2(5,-1) 1 4(5,+1) (4,4) 2 1(0,inf) 2 (4,4) 2 6(4,+1) (5,2) (6,6) 3(1,+3) (3,2) 5(3,1)
2 1 4 (4,4) (2,1) 1(0,inf) 2 (4,4) (2,1) 6 (5,3) (6,6) 3(1,2) (3,3) 5
图中红色的是可增广链,可见S={1,3}, S’={2,4,5,6}, 蓝色的三条边(1,2), (3,5),(2,3)组成的集合是最小割,割集容量为(1,2)和(3,5)两条边的容量之和7,也就是最大流的流量.
参考文献
[1] 杨民助.运筹学[M].西安:西安交通大学出版社,2000,201-204
[2] 宁宣熙.运筹学实用教程[M].第二版.北京:科学出版社,2007,147-152 [3] 黄桐城.运筹学基础教程[M].第一版.上海:上海人民出版社,2004,124-128
6
2(5,-1) 1 4(5,+1) (4,4) 2 1(0,inf) 2 (4,4) 2 6(4,+1) (5,2) (6,6) 3(1,+3) (3,2) 5(3,1)
2 1 4 (4,4) (2,1) 1(0,inf) 2 (4,4) (2,1) 6 (5,3) (6,6) 3(1,2) (3,3) 5
图中红色的是可增广链,可见S={1,3}, S’={2,4,5,6}, 蓝色的三条边(1,2), (3,5),(2,3)组成的集合是最小割,割集容量为(1,2)和(3,5)两条边的容量之和7,也就是最大流的流量.
参考文献
[1] 杨民助.运筹学[M].西安:西安交通大学出版社,2000,201-204
[2] 宁宣熙.运筹学实用教程[M].第二版.北京:科学出版社,2007,147-152 [3] 黄桐城.运筹学基础教程[M].第一版.上海:上海人民出版社,2004,124-128
6
正在阅读:
最大流问题03-30
9-16公路工程设计收费标准说明11-21
PSP 641U备用电源自投装置技术说明书V1.105-23
少儿艺术小主持人培训教材第二册04-20
叶集试验区规范处置不合格党员流程材料06-07
湖南地区一级建造师(一建)历年历年分数合格线公布Word 文档04-21
2017年黑龙江房地产估价师《制度与政策》:房地产中介服务人员的职业道德试题12-15
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 大流
- 问题
- 矿石基本化学分析成果质量检查办法
- 藏羌歌曲歌词
- 成都市重点高中选拔考试数学试卷(共4套)
- 北师大二年级上册数学第一单元加与减测试卷
- 中级财务会计 - 习题 - 长期股权投资
- 关于初中《道德与法治》课程的思考
- 磷化工概论—2
- 斜坡屋面的设计构造
- 2016年室内设计师就业前景介绍每日一讲(8月7日)
- 苏荣在中国共产党江西省第十三次党代会上的报告
- SP-P-015会议管理实施细则
- 生理心理学复习资料
- 前进中的物理学与人类文明
- 实验 二 栈和队列的基本操作实现及其应用
- 小学修辞手法 修改病句详解与练习
- 第十八届全国中小学生绘画书法作品比赛成绩通报
- 人民防空档案管理暂行规定
- 浅谈小生班主任管理学生的艺术
- 红旗镇岗位廉政风险防范管理工作实施方案
- 2011年高中保送生考试数学模拟试卷及参考答案标准