运筹学最大流课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《运筹学最大流课件.ppt》由用户(ziliao2023)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学 最大 课件
- 资源描述:
-
1、Page 1如何制定一个运输计划使生产地到销售地的产品输送量最大。如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。这就是一个网络最大流问题。Page 2基本概念:基本概念:队网络上的每条弧队网络上的每条弧(vi,vj)都给出一个最大的通都给出一个最大的通过能力,称为该弧的过能力,称为该弧的,简记为,简记为cij。容量网络中通常规定。容量网络中通常规定一个一个(也称源点,记为也称源点,记为s)和一个和一个(也称汇点,记为也称汇点,记为t),网络中其他点称为网络中其他点称为。st4844122679Page 32.网络的最大流网络的最大流是指网络中从发点到收点之间允
2、许通过的最大流量。是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流与可行流 流流是指加在网络各条弧上的实际流量,对加在弧是指加在网络各条弧上的实际流量,对加在弧(vi,vj)上上的负载量记为的负载量记为fij。若。若fij=0,称为零流。,称为零流。满足以下条件的一组流称为满足以下条件的一组流称为可行流可行流。容量限制条件。容量网络上所有的弧满足:容量限制条件。容量网络上所有的弧满足:0fijcij 中间点平衡条件。中间点平衡条件。),(0),(),(tsivvfvvfijji 若以若以v(f)表示网络中从表示网络中从st的流量,则有:的流量,则有:0),(),()(tjjsvv
3、fvvffvPage 4结论:任何网络上一定存在可行流。(零流即是结论:任何网络上一定存在可行流。(零流即是可行流)可行流)网络最大流问题:网络最大流问题:指满足容量限制条件和中间点平衡的条件下,使指满足容量限制条件和中间点平衡的条件下,使v(f)值达到最大。值达到最大。Page 5 割与割集割与割集割是指容量网络中的发点和收点分割开,并使割是指容量网络中的发点和收点分割开,并使st的流中断的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之的一组弧的集合。割容量是组成割集合中的各条弧的容量之和,用和,用 表示。表示。),(VVc ),(),(),(),(VVjijivvcVVc如下图
4、中,如下图中,AA将网络上的点分割成将网络上的点分割成 两个集合。并两个集合。并有有 ,称弧的集合,称弧的集合(v1,v3),(v2,v4)是一个割,且是一个割,且 的流量为的流量为18。VV,VtVs ,VV Page 6v1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AABBPage 7 设网络设网络N中一个从中一个从 s 到到 t 的流的流 f 的流量为的流量为v(f),(V,V)为任意一个割集,则为任意一个割集,则 v(f)=f(V,V)f(V,V)对网络对网络 N中任意流量中任意流量v(f)和割集和割集(V,V),有,有v(f)c(V,V)证
5、明证明 w=f(V,V)f(V,V)f(V,V)c(V,V)最大流量最大流量v(f)不大于最小割集的容量,即:不大于最小割集的容量,即:v(f)minc(V,V)在网络中在网络中st的最大流量等于它的最小割集的容量,的最大流量等于它的最小割集的容量,即:即:v(f)=c(V,V)Page 8在网络的发点和收点之间能找到一条链,在该链上所有在网络的发点和收点之间能找到一条链,在该链上所有指向为指向为st的弧,称为前向弧,记作的弧,称为前向弧,记作+,存在存在f0,则称这样的链为,则称这样的链为增广链。增广链。例如下图中,例如下图中,sv2v1v3v4t。网络网络N中的流中的流 f 是最大流当且仅
6、当是最大流当且仅当N中不包含任何增广中不包含任何增广链链Page 9v1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)Page 10求网络最大流的标号算法:求网络最大流的标号算法:由一个流开始,系统地搜寻增广链,然后在此链上增流,由一个流开始,系统地搜寻增广链,然后在此链上增流,继续这个增流过程,直至不存在增广链。继续这个增流过程,直至不存在增广链。(1)找出第一个可行流,(例如所有弧的流量找出第一个可行流,(例如所有弧的流量fij=0。)。)(2)用标号的方法找一条增广链用标号的方法找一条增广链 首先给发点首先给发点s标号标号(),标号中的数字表示允许
7、的最大调整量。标号中的数字表示允许的最大调整量。选择一个点选择一个点 vi 已标号并且另一端未标号的弧沿着某条链已标号并且另一端未标号的弧沿着某条链向收点检查:向收点检查:Page 11 如果弧的起点为如果弧的起点为vi,并且有,并且有fij0,则,则vj标号标号(fji)(3)重复第重复第(2)步,可能出现两种结局:步,可能出现两种结局:标号过程中断,标号过程中断,t无法标号,说明网络中不存在增广链,无法标号,说明网络中不存在增广链,目前流量为最大流。同时可以确定最小割集,目前流量为最大流。同时可以确定最小割集,记已标号的点记已标号的点集为集为V,未标号的点集合为未标号的点集合为V,(V,V
8、)为网络的最小割。为网络的最小割。t得到标号,反向追踪在网络中找到一条从得到标号,反向追踪在网络中找到一条从s到到t得由标号得由标号点及相应的弧连接而成的增广链。继续第点及相应的弧连接而成的增广链。继续第(4)步步Page 12 所所有有非非增增广广链链上上的的弧弧对对增增广广链链上上所所有有后后向向弧弧对对增增广广链链上上所所有有前前向向弧弧ftftff)()(4)修改流量。设原图可行流为修改流量。设原图可行流为f,令,令得到网络上一个新的可行流得到网络上一个新的可行流f。(5)擦除图上所有标号,重复擦除图上所有标号,重复(1)-(4)步,直到图中找不到任何步,直到图中找不到任何增广链,计算
9、结束。增广链,计算结束。Page 13例例6.10 用标号算法求下图中用标号算法求下图中st的最大流量,并找出最小割。的最大流量,并找出最小割。v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)Page 14解:解:(1)先给先给s标号标号()v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()Page 15v1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)()(2)检查与检查与s点相邻的未标号的点,因点相邻的未标号的点,因fs1cs1,故对,故对v1标号标号=min,cs
展开阅读全文