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

1、理学院毕业设计（论文）题目：线性规划算法的应用及其MATLAB实现专 业 数学与应用数学班 级 学 号 姓 名 蒋芬指 导 教 师 许建强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 military, economic and

3、 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 article discusses the l

4、inear 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 results of model runs us

5、ing 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线性规划求解实际问题113.1运输问题113.1.1

6、问题概述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年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规

10、划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。比如1）生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力配合等计划以适应波动的需求计划，主要用线性规划和模拟方法等。如巴基斯坦某一重型制造厂用线性规划安排生产计划，节省10%的生产费用。此外还可用于生产作业计划、日程表的编排等。此外还有在合理下料、配料问题、物料管理等方面的应用。2）运输问题：这涉及空运、水运、公路运输、铁路运输、管道运输、场内运输。空运问题涉及飞行航班和飞行机组人员服务时间安排等。为此在国际

11、运筹学协会中设有航空后的运行安排。公路运输出了汽车调度以外，还有公路网的设计和分析，市内公共汽车的路线选择和行车时间表的安排，出租汽车的调度和停车场的设立。铁路方面的应用就更多了。3）车辆问题：在我过城市化水平不断提高和车辆数量不断增加的前提下，车辆交通问题给我们带来了巨大的问题。因此在这种情况下我们需要未雨绸缪，对城市车辆进行调研分析，优化车辆路线，提出预防和缓解交通拥堵的对策。建立线性规划模型的方法。(可以适当展开)建立实际问题线性规划模型的基本步骤。1.3 文献综述（1）陈婷，何中元，线性规划算法在车辆调度中的应用，计算机工程与科学，2005，27，52-55. 此文献中陈婷，何中元主要

12、介绍了线性规划理论及其在一般运输问题中的应用。然后将其推广到车辆调度问题,提出并建立了一个动态的、开放的现代智能车辆管理调度系统模型，最后对各种模型求解算法进行了比较和分析，并给出了计算结果。（2） 李军.车辆调度问题的分派启发式算法J.系统工程理论与实践.1991.（1）：1920 此文献中李军对有时间窗的车辆调度问题进行了分析,提出了以分派为基础的启发式算法。算法中讨论了如何完成任务所需要的车辆数。定义了两种分派费用，设计了在分配过程中安排线路的方法，并用实例进行了验证，最后对算法的适用性及进一步应用进行了讨论。（3） Jacques Renaud,Gilbert Laporte and

13、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.4 论文研究主要内容 本课题主要是研

14、究利用线性规划分析运输问题、选址问题，以寻找在成本和收益按一定的比例组合最优的决策。建立数学模型，即用数学符号和式子表述决策变量，构造目标函数、确定约束条件。本文主要对线性规划，0-1规划，整数规划进行梳理，了解这些方法的理论基础和应用背景。了解线性规划的算法，运用实例忽略不必要、次要的因素，主要考虑运输成本建立相应的数学模型。选择运输成本最小最优方案，运用matlab进行线性规划的算法的实现。 运输问题考虑的是将某种物质从若干供应点运往一些需求点，在供需量约束条件下使总费用最小，或者利润最大。运输问题是线性规划应用最广泛的领域之一。在标准的运输问题中，供需两通常是平衡的，即供应点的总供应量等

15、于需求点的总需求量。本文中涉及供大于需，单这并不会引起本质的区别，一样可以方便地建立线性规划模型求解。 选址问题研究内容十分广泛，从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴，涉及经济、政治、社会、管理、心理及工程地质等多门学科。设施选址是众多选址问题的一个重要研究领域。所研究的设施是指与生产、商业流通及人类生活有关的用地规模相对较小的具体网点、场所，如工厂、仓库、消防站、变电站、污水处理中心，加油(气)站等。研究方法主要依靠运筹学、拓扑学、管理学等计量方法，这是设施选址与其他选址问题的重要区别。本

16、文研究的选址问题属于覆盖问题，由于原有公司不能满足顾客的需求量，因此需要研究满足覆盖所有需求点顾客的前提下，使得运输费用最小。2 背景知识介绍2.1线性规划 线性规划的广泛应用是计算机时代的产物。早在1939年苏联学者康托洛维奇(JI.B.K a H T o P o B H Y)在解决工业生产组织和计划问题时，已提出了类似线性规划的模型，并给出了“解乘数法”的求解方法。由于当时未被重视，直到1960年康托洛维奇再次发表了最佳资源利用的经济计算一书后，才受到国内外的一致重视。为此康托洛维奇获得了诺贝尔经济学奖。 1947年，美国学者GeorgeDantzig（丹茨格）发明了求解线性规划的单纯形法

