运筹学课程设计之最大网速问题的数学模型.doc_第1页
运筹学课程设计之最大网速问题的数学模型.doc_第2页
运筹学课程设计之最大网速问题的数学模型.doc_第3页
运筹学课程设计之最大网速问题的数学模型.doc_第4页
运筹学课程设计之最大网速问题的数学模型.doc_第5页
已阅读5页,还剩19页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

最大网速问题的数学模型最大网速问题的数学模型摘要本题给出了各节点之间的网络流图,需求解它们之间的最大流,即最大网速,为了能有效地解决此问题,我们首先利用求解最大流的标号法对网络图中的可增广链进行逐一分析,并对该链上的流量进行调整,直到该图中没有可增广链后,求得节点1到节点6的最大网速为6兆,然后再通过MATLAB编程实现对标号法求解的结果进行验证。最后,又通过提高各节点之间的网速来达到提高从节点1到节点6网速的目的,得出了各链之间增加的具体流量。即到的容量应增加到,到的容量应增加到,到与到的容量都应增加到。当然若,即,则到的容量不变。同理,若,即,则到与到的容量也不变。关键词:网络最大流;可增广链;网络流图;MATLAB;目 录一 问题的提出.1二 模型假设.1三 符号说明.2四 问题的分析.2五 模型的建立与求解.2 5.1 模型的建立.2 5.1.1 可行流.3 5.1.2 割集.3 5.1.3 最大流-最小割定理.45.1.4 可增广链推论.4 5.1.5 寻求最大流的方法.4 5.1.6 可行流调整算法.45.1.7 最大流的标号算法.45.2 模型的求解.5六 模型的优化.136.1 网络最大流的算法拓展.136.2 问题的优化求解.14模型评价.16参考文献.17附录.18一、问题的提出下图为一网络,节点1到节点2的宽带带宽为6兆,节点1到节点3的宽带带宽为2兆,节点2到节点4的宽带带宽为3兆,节点4到节点6的宽带带宽为2兆,求节点1到节点6的最大网速。进一步,若想提高节点1到节点6的最大网速x兆,如何实现?二、模型假设2.1 假设流量在网络传输中没有损失;2.2 假设环境对网速没有影响;三、符号说明3.1 符号说明符号含义、某一顶点处的标号、始点和终点的标号标号点集合为标号点集合割集可行流/从到的流量/从到的流量到所在链上的容量边集流量调整量四、问题分析问题的分析:通过对题目的剖析,我们可以知道,要想求解最大流,我们必须要保证在从节点1到节点6之间没有可增广链,因此本题求解的方向是从如何求解可增广链,然后逐步求得最大流。五、模型建立及求解5.1模型的建立由题中所给图形,我们可以对其标号做一点修改,得到图1:图1 网络传输过程中的流量图为了方便对问题的求解,我们引入以下概念和定理:5.1.1 可行流由书中所给定义知非负数为边的容量,本文中即指带宽,而图中(8,1)对应(,)其中表示任一边(,)的流量,本文中即指单位成本,通过容量可以构建一个容量网络。要想求最大流,则找到所有的可行流,而可行流需满足如下条件:(1)容量限制条件:对G中每条边,有;(2)平衡条件:对中间点,有,即物资的输入量与输出量相等。5.1.2割集容量网络,为收、发点,若有边集为的子集,将G分为两个子图和,其顶点集合分别记为,分属,满足:不连通;为的真子集,而仍连通,则称为G的割集,记为。另外,割集中所有始点在,终点在的边的容量之和,称为的割集容量,记为。5.1.3 最大流-最小割定理任一个网络G中,从到的最大流的流量等于分离、的最小割的容量。5.1.4 可增广链推论可行流是最大流的充要条件是不存在从到的(关于的)可增广链。5.1.5 寻求最大流的方法:从一个可行流开始,寻求关于这个可行流的可增广链,若存在,则可经过调整,得到一个新的可行流,其流量比原来的可行流要大,重复这个过程,知道不存在关于该流的可增广链时就得到了最大流。5.1.6 可行流调整算法根据的定义,中的前向边上必有,后向边上必有。令取我们把修改为:不难验证仍为可行流。5.1.7 最大流的标号算法:用标号法寻求网络中最大流的基本思想是寻找可增广链,使网络的流量得到增加,直到最大为止。即首先给出一个初始流,这样的流是存在的,例如零流。如果存在关于它的可增广链,那么调整该链上每条弧上的流量,就可以得到新的流。对于新的流,如果仍存在可增广链,则用同样的方法使流的值增大,继续这个过程,直到网络中不存在关于新得到流的可增广链为止,则该流就是所求的最大流。这种方法分为以下两个过程:1.标号过程:通过标号过程寻找一条可增广链;2.调整过程:沿着可增广链的逆方向依次调整网络的流量。这两个过程的步骤分述如下。(A)标号过程:(i)给发点标号为。(ii)若顶点已经标号,则对的所有未标号的邻接顶点按以下规则标号: 若,且时,令,则给顶点标号为,若,则不给顶点标号。,且,令,则给标号为,若,则不给标号。(iii)不断地重复步骤(ii)直到收点被标号,或不再有顶点可以标号为止。当被标号时,表明存在一条从到的可增广链,则转向调整过程(B)。如若点不能被标号,且不存在其它可以标号的顶点时,表明不存在从到的可增广链,算法结束,此时所获得的流就是最大流。(B)调整过程(1)令(可增广链简写为KZGL,前向边简称QXB,后向边简写为HXB)(2)去掉所有标号,回到第一步,对可行流重新标号。5.2 模型的求解对于本题,我们采取标号法进行求解。我们对进行标号,检查邻接点,发现满足,且。令则给标号。同理可知给以标号。检查的邻接点,知已标号,发现满足,且。令则给标号。检查的邻接点,发现满足,且。令则给标号。由于已得标号,说明存在可增广链,故标号过程结束,得图2:图2 到的可增广链图由图中可知,可增广链为。因为找到了一条可增广链,所以转入调整过程,取为调整量,由点开始,由逆可增广链方向按标号找到点。令。, 再由点的标号找到前一个点,并令。按的标号,找到前一个点,并令。调整过程结束,调整中的可增广链见图2的双线边,调整后的可行流情况见图3:图3 经第一次标号调整后的可行流图至此,重新开始标号,寻找下一条可增广链。首先对进行标号,检查邻接点,发现满足,且。令则给标号。检查的邻接点,知已标号,发现满足,且。令则给标号。检查的邻接点,发现满足,但不满足标号条件。因此检查的邻接点,发现满足,且。因此令则给标号。检查的邻接点,发现满足,且。令则给标号。检查的邻接点,发现满足,且。令则给标号。由于已得标号,说明存在可增广链,故标号过程结束,得图4:图4 到的可增广链图由图中可知,可增广链为。因为找到了一条可增广链,所以转入调整过程,取为调整量,由点开始,由逆可增广链方向按标号找到点。令。, 再由点的标号找到前一个点,并令。按的标号,找到前一个点,并令。按的标号,找到前一个点,并令。按的标号,找到前一个点,并令。调整过程结束,调整中的可增广链见图4的双线边,调整后的可行流情况见图5:图5 经第二次标号调整后的可行流图至此,重新开始标号,寻找下一条可增广链。求解方法同上,由于到段不满足标号条件,故根据可得标号过程结束后的可增广链图见图6:图6 到的可增广链图由图中可知,可增广链为。因为找到了一条可增广链,所以转入调整过程,取为调整量,由点开始,由逆可增广链方向按标号找到点。令。, 再由点的标号找到前一个点,并令。按的标号,找到前,并令。按的标号,找到前一个点,并令。调整过程结束,调整中的可增广链见图6的双线边,调整后的可行流情况见图7:图7 经第三次标号调整后的可行流图至此,重新开始标号,寻找下一条可增广链。求解方法同上,由于到及段均不满足标号条件,故根据可得标号过程结束后的可增广链图见图8:图8 到的可增广链图由图中可知,可增广链为。因为找到了一条可增广链,所以转入调整过程,取为调整量,由点开始,由逆可增广链方向按标号找到点。令。, 再由点的标号找到前一个点,并令。按的标号,找到前一个点,并令。调整过程结束,调整中的可增广链见图8的双线边,调整后的可行流情况见图9:图9 经第四次标号调整后的可行流图至此,又要重新开始标号,寻找下一条可增广链。求解方法依然同上,由图9可知到段及到段均不满足标号条件,故根据知图9中已不存在可增广链,因此可得如图10所示的最小割图:图10 最小割示意图由图知标号点集合为;未标号点集合为;最小割集为;割集容量为,与最大流的流量相等。综上所述,我们已经求得节点1到节点6的最大网速为6兆。为了验证上述算法的正确性,我们又通过MATLAB编程(程序详见附录1)计算出其最大流为 0 4 2 0 0 0 0 0 1 3 0 0= 0 0 0 0 4 0 0 0 1 0 0 2 0 0 0 0 0 4综合结果可知,我们求得的最大网速是正确的。六、模型的优化6.1 网络最大流的算法拓展:6.1.1 Ford-Fulkerson增广路方法 6.1.1.1 Ford-Fulkerson标号算法(最简单的实现)分别记录这一轮扩展过程中的每个点的前驱与到该节点的增广最大流量,从源点开始扩展,每次选择一个点(必须保证已经扩展到这个点),检查与它连接的所有边,并进行扩展,直到扩展到t。6.1.1.2 最大容量增广路算法 每次找一条容量最大的增广路来增广,找的过程类似Dijkstra,实现起来相当简单。6.1.1.3 Edmonds-Karp,最短路增广算法的BFS实现 每次找一条最短的增广路,BFS是一个可以很方便的实现思想。6.1.1.4 距离标号算法最短路增广的O(n)寻找实现,使用距离函数d:dt=0;d0 maxf=zeros(1,n);pred=zeros(1,n); list=1;record=list;maxf(1)=M; while (isempty(list)&(maxf(n)=0) flag=list(1);list(1)=; index1=(find(u(flag,:)=0); label1=index1(find(u(flag,index1). -f(flag,index1)=0); label1=setdiff(label1,record); list=union(list,label1); pred(label1)=flag; maxf(label1)=min(maxf(flag),u(flag,label1). -f(flag,label1); record=union(record,label1); label2=find(f(:,flag)=0); label2=label2; label2=setdiff(label2,record); list=union(list,label2); pred(label2)=-flag; maxf(label2)=min(maxf(flag),f(label2,flag); record=union(record,label2); end if

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论