毕业设计论文基于线性规划的最优路径设计.doc

1、基于线性规划的最优路径设计摘要各个领 域中的大量问题都可以归结为线性规划问题尤其在物流管理活动中,有大量的规划问题,如网络配送中的运输规划问题,它属于线性规划问题的特例运输问题存在多种解法,目前计算机应用普及,用一般的解线性规划的软件来解运输问题是一条较好的途径根据调查表明,近几十年来,线性规划在各个行业中都得到了广泛的应用,而且运输问题的模型不单只是适用于一般意义上的物资运输问题,更重要的是它适用于一切道路网络问题因此。关键词 线性 规划Floyd算法优路径Linear programming-based optimal path designAbstractLARGE number of

2、problems in various fields can be reduced to linear programming problems,especially in logistics management activities,a large number of planning issues,such as network distribution problems in transport planning,it is a special case of linear programming problems with multiple solution of the trans

3、port,the current popularity of computer applications,using the general linear programming software to solve the transport problem is a good way to According to the survey indicated that in recent decades,linear programming in all sectors have been widely used,and transport and the model is not only

4、applicable to the general sense of material transport,more importantly,it applies to all road network problem,therefore and improve the economic effect of the general in two ways:first,the technological improvements.Second,improvement of production organization and planning,namely reasonable arrange

5、 the human and material resources.The method overcomes the maximum distance equal to the average distance method and the lack of equal laws,principles are more simple and clear,high precision,this easy to play the advantages of computer technology to improve the accuracy of economic distance.In this

