《运筹学课程设计关键要素.docx》由会员分享,可在线阅读,更多相关《运筹学课程设计关键要素.docx(25页珍藏版)》请在优知文库上搜索。
1、芟场科笈*运筹学课程设计网络日勺数据传播最大流问题的模型探讨院(系)名称XXXXXX专业班级XXXXX学号XXXXXX学生姓名XXXXXX指导教师XXXXXX2023年05月26日课程设计任务书20232023学年第二学期专业班级:XXXXX学号:XXXXX姓名:XXXXX课程设计名称:运筹学设计题目:网络B数据传播最大流问题B模型探讨完毕期限:自2023年05月19日至月23年05月26日1周设计根据、规定及重要内容:一、设计目B一种网络中流量B最大值对企业尤为重要一种详细量化B处理方案B制定是一种很棘手B问题.本论文结合建模知识,建立实际最大流问题的合理对BB模型,运用线性规划和最大流B知
2、识,对上述问题建立合适的数学模型,并借助LlNGo软件求解.对上述问题给出一种量化可行的处理方窠,从而使网络中的流量抵达最大化,从而更好的合理的处理实际问题,将所学理论知识更好的服务于实践.二、设计规定结合实际问题的例子,以线性规划理论和最大流理论为基础,建立最大流问题的模型,运用LINGO软件求解,探讨网络中最大流的问题.给出一种最优化的处理方案,使网络中B流量抵达最大.三、参照文献1刁在筠,刘桂真,宿洁,马建华.运筹学M.北京:高等教育出版社,2023.2韩中庚,郭晓丽,杜剑平,宋留勇.实用运筹学M.北京:清华大学出版社,2023.3谢金星.数学模型与LINGo软件M.北京:清华大学出版社
3、,2023.计划答辩时间:2023年05月26日指导教师(签字):教研室主任(签字):同意日期:年月日网络的数据传播最大流问题的探讨摘要网络最大流问题是网络B另一种基本问题.许多系统包括了流量问题.例如交通系统有车流量,金融系统有现金流,控制系统有信息流等.许多流问题重要是确定此类系统网络所能承受的最大流量以及怎样抵达这个最大流量.同样地,网络的数据传播最大流问题也采用了这样的原理,运用了线性规划模型求解了最大流问题.运用LlNGO软件编程得到了求解成果为,计算机网络中,从节点1到节点9的最大传播带宽为14.2Mbs.关键词:最大流,LlNGo软件,模型1问题重述错误!未定义书签。2探讨过程错
4、误!未定义书签。2.1 参照知识背景错误!未定义书签。2.1.1 数学模型背景错误!未定义书签。2.1.2 最大流问题背景错误!未定义书签。2.1.3 1.INGo软件背景错误!未定义书签。2.2 建模过程错误!未定义书签。2.2.1 模型假设错误!未定义书签。2.2.2 符号阐明错误!未定义书签。2.2.3 问题分析错误!未定义书签。2.2.4 建立最大流问题的J模型错误!未定义书签。2.2.5 模型求解错误!未定义书签。3实际应用错误!未定义书签。总结错误!未定义书签。1问题重述分组互换技术在计算机网络发挥着重要的作用,从源节点到目的节点传送文献不再需要固定的一条“虚途径”,而是将文献分割
5、为几种分组,再通过不同样B途径传送到目的节点,目的节点再根据分组信息进行重组,还原文献,分组互换技术具有文献传播时不需要一直占用一条线路,不怕单条线路掉线,多路传播提高传播速率等长处.目前考察如图所示的网络,假设图中连接两个节点间的数字体现两互换机间的可用带宽,建立数学模型,计算从节点1到节点9时最大传播带宽是多少?图1计算机网络带宽示意图(单位:Mbs)2探讨过程本次设计在综合理解一定日勺数学模型、运筹学中日勺最大流、LINGO软件中某些知识的基础上,以图论理论为基础,对实际例子进行一定的分析后,建立合理的最大流问题模型.然后,运用LINGo软件求得成果.给出节点1到节点9的最大传播带宽是多
6、少.2.1参照知识背景数学模型背景一提到数学,人们首先想到的是它的抽象和难懂,以及它0严密的推理和证明,也正是由于数学的高度抽象性,才决定了它也具有广泛的应用性.要运用数学措施处理实际问题,不管这个问题是来自工程、经济、金融还是社会、生命科学领域,都必须设法在数学与实际问题之间架设一座桥梁,首先要将这个实际问题化为一种对应的数学问题,另首先对这个数学问题进行分析与计算,最终将所求的解答回归为现实,就是数学模型,而架设桥梁B过程,就称为数学建模,即为所考察B实际问题建立数学模型.当然,建立数学模型的过程一次成功B也许性不是很大.只有最终通过实践检查为有效的数学模型,才能算是成功的数学模型.2.1
7、.2 最大流问题背景图论是运筹学的一种重要分支,伴随计算机时逐渐普及,它越来越急速的渗透到工农业生产、商业活动、军事行动和科学研究B各个方面.它是以图为研究对象的,这里所说B图是由若干给定B点及连接两点的线所构成B图形,这种图形一般用来描述某些事物之间B某种特定关系,用点代表事物,用连接两点的线体现对应的两个事物之间具有的这种特定关系.图论其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、流体动力学、心理学、社会学、交通管理、电信网络等领域.尤其是在20世纪50年代后来,伴随科学技术的发展和计算机的出现与广泛0应用,促使了运筹学B发展,图论的理论也得到了深入B发展.尤其是庞大B复杂工程
8、系统和管理问题都可以转化为图B问题,从而可以处理诸多工程设计和管理决策中的最优化问题.诸如像完毕工程任务B时间至少、距离最短、费用至少、收益最大、成本最低等实际问题.因此,图论在数学、工程技术及经济等各个领域都受到了越来越广泛日勺重视.其中,最大流问题是是图论中最常见的问题.1.lNGo软件背景1.ing。是用来求解线性和非线性优化问题的简易工具.LINGO内置了一种建立最优化模型B语言,可以简便地体现大规模问题,运用LINGO高效B求解器可迅速求解并分析成果.LINGO全称是LinearINteractiveandGeneralOptimizerB缩写交互式的J线性和通用优化求解器.它是一套
9、设计用来协助您迅速,以便和有效的构建和求解线性,非线性,和整数最优化模型的功能全面的工具.包括功能强大的建模语言,建立和编辑问题0全功能环境,读取和写入Excel和数据库B功能,和一系列完全内置的求解程序.LindoZLingo软件作为著名的专业优化软件,其功能比较强、计算效果比很好,与那些包括部分优化功能B非专业软件相比,一般具有明显0优势.此外,LindoZLingo软件使用起来非常简便,很轻易学会,在优化软件(尤其是运行于个人电脑上的优化软件)市场占有很大份额,在国外运筹学类的教科书中也被广泛用做教学软件.2.2建模过程2.2.1 模型假设(1)假设网络传播过程中没有流量损失.(2)假设
10、网络传播没有中断.(3)假设网络信号良好.2.2.2 符号阐明F:分组传播方式矩阵时体现Zj:从节点i到节点jB实际传播带宽C:容量矩阵V(/):网络传播带宽值P,C,f:边集2.2.3 问题分析网络B数据传播问题是有关图论中B最大流问题,如图1就是一种网络,各边上B数值代表该边的容量,其中标号为1日勺点为源,标号为9日勺点为汇,其他节点为中间顶点.实际中,可以把“网络”当作是水管构成日勺网络,“容量”当作是水管的单位时间的最大通过量,而“流”则是水管网络中流动的水,“源”是水管网络的水的注入口,“汇”是水管网络水的流出口.对于所有中间顶点,流入rJ总量应当等于流出09总量,一种网络B流量值定
11、义为从源流出的总流量,不难得到网络B总流量也等于流入汇的总流量,综上所述,我们可以得到网络中B最大流B值.2.2.4 建立最大流问题的模型将此问题视为一种网络的最大流问题,寻找网络的J最大流问题,实际上可以化为求解一种特殊的1线性规划问题,即求一组函数4=(匕,匕)在满足(/(井了。(,口)和V(),v=v/(匕)-Zf(W0)=,O,y=V,vw匕,匕的条件下,使V()有最大值的问题,即UEVH,6V-V(v=v,.maxVzVrH二匕,力一,匕eV,4匕,匕,将分组的传播方式用如下矩阵来刻画:UjWVwV-V(),v.=vr九九f9%fl2%储2其中左体现从节点i到节点j时实际传播带宽,记
12、容量矩阵为:O2.5O5.66.1OOOOOO7.1OO3.6OOOOOOOOOO3.4OOOOO4.9O7.4OOC=O2.4OOO7.25.7OOOO3.8OOOO5.34.5OOOOO3.8OO6.7OOOOOOOO7.4OOOOOOOOO由此可以建立线性规划模型如下:maxVfS.t.jeVkeVVz(z=l)-VzO=9)0(/1,9)OFC.2.2.5模型求解该模型B求解,采用LlNGO软件,其对应的程序如下:MODEL:sets:nodesl,2,3z4,5,6z7z8z9;!节点集arcs(nodes,nodes):p,c,f;!边集endsetsdata:!邻接矩阵P=O,1
13、,0,1,1,0,0,0,0,1,0,1,0,1,1,0,0,O,0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,lzlz0zlz0zlzlz0z0z0,1,1,0,1,0,1,1,1,0,0,0,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0,0,0,1,1,1,0;!容量矩阵C=O,2.5,0,5.6,6.1,0,0,0,0,0,0,7.1,0,0,3.6,0,0,0,0,0,0,0,0,0,0,3.4,0,0,0,0,0,4.9,0,7.4,0,0,0,2.4,0,0,0,7.2,5.7,0,0,0,0,3.8,0,0,0,0,5.3,4.
14、5,0,0,0,0,0,3.8,0,0,6.7,Oz0,0,0,Oz0,0,0,7.4z0,0,0,O,0,0,0,Oz0;enddatamax=flow;!清除源和汇Ofor(nodes(i)i#ne#l#and#i#ne#size(nodes):!中间节点约束0sum(nodes(j):p(izj)*f(i,j)=Osum(nodes(j):P(j,i)*f(j,i);SUln(nodes(i):p(lzi)*f(l,i)=flow7!源汇节点约束0for(arcs:bnd(0,f,c)/!容量约束END运行该程序,得到运行成果如下:Globaloptimalsolutionfound.Objectivevalue:14.20230Infeasibilities:0.000000Totalsolveriterations:11VariableValue