17、,从而为线性规划的推广奠定了基础。有人认为，求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。 1947年，美国数学家丹捷格(G.B.Dantizg)发表了关于线性规划的研究成果，所解决的问题是美国空军军事规划时提出的，并给出了求解线性规划问题的单纯形算法。 在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后，它的适用领域更广泛了。从解决技术问题中的最优化设计到工业、农业、商业、交通输业、军事、经济计划与管理、决策等各个领域均可发挥作用；从范围来看，小到一个小组的日常工作和计划安排，大至整个部门以致国民经济计划的最优方案的提出，都有用武之地。它具有适应性强、应用广泛

18、、计算技术比较简单的特点，是现代管理科学的重要基础和手段之一。 线性规划：线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成的符合抽象数学模型。 线性规划研究的问题主要有两类： 1、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务； 2、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造的利润）最多。 在生产管理和经济活动中经常提出这样一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。2.2运输问题 在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问题，如粮、棉油、煤炭、钢铁、水泥、

19、化肥、木材等物资要由若干个产地调运到若干个销售地。因此问题出现了，怎样制定合理的调运方案才能使总运费最小？对企业来说，生产决策的主要目标是：在现有条件下，如何最有效地利用人力、物力、财力等各种资源，以取得最大的经济效益。在21世纪物资短缺年代，企业可以靠扩大产量、降低制造成本去攫取第一利润。在物资丰富的年代，企业又可以通过扩大销售攫取第二利润。可是在新世纪和新经济社会，第一利润源和第二利润源已基本到了一定极限，目前剩下的一未开垦的处女地就是运输。降价是近几年家电行业企业之间主要的竞争手段，降价竞争的后盾是企业总成本的降低，即功能、质量、款式和售后服务以外的成本降价，也就是降低运输成本。国外的制

20、造企业很早就认识到了货运是企业竞争力的法宝，搞好运输可以实现零库存、零距离和零流动资金占用，是提高为用户服务，构筑企业供应链，增加企业核心竞争力的重要途径。在经济全球化、信息全球化和资本全球化的21世纪，企业只有建立现代货物运输结构，才能在激烈的竞争中，求得生存和发展。在此，运输对企业的重要性可窥一斑。 日常生活中，人们经常需要将某些物品由一个空间位置移动到另一个空间位置，这就产生了运输，如何判定科学的方案，使运输所需的总费用最少，就是运输的最优化决策问题。运输的最优化决策问题可以建立相应的数学模型，即通过数学运算进行解决。 运输问题是经常出现在社会经济生活和军事中的优化问题,是一种特殊的线性

21、规划问题,它是早期的线性网络中优化的一个例子.运输问题不仅仅代表了物资合理调运、车辆合理调度等常见问题,一些些其他类型的实际问题经过适当假设变换后也可以归结为运输问题,如最小费用流问题、最短路问题、指派问题可转化为运输问题或转运问题。运输问题在运筹学教学过程中占有及其重要地位,并且得到了许多学者的广泛关注,取得了众多重要的研究成果.2.3选址问题 1909 年，Weber 研究了在平面上确定一个仓库的位置使得仓库与多个顾客之间的总距离最小的问题(称为韦伯问题) ，正式开始了选址理论的研究。1964 年，Hakimi 提出了网络上的p-中值问题与p-中心问题，这篇具有里程碑意义的论文大大激发了选

22、址问题的理论研究，从此，选址理论的研究开始活跃起来，文献数目也急剧增多。 选址问题：基本问题（1） P-中位问题（p-median problems）：P-中位问题（也叫P-中值问题）是研究如何选择P个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。（2） P-中心问题（p-center problems）（3） P-中心问题也叫 minmax 问题，是探讨如何在网络中选择 P 个服务站，使得任意一需求点到距离该需求点最近的服务站的最大距离最小问题。（4） 覆盖问题（covering problems）（5） 覆盖问题分为最大覆盖问题和集覆盖问题两类。集覆盖问题研究满足覆盖所有需求点

