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

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

2、blems 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 transpor

3、t,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 app

4、licable 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 th

5、e 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 pa

6、per,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.2线性规划的数学模型的一般形式.错误!未定义书签。1.3线性规划问题的解.错误!未定义书签。第

7、二章线性规划在运输中的应用 (12.1运输问题的特征.错误!未定义书签。2.2线性规划在运输问题中的一般数学形式.错误!未定义书签。第三章Floyd算法.错误!未定义书签。3.1最短路径定义.错误!未定义书签。3.2Floyd算法.错误!未定义书签。3.3Fl oyd算法演示系统.错误!未定义书签。第四章线性规划在运输问题中的实例.错误!未定义书签。4.1例题:钢管订购与运输.错误!未定义书签。4.2模型假设.错误!未定义书签。4.3问题分析:.错误!未定义书签。4.4符号说明:.错误!未定义书签。4.5模型建立与求解.错误!未定义书签。结论 (1致谢语 (2参考文献 (3附录.错误!未定义书

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

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

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

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

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

13、根本问题。在铁(公路设计过程中,应用最优化技术搞好供料方案的优化设计,相关方案未见详细报道。鉴于这种情况,笔者正是从上述背景下,引入供料方案的优化模型,通过线性规划的表上作业法详细地阐述供料方案中运输路径的选择问题,并求其最优解,从而为供料方案的设计提出几点建议与参考。使用禁忌搜索算法,oilbertLaPorte,HeleneMereure,YvesNobert使用分枝定界算法,Danting,Ramse使用线性规划的单纯形法,HowKAndrewLAndrewL基于时间窗的混合算法,于叮ankiliscD,儿ranondisCT使用了空间决策支持系统,ehia一Ho一ehen,e址ng一J

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

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

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

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

18、述所计算的结果是建立在当前的运输和投资成本基础上的,所以在仔细研究每一种情况的时候,应认真考虑一下这些成本可能带来的变化对于每一种情况来说,必须要描述出未来这些成本的变化情况,这样就可以知道目前所作出的决定是否正确。运用线性规划法来指导一些投资决策具有一定的理论意义和实际价值几乎所有公司都会遇到有约束条件下的最优化问题,因此线性规划在许多管理问题中都能应用,本文仅从如何利用现有资源获得最大利润进行优化设计只要是对生产制造投资财务工程等求最大利润最小成本等问题,就基本上可以用线性规划来求解。线性规划是合理利用、调配资源的一种应用数学方法。它的基本思路就是在满足一定的约束条件下,使预定的目标达到最优。它的研究内容可归纳为两个方面:一是系统的任务已定,如何合理筹划,精细安排,