运筹学课程设计要点.doc
运筹学课程设计网络的数据传输最大流问题的模型探讨院（系）名称 xxxxxx 专 业 班 级 xxxxx 学 号 xxxxxx 学 生 姓 名 xxxxxx 指 导 教 师 xxxxxx 2014年 05 月26日课程设计任务书20132014学年第二学期专业班级： 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 问题重述12 探讨过程12.1 参考知识背景12.1.1 数学模型背景12.1.2 最大流问题背景22.1.3 LINGO软件背景22.2 建模过程32.2.1 模型假设32.2.2 符号说明32.2.3 问题分析32.2.4 建立最大流问题的模型42.2.5 模型求解53 实际应用12总 结13参考文献141 问题重述分组交换技术在计算机网络发挥着重要的作用，从源节点到目的节点传送文件不再需要固定的一条“虚路径”，而是将文件分割为几个分组，再通过不同的路径传送到目的节点，目的节点再根据分组信息进行重组，还原文件，分组交换技术具有文件传输时不需要始终占用一条线路，不怕单条线路掉线，多路传输提高传输速率等优点现在考察如图所示的网络，假设图中连接两个节点间的数字表示两交换机间的可用带宽，建立数学模型，计算从节点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 符号说明：分组传输方式矩阵的表示：从节点i到节点j的实际传输带宽：容量矩阵：网络传输带宽值：边集2.2.3 问题分析网络的数据传输问题是关于图论中的最大流问题，如图1就是一个网络，各边上的数值代表该边的容量，其中标号为1的点为源，标号为9的点为汇，其他节点为中间顶点实际中，可以把“网络”看成是水管组成的网络，“容量”看成是水管的单位时间的最大通过量，而“流”则是水管网络中流动的水，“源”是水管网络的水的注入口，“汇”是水管网络水的流出口对于所有中间顶点，流入的总量应该等于流出的总量，一个网络的流量值定义为从源流出的总流量，不难得到网络的总流量也等于流入汇的总流量，综上所述，我们可以得到网络中的最大流的值2.2.4 建立最大流问题的模型将此问题视为一个网络的最大流问题，寻找网络的最大流问题,事实上可以化为求解一个特殊的线性规划问题,即求一组函数在满足和的条件下，使有最大值的问题，即将分组的传输方式用以下矩阵来刻画：，其中表示从节点i到节点j的实际传输带宽，记容量矩阵为：，由此可以建立线性规划模型如下： 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.20000 Infeasibilities: 0.000000 Total solver iterations: 11 Variable Value Reduced Cost FLOW 14.20000 0.000000 P( 1, 1) 0.000000 0.000000 P( 1, 2) 1.000000 0.000000 P( 1, 3) 0.000000 0.000000 P( 1, 4) 1.000000 0.000000 P( 1, 5) 1.000000 0.000000 P( 1, 6) 0.000000 0.000000 P( 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.000000 P( 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.000000 C( 2, 4) 0.000000 0.000000 C( 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.000000 C( 7, 3) 0.000000 0.000000 C( 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
