版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、网络流简介 2背景 许多系统包含了流量问题。 例如: 公路系统中有车辆流, 控制系统有信息流, 供水系统中有水流, 金融系统中有现金流等。3 图为连接产地V1和销地V7的交通网,边上 的数字表示这条边的最大通过量Cij(容量),括号里的数字表示实际通过量fij(流量)。 所有括号里的数fij (i=1,7)给出一种运输方案。例流, 流量, 最大流sv1v3v2v4t11/168/13101/412/1215/204/47/74/911/14 称 f: VVR 为可行流, 若f 满足: (1) 容量限制, f(u,v) c(u,v) / c为容量极限 (2) 反对称性, f(u,v) = -f(
2、v,u) (3) 流守恒性, 任意uVs,t, vV f(u,v) = 0 流量 |f| = vV f(s,v). 最大流: 给定流网络G,s,t,c, 求 max |f| : f是G的流45x,y = c, f非可行流流网络的割割(S,T): (1) T=V-S (2) sS, tT. f(S,T)=uS,vTf(u,v) : f穿过割(S,T)的净流c(S,T)=uS,vTc(u,v) : 割(S,T)的容量sv1v3v2v4t11/168/130/101/412/1215/204/47/74/911/14S T例.下图中的割(S,T), S=s,v1,v2,T=v3,v4,t.f(S,T
3、)=19, c(S,T)=26.67最大流最小割定理 f(S,T) = |f|, |f| min c(S,T) | 割(S,T) . 定理(最大流最小割) 下列条件等价 (1) f是G的一个最大流; (2) G不包含增广路径; (3) 存在割(S,T)使得 |f| = c(S,T). 最大流算法基本思想: 找从s到t的增广路径, 增大流, 无则停止, 得最大流 89求解最大流增广路径设f是一个可行流,p是从s到t的一条路,若:(1) 在p的所有前向边(i,j)上,0f(i,j)c(i,j). 非饱和边 改进量为a = c(i,j) - f(i,j)。 (2) 在p的所有后向边(i,j)上,0f
4、(i,j)c(i,j). 非零流边 改进量为a = f(i,j)。 则称P为关于可行流f的一条增广路。所有边的可改进量的最小值为增广路p的改进量10按下面的公式修改当前的流:如果网络中有一条可改进量为k的增广路,则沿着它改进(所有前向边流量增加k,所有后向边的流量减少k)以后流仍然是可行的,且网络流量增加k残流网络为寻找增广路,可定义残流网络,残流网络中存在从源到汇的容量大于0的路径,即增广路残流网络G*与原网络G有相同顶点,原网络每条边(i,j)在残流网络中对应一条或两条边:令G中(i,j)的流量为f,容量为c。(1) (i,j)为零流边,G*中有边(i, j),容量为c(2) (i,j)为
5、饱和边,fc,G*中有边(j, i),容量为c(3) (i,j)为弱流边,G*包含边(i, j),容量c - f; G*亦包含边(j, i),容量为f1112最大流增广路算法(Ford-Fulkerson) 设f是网络G的一个可行流,如果不存在从s到t关于f的可改进路p,则f一定是最大流。 增广路方法: (1)置f=0为初始可行流; (2)while (存在从s到t关于f的可改进路)do begin 找出一条从s到t关于f的可改进路p; 计算关于f的可改进路p的可改进量a; 根据可改进量a改进当前可行流的流量 end;134112212331s2453t这是初始网络以及初始剩余网络.剩余网络N
6、中任何一条从s到t的路径都是增广路Ford-Fulkerson 最大流144112212331在G(x)中寻找任何s-t 路径.s2453t15411213判定路径的可改经量a.在路径上发送 a单位的流.更新剩余容量.111212321s2453t16411213寻找任何s-t 路径 111212321s2453t1742111122111131111321s2453t判定路径的可改进量 a 在路径中发送 a 单位的流.更新剩余网络1842111122111131111321s2453t寻找任何 s-t 路径191111141211211311321s2453t判定路径的可改进量 a 在路径中
7、发送 a单位的流.更新剩余网络2011111412112211311321s2453t寻找任何 s-t 路径21111211114221122111311s2453t2判定路径的可改进量 a 在路径中发送 a 单位的流.更新剩余网络2211211114221122111311s2453t寻找任何 s-t 路径223111114131121132212121s2453t2判定路径的可改进量 a 在路径中发送 a单位的流.更新剩余网络24111114131121132212121s2453t2在剩余网络中没有 s-t 路径.此流是最优的.25111114131121132212121s2453t2
8、这些是从结点 s 可达的结点.最小截量=5 V1=s,2,3,4,5,V2=ts2453261122212s2453t这是最优流.274112212331s2453t这是初始网络以及初始剩余网络.寻找最短增广路Edmonds-Karp 最大流最短增广路法基于Ford- Fulkerson算法每次用一遍 BFS 寻找从源点 s 到终点 t 的最短路作为增广路径,然后增广流量 f 并修改残量网络,直到不存在新的增广路径2814112212331宽度优先搜索,标号节点距离s2453t011222914112212331选取2条最短增广路中的任一条s2453t0112230422213判定路径的可改经
9、量a=2.在路径上发送 a单位的流.更新剩余容量.更新节点距离11212311s2453t10122231422213寻找最短 路径11212311s2453t1012223242213在路径上发送 a单位的流.更新剩余容量.更新节点距离1121311s2453t102323433422131121311s2453t1023234寻找最短路径34322131121211s2453t02111在路径上发送 a单位的流.更新剩余容量.无法标号,算法结束35111114131121132212121s2453t2这些是在剩余网络中从结点 s 可达的结点.最小截量=5 V1=s,2,3,4,5,V2=
10、ts2453361122212s2453t这是最优流. (最短增广路只用三条增广路就得到最大流)bool bfs(int src, int dst)int EK(int src,int dst) int i, totalFlow = 0, PingJing; while (bfs(src, dst) PingJing = INF; for (i = dst; i != src; i = prei) PingJing = min(PingJing, edgepathi.flow); totalFlow += PingJing; for (i = dst; i != src; i = prei)
11、edgepathi.flow -= PingJing; edgepathi 1.flow += PingJing; 01000000121234510010000001000000437EK算法核心代码练习1: 无向图的网络流下图为某地区运输网. 边上的数字表示运输能力(单位:万吨/小时),则从顶点1到顶点5的最大运输能力可以达到_万吨/小时. 120424101068532438最大流题目选讲1. DinningFarmer John的牛饿了,到了午餐时间需要吃饭和喝饮料,现在已知有n头牛,a种食物和b种饮料,每头牛都有一些食物和饮料是喜欢的,牛们只会吃喜欢的食物和喜欢的饮料,每种食物和饮料
12、只有一份,现在请问最多有多少头牛能够吃到喜欢的食物和饮料。39最大流题目选讲增加源点src与汇点dst,src到每种食物连一条容量为1的边,保证每种食物只用一次,同理每种饮料到汇点连一条容量为1的边,保证每种饮料只用一次。将每头牛拆成两个点,中间连一条容量为1的边,保证每头牛只用一次,每种食物到喜欢他的牛左侧的点连容量为INF的边,每头牛右侧的点到每种饮料连容量为INF的边,求最大流即可。40最大流题目选讲2. 喜羊羊与灰太狼在一个M*N的方格形地图上,有一些格子中有羊,有一些格子中有狼,还有一些格子是空地,每个格子内最多只能有一只狼或羊,先要沿着格子边沿修建围墙,请问最少修建多长的围墙能够将
13、狼和羊隔开。41最大流题目选讲实际上是一个多源汇最小割问题,我们把地图中每个方格作为网络中的一个节点,任意相邻两个方格建立双向容量为1的边。此时我们假设有狼的格子为源点,有羊的格子为汇点,显然只要有从任意源点到达任意汇点的一个流,则说明狼可以通过这条路径吃到羊,所以只要割断这个图就可以隔开狼和羊,而每割断一条边正好对应修建一段墙,原问题也就成功转化为多源汇最小割问题。为解决问题,我们添加超级源点src和超级汇点dst,src到每个狼的格子有容量为INF的边,每个羊的格子到dst有容量为INF的边,在此网络中由最大流最小割定理,求出最大流即为答案42 阿P与阿Q都是四驱车好手,他们各有N辆四驱车
14、。为了一比高下,他们约好进行一场比赛。这次比赛共有M个分站赛,赢得分站赛场次多的获得总冠军。每个分站赛中,两人各选一辆自己的赛车比赛。分站赛的胜负大部分取决于两车的性能,但由于种种原因(如相互之间的干扰),性能并不是决定胜负的唯一指标,有时会出现A赢B、B赢C、C赢D、D又赢A的局面。幸好有一种高智能机器,只要给定两辆四驱车,就能立刻判断谁会赢,在总比赛前它就已经把阿p的每辆车与阿q的每辆车都两两测试过了,并且还把输赢表输入了电脑。 43 另外,由于比赛的磨损,每辆四驱车都有自己的寿命(即它们能参加分站赛的场次),不同的四驱车寿命可能不同,但最多不会超过50场。两辆四驱车最多只能交手一次。 现
15、给定N、M(1=N=100,1=M=1000)、N*N的一个输赢表、每辆四驱车的寿命,并假设每次分站赛两人都有可选的赛车,请你计算一下阿P最多能够赢得多少个分站赛。44 1、建立N个点代表阿P的N辆车,分别以1到N标号; 2、建立N个点代表阿Q的N辆车,分别以N+1到2N标号; 3、若阿P的第I辆车能够跑赢阿Q的第J辆车,则加一条弧IN+J,容量为1,表示两辆四驱车最多只能交手一次; 4、增加一个源点S,S与1到N中的每一个结点I都连一条弧SI,容量为阿P的第I辆车的寿命; 5、增加一个汇点T,N+1到2N中的每一个结点N+J到T都连一条弧N+JT,容量为阿Q的第J辆车的寿命; 6、再增加一个
16、源点S2,加一条弧S2S,容量为M,表示最多M场分站赛 。该网络的最大流就是P最多能赢多少场比赛。4546线性规划简介 线 性 规 划(Linear Programming)线性规划问题线性规划的图解法48一、线性规划问题 设备产 品 A B C D利润(万元) 2 1 4 0 2 2 2 0 4 3 有 效 台 时 12 8 16 12 例、已知资料如右表所示,问如何安排生产才能使利润最大?模 型max Z = 2x1 + 3x2 x1 0 , x2 0s.t. 2x1 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12此为带约束的极值问题49目标函数:约束条件:2、线性规划
17、数学模型的一般形式50一 般 有两种方法图 解 法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但需将一般形式变成标准形式二、线性规划问题的求解方法(一)、求解方法511、解的概念 可行解:满足约束条件、的解为可行解。所有解的集合为可行解的集或可行域。 最优解:使目标函数达到最大值的可行解。(二)、线性规划问题的解522、解的基本定理 线性规划问题的可行域是凸集(凸多边形)。凸集凸集不是凸集顶 点 最优解一定是在凸集的某一顶点实现。53 先找一个可行解,与周围顶点比较,如不是最大,继续比较,直到找出最大为止。3、解的情况唯 一 解无 穷多 解无 界 解无可行解有最优解无最优解54 建立直角坐标 ,图中阴影部分及边界上的点均为其解,是由约束条件来反映的。例一、三、图 解 法55
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年电费成本降低与绿色能源发展报告
- 2026年光伏产业关键环节技术突破报告
- 2026年口才培训行业培训质量报告及改进措施
- 2026年互联网保险行业发展趋势报告:政策环境与市场前景
- 2026年体育产业回报周期与风险预警报告
- 2026年行业数字孪生解决方案深度解析报告
- 2026年体育行业赛事管理流程报告
- GBT 17954-2007工业锅炉经济运行
- 《肝细胞癌经动脉化疗栓塞抵抗及后续治疗专家共识(2022版)》
- 高中物理力学实验观察浮力产生原理测试技巧训练试题及答案
- GB/T 22417-2025工业车辆货叉叉套和伸缩式货叉技术性能和强度要求
- 锤击安全施工方案(3篇)
- 建筑拆除工程监理实施细则
- 湖北省仙桃、天门、潜江市2025-2026学年高一上化学期中联考试题含解析
- 西门子S7-1200 PLC应用技术 课件 项目七 步进电机与伺服电机控制程序设计
- DG-TJ08-2478-2025 装配式混凝土预制构件设计一生产数据交互标准
- 2025年国家级检验检测机构资质认定评审员考试在线题库(附答案)
- 进线柜保护培训课件
- GB/T 45743-2025生物样本细胞运输通用要求
- DB32-T 5090.2-2025 医院医患沟通规范 第2部分:门诊
- 中医护理小组工作总结
评论
0/150
提交评论