6、 paper,steel and transportation orders,for example,using matlab, lingo software to design the optimal path of the transport pipe,calculate the minimum pipe order and transport costs.KeywordsLinear Floyd algorithm Optimal path目录引言 (1第一章线性规划数学模型 (21.1概论 (21.1.1问题的提出 (21.1.2国外研究的现状 (31.1.3国内研究的现状 (41.1

7、.4本文研究的必要性 (41.2线性规划的数学模型的一般形式.错误!未定义书签。1.3线性规划问题的解.错误!未定义书签。1.3.1几个概念.错误!未定义书签。1.3.2线性规划问题的解.错误!未定义书签。1.3.3线性规划问题解的性质.错误!未定义书签。第二章线性规划在运输中的应用 (12.1运输问题的特征.错误!未定义书签。2.2线性规划在运输问题中的一般数学形式.错误!未定义书签。第三章Floyd 算法.错误!未定 义书签 。3.1最短路径定义.错误!未定义书签。3.1.1单源最短路径.错误!未定义书签。3.1.2任意顶点间的最短路径.错误!未定义书签。3.2Floyd算法 .错误!未定

8、义书签。3.2.1Floyd算法基本思想 .错误!未定义书签。3.2.2Floyd算法步 骤.错误!未定义书签。3.2.3算法复杂度比较.错误!未定义书签。3.3Fl oyd算法演示系统.错误!未定义书签。第四章线性规划在运输问题中的实例.错误!未定义书签。4.1例题:钢管订购与运输. 错误! 未定义书签。4.2模型假设.错误!未定义书签。4.3问题分析:.错误! 未定义书签。4.4符号说明:.错误! 未定义书签。4.5模型建立与求解.错误!未定义书签。结论 (1致谢语 (2参考文献 (3附录.错误!未定义书签 。引言各个领域中的大量问题都可以归结为线性规划问题尤其实物流问题。物流是物品从供应

9、地向接受地的实体流动过程。据数据统计,在机械产品的生产过程中,加工时间仅占10%左右,而物流时间却占90%,很大一部分生产成本消耗在物流过程中。而运杂费接近总物流费用50%。因此,运输成了降低物流费用最有潜力的领域,它是物流活动的核心。在运输组织中 ,如何选择合理路线使运输费用最省,线性规划是实现运输管理最优化最成功的方法。 线性规划创始人、美国G.Dantzig教授曾在一个学术会议上说,他除了发现单纯形法之外,还有两个功绩:一是 总结人们的实践经验,认识到在管理科学中大多数的实际关系都可用线性公式来表示;二是明确提出应该使用目标函数作为最优方案的选择准则。为此,本文主要介绍在物流运输中如何建

10、立它的线性规划数学模型。至于求解线性规划的单纯形法不在这里介绍,因为用单纯形法求解线性规划问题计算机应用软件包代替了人工计算,并能非常轻松地解决此问题。因此,现在物流业面临的新问题是针对具体的物资运输实物如何建立起数学模型,以及建立线性规划的条件。本文以钢管订购与运输为例,利用matlab 、lingo软件,设计出钢管运输的最优路径,求出钢管订购与运输的最小费用。第一章线性规划数学模型1.1概论线性规划作为运筹学的一人重要分支,是研究较早,理论较完善,应用最广泛的一门科学。它所研究的问题主要包括两个方面:一是在一 项任务确定后,如何以最低限度和成本( 如人力、物力、 资 金和时间等去完成这一任

11、 务;二是如何在现有条件下进行组织和安排,以完成更多的工作。因此,线性规划就是求一组变量的值,使它满足一组线性式子,并使一个线性函数的值最大(或最小的数学方法线性规划所研究的问题主要有两类:一类是已给定一定数量的人力和物力 资源,如何用这些资源完成最大量的任务;另一类是已给定一 项任务,如何统筹安排,才能以最小量的资源去完成这项任务。即有关“多、快、好、省” 的最优化问题。随着我国市场经济体系的逐步确立以及我国成功加入WTO,企业生存与发展的内外在环境发生了深刻的变化,经营方式也由粗放型向集约型转化,而成本管理正是这一转变的核心,成本信息是企业管理和企业决策的关键要素与先决条件。作为我国新兴的

12、第三方物流企业正处于起步和发展阶段,资金相对短缺,企业实力也相对薄弱,尤其是在现有的物流企业中,成本始终居高不下。要想在市场竞争中取得优势地位和长远发展,企业就必须建立适合自身发展特点的成本核算体系,从而控制成本支出,提高经济效益。线性规划则起着至关重要的作用。1.1.1问题的提出供料方案的优化实质上是在有限的资源下运用最优化技术进行物料调配的规划活动,其目的是保证物料运输运费的最小化。近年来,随着我国四个现代化建设速度的加快,很多行业尤其是基础性建设行业,其发展突飞猛进。各行各业出现了欣欣向荣的良好局面,但同时因计划和管理不当,在时间、人力、物力和资金等方面造成了很大的浪费,从而给我国的经济

13、建设带来了严重损失。为了适应现代化建设的发展,尤其是要保证基础性行业不能出现资金的过度浪费,国家要求相关主管部门严格把关,切实做好资金使用合理这一关。而要达到这种要求,就要求相关的设计、施工、 监理部门做好优化设计这一环。 传统模式下的优化设计主要是根据设计者的经验而定,并没有形成一套科学合理的优化方法。因此,实际操作中许多优化设计往往不一定就是最佳的优化方案,从而造成了大量的资源浪费。作为铁(公路设计部门来讲,如何搞好施工组织方案、施工供料方案的优化设计,降低工程总造价,提高资金的利用效率,不仅关系到本部门的生计问题,同时也关系到国家投资规划是否切实可行的根本问题。在铁( 公路设计过程中,应

14、用最优化技术搞好供料方案的优化设计,相关方案未见详细报道。鉴于 这种情况,笔者正是从上述背景下,引入供料方案的优化模型,通过线性规划的表上作业法详细地阐述供料方案中运输路径的选择问题,并求其最优解,从而为供料方案的设计提出几点建议与参考。1.1.2国外研究的现状供料方案的优化问题其实属于运筹学应用研究的规划问题。早在上世纪20年代,以兰德公司(RAND为首的一些部门开始运用运筹学着重研究战略性问题以及武器系统的设计和其可能合理运用的方法,取得了良好的效果。后来运筹学相继在工业、农业、经济 和社会问题等各 领域都有应用。与此同 时 ,运筹数学有了飞快的发展,并形成了运筹学的许多分支。如数学规划(

15、线性规划、非线性规划、整数 规划、目标规划、动态规划、随机规划等、图论与网络、排队论、存 贮论、对策论、决策论、维修更新理论、搜索 论、可靠性和质量管理等。 线性规划是由丹捷格 (G.B.Dantzig在1947年发表的一篇成果,而应用到实际问题中的是美国空军军事规划小组,当时他们提出了求解线性规划的单纯形法。线性规划提出后很快受到经济学家的重视,并在运筹学某些领域中发挥过重要作用。1974年,Zeleny等将解线性规划的单纯形法给予适当修改后,用来解多目标线性规划问题,或把多目标线性规划问题化成单目标的线性规划问题后求解,给运筹学工作者带来了很大方便,尤其是在求汽车运输调配规划问题上带来了捷

16、径。上世纪六十年代初由LandDoig和Dakin等人提出用分枝定界法求解整数规划问题,由于该法灵活且便于用计算机求解,所以现在它己是解整数规划的重要方法。该法在求解供料运输问题上虽然比穷举法优越,因为它仅在一部分可行解的整数解中寻求最优解,计算量比穷举法小。但若变量数目很大,其计算工作量也是相当可观的。1951年美国数学家贝尔曼(R.Bellman创造了解决最优化问题的一种新的方法一一动态规划。动态规划法是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。工程上的许多问题用动态规划的方法去处理,常常比线性规划或非线性规划更有成效。但由于动态规划依赖条件较强,且存在维数障碍,故在供

17、料运输的汽车模型上应用不是很广。在总体计划方面主要是从总体确定生产、存贮和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟方法等。如解决供料、物流、车流调配等问题中,Attahiru.s.A使用模拟退火算法 ,Barbarosoghi,ozgur、xuJ,J使用禁忌搜索算法,oilbertLaPorte,HeleneMereure,YvesNobert使用分枝定界算法,Danting,Ramse使用线性规 划的单纯形法,HowKAndrewLAndrewL 基于时间窗的混合算法,于叮ankiliscD, 儿ranondisCT使用了空间决策支持系统,ehia一Ho一ehen,e址n

18、g一Jung 叭ng,Pei一channehang应用了 蚁群算法,HwangH51 研究了基于有时间限制的基因遗传算法的改进模型的车辆运输问题,他们都较好地解决了汽车调配、流向、最佳路线等难题。国外有关运筹学的理 论与实践方面的研究,对国内运筹学的发展起到了积极有益的促进作用。我们可以从借鉴中创新、从 创新中 发展,不断地运用运筹学的先进算法为我们的实际问题服务。1.1.3国内研究的现状国内对运筹学的研究始于上世纪80年代,与国外的研究几乎同时起步。钱颂迪、胡运权结合运筹学,运用线性规划和数学模拟方法解决了生产应用中的合理下料、配料问题,以及物料管理等方面的应用。李军、 张锦、秦明森脾运用线

19、性规划,解决了物流运输中汽车路径选择的原则、方法及技巧,很好地建立了汽车运行费用最少的数学模型,方便物流规划者使用。郭耀煌、陈唐民、陈星明 结合线性规划、多目标决策等理论,重点解决了车辆调配或车流运输中最短时间的数学模型,给车流规划带来了极大方便。邓先礼、施光燕、邢文 训四等人运用最优化技 术,结合线性规划,解决了运输规划中最短路径问题、最佳运费问题,给工程设计提供了参考依据。左永林、柳志新 结合水电工程砂石料场优选的实例,运用动态规划的方法解决了供料方案的优化研究。目前,国内外虽然对线性规划理论的研究日臻完善,但在实际应用中由于理论的深度及结合实际问题的多样性,尤其在大中型铁(公路建设规划中

20、,很多设计者并未按其优化模型进行规划设计。因此有必要结合实际问题,寻找一种直观、简单方便的优化模型推广应用。线性规划中的表上作业法正是在这种情况中能方便地发挥用场。本文主要基于线性规划进行展开研究,以期望对今后工程设计的顺利开展提供一点点建议。1.1.4本文研究的必要性(1.理论 上的必要性运输模型虽然很多,然而带有限制因素的运输模型上未见详细报道。 诸如供料场日开采能力受限制,行车运货的密度受限制,开行时间受安全环保的限制等,而这类情况时有发生。因此有必要对这类实用性较强的模型进行深入地研究;(2. 工程实践上的必要性由于大多上供料方案的 优化设计采用传统的工区分段法。该法 虽然简单、直观,

21、也能解决实际问题,但常常出现供料运输上的抢购现象,即针对某一供料点,很多需料点同时排队进行购料运输,而稍远的供料点却出现门庭冷清的现象。发生此类情况主要是由于在供料运输的规划设计时采用的是工段分区法,该法只是一个局部优化的运输模型,并不能解决全局性的运输调配问题。因此,为保证整个工程的顺利进行,保证供需平衡并且达到运费最小,有必要进行工程实际上的应用研究。第二章线性规划在运输中的应用在现实的生产经营、商品销售、 经济建设和物资管理过程中,常常会遇到各类物资的分配和调运问题,即将各种生产资料或生活资料消耗品从供给基地调运到需求基地,这里就需要如何根据现有条件科学、合理的安排调运方案,提高运输经济

22、效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。结论从中可以注意到上述所计算的结果是建立在当前的运输和投资成本基础上的,所以在仔细研究每一种情况的时候,应认真考虑一下这些成本可能带来的变化对于每一种情况来说,必须要描述出未来这些成本的变化情况,这样就可以知道目前所作出的决定是否正确。运用线性规划法来指导一些投资决策具有一定的理论意义和实际价值几乎所有公司都会遇到有约束条件下的最优化问题,因此线性规划在许多管理问题中都能应用,本文仅从如何利用现有资源获得最大利润进行优化设计只要是对生产制造投资财务工程等求最大利润最小成本等问题,就基本上可以用线性规划来求解。线性规划是合理利用

23、、调配资源的一种应用数学方法。它的基本思路就是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,用最少的资源(人力、物力和财力去实现这个任务;二是资源的数量已定,如何合理利用、 调配 ,使任务完成的最多。前者是求极小,后者是求极大。线性 规划是在满足企业内、外部的条件下,实现管理目标和极值(极小值 和极大 值问题,就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此,线性规划是辅助企 业“转轨”、“变型”的十分有利的工具,它在辅助企业经营决策、计 划优化等方面具有重要的作用。把线性规划的知识运用到企业中去,可以使企业

24、适应市场激烈的竞争,及时、准确、科学的制定生产计划、投资计划、对资源进行合理配置。过去企业在制定计划,调整分配方面很困难,既要考虑生产成本,又要考虑获利水平,人工测算需要很长时间,不易做到机动灵活,运用线性规划并配合计算机进行测算非常简便易行,几分钟就可以拿出最优方案,提高了企业决策的科学性和可靠性。其决策理论是建立在严格的理论基础之上,运用大量基础数据,经严格的数学运算得到的,从而在使企业能够在生产的各个环节中优化配置,提高了企业的效率,对企业是大有益处的。山东工商学院 2010 届毕业论文 致谢语 “不积跬步无以至千里” ，这次毕业论文能够最终顺 利完成， 归功于各位老师 四年间的认 真负

25、责，使我能够很好的掌握 专业知识，并在 毕业论 文中得以体现。也正是你 们长期不懈的 支持和帮助才使得我的毕业论文最终顺利完成。最后，我向全体老师们表示衷心感谢特别感 谢, 谢谢你们四年的辛勤栽培！ 2 山东工商学院 2010 届毕业论文 参考文献： 1.黄玉刚. 浅析线性规划法在铁路工程材料经济运距计算中的应用J 2006.(02. 2.卢米雪. 基于线性规划的资源管理决策模型的研究与应用J . 中南财经政法研究生学报 2008(05. 3.铁路工程技术 手册 - 铁道部第二勘测设计 院.中国铁道出版社. 4.徐干成等 .地下工程支护结 构.中国水利水电出版社. 5.铁路隧道设计规范. TB

26、10003 2005. 6.时速 250 公里客运专线铁路双 线隧道复合式衬砌:通隧 2005 0201. 7. 林华珍,周根贵.求解最短路问题的一种优化矩阵算法J.长江大学学报理工卷,2007,(05. 8. 宋丽敏 .最短路径的 编程实现 J. 华北航天工 业学院学报J,2001,(04. 9 .桂劲松,康海贵.结构可靠计算的最优方法及 matlab 实现J. 四川建筑科学研究,2004,(02. 10 姜启源，数学模型（第二版） ，北京：高等教育出版社，1993. 11 谢金星，薛毅 编 著， 优化模型与 LINGO/LINDO 软件，北京:清华大学出版社，2005 年。 12 谢金星，邢文训，网络优化，北京：清 华大学出版社，2000 13 张立. 钢管订购与运输的优化模型J. 常熟理工学院学报 2006(04 14. 杨 振 华 , 胡 国 雷 , 郭 跃 华 . 钢 管 订 购 与 运 输 问 题 一 的 数 学 模 型 与 求 解 J. 数 学 的 实 践 与 认 识.2002(03 15. 吴 雪 琴 . 线 性 规 划 在 物 流 运 输 中 数 学 模 型 的 建 立 及 应 用 J. 江 西 电 力 职 业 技 术 学 院 学 报.2007(01 16. 启源.数学模型M.北京:高等教育出版社 ,1997. 17.