23、顾客的前提下，服务站总的建站个数或建设费用最小的问题。 选址问题的扩招问题： 在前面三个基本选址问题的基础上考虑其它因素就形成了扩展选址问题。由于扩展选址问题是由不同的分类方法根据实际应用需要组合而成，所以各类型之间存在较大的交叉，这里仅以最具代表特征的部分对不同的类型命名并进行综述。 （1）带固定费用和容量限制的选址问题 最容易也最常想到也最有实际意义的就是考虑服务站建站的固定费用和服务站的容量(服务能力)限制这两个因素，所以早期对基本选址问题的扩展研究较多地集中在将这两个因素加进基本选址问题上。无容量限制固定费用下的选址问题(UFLP)就是将固定建站费用加到 P-中位问题的目标函数上，并且

24、去掉对服务站建站个数的约束。 （2）截流问题 截流问题研究顾客需求产生在路线上的问题，根据服务站工作性质可以分为服务型和对抗型两大类。服务型截流问题广泛应用于交通规划、交通服务、交通监测等方面，比如如何在交通路网中设立交通量观测点使监测到的交通流量最大的问题就是服务型截流问题。对抗型截流问题用于解决收费、检查、缉私等站点的选址问题。 （3）Hub 选址问题 Hub 选址问题是和截流问题有些类似的选址问题，需求也是产生在 OD 对上，在顾客从 O 点出发到 D 的过程中要接受 Hub 的服务。同截流问题不同的是，OD 流并不是走最短路从 O 点到 D 点，经过 Hub 中转服务后要比直接从 O

25、点到 D 点要快 （4）选址分配问题 选址分配问题的一般形式类似于 P-中位问题 （5）随机选址问题 随机选址问题中考虑到现实世界的复杂性，把服务站的运行时间、建设成本、需求点位置、需求数量等部分或全部输入参数看作是不确定的。随机选址问题分为随机概率问题和随机情景问题。随机概率问题是指输入参数是服从某种分布时的随机选址问题。随机情景问题是将不确定的性分解成多个可能在将来发生的状态，同随机概率选址问题相区别的是它是离散的随机问题，模型的目标是在所有可能的情况下达到最佳。 （6）动态选址问题 现实世界中不仅存在着不确定性，也存在着动态性，因此动态模型能更准确地反映实际问题，当然，考虑动态因素不可避

26、免地会增加模型的复杂性和求解的难度。动态选址问题研究的是在未来若干时间段内服务站的最优选址问题，在不同的时间段内动态选址模型的参数值是不同的，但在某一具体的时间段内模型参数是确定的。 （7）竞争选址问题 竞争选址问题考虑市场上存在两个以上的同类产品或服务的提供者，或服务站提供多个产品或服务。目前的竞争选址研究集中在静态问题上，考虑确定和随机两种情况，研究背景多以连锁零售业为主。静态确定型的竞争选址问题是在现存的竞争者已知而且确定，顾客只到最有吸引力的服务站的“全有全无”假设的条件下研究的，静态随机竞争选址问题是在 Huff的引力模型的基础上研究的。2.4线性规划几种常见的模型 线性规划时运筹学

27、的一个重要分支。自1947年丹捷格（G.B.Gantzig）提出了一般线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实际中日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件个决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优设计到工业、农业、交通运输业、军事、经济计划和管理决策等领域都能发挥作用。长期以来，建立线性规划的数学模型来合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果，一直是各国有关专家和官员关注的课题。一个理想的数学模型能够准确的使得有限的资源能得到最大化的使用，不同类型线性规划模型有各自不同的特点，能解决不同的实

28、际问题，弄清这些特点根据不同的实际问题建立几种模型。线性规划模型主要有以下几种，一般模型，整数模型，0-1模型等等。下面将逐一介绍。模型1 线性规划一般模型在这个模型中（1）每一个问题都用一组决策变量（）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负且连续的。（2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或不等式表示。（3）都有一个要求达到的目标，它可以用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。一般形式为：（1） 模型2 整数规划模型 在有些线性规划问题中，

29、对于某些具体问题，常有要求解答必须是整数的情形，例如，所求解是机器的台数、完成工作的人数或者装卸的车数等，分数或小数的解答就不合要求。因此，对求最优整数解的问题，有必要另行研究，这样的问题称为整数规划。整数规划中如果所有的便是都限制为（非负）整数，就称为纯整数规划或者为全整数规划；如果一部分变数限制为整数，则称为混合整数规划。整数规划的一般形式：（2）模型3 0-1规划模型0-1规划是决策变量仅取值0或1的一类特殊的整数规划。0-1规划的一般形式（3）2.5小结 现实生活中很多问题都能运用线性规划的数学模型来解决，通过忽略次要因素或者给不能忽略的因素加一定的权重建立数学模型。得到最优的方案。对

