第七章——图论模型
10页1、1第七章 图论模型 7.4 网 络 最 大 流7.4.1 引例如图有一连接某产品的产地 v1 与销地 v6 的交通网 .每条弧表示运输线路.弧旁的数字表示该运输线的最大通过能力.要求制定一个运输计划使从 v1 到 v6 的产品输送量最大 .这就是一个网络最大流问题.7.4.2 基本概念设有一有向图 D=(V,A), 发点是指定的起始点 vs V; 收点是指定的终止点 vt V. 对每一弧 (vi,vj) A , 规定一个非负数 Cij 表示流量的上限称为容量; 指定了发点、收点和各弧容量的有向图 D 称为网络; 所谓网络上的一个流是指定义在弧集 A 上的一个实函 f = f(vi,vj). fij =f(vi,vj) 称为从 vi到 vj 的流量 .若 f 满足以下 2 个条件者,则称 f 为可行流.(1) 容量限制 对每一条弧(v i,vj) A, 0 fij Cij(2) 平衡条件 (i)对每个中间点 vi A,流入量等于流出量 .(流出 vi) (流入 vi)Av, Av,kiijji ikff)( )((ii) 发点净流出量等于收点净流入量v1 v6v2v3v4v5104853
2、5631117图 7.4.12(称为总流量)fVffff Av,tiAv,jtAv,ksAv,sj ittjskjs )()()()(最大流问题就是求一个可行流 f,使 达到最大.)(fV对可行流 f,若 fij=Cij,则称( vi,vj)为饱和弧 ;对可行流 f,若 fij=0,则称(vi,vj)为零弧; 根据原网络的每条弧变作一条顺向弧和一条逆向弧,且把顺向弧的容量定义为 ,逆向弧的容量定义为 ,这样得到ijijijf ijijfC的网络称为原网络 D=(V,A,C)关于流 f 的增量网络,记为 .),()CAVN例 7.4.1 图 7.4.2(b) 就是图 7.4.2(a) 的一个增量网络.7.4.3 求网络最大流的方法(1) 增量网络与原网络的关系3,05,1 4,14,32,2st1V2Vijcijf24011 1333st1V2V0图 7.4.2(a) (b)网络最大流问题的线性规划模型: , , , , ,max () () .0 (), sj ksjt tiij kisjksjttivAvAvAvAijkivvijijijVffffVftfff( ) ( ) ( )
3、( )( ) ( )3N(f)的顺向弧的数表示原网络对应弧上最大可增加的流量.N(f) 的逆向弧的数表示原网络对应弧上最大可减少的流量.若在 N(f)中能找到从s 到 t 的一条路 P,且每条弧容量为正数,则称 P 为 f 的增广链.令:,则 ,称为增广量.0ijjiij C,)v,(|Cmn 0对原网络的流 f 作如下调整:, (7.4.1)其 它( ,),(ij ijij jiijijf Pvff则 是新的可行流且 ,若 N(f)中不存在增广f )()()( fVfVf链,则对应的流 f 已是最大流.(2) 步骤以零流 f=0 作初始可行流作增量网络 N(f)寻找增广链 P.若无,则结束 .令 0ijjiij C,P)v,(|Cmn按(7.4.1)式调整流量,得新流 f.转例 7.4.2 求图 7.4.3(a)的网络的最大流, 初始可行流零流 =0, 对应的f增量网络 N(f)如图 7.4.3(b)所示. 寻找得增广链 P:. v1 v2 v3 v4,求得=4.v1v2v3v43,04,05,02,04,0(a)34 0504 0v1v2v3v4020图 7.4.3(b)4按(7.
《第七章——图论模型》由会员壹****1分享,可在线阅读,更多相关《第七章——图论模型》请在金锄头文库上搜索。
把学习放在群众路线教育突出位置
好用的高校职业规划模板集锦九篇
加油站经理的竞聘演讲稿
2022小班教学工作总结4篇(模板)
自考学前比较教育复习资料
一年级上册拼音1--13课练习题
吸烟检讨书
幼儿同伴冲突及其解决与策略
第三次集中研讨方案
自愿离婚协议书范例
2019年学校招商引资工作汇报(二篇)
高安全智能型金库门禁方案建议书
最新化工原理课程设计zzd
2023年员工试用期工作总结范本(3篇).doc
2022年天津市建筑施工企业“安管人员”C2类专职安全生产管理人员考试历年真题汇总含答案参考92
群众路线教育实践活动学习心得体会 市财政支付中心党员
大学生学期自我鉴定
福建师范大学21秋《学前心理学》综合测试题库答案参考77
重庆市江津第五中学七年级英语上册StarterUnit2WhatsthisinEnglish第1课时导学案无答案新版人教新目标版
2021版高考历史一轮总复习第7单元资本主义世界市场的形成和发展单元过关训练新人教版
2024-04-28 3页
2024-04-28 7页
2024-04-28 8页
2024-04-28 5页
2024-04-28 3页
2024-04-28 4页
2024-04-28 4页
2024-04-25 30页
2024-04-25 22页
2024-04-25 7页