线性规划算法的应用及其MATLAB实现

1理学院毕业设计（论文）题目：线性规划算法的应用及其MATLAB实现专业数学与应用数学班级10122111学号1012211139姓名蒋芬指导教师许建强2013年5月2日2线性规划算法的应用及其MATLAB实现摘要：线性规划作为一种优化工具，50年代后线性规划的应用范围不断扩大。已被广泛的运用于军事，经济等部门，是辅助人们进行科学管理的一种数学方法。它广泛应用现有的科学技术和数学方法，解决实际中的问题，帮助决策人员选择最优方案和决策。本篇文章主要论述了线性规划的算法及其在实际生活中的几种典型的应用及算法在Matlab中的实现。如在运输中的应用，通过线性规划计算出的方案合理安排人力物力等资源，使经济效果达到最好。利用lingo软件得出模型运行结果，分析模型的影子价格。关键词：线性规划的算法、最优方案、Matlab、应用、lingo、影子价格ApplicationofMATLABlinearprogrammingalgorithmAbstract：Linearprogrammingasanoptimizationtool,Afterthe1950s,thescopeofapplicationoflinearprogrammingcontinuestoexpand.Hasbeenwidelyusedinmilitary,economicandothersectors,IsamathematicalmethodtohelppeopletoachieveascientificmanagementItiswidelyusedintheexistingscienceandtechnologyandmathematicalmethodstosolvepracticalproblemsandhelpdecisionmakerschoosethebestsolutionanddecisionmaking.ThisarticlediscussesthelinearprogrammingalgorithmandsometypicalapplicationsandalgorithmsinreallifeimplementationsinMatlab.Suchastransportation,computedbylinearprogrammingoftheprogramreasonablearrangementmanpowermaterialresources,maketheeconomiceffectisthebest.Theresultsofmodelrunsusingthelingosoftware,theanalysismodelofshadowprice.Keywords:Linearprogrammingalgorithm,theoptimalscheme,Matlab,Application，LingoTheshadowprice3目录1引言..............................................................41.1课题的目的和意义............................................41.2国内外研究现状与发展趋势....................................41.3文献综述....................................................51.4论文研究主要内容............................................52背景知识介绍......................................................62.1线性规划.....................................................62.2运输问题.....................................................72.3选址问题.....................................................72.4线性规划几种常见的模型.......................................92.5小结........................................................103线性规划求解实际问题............................................113.1运输问题....................................................113.1.1问题概述..............................................113.1.2实际问题模型建立及求解................................123.1.3结果分析..............................................153.1.4运输问题“影子价格”..................................153.2选址问题....................................................163.2.1问题概述..............................................163.2.2实际问题模型建立及求解................................173.2.3结果分析..............................................194总结.............................................................205致谢.............................................................206参考文献.........................................................217附录.............................................................227.1程序........................................................2241引言1.1课题的目的和意义线性规划法是解决多变量最优决策的数学方法，是在各种相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。1.2国内外研究现状与发展趋势法国数学家J.-B.-J.傅里叶和C.瓦莱－普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家Л.В.康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。比如1）生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力配合等计划以适应波动的需求计划，主要用线性规划和模拟方法等。如巴基斯坦某一重型制造厂用线性规划安排生产计划，节省10%的生产费用。此外还可用5于生产作业计划、日程表的编排等。此外还有在合理下料、配料问题、物料管理等方面的应用。2）运输问题：这涉及空运、水运、公路运输、铁路运输、管道运输、场内运输。空运问题涉及飞行航班和飞行机组人员服务时间安排等。为此在国际运筹学协会中设有航空后的运行安排。公路运输出了汽车调度以外，还有公路网的设计和分析，市内公共汽车的路线选择和行车时间表的安排，出租汽车的调度和停车场的设立。铁路方面的应用就更多了。3）车辆问题：在我过城市化水平不断提高和车辆数量不断增加的前提下，车辆交通问题给我们带来了巨大的问题。因此在这种情况下我们需要未雨绸缪，对城市车辆进行调研分析，优化车辆路线，提出预防和缓解交通拥堵的对策。建立线性规划模型的方法。(可以适当展开)建立实际问题线性规划模型的基本步骤。1.3文献综述（1）陈婷，何中元，线性规划算法在车辆调度中的应用，计算机工程与科学，2005，27，52-55.此文献中陈婷，何中元主要介绍了线性规划理论及其在一般运输问题中的应用。然后将其推广到车辆调度问题,提出并建立了一个动态的、开放的现代智能车辆管理调度系统模型，最后对各种模型求解算法进行了比较和分析，并给出了计算结果。（2）李军.车辆调度问题的分派启发式算法[J].系统工程理论与实践.1991.（1）：19～20此文献中李军对有时间窗的车辆调度问题进行了分析,提出了以分派为基础的启发式算法。算法中讨论了如何完成任务所需要的车辆数。定义了两种分派费用，设计了在分配过程中安排线路的方法，并用实例进行了验证，最后对算法的适用性及进一步应用进行了讨论。（3）JacquesRenaud,GilbertLaporteandFayezF.BoctorAtabuSearchHeuristicforthemulti-depotvehicleRoutingProblems.Networks,1997,30,105–119.此文献中JacquesRenaud，GilbertLaporte与FayezF.Boctor最重要的解决车辆路径规划问题的塔布启发式搜索算法。回顾了十个最重要的解决车辆路径规划问题的塔布启发式搜索算法。首先描述一些主要的塔布搜索特性：邻里关系结构、短期记忆、长期记忆、强化。然后描述各种塔布搜索的算法，最后给出计算结果和结论。1.4论文