运筹学课程设计要点

1、运筹学课程设计网络的数据传输最大流问题的模型探讨院（系）名称 XXXXXX专业班级XXXXX学号XXXXXX学生姓名XXXXXX指导教师XXXXXX2014年05月26日课程设计任务书20132014学年第二学期专业班级：XXXXX 学号： XXXXX 姓名： XXXXX课程设计名称：运筹学设计题目： 网络的数据传输最大流问题的模型探讨完成期限：自2014年05 月19日至2014年05 月_26日丄周设计依据、要求及主要内容：一、设计目的一个网络中流量的最大值对企业尤为重要，而一个具体量化的解决方案的制定是一个很棘手的问题本论文结合建模知识，建立实际最大流问题的合理正确的模型，利用 线性规划

2、和最大流的知识，对上述问题建立适当的数学模型，并借助LINGO软件求解对上述问题给出一个量化可行的解决方案，从而使网络中的流量达到最大化，从而 更好的合理的解决实际问题，将所学理论知识更好的服务于实践.二、设计要求结合实际问题的例子，以线性规划理论和最大流理论为基础，建立最大流问题的模型，利用LINGO软件求解，探讨网络中最大流的问题给出一个最优化的解决方案， 使网络中的流量达到最大.三、参考文献1 刁在筠，刘桂真，宿洁，马建华.运筹学M.北京：高等教育出版社，2007.2 韩中庚，郭晓丽，杜剑平，宋留勇.实用运筹学M.北京：清华大学出版 社,2011.3 谢金星.数学模型与LINGO软件M.

3、北京：清华大学出版社，2005.计划答辩时间：2014年05月26日指导教师（签字）：教研室主任（签字）： 批准日期：年 月 日课程设计说明书（论文）第I页网络的数据传输最大流问题的探讨摘 要网络最大流问题是网络的另一个基本问题许多系统包含了流量问题例如交通系 统有车流量，金融系统有现金流，控制系统有信息流等许多流问题主要是确定这类系 统网络所能承受的最大流量以及如何达到这个最大流量同样地，网络的数据传输最大 流问题也采用了这样的原理，利用了线性规划模型求解了最大流问题运用LINGO软件编程得到了求解结果为，计算机网络中，从节点1到节点9的最大传输带宽为14.2Mb/s.关键词：最大流，LIN

4、GO软件，模型课程设计说明书（论文）第II页目 录1 问题重述12探讨过程1.2.1 参考知识背景1.2.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实际应用1.0总 结11参考文献12课程设计说明书（论文）第3页1 问题重述分组交换技术在计算机网络发挥着重要的作用，从源节点到目的节点传送文件不再需要固定的一条“虚路径”，而是将文件分割为几个分组，再通过不同的路径传送到目 的节点，目的节点再根据分组信息

5、进行重组，还原文件，分组交换技术具有文件传输时 不需要始终占用一条线路，不怕单条线路掉线，多路传输提高传输速率等优点现在考 察如图所示的网络，假设图中连接两个节点间的数字表示两交换机间的可用带宽，建立 数学模型，计算从节点1到节点9的最大传输带宽是多少？2探讨过程本次设计在综合了解一定的数学模型、运筹学中的最大流、LINGO软件中一些知识的基础上，以图论理论为基础，对实际例子进行一定的分析后，建立合理的最大流问 题模型然后，利用LINGO软件求得结果给出节点1到节点9的最大传输带宽是多 少.2.1参考知识背景2.1.1数学模型背景一提到数学，人们首先想到的是它的抽象和难懂，以及它的严密的推理和

6、证明，也 正是由于数学的高度抽象性，才决定了它也具有广泛的应用性要运用数学方法解决实 际问题，不论这个问题是来自工程、经济、金融还是社会、生命科学领域，都必须设法在数学与实际问题之间架设一座桥梁，首先要将这个实际问题化为一个相应的数学问 题，其次对这个数学问题进行分析与计算，最后将所求的解答回归为现实，就是数学模 型，而架设桥梁的过程，就称为数学建模，即为所考察的实际问题建立数学模型.当然,建立数学模型的过程一次成功的可能性不是很大.只有最后经过实践检验为有效的数学 模型，才能算是成功的数学模型.2.1.2最大流问题背景图论是运筹学的一个重要分支，随着计算机的逐渐普及，它越来越急速的渗透到 工

