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

山东工商学院2010届毕业论文 PAGE基于线性规划的最优路径设计[摘要]各个领域中的大量问题都可以归结为线性规划问题尤其在物流管理活动中，有大量的规划问题，如网络配送中的运输规划问题，它属于线性规划问题的特例运输问题存在多种解法，目前计算机应用普及，用一般的解线性规划的软件来解运输问题是一条较好的途径根据调查表明,近几十年来,线性规划在各个行业中都得到了广泛的应用，而且运输问题的模型不单只是适用于一般意义上的物资运输问题，更重要的是它适用于一切道路网络问题因此。[关键词]线性规划Floyd算法优路径Linearprogramming-basedoptimalpathdesign[Abstract]LARGEnumberofproblemsinvariousfieldscanbereducedtolinearprogrammingproblems,especiallyinlogisticsmanagementactivities,alargenumberofplanningissues,suchasnetworkdistributionproblemsintransportplanning,itisaspecialcaseoflinearprogrammingproblemswithmultiplesolutionofthetransport,thecurrentpopularityofcomputerapplications,usingthegenerallinearprogrammingsoftwaretosolvethetransportproblemisagoodwaytoAccordingtothesurveyindicatedthatinrecentdecades,linearprogramminginallsectorshavebeenwidelyused,andtransportandthemodelisnotonlyapplicabletothegeneralsenseofmaterialtransport,moreimportantly,itappliestoallroadnetworkproblem,thereforeandimprovetheeconomiceffectofthegeneralintwoways:first,thetechnologicalimprovements.Second,improvementofproductionorganizationandplanning,namelyreasonablearrangethehumanandmaterialresources.Themethodovercomesthemaximumdistanceequaltotheaveragedistancemethodandthelackofequallaws,principlesaremoresimpleandclear,highprecision,thiseasytoplaytheadvantagesofcomputertechnologytoimprovetheaccuracyofeconomicdistance.Inthispaper,steelandtransportationorders,forexample,usingmatlab,lingosoftwaretodesigntheoptimalpathofthetransportpipe,calculatetheminimumpipeorderandtransportcosts.[Keywords]LinearFloydalgorithmOptimalpath目录TOC\o"1-4"\h\z\u引言 1第一章线性规划数学模型 21.1概论 21.1.1问题的提出 21.1.2国外研究的现状 31.1.3国内研究的现状 41.1.4本文研究的必要性 41.2线性规划的数学模型的一般形式 51.3线性规划问题的解 51.3.1几个概念 51.3.2线性规划问题的解 61.3.3线性规划问题解的性质 6第二章线性规划在运输中的应用 72.1运输问题的特征 72.2线性规划在运输问题中的一般数学形式 8第三章Floyd算法 93.1最短路径定义 93.1.1单源最短路径 93.1.2任意顶点间的最短路径 103.2Floyd算法 103.2.1Floyd算法基本思想 103.2.2Floyd算法步骤 113.2.3算法复杂度比较 123.3Floyd算法演示系统 13第四章线性规划在运输问题中的实例 144.1例题：钢管订购与运输 144.2模型假设 174.3问题分析： 174.4符号说明： 194.5模型建立与求解 20结论 26致谢语 27参考文献 28附录 31PAGE4引言各个领域中的大量问题都可以归结为线性规划问题尤其实物流问题。物流是物品从供应地向接受地的实体流动过程。据数据统计，在机械产品的生产过程中，加工时间仅占10%左右，而物流时间却占90%，很大一部分生产成本消耗在物流过程中。而运杂费接近总物流费用50%。因此，运输成了降低物流费用最有潜力的领域，它是物流活动的核心。在运输组织中，如何选择合理路线使运输费用最省，线性规划是实现运输管理最优化最成功的方法。线性规划创始人、美国G.Dantzig教授曾在一个学术会议上说，他除了发现单纯形法之外，还有两个功绩：一是总结人们的实践经验，认识到在管理科学中大多数的实际关系都可用线性公式来表示；二是明确提出应该使用目标函数作为最优方案的选择准则。为此，本文主要介绍在物流运输中如何建立它的线性规划数学模型。至于求解线性规划的单纯形法不在这里介绍，因为用单纯形法求解线性规划问题计算机应用软件包代替了人工计算，并能非常轻松地解决此问题。因此，现在物流业面临的新问题是针对具体的物资运输实物如何建立起数学模型，以及建立线性规划的条件。。本文以钢管订购与运输为例，利用matlab、lingo软件，设计出钢管运输的最优路径，求出钢管订购与运输的最小费用。第一章线性规划数学模型1.1概论线性规划作为运筹学的一人重要分支，是研究较早，理论较完善，应用最广泛的一门科学。它所研究的问题主要包括两个方面：一是在一项任务确定后，如何以最低限度和成本（如人力、物力、资金和时间等）去完成这一任务；二是如何在现有条件下进行组织和安排，以完成更多的工作。因此，线性规划就是求一组变量的值，使它满足一组线性式子，并使一个线性函数的值最大（或最小）的数学方法线性规划所研究的问题主要有两类：一类是已给定一定数量的人力和物力资源，如何用这些资源完成最大量的任务；另一类是已给定一项任务，如何统筹安排，才能以最小量的资源去完成这项任务。即有关“多、快、好、省”的最优化问题。随着我国市场经济体系的逐步确立以及我国成功加入WTO,企业生存与发展的内外在环境发生了深刻的变化,经营方式也由粗放型向集约型转化,而成本管理正是这一转变的核心,成本信息是企业管理和企业决策的关键要素与先决条件。作为我国新兴的第三方物流企业正处于起步和发展阶段,资金相对短缺,企业实力也相对薄弱,尤其是在现有的物流企业中,成本始终居高不下。要想在市场竞争中取得优势地位和长远发展,企业就必须建立适合自身发展特点的成本核算体系,从而控制成本支出,提高经济效益。线性规划则起着至关重要的作用。1.1.1问题的提出供料方案的优化实质上是在有限的资源下运用最优化技术进行物料调配的规划活动,其目的是保证物料运输运费的最小化。近年来,随着我国四个现代化建设速度的加快,很多行业尤其是基础性建设行业,其发展突飞猛进。各行各业出现了欣欣向荣的良好局面,但同时因计划和管理不当,在时间、人力、物力和资金等方面造成了很大的浪费,从而给我国的经济建设带来了严重损失。为了适应现代化建设的发展,尤其是要保证基础性行业不能出现资金的过度浪费,国家要求相关主管部门严格把关,切实做好资金使用合理这一关。而要达到这种要求,就要求相关的设计、施工、监理部门做好优化设计这一环。传统模式下的优化设计主要是根据设计者的经验而定,并没有形成一套科学合理的优化方法。因此,实际操作中许多优化设计往往不一定就是最佳的优化方案,从而造成了大量的资源浪费。作为铁(公)路设计部门来讲,如何搞好施工组织方案、施工供料方案的优化设计,降低工程总造价,提高资金的利用效率,不仅关系到本部门的生计问题,同时也关系到国家投资规划是否切实可行的根本问题。在铁(公)路设计过程中,应用最优化技术搞好供料方案的优化设计,相关方案未见详细报道。鉴于这种情况,笔者正是从上述背景下,引入供料方案的优化模型,通过线性规划的表上作业法详细地阐述供料方案中运输路径的选择问题,并求其最优解,从而为供料方案的设计提出几点建议与参考。1.1.2国外研究的现状供料方案的优化问题其实属于运筹学应用研究的规划问题。早在上世纪20年代,以兰德公司(RAND)为首的一些部门开始运用运筹学着重研究战略性问题以及武器系统的设计和其可能合理运用的方法,取得了良好的效果。后来运筹学相继在工业、农业、经济和社会问题等各领域都有应用。与此同时,运筹数学有了飞快的发展,并形成了运筹学的许多分支。如数学规划(线性规划、非线性规划、整数规划、目标规划、动态规划、随机规划等)、图论与网络、排队论、存贮论、对策论、决策论、维修更新理论、搜索论、可靠性和质量管理等。线性规划是由丹捷格(G.B.Dantzig)在1947年发表的一篇成果,而应用到实际问题中的是美国空军军事规划小组,当时他们提出了求解线性规划的单纯形法。线性规划提出后很快受到经济学家的重视,并在运筹学某些领域中发挥过重要作用。1974年,Zeleny等将解线性规划的单纯形法给予适当修改后,用来解多目标线性规划问题,或把多目标线性规划问题化成单目标的线性规划问题后求解,给运筹学工作者带来了很大方便,尤其是在求汽车运输调配规划问题上带来了捷径。上世纪六十年代初由LandDoig和Dakin等人提出用分枝定界法求解整数规划问题,由于该法灵活且便于用计算机求解,所以现在它己是解整数规划的重要方法。该法在求解供料运输问题上虽然比穷举法优越,因为它仅在一部分可行解的整数解中寻求最优解,计算量比穷举法小。但若变量数目很大,其计算工作量也是相当可观的。1951年美国数学家贝尔曼(R.Bellman)创造了解决最优化问题的一种新的方法一一动态规划。动态规划法是运筹学的一个分支,它是解决多阶段决策过程最优化的一种数学方法。工程上的许多问题用动态规划的方法去处理,常常比线性规划或非线性规划更有成效。但由于动态规划依赖条件较强,且存在维数障碍,故在供料运输的汽车模型上应用不是很广。在总体计划方面主要是从总体确定生产、存贮和劳动力的配合等计划以适应波动的需求计划,主要用线性规划和模拟方法等。如解决供料、物流、车流调配等问题中,Attahiru.s.A使用模拟退火算法,Barbarosoghi,ozgur、xuJ,J使用禁忌搜索算法,oilbertLaPorte,HeleneMereure,YvesNobert使用分枝定界算法,Danting,Ramse使用线性规划的单纯形法,HowKAndrewLAndrewL基于时间窗的混合算法,于叮ankiliscD,儿ranondisCT使用了空间决策支持系统,ehia一Ho一ehen,e址ng一Jung叭ng,Pei一channehang应用了蚁群算法,HwangH51研究了基于有时间限制的基因遗传算法的改进模型的车辆运输问题,他们都较好地解决了汽车调配、流向、最佳路线等难题。国外有关运筹学的理论与实践方面的研究,对国内运筹学的发展起到了积极有益的促进作用。我们可以从借鉴中创新、从创新中发展,不断地运用运筹学的先进算法为我们的实际问题服务。1.1.3国内研究的现状国内对运筹学的研究始于上世纪80年代,与国外的研究几乎同时起步。钱颂迪、胡运权结合运筹学,运用线性规划和数学模拟方法解决了生产应用中的合理下料、配料问题,以及物料管理等方面的应用。李军、张锦、秦明森脾运用线性规划,解决了物流运输中汽车路径选择的原则、方法及技巧,很好地建立了汽车运行费用最少的数学模型,方便物流规划者使用。郭耀煌、陈唐民、陈星明结合线性规划、多目标决策等理论,重点解决了车辆调配或车流运输中最短时间的数学模型,给车流规划带来了极大方便。邓先礼、施光燕、邢文训四等人运用最优化技术,结合线性规划,解决了运输规划中最短路径问题、最佳运费问题,给工程设计提供了参考依据。左永林、柳志新结合水电工程砂石料场优选的实例,运用动态规划的方法解决了供料方案的优化研究。目前,国内外虽然对线性规划理论的研究日臻完善,但在实际应用中由于理论的深度及结合实际问题的多样性,尤其在大中型铁(公)路建设规划中,很多设计者并未按其优化模型进行规划设计。因此有必要结合实际问题,寻找一种直观、简单方便的优化模型推广应用。线性规划中的表上作业法正是在这种情况中能方便地发挥用场。本文主要基于线性规划进行展开研究,以期望对今后工程设计的顺利开展提供一点点建议。1.1.4本文研究的必要性（1）.理论上的必要性运输模型虽然很多,然而带有限制因素的运输模型上未见详细报道。诸如供料场日开采能力受限制,行车运货的密度受限制,开行时间受安全环保的限制等,而这类情况时有发生。因此有必要对这类实用性较强的模型进行深入地研究;（2.）工程实践上的必要性由于大多上供料方案的优化设计采用传统的工区分段法。该法虽然简单、直观,也能解决实际问题,但常常出现供料运输上的抢购现象,即针对某一供料点,很多需料点同时排队进行购料运输,而稍远的供料点却出现门庭冷清的现象。发生此类情况主要是由于在供料运输的规划设计时采用的是工段分区法,该法只是一个局部优化的运输模型,并不能解决全局性的运输调配问题。因此,为保证整个工程的顺利进行,保证供需平衡并且达到运费最小,有必要进行工程实际上的应用研究。第二章线性规划在运输中的应用在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。结论从中可以注意到上述所计算的结果是建立在当前的运输和投资成本基础上的，所以在仔细研究每一种情况的时候，应认真考虑一下这些成本可能带来的变化对于每一种情况来说，必须要描述出未来这些成本的变化情况，这样就可以知道目前所作出的决定是否正确。运用线性规划法来指导一些投资决策具有一定的理论意义和实际价值几乎所有公司都会遇到有约束条件下的最优化问题,因此线性规划在许多管理问题中都能应用,本文仅从如何利用现有资源获得最大利润进行优化设计只要是对生产制造投资财务工程等求最大利润最小成本等问题,就基本上可以用线性规划来求解。线性规划是合理利用、调配资源的一种应用数学方法。它的基本思路就是在满足一定的约束条件下，使预定的目标达到最优。它的研究内容可归纳为两个方面：一是系统的任务已定，如何合理筹划，精细安排，用最少的资源(人力、物力和财力)去实现这个任务；二是资源的数量已定，如何合理利用、调配，使任务完成的最多。前者是求极小，后者是求极大。线性规划是在满足企业内、外部的条件下，实现管理目标和极值(极小值和极大值)问题，就是要以尽少的资源输入来实现更多的社会需要的产品的产出。因此，线性规划是辅助企业“转轨”、“变型”的十分有利的工具，它在辅助企业经营决策、计划优化等方面具有重要的作用。把线性规划的知识运用到企业中去，可以使企业适应市场激烈的竞争，及时、准确、科学的制定生产计划、投资计划、对资源进行合理配置。过去企业在制定计划，调整分配方面很困难，既要考虑生产成本，又要考虑获利水平，人工测算需要很长时间，不易做到机动灵活，运用线性规划并配合计算机进行测算非常简便易行，几分钟就可以拿出最优方案，提高了企业决策的科学性和可靠性。其决策理论是建立在严格的理论基础之上，运用大量基础数据，经严格的数学运算得到的，从而在使企业能够在生产的各个环节中优化配置，提高了企业的效率，对企业是大有益处的。致谢语“不积跬步无以至千里”，这次毕业论文能够最终顺利完成，归功于各位老师四年间的认真负责，使我能够很好的掌握专业知识，并在毕业论文中得以体现。也正是你们长期不懈的支持和帮助才使得我的毕业论文最终顺利完成。最后，我向\全体老师们表示衷心感谢特别感谢,谢谢你们四年的辛勤栽培！参考文献：[1].黄玉刚.浅析线性规划法在铁路工程材料经济运距计算中的应用[J]2006.(02).[2].卢米雪.基于线性规划的资源管理决策模型的研究与应用[J].中南财经政法研究生学报2008(05).[3].铁路工程技术手册-铁道部第二勘测设计院.中国铁道出版社.[4].徐干成等.地下工程支护结构.中国水利水电出版社.[5].铁路隧道设计规范.TB10003–2005.[6].时速250公里客运专线铁路双线隧道复合式衬砌:通隧20050201.[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].贺明峰.数学模型引论[M].北京:高等教育出版社,2001.[18].数学实验[M].北京:科学出版社,2000.[19].石涌.精通MATLAB6.5版[M].北京:北京航空航天大学出版社,2003.[20].吴成强.\o"线性目标函数最优解的探求相似度44%"线性目标函数最优解的探求[J].中学生理科月刊,2003,(10)[21].徐伟宣.\o"用参数线性规划求解一个非线性规划问题相似度43%"用参数线性规划求解一个非线性规划问题[J].中国管理科学,1989,(04)[22].周玉英.\o"如何求线性规划问题的最优解相似度40%"如何求线性规划问题的最优解[J].数学爱好者(高二版),2006,(02)[23].徐伟宣,何建秋,邹庆云.\o"目标函数带绝对值号的特殊非线性规划问题相似度38%"目标函数带绝对值号的特殊线性规划问题[J].中国管理科学,1987,(03)[24].汤子赓.\o"约束函数和目标函数带绝对值号的特殊非线性规划问题的求解方法相似度36%"约束函数和目标函数带绝对值号的特殊线性规划问题的求解方法[J].中国管理科学,1989,(03)[25].刘国华.\o"线性规划思想在非线性规划问题中的应用相似度36%"线性规划思想在线性规划问题中的应用[J].新高考(语文数学英语),2008,(Z1)[26].黄智灵.\o"如何求取可靠的整数最优解相似度33%"如何求取可靠的整数最优解[J].福建中学数学,2003,(04)[27].凌世春.\o"线性规划问题精讲精析相似度33%"线性规划问题精讲精析[J].考试(高考数学版),2007,(04)[28].石彤菊,许会峰.\o"基于网上数学实验设计开发——无约束非线性规划问题算法的实现相似度33%"基于网上数学实验设计开发——无约束线性规划问题算法的实现[J].保定师范专科学校学报,2005,(04)[29].何杭佳.\o"同伦连续方法及其在非线性规划中的应用相似度32%"同伦连续方法及其在线性规划中的应用[J].玉林师范学院学报(自然科学版),2007,(05)[30]陈冬英.线性规划法在运输问题中的应用[J].科技广场,2008,(11).[31]钟志梅,韦莉.2008高考线性规划问题分类解析[J].数学教学研究,2009,(01).[32]郭永生.线性规划在钢筋下料中的应用[J].煤炭工程,2009,(01).[33]卢米雪.基于线性规划的资源管理决策模型的研究与应用[J].中南财经政法大学研究生学报,2008,(05).[34]夏咏芳.线性规划模型的四种示例[J].数学学习与研究(教研版),2009,(03).[35]徐加华.线性规划中的参数问题[J].数理天地,HYPERLINK"/kns50/Navi/Bridge.aspx?DBCode=cjfd&LinkType=IssueLink&Field=BaseID*year*issue&TableName=CJFDYEARINFO&Value=SLDG*20