30、于线性规划问题有以下步骤：1）明确问题：何种方案使得所解最大化或最小化；2）确定决策变量：是问题中要确定的未知量，表明规划中用数量表示的方案或决策；3）定义目标函数：或；4）根据问题表示约束条件；5）确定数学模型，求解。3线性规划求解实际问题3.1运输问题3.1.1问题概述现在人们生产活动中，不可避免的要进行物资调运工作，如某时期内将生产基地的蔬菜，粮食等各类物资，分别运到需要这些物资的地区。如何根据各地的生产量和需求量及各地之间的运输费用，如何制定一个运输方案，使总的运输量费用最小，这类的问题称为运输问题。假设有个产地，记为，生产某种物资，可供应的产量分别为,有n个销地，记为，其需求量分别为

31、，假设在供需平衡的情况下，即=，从第个产地到个销地的单位物资的运费为，在满足各地需求的前提下，求运费最小的方案。设为第个产地到第个销地的运量，则运输问题的数学模型为（4） 当目标是利益时，目标式改为最大值，在供需平衡条件下，有个等式约束，有个变量，约束条件的系数矩阵有行列，目标函数由运价矩阵与变量矩阵对应元素相乘求和构成。3.1.2实际问题模型建立及求解1）供需平衡例1：某食品公司有三个罐头加工厂A1、A2、A3，四个仓库B1、B2、B3、B4。已知相关数据如下：求总的运输费用最小的运输策略。加工厂仓库B1B2B3B4产量A146451365486775A2352416690791125A39

32、95682388685100分配量80657085表（一）数学模型为：（5）利用matlab编写程序求解得： gxphOptimization terminated.fval = 1.5254e+05ans = 0.0000 20.0000 0.0000 55.0000 80.0000 45.0000 0.0000 0.0000 0.0000 0.0000 70.0000 30.0000因此总的运输费用最小为，运输方案为：仓库B2和加工厂A1生产20；仓库B4和加工厂A1生产55；仓库B1和加工厂A2生产80；仓库B2和加工厂A2生产45；仓库B3和加工厂A3生产70；仓库B4和加工厂A3生产

33、30。2）供大于需例2：某水管站主管着广阔地域的水资源分配机构。由于该地域十分干燥，需要从外地引水。已知引入的水来自R1、R2、R3三条河流，主要供应客户为D1、D2、D3、D4四个城市的供水部门。除了R3的水不能供应D4之外，所有的河流均可供应这四个城市。运输表格如下：求合理的供水方案。河流城市D1D2D3D4供量R11601302201705R21401301901506R3190200230-5需求2541.5表（二）数学模型为：（6）利用matlab编写程序求解得： gdyxOptimization terminated.fval = 1.9750e+03ans = 0.0000 5.

34、0000 0.0000 0.0000 2.0000 0.0000 2.5000 1.5000 0.0000 0.0000 1.5000 0.0000运送水的最小费用为：1975，合理的供水方案为：R1为城市D1供水的供量为5；R2为城市D1供水的供量为2；R2为城市D3供水的供量为2.5；R2为城市D4供水的供量为1.5；R3为城市D3供水的供量为1.53.1.3结果分析该模型根据实际问题忽略次要因素，主要考虑运输成本，此模型的优点：我们通过题目要求分析出了目标函数，写出了约束条件，建立了模型，该模型建立出了较理想状态下最优分配方案，可使运费最少。有优点也有缺点，缺点：该模型有一定的局限性，如

35、现实中不能时刻都保证道路的畅通，为了更贴近实际，应考虑道路的畅通性对运输过程中的影响。另外，模型较简单，可能误差较大。供需平衡时产品的生产与需求相同不会产生产品的堆积，这样大大减低了生产成本。当供大于需出现时产品就会堆积，增加一定的存储费用，因此在建立数学模型式供大于需存在不等式，所以在使用matlab编写程序时，假设A为约束条件矩阵，b为目标函数的系数向量。当存在不等式时A，b不为空，如没有不等式，而只有等式是，,。3.1.4运输问题“影子价格”定义：基于线性规划中的合理利用有限资源以求得最好的经济效果的规划问题。影子价格是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。

