您所在位置：网站首页 > 医学/心理学 > 基础医学第三节最大流问题

第三节最大流问题

14页

卖家[上传人]：资****亨

文档编号：482666187

上传时间：2024-05-09

文档格式：PPT

文档大小：1.07MB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

35 金贝

/ 14 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、第三节第三节最大流问题最大流问题3.1 根本概念与定理根本概念与定理3.2 求解网络最大流的方法标号法求解网络最大流的方法标号法精品课程?运筹学?编辑ppt第三节最大流问题n 流量问题在实际中是一种常见的问题。流量问题在实际中是一种常见的问题。如公路系统中有车辆流量问题，供电系统如公路系统中有车辆流量问题，供电系统中有电流量问题等等。最大流问题是在单中有电流量问题等等。最大流问题是在单位时间内安排一个运送方案，将发点的物位时间内安排一个运送方案，将发点的物质沿着弧的方向运送到收点，使总运输量质沿着弧的方向运送到收点，使总运输量最大。最大。精品课程?运筹学?编辑ppt3.1 3.1 根本概念与定理根本概念与定理设设cijcij为弧为弧i i，j j的容量，的容量，fijfij为弧为弧i i，j j的流量。容量是弧的流量。容量是弧i i，j j单位时间内单位时间内的最大通过能力，流量是弧的最大通过能力，流量是弧i i，j j单位时间单位时间内的实际通过量，流量的集合内的实际通过量，流量的集合f=fijf=fij称为网称为网络的流。发点到收点的总流量记为络的流。发点到收点的总流量记为v=

2、v(f)v=v(f)。设设D=(V,A)D=(V,A)是一有向图且对任意是一有向图且对任意E E均有容量均有容量cij=cij=vivi，vjvj，记，记C=cijC=cijvivi，vjvjA,A,此外此外精品课程?运筹学?编辑pptD中只有一个源vs和汇vt(即D中与vs相关联的弧只能以vs为起点，与vt相关联的弧只能以vt为终点)，那么称D=(V,A,C,vs,vt)为一网络。例6.3.1图6-3-1给出了一张网络，其中：vs为源，vt为汇，弧旁的数字为该段弧的容量cij与流量fij，那么显然有0fijcij。精品课程?运筹学?编辑ppt 最最大大流流问问题题可可以以建建立立如如下下形形式式的的线线性性规规划划数数学学模模型型。图图6-3-1最最大大流流问问题题的的线线性性规规划划数数学学模型为模型为 max v=fs1+fs2 所有弧所有弧(i,j)由由线线性性规规划划理理论论知知，满满足足式式上上式式的的约约束束条条件件的的解解fij称称为为可可行行解解，在在最最大大流流问问题题中中称称为为可可行流行流。精品课程?运筹学?编辑ppt可行流满足以下三个条件：可行流满足以下三个条

3、件：条件条件2 2和条件和条件3 3也称为流量守恒条件。也称为流量守恒条件。精品课程?运筹学?编辑ppt 在图D中，从发点到收点的一条路线称为链，从发点到收点的方向规定为链的方向。与链的方向相同的弧称为前向弧，前向弧集合记为u+，与链的方向相反的弧称为后向弧，后向弧集合记为u-。设f是一个可行流，如果存在一条从发点vs到收点vt到的链u满足：1所有前向弧上fijcij (2)所有后向弧上fij0 那么称链u为增广链.精品课程?运筹学?编辑ppt 设S,TV,ST=,vsS,vtT那么称S，T=vi，vjviS,vjT为图D的一个割集；称CS，T=为割集S，T的容量。显然对任意可行流f及任意割集S，T总有V(f)=C(S,T).故有某个可行流f*及某一割集S*，T*使得V(f*)=CS*，T*，那么f*为D的最大流，S*，T*为最小容量割集。定理6.3.1 图D上的可行流f*是最大流的充要条件是D上不存在关于f*的增广链。精品课程?运筹学?编辑ppt3.2求解网络最大流的方法标号法标号法是一种图上迭代计算方法，该算法首先给出一个初始可行流，通过标号找出一条增广链，然后调整增广链上的流量，

4、得到更大的流量。再用标号找出一条新的增广链，再调整直到标号过程不能进行下去为止，这时的可行流就是最大流。精品课程?运筹学?编辑ppt标号法步骤如下：标号法步骤如下：第第一一步步找找出出一一个个初初始始可可行行流流fij(0),fij(0),例例如如所所有有弧弧的的流量流量fij(0)=0.fij(0)=0.第二步第二步对点进行标号找出一条增广链。对点进行标号找出一条增广链。1 1 起点标号起点标号 2 2选选一一个个点点vivi已已标标号号且且另另一一端端未未标标号号的的弧弧沿着某条链向收点检查沿着某条链向收点检查 a a如如果果弧弧是是前前向向弧弧且且有有fijfijcijcij，那那么么vjvj标标号号 j=cijfij j=cijfijb b如如果果弧弧是是后后向向弧弧且且有有fij0fij0，那那么么vjvj标标号号j=fijj=fij精品课程?运筹学?编辑ppt 当收点已得到标号时，说明已找到增广链，当收点已得到标号时，说明已找到增广链，依据依据v的标号反向追踪得到一条增广链。当收的标号反向追踪得到一条增广链。当收点不能得到标号时，说明不存在增广链，计算点不能得到标号时，

5、说明不存在增广链，计算结束结束第三步第三步调整流量调整流量(1)求求增增广广链链上上点点的的vi标标号号的的最最小小值值，得得到到调调整整量号量号 =(2)调整流量调整流量精品课程?运筹学?编辑ppt fij+vi，vju+f1=fij vi，vj)u-fij vi，vj)u得到新的可行流f1，去掉所有标号，返回到第二步从发点重新标号寻找增广链，直到收点不能标号为止。精品课程?运筹学?编辑ppt例例6.3.26.3.2用用标标号号法法求求网网络络最最大大流流图图6-3-16-3-1，弧旁数字为弧旁数字为cij cij，fij(0)fij(0)。解解 1 1 标号过程。见图标号过程。见图6-3-26-3-2。2 2 增增广广链链为为vsvs，v1v1，v2v2，v3v3，vt vt 注意注意v2v2，v1v1，v3v3，v2v2u-u-。3 3调整量调整量=2=2调整后得图调整后得图6-3-36-3-3。4 4 二次标号过程。见图二次标号过程。见图6-3-36-3-3。精品课程?运筹学?编辑ppt 标号无法进行下去，最大流流量V(f*)=3+6=9，最小割集S*，T*,S*=vs,T*=v1，v2，v3，v4，vt。精品课程?运筹学?编辑ppt

《第三节最大流问题》由会员资****亨分享，可在线阅读，更多相关《第三节最大流问题》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源