1、毕业论文 开题报告 信息与计算科学 MATLAB 软件在运筹学中的应用 一、 选题的背景、意义 运筹学是一门研究如何有效地组织和管理人机系统的科学。由于它同管理科学的紧密联系，它在研究解决实际问题时所蕴涵的的系统整体优化思想，以及从提出问题、分析建模、求解到方案实施的一整套严密科学方法。 1 随着科学技术和生产的发展，运筹学已渗入很多领域里，发挥了越来越重要的作用。运筹学本身也在不断发展，现在已经是一个包括好几个分支的数学部门了。比如 ：数学规划（又包含线性规划；非线性规划；整数规划；组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等等。 2 随着科技
2、的快速发展，现如今运筹学问题已经可以用 LINDO、 LINGO、 MATLAB等软件来代替复杂、繁琐的运算。其中又以 MATLAB 软件在现实使用中最为广泛，广受使用者的好评。 什么是 MATLAB 软件？ MATLAB 是由美国 mathworks 公司发布的主要面对科学计算、可视化以及交互式程序设计的高科技计算环境 。它将数值分析、矩阵计算、科学数据可视化以及非线性动态系统的建模和仿真等诸多强大功能集成在一个易于使用的视窗环境中，为科学研究、工程设计以及必须进行有效数值计算的众多科学领域提供了一种全面的解决方案，并在很大程度上摆脱了传统非交互式程序设计语言（如 C、 Fortran）的编
3、辑模式，代表了当今国际科学计算软件的先进水平。 MATLAB 和 Mathematica、 Maple 并称为三大数学软件。它在数学类科技应用软件中在数值计算方面首屈一指。 MATLAB 可以进行矩阵运算、绘制函数和数据、实现算法、创建用户界面 、连接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、图像处理、信号检测、金融建模设计与分析等领域 。 MATLAB 的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用 MATLAB 来解算问题要比用 C， FORTRAN 等语言完成相同的事情简捷得多，并且 mathwork 也吸收了像 Maple 等软件的
4、优点 ,使 MATLAB 成为一个强大的数学软件。在新的版本中也加入了对 C， FORTRAN， C+ ， JAVA 的支持。可以直接调用 ,用户也可以将自己编写的实用程序导入到 MATLAB 函数库 中方便自己以后调用，此外许多的 MATLAB 爱好者都编写了一些经典的程序，用户可以直接进行下载就可以用。 3 二、研究的基本内容与拟解决的主要问题 2.1 运筹学历史背景： 运筹学作为科学名词出现在 20 世纪 30 年代末。第二次世界大战期间，运筹学的研究与应用范围主要是战略、战术方面。随着世界性战争的结束，各国开始快速发展经济，世界范围内的剧烈竞争也体现在经济、技术方面，运筹学的研究也向些
5、方面拓展。运筹学为了适应时代的要求，在近几十年中，无论从理论上还是应用上都得到 了快速的发展。在应用方面，今天运筹学已经涉及了服务、管理、规划、决策、组织、生产、建设等诸多方面，甚至可以说，很难找出它涉不到的领域。在理论方面，由于运筹学的需要和刺激而发展起来的一些数学分支，如数学规划，应用概率与统计、应用组合数学、对策论、数理经济学、系统科学等，都得到了迅速发展。 4 第二次世界大战以后，运筹学的活动扩展到工业和政府等部门，它的发展大致可分为三个阶段： 1.从 1945 年到 20 世纪 50 年代初，被称为创建时期。此阶段的特点是从是运筹学研究的 人数不多，范围较小，运筹学的出版物、学会等寥
6、寥无几。 2.从 20 世纪 50 年代初期到 50 年代末期，被认为是运筹学的成长时期。此阶段的一个特点是电子计算机技术的迅速发展，使得运筹学中一些方法如单纯形法、动态规划方法等，使得以用来解决实际管理系统中的优化问题，促进了运筹学的推广应用。 3.自 20 世纪 60 年代以来，被认为是运筹学开始普及和迅速发展的时期。此阶段的特点是运筹学进一步细分为各个分支，专业学术团体迅速增多，更多的期刊创办，运筹学书籍大量出版，以及更多学校将运筹学课程纳入教学计划之中。 由于运筹学在提高组织 机构的效率方面已取得显著成效，它的影响还在继续扩展。 5 6 2.2 MATLAB 历史背景： 随着科技的发展
7、运筹学问题的计算也由越来越多的软件来代替，从而节省解决问题的时间和精力，而 MATLAB 软件就是其中一种应用广泛的软件。 MATLAB 名字由 MATrix 和 LABoratory 两词的前三个字母组合而成。那是 20 世纪七十年代后期的事：时任美国新墨西哥大学计算机科学系主任的 Cleve Moler 教授出于减轻学生编程负担的动机，为学生设计了一组调用 LINPACK 和 EISPACK 库程序的 “ 通俗易用 ”的接口，此即用 FORTRAN 编写的萌芽状态的 MATLAB 。 3 经几年的校际流传，在 Little 的推动下，由 Little 、 Moler 、 Steve Ban
8、gert 合作，于 1984 年成立了 MathWorks 公司，并把 MATLAB 正式推向市场。从这时起， MATLAB 的内核采用 C 语言编写，而且除原有的数 值计算能力外，还新增了数据图视功能。 MATLAB 以商品形式出现后，仅短短几年，就以其良好的开放性和运行的可靠性，使原先控制领域里的封闭式软件包（如英国的 UMIST ，瑞典的 LUND 和 SIMNON ，德国的 KEDDC ）纷纷淘汰，而改以 MATLAB 为平台加以重建。在时间进入 20 世纪九十年代的时候， MATLAB 已经成为国际控制界公认的标准计算软件。 7 Matlab软件是由美国 Mathworks公司推出的
9、用于数值计算和图形处理的 科学计算系统环境。它具有强大的数值计算、绘图、优化和编程等功能。 Matlab 的基础是矩阵计算 ,但是由于它的开放性 ,并且 Mathwork 也吸收了像 Maple 等软件的优点 ,使 Matlab 成为一个强大的数学软件。总的来说 ,Matlab 有如下优势和特点 : 1) 友好的工作平台和编程环境。 2) 简单易用的程序语言。 3) 强大的科学计算机数据处理能力。 4) 应用广泛的模块集合工具箱。 5) 实用的程序接口和发布平台。 6) 应用软件开发。 在实际教学中主要是通过实例的方法来说明 Matlab 在教学过程中 的方便性和直观性。 8 2.3 运筹学建
10、模： 运筹学建模在理论上应属于数学建模的一个部分。因此，运筹学建模要根据实际问题决定使用哪一种方法建模，如取决于人们对研究对象的了解程度和建模目的。建模要经过哪些步骤并没有一定的模式，通常与问题性质、建模目的等有关。机理分析方法模型的一般过程为：模型准备，模型假设，模型构成，模型求解，模型分析，模型检验，模型应用。也可以将之简化为数学模型的表述、求解、解释、验证几个阶段。 9 10 2.4 运筹学在现实生活中的应用： (1)线性规划主要研究在经营管理中如何有效地利用现有人力、物力完成更多的任务 ,或在预定的任务目标下 ,如何耗用最少的人力、物力去实现目标。 实例 :某村计划在 100 hm2
11、土地上种植 A ,B ,C 三种农作物 ,可供劳力、粪肥、化肥等资源的数量 ,种植每公顷作物所需资源数量以及能获利润如表 1 所示。 表 1 资源数量及利润表 类型 用工 / 个 粪肥 / t 化肥 / kg 每公顷利润 / 元 作物 A 450 35 350 1 500 作物 B 600 25 400 1 200 作物 C 900 30 300 1 800 可供资源 63 000 3 300 33 000 问如何选择种植方案 ,使所获利润最大。 设 x1 , x2 , x3 分别表示农作物 A ,B ,C 的种植面积 ,则问题的 模型可归结如下 : max z = 1 500 x1 + 1
12、200 x2 + 1 800 x3 s. t . x1 + x2 + x3 = 100 450 x1 + 600 x2 + 900 x3 63 000 35 x1 + 25 x2 + 30 x3 3 300 350 x1 + 400 x2 + 300 x3 33 000 x1 , x2 , x3 0 用 Matlab 求解上述规划问题 ,只需编制如下的程序 : f = 1 500 1 200 1 800 ; f = - f ; a = 450 600 900 ;35 25 30 ;350 400 300 ; b = 6 300 3 300 33 000 ; aeq = 1 1 1 ;beq =
13、 100 ; lb = zeros(3 ,1) ; x ,fval ,exitflag ,output ,lambda = linprog(f ,a ,b ,aeq ,beq ,lb) ; 执行上述程序后 ,可得问题的最优解 :exitflag = 1 ,fval = - 16 200 , x1 = 60 , x2 = 0 , x3 = 40 。由此可知最优的种植方案为种植 A 作 物 60 hm2 ,种植 C 作物 40 hm2 ,总利润为 16 200 元。 11 (2) 在现实生活中 ,有各种性质的指派问题 ,例如有若干项工作需要分配给若干人来完成 ;有若干班级需要安排给各教师上课等。这
14、些问题的基本要求是在满足特定的指派要求条件下 ,使指派方案的总体效果最佳。指派问题一般的解法为匈牙利解法。实例 :某商业公司计划开办 4 家新商店 ,为了尽早建成营业 ,商业公司决定由 4 家建筑公司 A ,B ,C ,D 分别承建。规定每家建筑公司只能承建一家新商店 ,每家新商店只能承包给一个建筑公司。建筑公司对新商店的建造费用的报价 (万元 ) 如表 2 所示。要求商业公司 应当对 4 家建筑公司怎样分配建造任务 ,才能使总的建造费用最少。 表 2 建造费用报价表（单位：万元） 建筑公司 商店 1 商店 2 商店 3 商店 4 A 15 18 21 24 B 19 23 22 18 C 2
15、6 17 16 19 D 19 21 23 17 这是一个平衡的分派问题。输入如下的 Matlab 程序 : e = 15 18 21 24 ;19 23 22 18 ;26 17 16 19 ;19 21 23 17 ; a = e ;f = a ( :) ; o = ones(1 ,4) ;z = zeros(1 ,4) ;y = eye (4) ; aeq = o ,z ,z ,z ;z ,o ,z ,z ;z ,z ,o ,z ;z ,z ,z ,o ; aeq = aeq ;y ,y ,y ,y ; beq = ones(8 ,1) ;lb = zeros(16 ,1) ; x ,f
16、val ,exitflag ,output ,lambda = linprog(f , , ,aeq ,beq , lb) ; xv = reshape (x ,4 ,4) ; xx = xv ; %xx 为指派方阵 xx0 = round(xx) ; %xx0 为 xx 取整后的方阵 xe = xx0. / e ;xe = xx0. 3 e ; rfv = sum(sum(xe) ) ; 在 Matlab 中执行上述程序后得到 fval = 70 ,即最优解为 70 ;得到指派方阵 xx 以及 xx0 的结果 ,由 fval = 70 可知 ,xx0 为最优指派方阵 ,即最优指派方案为 :商
17、店 1 承包给建筑公司 B ,商店 2承包给建筑公司 A ,商店 3 承包给建筑公司 C ,商店 4 承包给建筑公司 D ,总耗费 70 万元。由此可知 ,利用该软件求解指派问题非常简单 ,而且速度很快。 12 13 三、研究的方法与技术路线、研究难点，预期达到的目标 1.研究内容 （ 1）了解运筹学， MATLAB 产生的背景及意义，知道运筹学和 MATLAB 的基本发展历程。 （ 2）对运筹学问题有深刻认识，掌握用 MATLAB 软件来解决运筹学问题的基本方法，了解运筹学研究的基本问题。 （ 3）清楚运筹学今后的发展方向及进一步研究需要的知识。 2.研究方法及技术路线 本论文主要以查找资料
18、、参考文献，以学过的相关知识，在前人的研究论述基础上，用MATLAB 软件来解决基本运筹学问题，并用来优化社会中的常见问题。采取了从大量阅读已有的数据资料 然后对这些内容进行归纳总结 最后运用相关知识来求解及应用的技术路线 。 3、研究难点 （ 1）对运用 MATLAB 软件解决运筹学问题的基本方法及它的应用的掌握程度有待加强，对运筹学的不同 方法的运用的进一步加深了解； （ 2）由于论题比较宽泛，很难有对一点或一面进行深入研究； （ 3）运筹学的方法有很多种，本文讲述其中几种基本的方法；它的应用领域也很广泛，本文只论述常见的方面。 4、预期达到的目标 通过这次论文的撰写更好的了解了运筹学及
19、MATLAB 软件的发展历程，深入的认识了运筹学问题，更好的掌握了解决运筹学问题的方法，并会应用此理论来解决社会中常见的问题，同时还可以结合其他知识来综合解决这类问题。除此，对运筹学和 MATLAB 软件的掌握，还能更好的学习其他相关理论，能更容易的更好的解决这类问题。 四、论文详细工作进度和安排 第 7 学期第 9 周（ 2010 年 11 月 5 号）至第 7 学期第 19 周（ 2011 年 1 月 10 号） 完成毕业论文文献检索、文献综述、外文文献翻译及开题报告。 第 7 学期第 19 周（ 2011 年 1 月 10 号）至第 8 学期第 3 周（ 2011 年 3 月 11 号）
20、 完成毕业论文的数据收集、论文初稿。 第 8 学期第 3 周（ 2011 年 3 月 11 号）至第 8 学期第 11 周（ 2011 年 5 月 3 号） 1、进入实习单位进行毕业实习，对论文进行修改； 2、第 11 周（ 2011 年 5 月 3 日）前必须返校，完成毕业实习返校 ，并递交毕业实习报告，进一步完善毕业论文； 第 8 学期第 14 周（ 2011 年 5 月 23 号 2011 年 5 月 28 号）完成第一轮毕业论文答辩； 第 8 学期第 15 周（ 2011 年 5 月 28 号 2011 年 6 月 3 号）第一轮毕业论文答辩未通过的学生完成第二轮毕业论文答辩，并随机抽
21、取部分完成较好地毕业论文进行校级答辩。 五、主要参考文献： 1 胡运权，郭耀煌 运筹学教程 M 北京：清华大学出版社， 2007： I-I 2 周晓阳 数学实验与 MatlabM 武汉：华中科技大学出版社， 2002： 210-213 3 吴祈宗，郑志勇，邓伟 运筹学与最优化 MATLAB 编程 M 北京：机械工业出版社， 2009： 1-1 4 曹卫华，郭正 最优化技术方法及 MATLAB 的实现 M 北京：化学工业出版社， 2005： 10-11 5 杜 辉 优化建模软件在运筹学中的应用 J 山西建筑， 2009， 20（ 12）： 367-368 6 Rangarajan K.Sunda
22、ram 最优化导论 M 北京：人民邮电出版社， 2008： 210-213 7 黄雍检，赖明勇 MATLAB 语言在运筹学中的应用 M 长沙： 湖南大学出版社， 2005： 210-213 8 Frederick S. Hillier ， Gerald J. Lieberman 运筹学导论 M 北京： 清华大学出版社 ,， 2006： 210-213 9 林志程 Matlab 语言在网络最大流中的应用 J 微计算机应用 ， 2005， 26（ 4）： 15-18 10 姜启源，谢金星，叶俊 数学建模 M 北京：高等教育出版社 , 2003, 28（ 4）： 10-11 11 吕游 运筹学的应用与发展 J 活力 ， 2010， 17（ 6）： 165-165 12 白宏学 浅谈运筹学在生活中的应用 J 活力 ， 2010， 21（ 10）： 99-99 13 刘诚 浅谈线性规划模型 及其实际应用 J 数理化学习：初中教师版 ， 2009， 14（ 9）： 6-7 14 胡红萍 ， 胡红莉 运筹学课程教学中的几点体会 J 中北大学学报 (社科版 ) ， 2005， 9（ 2）： 10-11 15 余 跃 ， 王婷婷 在运筹学课程教学中培养学生的创新思维 J 吉林省教育学院学报 ， 2007， 22（ 2） ： 27-29