7、农业生产、商业活动、军事行动和科学研究的各个方面.它是以图为研究对象的，这 里所说的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应的两个事物之间 具有的这种特定关系.图论其广阔的应用领域涵盖了人类学、计算机科学、化学、环境 保护、流体动力学、心理学、社会学、交通管理、电信网络等领域.特别是在20世纪50年代以后，随着科学技术的发展和计算机的出现与广泛的应用，促使了运筹学的发展，图论的理论也得到了进一步的发展.特别是庞大的复杂工程系统和管理问题都可以转化为图的问题，从而可以解决很多工程设计和管理决策中的最优化问题

8、.诸如像完成工程 任务的时间最少、距离最短、费用最少、收益最大、成本最低等实际问题.因此，图论 在数学、工程技术及经济等各个领域都受到了越来越广泛的重视.其中，最大流问题是 是图论中最常见的问题.2.1.3 LINGO软件背景Lingo 3是用来求解线性和非线性优化问题的简易工具.LINGO内置了一种建立最优化模型的语言，可以简便地表达大规模问题，利用LINGO高效的求解器可快速求解并分析结果.LINGO 全称是Lin ear INteractive and Ge neral Optimizer的缩写-交互式的 线性和通用优化求解器.它是一套设计用来帮助您快速，方便和有效的构建和求解线性， 非

9、线性，和整数最优化模型的功能全面的工具.包括功能强大的建模语言，建立和编辑问题的 全功能环境，读取和写入 Excel和数据库的功能，和一系列完全内置的求解程 序.Lin do/L in go软件作为著名的专业优化软件，其功能比较强、计算效果比较好，与 那些包含部分优化功能的非专业软件相比，通常具有明显的优势.此外，Lindo/Lingo软 课程设计说明书(论文)第4页件使用起来非常简便，很容易学会，在优化软件(尤其是运行于个人电脑上的优化软件) 市场占有很大份额，在国外运筹学类的教科书中也被广泛用做教学软件.2.2建模过程 2.2.1模型假设(1) 假设网络传输过程中没有流量损失.(2) 假设

10、网络传输没有中断.(3) 假设网络信号良好.2.2.2符号说明F :分组传输方式矩阵的表示fj：从节点i到节点j的实际传输带宽C :容量矩阵V(f):网络传输带宽值p,c, f :边集2.2.3问题分析网络的数据传输问题是关于图论中的最大流问题，如图1就是一个网络，各边上的数值代表该边的容量，其中标号为1的点为源，标号为9的点为汇，其他节点为中间顶 点实际中，可以把“网络”看成是水管组成的网络，“容量”看成是水管的单位时间的最大通过量，而“流”则是水管网络中流动的水，“源”是水管网络的水的注入口， “汇” 是水管网络水的流出口.对于所有中间顶点，流入的总量应该等于流出的总量，一个网 络的流量值

11、定义为从源流出的总流量，不难得到网络的总流量也等于流入汇的总流量， 综上所述，我们可以得到网络中的最大流的值.课程设计说明书(论文)第5页2.2.4建立最大流问题的模型将此问题视为一个网络的最大流问题，寻找网络的最大流问题，事实上可以化为求解一个特殊的线性规划问题,即求一组函数侖二f W,Vj)在满足Q f (u,v c(u,v)和Zu.VV(f),V=Vs；f (w, v) =?0,v =V,v = Vs,Vt-V( f ),v =Vt.的条件下，使V (f)有最大值的问题，即maxVf、fij u jeVVf ,v =Vs,-送fji=$0,Vi V,Vi HVsM,将分组的传输方式用以下

12、矩阵来刻画:Wj fVI亠(f),Vi =Vf0 乞 fij 9)0(i = 1,9)0 乞 F C.课程设计说明书（论文）第9页225模型求解该模型的求解，采用LINGO软件，其相应的程序如下:MODEL:sets :nodes/1,2,3,4,5,6,7,8,9/;！节点集arcs( no des ,no des):p,c,f;！边集en dsetsdata :！邻接矩阵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,

