《线性规划算法的应用及其matlab实现》由会员分享，可在线阅读，更多相关《线性规划算法的应用及其matlab实现（23页珍藏版）》请在金锄头文库上搜索。
1、理学院毕业设计（论文）题目：线性规划算法的应用及其MATLAB实现专 业 数学与应用数学班 级 10122111学 号 1012211139姓 名 蒋芬指 导 教 师 许建强2013年5月2日线性规划算法的应用及其MATLAB实现摘要：线性规划作为一种优化工具，50年代后线性规划的应用范围不断扩大。已被广泛的运用于军事，经济等部门，是辅助人们进行科学管理的一种数学方法。它广泛应用现有的科学技术和数学方法，解决实际中的问题，帮助决策人员选择最优方案和决策。本篇文章主要论述了线性规划的算法及其在实际生活中的几种典型的应用及算法在Matlab中的实现。如在运输中的应用，通过线性规划计算出的方案合理安
2、排人力物力等资源，使经济效果达到最好。利用lingo软件得出模型运行结果，分析模型的影子价格。关键词：线性规划的算法、最优方案、Matlab、应用、lingo、影子价格Application of MATLAB linear programming algorithmAbstract：Linear programming as an optimization tool, After the 1950s, the scope of application of linear programming continues to expand. Has been widely used in mili
3、tary, economic and other sectors, Is a mathematical method to help people to achieve a scientific management It is widely used in the existing science and technology and mathematical methods to solve practical problems and help decision makers choose the best solution and decision making. This artic
4、le discusses the linear programming algorithm and some typical applications and algorithms in real life implementations in Matlab. Such as transportation, computed by linear programming of the program reasonable arrangement manpower material resources, make the economic effect is the best.The result
5、s of model runs using the lingo software, the analysismodel of shadow price.Keywords: Linear programming algorithm, the optimal scheme, Matlab,Application，Lingo The shadow price目录1 引言41.1 课题的目的和意义41.2 国内外研究现状与发展趋势41.3 文献综述51.4 论文研究主要内容52 背景知识介绍62.1线性规划62.2运输问题72.3选址问题72.4线性规划几种常见的模型92.5小结103线性规划求解实际
6、问题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程序221 引言1.1 课题的目的和意义 线性规划法是解决多变量最优决策的数学方法，是在各种相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。 线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助
7、人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。 在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定
8、的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。 1.2 国内外研究现状与发展趋势 法国数学家J.-B.-J.傅里叶和C.瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947年美国数学家G.B.丹
9、齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947年美国数学家J.von诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。50年代后对线性规划进行大量的理论研究，并涌现出一大批新的算法。例如，1954年C.莱姆基提出对偶单纯形法，1954年S.加斯和T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年A.塔克提出互补松弛定理，1960年G.B.丹齐克和P.沃尔夫提出分解算法等。1979年苏联数学家L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984年美国贝尔电话实验
10、室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。比如1）生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力配合等计划以适应波动的需求计划，主要用线性规划和模拟方法等。如巴基斯坦某一重型制造厂用线性规划安排生产计划，节省10%的生产费用。此外还可用于生产作业计划、日程表的编排等。此外还有在合理下料、配料问题、物料管理等方面的应用。2）运输问题：这涉及空运、水运、公路运输、铁路运输、管道运输、场内运输。空运问题涉及飞行航班和飞
11、行机组人员服务时间安排等。为此在国际运筹学协会中设有航空后的运行安排。公路运输出了汽车调度以外，还有公路网的设计和分析，市内公共汽车的路线选择和行车时间表的安排，出租汽车的调度和停车场的设立。铁路方面的应用就更多了。3）车辆问题：在我过城市化水平不断提高和车辆数量不断增加的前提下，车辆交通问题给我们带来了巨大的问题。因此在这种情况下我们需要未雨绸缪，对城市车辆进行调研分析，优化车辆路线，提出预防和缓解交通拥堵的对策。建立线性规划模型的方法。(可以适当展开)建立实际问题线性规划模型的基本步骤。1.3 文献综述（1）陈婷，何中元，线性规划算法在车辆调度中的应用，计算机工程与科学，2005，27，5
12、2-55. 此文献中陈婷，何中元主要介绍了线性规划理论及其在一般运输问题中的应用。然后将其推广到车辆调度问题,提出并建立了一个动态的、开放的现代智能车辆管理调度系统模型，最后对各种模型求解算法进行了比较和分析，并给出了计算结果。（2） 李军.车辆调度问题的分派启发式算法J.系统工程理论与实践.1991.（1）：1920 此文献中李军对有时间窗的车辆调度问题进行了分析,提出了以分派为基础的启发式算法。算法中讨论了如何完成任务所需要的车辆数。定义了两种分派费用，设计了在分配过程中安排线路的方法，并用实例进行了验证，最后对算法的适用性及进一步应用进行了讨论。（3） Jacques Renaud,Gi
13、lbert Laporte and Fayez F.Boctor A tabu Search Heuristic for the multi-depot vehicle Routing Problems. Networks, 1997, 30, 105119. 此文献中Jacques Renaud，Gilbert Laporte与 Fayez F.Boctor最重要的解决车辆路径规划问题的塔布启发式搜索算法。回顾了十个最重要的解决车辆路径规划问题的塔布启发式搜索算法。首先描述一些主要的塔布搜索特性：邻里关系结构、短期记忆、长期记忆、强化。然后描述各种塔布搜索的算法，最后给出计算结果和结论。1.
14、4 论文研究主要内容 本课题主要是研究利用线性规划分析运输问题、选址问题，以寻找在成本和收益按一定的比例组合最优的决策。建立数学模型，即用数学符号和式子表述决策变量，构造目标函数、确定约束条件。本文主要对线性规划，0-1规划，整数规划进行梳理，了解这些方法的理论基础和应用背景。了解线性规划的算法，运用实例忽略不必要、次要的因素，主要考虑运输成本建立相应的数学模型。选择运输成本最小最优方案，运用matlab进行线性规划的算法的实现。 运输问题考虑的是将某种物质从若干供应点运往一些需求点，在供需量约束条件下使总费用最小，或者利润最大。运输问题是线性规划应用最广泛的领域之一。在标准的运输问题中，供需
15、两通常是平衡的，即供应点的总供应量等于需求点的总需求量。本文中涉及供大于需，单这并不会引起本质的区别，一样可以方便地建立线性规划模型求解。 选址问题研究内容十分广泛，从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，涉及经济、政治、社会、管理、心理及工程地质等多门学科。设施选址是众多选址问题的一个重要研究领域。所研究的设施是指与生产、商业流通及人类生活有关的用地规模相对较小的具体网点、场所，如工厂、仓库、消防站、变电站、污水处理中心，加油(气)站等。研究方法主要依靠运筹学、拓扑学、管理学等计量方法，这是设施选址与其他选址问题的重要区别。本文研究的选址问题属于覆盖问题，由于原有公司不能满足顾客的需求量，因此需要研究满足覆盖所有需求点顾客的前提下，使得运输费用最小。2 背景知识介绍2.1线性规划 线性规划的广泛应用是计算机时代的产物。早在1939年苏联学者康托