36、本文将对运输问题每个约束条件的“影子价格”（一般情况下lindo给出的是充分条件）。运用lingo软件建立线性规划数学模型并求解，这也就是通常所说的对目标函数系数的敏感性分析。这里主要对于运输问题中供大于需这类问题进行“影子价格”的分析。基本数据获取同上：运用lingo软件求解模型结构如下： Global optimal solution found. Objective value: 1975.000 Total solver iterations: 7 Variable Value Reduced Cost X11 0. 0. X12 5. 0. X13 0. 10.00000 X14 0

37、. 0. X21 2. 0. X22 0. 20.00000 X23 2. 0. X24 1. 0. X31 0. 10.00000 X32 0. 50.00000 X33 1. 0. X34 0. 0.E+11 Row Slack or Surplus Dual Price 1 1975.000 -1. 2 0. 20.00000（1） 3 0. 40.00000（2） 4 3. 0.（3） 5 0. -180.0000（4） 6 0. -150.0000（5） 7 0. -230.0000（6） 8 0. -190.0000（7）对于上述运行结果除了告诉我们问题的最优解和最优值以外，还有许

38、多对分析结果有用的信息。结合给予说明。1）7个约束条件的右端不妨看作7种“资源”，输出结果的第19-25行“Slack or Surplus”给出这7种“资源”在最优解下是否剩余，（1）-（7）种“资源”的剩余均为零，表明7种“资源”都已用完。一般称“资源”剩余为零的约束为紧约束（有效约束）。2）目标函数可以看着“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长（减少）。输出结果第19-25行“ Dual Price”给出这7种资源在最优解下“资源”增加一个单位时“效益”的增量。约束条件影子价格影子价格的含义河流R1的供量 20.00000河流R1的供量增加1个单位时，运输的成本降低

39、20个单位。河流R2的供量 40.00000河流R2的供量增加1个单位时，运输的成本降低40个单位。河流R3的供量 0.河流R1的供量增加1个单位时，运输的成本不会发生变化。表（三）这里，“效益”的增量可以看作是“资源”的潜在价格，经济学上称为影子价格，即河流R1供应的一个单位的影子价格为20元，河流R2供应的一个单位的影子价格为40元。3.2选址问题3.2.1问题概述 某公司原有工厂，现准备新建一个工厂，向仓库提供产品，现有两个选址方案。两个方案除了运输成本以外其他成本都相同。公司考虑选择一个使得成本最小的方案。该问题实际是求最小值的问题，把两个备选方案代入现有条件比较最小运输成本差异，最小

40、运输成本较小的方案入选。假设工厂向仓库运输的运输成本为，工厂向仓库运输的数量为。工厂向仓库运输成本为，工厂向仓库运输数量为，工厂向仓库运输成本为，工厂向仓库运输数量为，表示供给量，表示需求量，表示工厂对仓库的供给量，表示工厂对仓库的供给量，则问题可以表示为：（7）（8）3.2.2实际问题模型建立及求解例3:已有两个物流园区F1和F2供应4个销售点P1, P2, P3，P4,由于需求量不断增加，需再设一个物流园区。可供选择的地点是F3和F4,试在其中选择一个作为最佳地址。根据已有资料分析得各物流园区到各销售点的总费用，如表所示:供应地与需求点供应量（台）8.07.87.77.870007.657

41、.507.357.1555007.15 7.057.187.65125007.087.207.507.45需求量（台）400080007000600025000表（四）假设供应地向销售点供应的数量为，。建立模型为：（9）（10）利用matlab编程求解如下： F3Optimization terminated.fval = 1.8187e+05ans = 1.0e+03 * 0.0000 0.0000 6.5000 0.5000 0.0000 0.0000 0.0000 5.5000 4.0000 8.0000 0.5000 0.0000则若增加点设在F3点，运输最小成本为： 1.8187e+

42、05 f4Optimization terminated.fval = 1.8287e+05ans = 1.0e+03 * 0.0000 0.0000 7.0000 0.0000 0.0000 0.0000 0.0000 5.50004.0000 8.0000 0.0000 0.5000则若增加点设在F3点，运输最小成本为： 1.8287e+05比较两地运输成本 1.8287e+05 -1.8187e+05=1000。因此新设物流园区选择在F3。3.2.3结果分析该选址问题是通过成本计算，也就是将运输费用、配送费用模型化，根据约束条件及目标函数建立数学公式，从中寻求费用最小的方案。但是这种方法

