《运筹学》课程设计网络的数据传输最大流问题的模型探讨院（系）名称 xxxxxx专业班级xxxxx学号xxxxxx学生姓名 xxxxxx指导教师 xxxxxx2014年05 月26日课程设计任务书2013—2014学年第二学期专业班级：xxxxx 学号：xxxxx 姓名：xxxxx课程设计名称：运筹学设计题目：网络的数据传输最大流问题的模型探讨完成期限：自2014 年05 月19 日至2014年05 月26 日 1 周设计依据、要求及主要内容：一、设计目的一个网络中流量的最大值对企业尤为重要,而一个具体量化的解决方案的制定是一个很棘手的问题．本论文结合建模知识，建立实际最大流问题的合理正确的模型，利用线性规划和最大流的知识，对上述问题建立适当的数学模型，并借助LINGO软件求解．对上述问题给出一个量化可行的解决方案，从而使网络中的流量达到最大化，从而更好的合理的解决实际问题，将所学理论知识更好的服务于实践．二、设计要求结合实际问题的例子，以线性规划理论和最大流理论为基础，建立最大流问题的模型，利用LINGO软件求解，探讨网络中最大流的问题．给出一个最优化的解决方案，使网络中的流量达到最大．三、参考文献[1] 刁在筠,刘桂真,宿洁,马建华.运筹学[M].北京:高等教育出版社,2007.[2] 韩中庚,郭晓丽,杜剑平,宋留勇.实用运筹学[M].北京:清华大学出版社,2011.[3] 谢金星.数学模型与LINGO软件[M].北京:清华大学出版社,2005. 计划答辩时间：2014年05月26日指导教师（签字）：教研室主任（签字）：批准日期：年月日网络的数据传输最大流问题的探讨摘要网络最大流问题是网络的另一个基本问题．许多系统包含了流量问题．例如交通系统有车流量，金融系统有现金流，控制系统有信息流等．许多流问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量．同样地，网络的数据传输最大流问题也采用了这样的原理，利用了线性规划模型求解了最大流问题．运用LINGO软件编程得到了求解结果为，计算机网络中，从节点1到节点9的最大传输带宽为14.2Mb/s.关键词：最大流，LINGO软件，模型目录1 问题重述 (1)2 探讨过程 (1)2.1 参考知识背景 (1)2.1.1 数学模型背景 (1)2.1.2 最大流问题背景 (2)2.1.3 LINGO软件背景 (2)2.2 建模过程 (3)2.2.1 模型假设 (3)2.2.2 符号说明 (3)2.2.3 问题分析 (3)2.2.4 建立最大流问题的模型 (4)2.2.5 模型求解 (5)3实际应用 (10)总结 (11)参考文献 (12)1问题重述分组交换技术在计算机网络发挥着重要的作用，从源节点到目的节点传送文件不再需要固定的一条“虚路径”，而是将文件分割为几个分组，再通过不同的路径传送到目的节点，目的节点再根据分组信息进行重组，还原文件，分组交换技术具有文件传输时不需要始终占用一条线路，不怕单条线路掉线，多路传输提高传输速率等优点．现在考察如图所示的网络，假设图中连接两个节点间的数字表示两交换机间的可用带宽，建立数学模型，计算从节点1到节点9的最大传输带宽是多少？图1 计算机网络带宽示意图(单位:Mb/s)2探讨过程本次设计在综合了解一定的数学模型、运筹学中的最大流、LINGO软件中一些知识的基础上，以图论理论为基础，对实际例子进行一定的分析后，建立合理的最大流问题模型．然后，利用LINGO软件求得结果．给出节点1到节点9的最大传输带宽是多少．2.1 参考知识背景2.1.1数学模型背景一提到数学，人们首先想到的是它的抽象和难懂，以及它的严密的推理和证明，也正是由于数学的高度抽象性，才决定了它也具有广泛的应用性．要运用数学方法解决实际问题，不论这个问题是来自工程、经济、金融还是社会、生命科学领域，都必须设法在数学与实际问题之间架设一座桥梁，首先要将这个实际问题化为一个相应的数学问题，其次对这个数学问题进行分析与计算，最后将所求的解答回归为现实，就是数学模型，而架设桥梁的过程，就称为数学建模，即为所考察的实际问题建立数学模型．当然，建立数学模型的过程一次成功的可能性不是很大．只有最后经过实践检验为有效的数学模型，才能算是成功的数学模型．2.1.2 最大流问题背景图论[1]是运筹学的一个重要分支，随着计算机的逐渐普及，它越来越急速的渗透到工农业生产、商业活动、军事行动和科学研究的各个方面．它是以图为研究对象的，这里所说的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应的两个事物之间具有的这种特定关系．图论其广阔的应用领域涵盖了人类学、计算机科学、化学、环境保护、流体动力学、心理学、社会学、交通管理、电信网络等领域．特别是在20世纪50年代以后，随着科学技术的发展和计算机的出现与广泛的应用，促使了运筹学的发展，图论的理论也得到了进一步的发展．特别是庞大的复杂工程系统和管理问题都可以转化为图的问题，从而可以解决很多工程设计和管理决策中的最优化问题．诸如像完成工程任务的时间最少、距离最短、费用最少、收益最大、成本最低等实际问题．因此，图论在数学、工程技术及经济等各个领域都受到了越来越广泛的重视．其中，最大流问题是是图论中最常见的问题．2.1.3 LINGO软件背景Lingo [3]是用来求解线性和非线性优化问题的简易工具．LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果．LINGO全称是Linear INteractive and General Optimizer的缩写---交互式的线性和通用优化求解器．它是一套设计用来帮助您快速,方便和有效的构建和求解线性,非线性,和整数最优化模型的功能全面的工具．包括功能强大的建模语言,建立和编辑问题的全功能环境,读取和写入Excel和数据库的功能,和一系列完全内置的求解程序．Lindo/Lingo软件作为著名的专业优化软件，其功能比较强、计算效果比较好，与那些包含部分优化功能的非专业软件相比，通常具有明显的优势．此外，Lindo/Lingo软件使用起来非常简便，很容易学会，在优化软件（尤其是运行于个人电脑上的优化软件）市场占有很大份额，在国外运筹学类的教科书中也被广泛用做教学软件．2.2建模过程2.2.1 模型假设（1）假设网络传输过程中没有流量损失．（2）假设网络传输没有中断．（3）假设网络信号良好．2.2.2 符号说明F：分组传输方式矩阵的表示f：从节点i到节点j的实际传输带宽ijC：容量矩阵()V f：网络传输带宽值p c f：边集,,2.2.3 问题分析网络的数据传输问题是关于图论中的最大流问题，如图1就是一个网络，各边上的数值代表该边的容量，其中标号为1的点为源，标号为9的点为汇，其他节点为中间顶点．实际中，可以把“网络”看成是水管组成的网络，“容量”看成是水管的单位时间的最大通过量，而“流”则是水管网络中流动的水，“源”是水管网络的水的注入口，“汇”是水管网络水的流出口．对于所有中间顶点，流入的总量应该等于流出的总量，一个网络的流量值定义为从源流出的总流量，不难得到网络的总流量也等于流入汇的总流量，综上所述，我们可以得到网络中的最大流的值．2.2.4 建立最大流问题的模型将此问题视为一个网络的最大流问题，寻找网络的最大流问题,事实上可以化为求解一个特殊的线性规划问题,即求一组函数{}{(,)}ij i j f f v v =在满足0(,)(,)f u v c u v ≤≤和(),;(,)(,)0,,,(),.s s t u V w V t V f v v f v u f w v v V v v v V f v v ∈∈=⎧⎪-==≠⎨⎪-=⎩∑∑的条件下，使()V f 有最大值的问题，即max V ,,=0,,,,..(),.0(,)j j ff i s ij ji i i s t UV w V i t ij ij i j V v v f f v V v v v s t V f v v f c v v V ∈∈⎧=⎧⎪⎪-∈≠⎨⎪⎨⎪-=⎩⎪⎪≤≤∈⎩∑∑将分组的传输方式用以下矩阵来刻画：111219212229919299f f f f f f F f f f ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦，其中ij f 表示从节点i 到节点j 的实际传输带宽，记容量矩阵为：0 2.50 5.6 6.10000007.100 3.60000000000 3.400000 4.907.4000 2.40007.2 5.70000 3.80000 5.3 4.500000 3.800 6.7000000007.4000000000C ⎡⎤⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥=⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦，由此可以建立线性规划模型如下：max V (1)=(9)..0(1,9)0.ffij ki f j V k V V i f f V i s t i F C ∈∈⎧=⎧⎪⎪--=⎪⎨⎨⎪≠⎩⎪⎪≤≤⎩∑∑2.2.5 模型求解该模型的求解，采用LINGO软件，其相应的程序如下：MODEL:sets:nodes/1,2,3,4,5,6,7,8,9/; ！节点集arcs(nodes,nodes):p,c,f; ！边集endsetsdata:！邻接矩阵p=0,1,0,1,1,0,0,0,0, 1,0,1,0,1,1,0,0,0, 0,1,0,0,0,1,0,1,0,1,0,0,0,1,0,1,0,0,1,1,0,1,0,1,1,0,0, 0,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=0,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.5,0,0,0,0,0,3.8,0,0,6.7, 0,0,0,0,0,0,0,0,7.4, 0,0,0,0,0,0,0,0,0;enddatamax=flow;@for(nodes(i)|i#ne#1#and#i#ne#@size(nodes): ！去除源和汇@sum(nodes(j):p(i,j)*f(i,j)) ！中间节点约束=@sum(nodes(j):p(j,i)*f(j,i)));@sum(nodes(i):p(1,i)*f(1,i))=flow; ！源汇节点约束@for(arcs:@bnd(0,f,c)); ！容量约束END运行该程序，得到运行结果如下：Global optimal solution found.Objective value: 14.20000Infeasibilities: 0.000000Total solver iterations: 11Variable Value Reduced CostFLOW 14.20000 0.000000P( 1, 1) 0.000000 0.000000P( 1, 2) 1.000000 0.000000P( 1, 3) 0.000000 0.000000P( 1, 4) 1.000000 0.000000P( 1, 5) 1.000000 0.000000P( 1, 6) 0.000000 0.000000P( 1, 7) 0.000000 0.000000 P( 1, 8) 0.000000 0.000000 P( 1, 9) 0.000000 0.000000 P( 2, 1) 1.000000 0.000000 P( 2, 2) 0.000000 0.000000 P( 2, 3) 1.000000 0.000000 P( 2, 4) 0.000000 0.000000 P( 2, 5) 1.000000 0.000000 P( 2, 6) 1.000000 0.000000 P( 2, 7) 0.000000 0.000000 P( 2, 8) 0.000000 0.000000 P( 2, 9) 0.000000 0.000000 P( 3, 1) 0.000000 0.000000 P( 3, 2) 1.000000 0.000000 P( 3, 3) 0.000000 0.000000 P( 3, 4) 0.000000 0.000000 P( 3, 5) 0.000000 0.000000 P( 3, 6) 1.000000 0.000000 P( 3, 7) 0.000000 0.000000 P( 3, 8) 1.000000 0.000000 P( 3, 9) 0.000000 0.000000 P( 4, 1) 1.000000 0.000000 P( 4, 2) 0.000000 0.000000 P( 4, 3) 0.000000 0.000000 P( 4, 4) 0.000000 0.000000 P( 4, 5) 1.000000 0.000000 P( 4, 6) 0.000000 0.000000 P( 4, 7) 1.000000 0.000000 P( 4, 8) 0.000000 0.000000 P( 4, 9) 0.000000 0.000000 P( 5, 1) 1.000000 0.000000 P( 5, 2) 1.000000 0.000000 P( 5, 3) 0.000000 0.000000 P( 5, 4) 1.000000 0.000000 P( 5, 5) 0.000000 0.000000 P( 5, 6) 1.000000 0.000000 P( 5, 7) 1.000000 0.000000 P( 5, 8) 0.000000 0.000000 P( 5, 9) 0.000000 0.000000 P( 6, 1) 0.000000 0.000000 P( 6, 2) 1.000000 0.000000 P( 6, 3) 1.000000 0.000000 P( 6, 4) 0.000000 0.000000 P( 6, 5) 1.000000 0.000000P( 6, 6) 0.000000 0.000000 P( 6, 7) 1.000000 0.000000 P( 6, 8) 1.000000 0.000000 P( 6, 9) 1.000000 0.000000 P( 7, 1) 0.000000 0.000000 P( 7, 2) 0.000000 0.000000 P( 7, 3) 0.000000 0.000000 P( 7, 4) 1.000000 0.000000 P( 7, 5) 1.000000 0.000000 P( 7, 6) 1.000000 0.000000 P( 7, 7) 0.000000 0.000000 P( 7, 8) 0.000000 0.000000 P( 7, 9) 1.000000 0.000000 P( 8, 1) 0.000000 0.000000 P( 8, 2) 0.000000 0.000000 P( 8, 3) 1.000000 0.000000 P( 8, 4) 0.000000 0.000000 P( 8, 5) 0.000000 0.000000 P( 8, 6) 1.000000 0.000000 P( 8, 7) 0.000000 0.000000 P( 8, 8) 0.000000 0.000000 P( 8, 9) 1.000000 0.000000 P( 9, 1) 0.000000 0.000000 P( 9, 2) 0.000000 0.000000 P( 9, 3) 0.000000 0.000000 P( 9, 4) 0.000000 0.000000 P( 9, 5) 0.000000 0.000000 P( 9, 6) 1.000000 0.000000 P( 9, 7) 1.000000 0.000000 P( 9, 8) 1.000000 0.000000 P( 9, 9) 0.000000 0.000000 C( 1, 1) 0.000000 0.000000 C( 1, 2) 2.500000 0.000000 C( 1, 3) 0.000000 0.000000 C( 1, 4) 5.600000 0.000000 C( 1, 5) 6.100000 0.000000 C( 1, 6) 0.000000 0.000000 C( 1, 7) 0.000000 0.000000 C( 1, 8) 0.000000 0.000000 C( 1, 9) 0.000000 0.000000 C( 2, 1) 0.000000 0.000000 C( 2, 2) 0.000000 0.000000 C( 2, 3) 7.100000 0.000000C( 2, 5) 0.000000 0.000000 C( 2, 6) 3.600000 0.000000 C( 2, 7) 0.000000 0.000000 C( 2, 8) 0.000000 0.000000 C( 2, 9) 0.000000 0.000000 C( 3, 1) 0.000000 0.000000 C( 3, 2) 0.000000 0.000000 C( 3, 3) 0.000000 0.000000 C( 3, 4) 0.000000 0.000000 C( 3, 5) 0.000000 0.000000 C( 3, 6) 0.000000 0.000000 C( 3, 7) 0.000000 0.000000 C( 3, 8) 3.400000 0.000000 C( 3, 9) 0.000000 0.000000 C( 4, 1) 0.000000 0.000000 C( 4, 2) 0.000000 0.000000 C( 4, 3) 0.000000 0.000000 C( 4, 4) 0.000000 0.000000 C( 4, 5) 4.900000 0.000000 C( 4, 6) 0.000000 0.000000 C( 4, 7) 7.400000 0.000000 C( 4, 8) 0.000000 0.000000 C( 4, 9) 0.000000 0.000000 C( 5, 1) 0.000000 0.000000 C( 5, 2) 2.400000 0.000000 C( 5, 3) 0.000000 0.000000 C( 5, 4) 0.000000 0.000000 C( 5, 5) 0.000000 0.000000 C( 5, 6) 7.200000 0.000000 C( 5, 7) 5.700000 0.000000 C( 5, 8) 0.000000 0.000000 C( 5, 9) 0.000000 0.000000 C( 6, 1) 0.000000 0.000000 C( 6, 2) 0.000000 0.000000 C( 6, 3) 3.800000 0.000000 C( 6, 4) 0.000000 0.000000 C( 6, 5) 0.000000 0.000000 C( 6, 6) 0.000000 0.000000 C( 6, 7) 0.000000 0.000000 C( 6, 8) 5.300000 0.000000 C( 6, 9) 4.500000 0.000000 C( 7, 1) 0.000000 0.000000 C( 7, 2) 0.000000 0.000000C( 7, 4) 0.000000 0.000000 C( 7, 5) 0.000000 0.000000 C( 7, 6) 3.800000 0.000000 C( 7, 7) 0.000000 0.000000 C( 7, 8) 0.000000 0.000000 C( 7, 9) 6.700000 0.000000 C( 8, 1) 0.000000 0.000000 C( 8, 2) 0.000000 0.000000 C( 8, 3) 0.000000 0.000000 C( 8, 4) 0.000000 0.000000 C( 8, 5) 0.000000 0.000000 C( 8, 6) 0.000000 0.000000 C( 8, 7) 0.000000 0.000000 C( 8, 8) 0.000000 0.000000 C( 8, 9) 7.400000 0.000000 C( 9, 1) 0.000000 0.000000 C( 9, 2) 0.000000 0.000000 C( 9, 3) 0.000000 0.000000 C( 9, 4) 0.000000 0.000000 C( 9, 5) 0.000000 0.000000 C( 9, 6) 0.000000 0.000000 C( 9, 7) 0.000000 0.000000 C( 9, 8) 0.000000 0.000000 C( 9, 9) 0.000000 0.000000 F( 1, 2) 2.500000 -1.000000 F( 1, 4) 5.600000 -1.000000 F( 1, 5) 6.100000 -1.000000 F( 2, 6) 3.600000 0.000000 F( 4, 5) 4.600000 0.000000 F( 4, 6) 0.000000 0.000000 F( 4, 7) 1.000000 0.000000 F( 5, 2) 1.100000 0.000000 F( 5, 6) 3.900000 0.000000 F( 5, 7) 5.700000 0.000000 F( 6, 8) 5.300000 0.000000 F( 6, 9) 2.200000 0.000000F( 7, 9) 6.700000 0.000000 F( 8, 9) 5.300000 0.000000Row Slack or Surplus Dual Price 1 14.20000 1.0000003 0.000000 0.0000004 0.000000 0.0000005 0.000000 0.0000006 0.000000 0.0000007 0.000000 0.0000008 0.000000 0.0000009 0.000000 -1.000000由以上运行结果可知：F(1,2)=2.5, F(1,4)=5.6, F(1,5)=6.1, F(2,6)=2.5, F(4,5)=4.6, F(4,7)=1.0, F(5,6)=5.0, F(5,7)=5.7, F(6,8)=3.0, F(6,9)=4.5, F(7,9)=6.7,F(8,9)=3.0,其他的F(i,j)=0，最优值为14.2.结果显示，此时可得到最大流为14.2Mb/s，实际流量分布如下图所示：图2计算机网络流量示意图3实际应用根据实际情况可知，最大流问题是涉及怎样使得配送网络中物流量最大的问题，将实际问题按照最大流问题的一般假设和原理用网络描述并建立数学模型，用计算机程序进行求解，研究如何应用最大流问题应对企业物流配送，求解一个在资源稀缺的条件下最大限度的进行物流合理配送，做到反映及时，措施果断．根据具体数值和条件，建立新最大流问题的模型．模型确定后，同样可以运用LINGO软件进行求解，此时的模型更符合实际情况，也能更好更合理的服务于企业．总结运筹学涉及到许多领域的知识，可以解决许多实际问题．这门课对于我们来说非常重要，我们不仅能够学到理论知识，还可将它应用到实际中去，为我们解决很多问题．如本次课程设计就是用运筹学知识，通过对实际问题建立合理的数学模型，然后求解，给出了一个量化的生产计划，进而更好的服务于社会．一个合理有效的生产计划对企业尤为重要,而一个具体量化的生产计划的制定是一个很棘手的问题．本论文结合建模知识，建立实际生产问题的合理正确的模型，利用线性规划知识，对上述问题建立适当的数学模型，并借助LINGO软件求解．对上述问题给出一个量化可行的生产计划，从而使生产利润达到最大化，或消耗量最少，从而更好的合理的解决实际问题，将所学理论知识更好的服务于实践．在此过程中，我也走了不少弯路．刚开始一直找不到合适的软件去求解，看到周围的同学们都早早的做好后．更加急躁，曾试图放弃这个课题，再找一个简单的容易完成的课题．由于自己的急躁心理和急于求成的想法，导致最终仍一无所获．最后，静下心来发现自己处理事情的方式存在很大的问题．总将课程设计当做一项任务去完成，而没有将自己所学的知识与社会实践相结合，试图解决世纪问题的尝试与热情．有一次，一个上午辛辛苦苦一个框架后，不料电脑中毒数据全部丢失．但此时我已经可以心平气和的静下心从头再来．于是很快又建立了新的框架，然后认真的将此课题作为一种尝试，全身心的投入去完成．通过这次课程设计，我也发现了自身的很多不足之处，在以后的学习中，我会不断的完善自我，不断进取，能使自己更加熟练掌握数学这门学科，更加巧妙的用所学到的知识解决实际问题，使其最终服务于实践，造福社会．参考文献[1] 刁在筠,刘桂真,宿洁,马建华.运筹学[M].北京:高等教育出版社,2007.[2] 韩中庚,郭晓丽,杜剑平,宋留勇.实用运筹学[M].北京:清华大学出版社,2011.[3] 谢金星.数学模型与LINGO软件[M].北京:清华大学出版社,2005.。