13、 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,740,0,0,2.4,0,0,0,725.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;en ddata！去除源和汇！中间节点约束！源汇节点约束！容量约束max =flow;

14、for (nodes(i)|i#ne#1#and#i#ne#size (nodes):sum( no des(j):p(i,j)*f(i,j)= sum( no des(j):p(j,i)*f(j,i);sum( no des(i):p(1,i)*f(1,i)=flow;for (arcs: bnd(0,f,c);END运行该程序，得到运行结果如下：Global optimal soluti on found.Objective value:14.20000In feasibilities:0.000000Total solver iterati ons:11VariableValueRedu

15、ced CostFLOW14.200000.000000P( 1,1)0.0000000.000000P( 1,2)1.0000000.000000P( 1,3)0.0000000.000000P( 1,4)1.0000000.000000P( 1,5)1.0000000.000000P( 1,6)0.0000000.000000P( 1,7)0.0000000.000000P( 1,8)0.0000000.000000P( 1,9)0.0000000.000000P( 2, 1)1.0000000.000000P( 2, 2)0.0000000.000000P( 2, 3)1.0000000

16、.000000P( 2, 4)0.0000000.000000P( 2, 5)1.0000000.000000P( 2, 6)1.0000000.000000P( 2, 7)0.0000000.000000P( 2, 8)0.0000000.000000P( 2, 9)0.0000000.000000P( 3, 1)0.0000000.000000P( 3, 2)1.0000000.000000P( 3, 3)0.0000000.000000P( 3, 4)0.0000000.000000P( 3, 5)0.0000000.000000P( 3, 6)1.0000000.000000P( 3,

17、 7)0.0000000.000000P( 3, 8)1.0000000.000000P( 3, 9)0.0000000.000000P( 4, 1)1.0000000.000000P( 4, 2)0.0000000.000000P( 4, 3)0.0000000.000000P( 4, 4)0.0000000.000000P( 4, 5)1.0000000.000000P( 4, 6)0.0000000.000000P( 4, 7)1.0000000.000000P( 4, 8)0.0000000.000000P( 4, 9)0.0000000.000000P( 5, 1)1.0000000

18、.000000P( 5, 2)1.0000000.000000P( 5, 3)0.0000000.000000P( 5, 4)1.0000000.000000P( 5, 5)0.0000000.000000P( 5, 6)1.0000000.000000P( 5, 7)1.0000000.000000P( 5, 8)0.0000000.000000P( 5, 9)0.0000000.000000P( 6, 1)0.0000000.000000P( 6, 2)1.0000000.000000P( 6, 3)1.0000000.000000P( 6, 4)0.0000000.000000P( 6,

19、 5)1.0000000.000000课程设计说明书（论文）第13页P( 6, 6)0.0000000.000000P( 6, 7)1.0000000.000000P( 6, 8)1.0000000.000000P( 6, 9)1.0000000.000000P( 7,1)0.0000000.000000P( 7, 2)0.0000000.000000P( 7, 3)0.0000000.000000P( 7, 4)1.0000000.000000P( 7, 5)1.0000000.000000P( 7, 6)1.0000000.000000P( 7, 7)0.0000000.000000P(

20、7, 8)0.0000000.000000P( 7, 9)1.0000000.000000P( 8, 1)0.0000000.000000P( 8, 2)0.0000000.000000P( 8, 3)1.0000000.000000P( 8, 4)0.0000000.000000P( 8, 5)0.0000000.000000P( 8, 6)1.0000000.000000P( 8, 7)0.0000000.000000P( 8, 8)0.0000000.000000P( 8, 9)1.0000000.000000P( 9, 1)0.0000000.000000P( 9, 2)0.00000

21、00.000000P( 9, 3)0.0000000.000000P( 9, 4)0.0000000.000000P( 9, 5)0.0000000.000000P( 9, 6)1.0000000.000000P( 9, 7)1.0000000.000000P( 9, 8)1.0000000.000000P( 9, 9)0.0000000.000000C( 1,1)0.0000000.000000C( 1,2)2.5000000.000000C( 1,3)0.0000000.000000C( 1,4)5.6000000.000000C( 1,5)6.1000000.000000C( 1,6)0

22、.0000000.000000C( 1,7)0.0000000.000000C( 1,8)0.0000000.000000C( 1,9)0.0000000.000000C( 2, 1)0.0000000.000000C( 2, 2)0.0000000.000000C( 2, 3)7.1000000.000000C( 2, 4)0.0000000.000000C( 2, 5)0.0000000.000000C( 2, 6)3.6000000.000000C( 2, 7)0.0000000.000000C( 2, 8)0.0000000.000000C( 2, 9)0.0000000.000000

23、C( 3, 1)0.0000000.000000C( 3, 2)0.0000000.000000C( 3, 3)0.0000000.000000C( 3, 4)0.0000000.000000C( 3, 5)0.0000000.000000C( 3, 6)0.0000000.000000C( 3, 7)0.0000000.000000C( 3, 8)3.4000000.000000C( 3, 9)0.0000000.000000C( 4, 1)0.0000000.000000C( 4, 2)0.0000000.000000C( 4, 3)0.0000000.000000C( 4, 4)0.00

24、00000.000000C( 4, 5)4.9000000.000000C( 4, 6)0.0000000.000000C( 4, 7)7.4000000.000000C( 4, 8)0.0000000.000000C( 4, 9)0.0000000.000000C( 5, 1)0.0000000.000000C( 5, 2)2.4000000.000000C( 5, 3)0.0000000.000000C( 5, 4)0.0000000.000000C( 5, 5)0.0000000.000000C( 5, 6)7.2000000.000000C( 5, 7)5.7000000.000000

25、C( 5, 8)0.0000000.000000C( 5, 9)0.0000000.000000C( 6, 1)0.0000000.000000C( 6, 2)0.0000000.000000C( 6, 3)3.8000000.000000C( 6, 4)0.0000000.000000C( 6, 5)0.0000000.000000C( 6, 6)0.0000000.000000C( 6, 7)0.0000000.000000C( 6, 8)5.3000000.000000C( 6, 9)4.5000000.000000C( 7,1)0.0000000.000000C( 7, 2)0.000

26、0000.000000C( 7, 3)0.0000000.000000C( 7, 4)0.0000000.000000C( 7, 5)0.0000000.000000C( 7, 6)3.8000000.000000C( 7, 7)0.0000000.000000C( 7, 8)0.0000000.000000C( 7, 9)6.7000000.000000C( 8, 1)0.0000000.000000C( 8, 2)0.0000000.000000C( 8, 3)0.0000000.000000C( 8, 4)0.0000000.000000C( 8, 5)0.0000000.000000C

27、( 8, 6)0.0000000.000000C( 8, 7)0.0000000.000000C( 8, 8)0.0000000.000000C( 8, 9)7.4000000.000000C( 9, 1)0.0000000.000000C( 9, 2)0.0000000.000000C( 9, 3)0.0000000.000000C( 9, 4)0.0000000.000000C( 9, 5)0.0000000.000000C( 9, 6)0.0000000.000000C( 9, 7)0.0000000.000000C( 9, 8)0.0000000.000000C( 9, 9)0.000

28、0000.000000F( 1, 2)2.500000-1.000000F( 1,4)5.600000-1.000000F( 1, 5)6.100000-1.000000F( 2, 6)3.6000000.000000F( 4, 5)4.6000000.000000F( 4, 6)0.0000000.000000F( 4, 7)1.0000000.000000F( 5, 2)1.1000000.000000F( 5, 6)3.9000000.000000F( 5, 7)5.7000000.000000F( 6, 8)5.3000000.000000F( 6, 9)2.2000000.00000

29、0F( 7, 9)6.7000000.000000F( 8, 9)5.3000000.000000Row Slack or Surplus Dual Price114.200001.000000课程设计说明书（论文）第#页0.0000000.000000课程设计说明书（论文）第#页课程设计说明书（论文）第14页30.0000000.00000040.0000000.00000050.0000000.00000060.0000000.00000070.0000000.00000080.0000000.00000090.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 实际应用根据实际情况可知，最大流问题是涉及怎样使得配送网络中物流量最大的问题，将实际问题按照最大流问题的一般假设和原理用网络描述并建立数学模型