43、也存在一定的缺陷，比如在寻求最优的地址解时，必须对业务量和生产成本进行正确的分析和判断。此类选址问题在选址时，应掌握的主要费用有，工厂到物流园区间的运输费。在选址时需要假设变动的因素使得成为不变因素。这样使得在建立数学模型的时候能抓住问题的本质。如果存在不能忽略的影响因素时，分别赋予一定的权重，采用加权法计算结果进行复查。4总结 本文通过对线性规划的模型和解法的研究，介绍了运输问题及选址问题的一般模型，并介绍求解过程，且分别进行Lingo和Matlab软件求解运输问题的操作，用matlab软件对现实实际生产问题的一个例子进行求解，分析求解结果的合理性，最后对供大于需的运输问题进行研究，利用li

44、ngo软件分析运行结果的影子价格。本文主要完成了以下工作：1）介绍了线性规划的模型和其常见的数学模型整数模型，0-1规划等，利用计算机工具对运输问题及选址问题进行了一一求解。2）通过对比较不同的运输问题进行了建模，并用matlab的软件进行了求解，得出结果进行比较分析，得出结论对供需平衡的运输问题其数学模型中约束条件都是等式不存在不等式，而对于供大于需的运输问题其数学模型中约束条件既有等式也有不等式。3）归纳总结了运输问题及选址问题的应用。4）比较两种不同运输问题在利用matlab编写程序求解数学模型时存在的不同。5致谢行文至此，我的这篇论文已接近尾声, 在论文完成之际，我首先向关心帮助和指导

45、我的指导老师许建强表示衷心的感谢并致以崇高的敬意！本学位论文是在我的指导老师许建强老师的亲切关怀与细心指导下完成的，从课题的选择到论文的最终完成，遇到了许多问题，是许老师给予了我细心的指导和不懈的支持，除此之外，他还关心我的实习工作情况，了解我的实际情况并热情的给我帮助。值得一提的是，许老师对学生认真负责，只要我有疑问他都会在第一时间帮我解决，许老师以其渊博的学识、严谨的治学态度、求实的工作作风和敏捷的思维给我留下了深刻的印象，在他的身上，我可以感受到一个学者的严谨和务实，这些都让我获益菲浅，并且将终生受用无穷。毕竟“经师易得，人师难求”，希望借此机会再次向许老师表示最衷心的感谢！在写毕业论文

46、的期间当然也得到了不少同学的帮助，在查阅参考资料时大家都能将自己好的网站资源共享，这对我的文论参考文献有了很大的帮助！在论文即将完成之际，我的心情无法平静，从开始进入课题到论文的顺利完成，有多少可敬的师长、同学、朋友给了我无言的帮助，在这里请接受我诚挚的谢意! 6参考文献1 刘承平数学建模方法高等教育出版社。2004.2 李军.车辆调度问题的分派启发式算法J.系统工程理论与实践.1991.（1）：19203 郑汉鼎.汽车调度问题的数学模型及其解法J.山东大学学报（自然科学版），1994.29（3）：9144 李军，郭强.车辆调度问题的改进表上作业法J.西南交通大学报，2000，35（5）：23

47、5 David Pisinger, Stefan Ropke. A general heuristic for vehicle routing problems. Computers & Operations Research, 2005,34, 24032435.6 Jacques Renaud,Gilbert Laporte and Fayez F.Boctor A tabu Search Heuristic for the multi-depot vehicle Routing Problems. Networks, 1997, 30, 105119.7 Fisher M L,Jaiku

48、mar R. A generalized assignment heuristic for vehicle routing J . Networks, 1981,11 (2): 109124页.8 姜大力,杨西龙,杜文,等.车辆路径问题的遗传算法研究J.系统工程理论与实践,1999,19(6):40-44. 9 杭省策,李怀祖.多车场车流分配的广义指派模型及其分解算法J.西安交通大学学报,1997,31(12):111-115.10 刑文训,谢金星.现代优化计算方法M.北京:清华大学出版社,1999：6882.11 陈婷，何中元，线性规划算法在车辆调度中的应用，计算机工程与科学，2005，27，52-55.12 朱玉龙，李建新，线性规划算法在武警部队车辆调度中的应用，农业装备与车辆工程，2011，2，43-46.13 姜启源，谢金星，叶俊，数学模型（第三版）高等教育出版社。2003.7附录7.1程序供需平衡c=464 513 654 867 352 416