2022年线性规划算法的应用及其MATLAB实现推荐 .pdf

《2022年线性规划算法的应用及其MATLAB实现推荐 .pdf》由会员分享，可在线阅读，更多相关《2022年线性规划算法的应用及其MATLAB实现推荐 .pdf（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 理学院毕业设计（论文）题目：线性规划算法的应用及其MATLAB 实现专业数学与应用数学班级10122111 学号1012211139 姓名蒋芬指导教师许建强2013 年 5 月 2 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 24 页 -2 线性规划算法的应用及其MATLAB 实现摘要：线性规划作为一种优化工具，50年代后线性规划的应用范围不断扩大。已被广泛的运用于军事，经济等部门，是辅助人们进行科学管理的一种数学方法。它广泛应用现有的科学技术和数学方法，解决实际中的问题，帮助决策人员选择最优方案和决策。本篇文章主要论述了线性规划的算法及其在实际生活中的几种典型的应用及

2、算法在Matlab 中的实现。如在运输中的应用，通过线性规划计算出的方案合理安排人力物力等资源，使经济效果达到最好。利用lingo 软件得出模型运行结果，分析模型的影子价格。关键词：线性规划的算法、最优方案、Matlab、应用、lingo、影子价格Application of MATLAB linear programming algorithm Abstract：Linear programming as an optimization tool,After the 1950s,the scope of application of linear programming continues

3、to expand.Has been widely used in military,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 solu

4、tion and decision making.This article 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 econom

5、ic effect is the best.The results 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 名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 24 页 -3 目录1 引言.4 1.1 课题的目的和意义.4 1.2 国内外研究现状与发展趋势.4 1.3 文献综述.5 1

6、.4 论文研究主要内容.5 2 背景知识介绍.6 2.1 线性规划.6 2.2 运输问题.7 2.3 选址问题.7 2.4 线性规划几种常见的模型.9 2.5 小结.10 3 线性规划求解实际问题.11 3.1 运输问题.11 3.1.1 问题概述.11 3.1.2 实际问题模型建立及求解.12 3.1.3 结果分析.15 3.1.4 运输问题“影子价格”.15 3.2 选址问题.16 3.2.1 问题概述.16 3.2.2 实际问题模型建立及求解.17 3.2.3 结果分析.19 4 总结.20 5 致谢.20 6 参考文献.21 7 附录.22 7.1 程序.22 名师资料总结-精品资料欢

7、迎下载-名师精心整理-第 3 页，共 24 页 -4 1引言1.1课题的目的和意义线性规划法是解决多变量最优决策的数学方法，是在各种相互关联的多变量约束条件下，解决或规划一个对象的线性目标函数最优的问题，即给与一定数量的人力、物力和资源，如何应用而能得到最大经济效益。线性规划是运筹学中研究较早、发展较快、应用广泛、方法较成熟的一个重要分支,它是辅助人们进行科学管理的一种数学方法.研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写 LP。它是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科

8、学的依据。在现实的生产经营、商品销售、经济建设和物资管理过程中，常常会遇到各类物资的分配和调运问题，即将各种生产资料或生活资料消耗品从供给基地调运到需求基地，这里就需要如何根据现有条件科学、合理的安排调运方案，提高运输经济效益。这就是属于线性规划中网络配送的以最小的成本完成货物的运输问题。运输问题就是讨论有关物资调运的问题，即将数量和单位运价都给定的某种物资从供应站运送到消费站，要求在供给和需求平衡的同时，制定出流量与流向，使总运输成本最低。运输问题是特殊的线性规划问题，根据问题的要求，建立数学模型，用表上作业法或线性规划软件求解，即可得出最佳的调运方案，取得了较好的经济效益。在运输问题中，确

9、定的需求限制占据着重要的地位，即必须确定需求以及相应地确定需求的约束条件。1.2国内外研究现状与发展趋势法国数学家J.-B.-J.傅里叶和C.瓦莱普森分别于1832 和1911 年独立地提出线性规划的想法，但未引起注意。1939 年苏联数学家.康托罗维奇在生产组织与计划中的数学方法一书中提出线性规划问题，也未引起重视。1947 年美国数学家 G.B.丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了基础。1947 年美国数学家 J.von 诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用范围和解题能力。50年代后对线性规划进行大量的理论研

10、究，并涌现出一大批新的算法。例如，1954 年 C.莱姆基提出对偶单纯形法，1954 年 S.加斯和 T.萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956 年 A.塔克提出互补松弛定理，1960年 G.B.丹齐克和 P.沃尔夫提出分解算法等。1979 年苏联数学家 L.G.Khachian提出解线性规划问题的椭球算法，并证明它是多项式时间算法。1984 年美国贝尔电话实验室的印度数学家 N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大。

11、比如1）生产计划：在总体计划方面主要是从总体确定生产、存储和劳动力配合等计划以适应波动的需求计划，主要用线性规划和模拟方法等。如巴基斯坦某一重型制造厂用线性规划安排生产计划，节省 10%的生产费用。此外还可用名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 24 页 -5 于生产作业计划、日程表的编排等。此外还有在合理下料、配料问题、物料管理等方面的应用。2）运输问题：这涉及空运、水运、公路运输、铁路运输、管道运输、场内运输。空运问题涉及飞行航班和飞行机组人员服务时间安排等。为此在国际运筹学协会中设有航空后的运行安排。公路运输出了汽车调度以外，还有公路网的设计和分析，市内公共汽车的

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

13、的现代智能车辆管理调度系统模型，最后对各种模型求解算法进行了比较和分析，并给出了计算结果。（2）李军.车辆调度问题的分派启发式算法J.系统工程理论与实践.1991.（1）：1920 此文献中李军对有时间窗的车辆调度问题进行了分析,提出了以分派为基础的启发式算法。算法中讨论了如何完成任务所需要的车辆数。定义了两种分派费用，设计了在分配过程中安排线路的方法，并用实例进行了验证，最后对算法的适用性及进一步应用进行了讨论。（3）Jacques Renaud,Gilbert Laporte and Fayez F.Boctor A tabu Search Heuristic for the multi-

14、depot vehicle Routing Problems.Networks,1997,30,105119.此文献中Jacques Renaud，Gilbert Laporte与 Fayez F.Boctor 最重要的解决车辆路径规划问题的塔布启发式搜索算法。回顾了十个最重要的解决车辆路径规划问题的塔布启发式搜索算法。首先描述一些主要的塔布搜索特性：邻里关系结构、短期记忆、长期记忆、强化。然后描述各种塔布搜索的算法，最后给出计算结果和结论。1.4论文研究主要内容本课题主要是研究利用线性规划分析运输问题、选址问题，以寻找在成本和收益按一定的比例组合最优的决策。建立数学模型，即用数学符号和式子表

15、述决策变量，构造目标函数、确定约束条件。本文主要对线性规划，0-1 规划，整数规划进行梳理，了解这些方法的理论基础和应用背景。了解线性规划的算法，运用实例忽略不必要、次要的因素，主要考虑运输成本建立相应的数学模型。选择运输成本最小最优方案，运用 matlab进行线性规划的算法的实现。名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 24 页 -6 运输问题考虑的是将某种物质从若干供应点运往一些需求点，在供需量约束条件下使总费用最小，或者利润最大。运输问题是线性规划应用最广泛的领域之一。在标准的运输问题中，供需两通常是平衡的，即供应点的总供应量等于需求点的总需求量。本文中涉及供大于需

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

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

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

19、理科学的重要基础和手段之一。线性规划：线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成的符合抽象数学模型。线性规划研究的问题主要有两类：1、任务确定后，如何统筹安排，尽量做到用尽量少的人力和物力资源来完成任务；2、有一定量的人力、物力资源，如何安排使用他们，使完成的任务（创造名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 24 页 -7 的利润）最多。在生产管理和经济活动中经常提出这样一类问题，即如何合理地利用有限的人力、物力、财力等资源，以便得到最好的经济效果。2.2 运输问题在处理产、供、销的经济活动中，会经常遇到物资调拨的运输问

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

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

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

23、问题，这篇具有里程碑意义的论文大大激发了选址问题的理论研究，从此，选址理论的研究开始活跃起来，文献数目也急剧增多。名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 24 页 -8 选址问题：基本问题（1）P-中位问题（p-median problems）：P-中位问题（也叫 P-中值问题）是研究如何选择P 个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。（2）P-中心问题（p-center problems）（3）P-中心问题也叫 minmax 问题，是探讨如何在网络中选择 P 个服务站，使得任意一需求点到距离该需求点最近的服务站的最大距离最小问题。（4）覆盖问题（co

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

25、问题上。无容量限制固定费用下的选址问题(UFLP)就是将固定建站费用加到 P-中位问题的目标函数上，并且去掉对服务站建站个数的约束。（2）截流问题截流问题研究顾客需求产生在路线上的问题，根据服务站工作性质可以分为服务型和对抗型两大类。服务型截流问题广泛应用于交通规划、交通服务、交通监测等方面，比如如何在交通路网中设立交通量观测点使监测到的交通流量最大的问题就是服务型截流问题。对抗型截流问题用于解决收费、检查、缉私等站点的选址问题。（3）Hub 选址问题 Hub 选址问题是和截流问题有些类似的选址问题，需求也是产生在 OD 对上，在顾客从 O 点出发到 D 的过程中要接受 Hub 的服务。同截流

26、问题不同的是，OD 流并不是走最短路从 O 点到 D 点，经过 Hub 中转服务后要比直接从O 点到 D 点要快（4）选址分配问题选址分配问题的一般形式类似于 P-中位问题（5）随机选址问题随机选址问题中考虑到现实世界的复杂性，把服务站的运行时间、建设成本、需求点位置、需求数量等部分或全部输入参数看作是不确定的。随机选址问题分为随机概率问题和随机情景问题。随机概率问题是指输入参数是服从某种分布时的随机选址问题。随机情景问题是将不确定的性分解成多个可能在将来发生的状态，同随机概率选址问题相区别的是它是离散的随机问题，模型的目标是在所有可能的情况下达到最佳。（6）动态选址问题现实世界中不仅存在着不

27、确定性，也存在着动态性，因此动态模型能更准确地反映实际问题，当然，考虑动态因素不可避免地会增加模型的复杂性和求解的名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 24 页 -9 难度。动态选址问题研究的是在未来若干时间段内服务站的最优选址问题，在不同的时间段内动态选址模型的参数值是不同的，但在某一具体的时间段内模型参数是确定的。（7）竞争选址问题竞争选址问题考虑市场上存在两个以上的同类产品或服务的提供者，或服务站提供多个产品或服务。目前的竞争选址研究集中在静态问题上，考虑确定和随机两种情况，研究背景多以连锁零售业为主。静态确定型的竞争选址问题是在现存的竞争者已知而且确定，顾客只到

28、最有吸引力的服务站的“全有全无”假设的条件下研究的，静态随机竞争选址问题是在 Huff的引力模型的基础上研究的。2.4 线性规划几种常见的模型线性规划时运筹学的一个重要分支。自1947 年丹捷格（G.B.Gantzig）提出了一般线性规划问题求解的方法单纯形法之后，线性规划在理论上趋向成熟，在实际中日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件个决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最优设计到工业、农业、交通运输业、军事、经济计划和管理决策等领域都能发挥作用。长期以来，建立线性规划的数学模型来合理地利用有限的人力、物力、财力等资源，以便得到最好的

29、经济效果，一直是各国有关专家和官员关注的课题。一个理想的数学模型能够准确的使得有限的资源能得到最大化的使用，不同类型线性规划模型有各自不同的特点，能解决不同的实际问题，弄清这些特点根据不同的实际问题建立几种模型。线性规划模型主要有以下几种，一般模型，整数模型，0-1 模型等等。下面将逐一介绍。模型 1 线性规划一般模型在这个模型中（1）每一个问题都用一组决策变量（nxxx,21）表示某一方案，这组决策变量的值就代表一个具体方案。一般这些变量取值都是非负且连续的。（2）存在有关的数据，同决策变量构成互不矛盾的约束条件，这些约束条件可以用一组线性等式或不等式表示。（3）都有一个要求达到的目标，它可

30、以用决策变量及其有关的价值系数构成的线性函数（称为目标函数）来表示。按问题的不同，要求目标函数实现最大化或最小化。一般形式为：名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 24 页 -10,0,0,0),(),(),(.max(min)21221122222121112121112211nnnnnnnnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcZ（1）模型 2 整数规划模型在有些线性规划问题中，对于某些具体问题，常有要求解答必须是整数的情形，例如，所求解是机器的台数、完成工作的人数或者装卸的车数等，分数或小数的解答就不合要求。因此，对求最优整数解

31、的问题，有必要另行研究，这样的问题称为整数规划。整数规划中如果所有的便是都限制为（非负）整数，就称为纯整数规划或者为全整数规划；如果一部分变数限制为整数，则称为混合整数规划。整数规划的一般形式：njxmibxatsxczjnjijijnjjj,2,1,0,2,1,.max(min)11为整数（2）模型 3 0-1 规划模型0-1 规划是决策变量仅取值0 或 1 的一类特殊的整数规划。0-1规划的一般形式njxmibxatsxczjnjijijnjjj,2,110,2,1,.max(min)11，或（3）2.5 小结现实生活中很多问题都能运用线性规划的数学模型来解决，通过忽略次要因素或者给不能忽

32、略的因素加一定的权重建立数学模型。得到最优的方案。名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 24 页 -11 对于线性规划问题有以下步骤：1）明确问题：何种方案使得所解最大化或最小化；2）确定决策变量：是问题中要确定的未知量，表明规划中用数量表示的方案或决策；3）定义目标函数：zmin或wmax；4）根据问题表示约束条件；5）确定数学模型，求解。3 线性规划求解实际问题3.1 运输问题3.1.1 问题概述现在人们生产活动中，不可避免的要进行物资调运工作，如某时期内将生产基地的蔬菜，粮食等各类物资，分别运到需要这些物资的地区。如何根据各地的生产量和需求量及各地之间的运输费用

33、，如何制定一个运输方案，使总的运输量费用最小，这类的问题称为运输问题。假设有m个产地，记为mAAA,21，生产某种物资，可供应的产量分别为maaa,21,有n个销地，记为nBBB,21，其需求量分别为nbbb,21，假设在供需平衡的情况下，即miai1=njbj1，从第 i 个产地到j个销地的单位物资的运费为ijC，在满足各地需求的前提下，求运费最小的方案。设njmixij,2,1,2,1为第 i 个产地到第j个销地的运量，则运输问题的数学模型为ijminjijxcz11min名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 24 页 -12 njmixbxaxijijmiiji

34、jnjij,2,1,2,1011（4）当目标是利益时，目标式改为最大值，在供需平衡条件下，有nm个等式约束，有 mn个变量，约束条件的系数矩阵A有nm行 mn列，目标函数由运价矩阵nmC*与变量矩阵nmX*对应元素相乘求和构成。3.1.2 实际问题模型建立及求解1）供需平衡例 1：某食品公司有三个罐头加工厂A1、A2、A3，四个仓库 B1、B2、B3、B4。已知相关数据如下：求总的运输费用最小的运输策略。加工厂仓库B1 B2 B3 B4 产量A1 464 513 654 867 75 A2 352 416 690 791 125 A3 995 682 388 685 100 分配量80 65

35、70 85 表（一）数学模型为：名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 24 页 -13 4,3,2,1;3,2,108570658010012575.685388682995791690416352867654513464min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxzij（5）利用 matlab 编写程序求解得：gxph Optimization terminated.fval=1.

36、5254e+05 ans=0.0000 20.0000 0.0000 55.0000 80.0000 45.0000 0.0000 0.0000 0.0000 0.0000 70.0000 30.0000 因此总的运输费用最小为152540，运输方案为：仓库B2 和加工厂 A1 生产20；仓库 B4和加工厂 A1生产 55；仓库 B1和加工厂 A2生产 80；仓库 B2和加工厂 A2生产 45；仓库 B3和加工厂 A3生产 70；仓库 B4和加工厂 A3生产 30。2）供大于需例 2：某水管站主管着广阔地域的水资源分配机构。由于该地域十分干燥，需要从外地引水。已知引入的水来自 R1、R2、R3

37、三条河流，主要供应客户为D1、D2、D3、D4四个城市的供水部门。除了R3的水不能供应 D4之外，所有的河流均可供应这四个城市。运输表格如下：求合理的供水方案。名师资料总结-精品资料欢迎下载-名师精心整理-第 13 页，共 24 页 -14 河流城市D1 D2 D3 D4 供量R1 160 130 220 170 5 R2 140 130 190 150 6 R3 190 200 230-5 需求2 5 4 1.5 表（二）数学模型为：4,3,2,1;3,2,105.1452565.230200190150190130140170220130160min34241433231332221231

38、2111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsMxxxxxxxxxxxxzij（6）利用 matlab 编写程序求解得：gdyx Optimization terminated.fval=1.9750e+03 ans=0.0000 5.0000 0.0000 0.0000 名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 24 页 -15 2.0000 0.0000 2.5000 1.5000 0.0000 0.0000 1.5000 0.0000 运送水的最小费用

39、为：1975，合理的供水方案为：R1为城市 D1供水的供量为 5；R2为城市 D1供水的供量为 2；R2为城市 D3供水的供量为 2.5；R2为城市D4供水的供量为 1.5；R3为城市 D3供水的供量为 1.53.1.3 结果分析该模型根据实际问题忽略次要因素，主要考虑运输成本，此模型的优点：我们通过题目要求分析出了目标函数，写出了约束条件，建立了模型，该模型建立出了较理想状态下最优分配方案，可使运费最少。有优点也有缺点，缺点：该模型有一定的局限性，如现实中不能时刻都保证道路的畅通，为了更贴近实际，应考虑道路的畅通性对运输过程中的影响。另外，模型较简单，可能误差较大。供需平衡时产品的生产与需求

40、相同不会产生产品的堆积，这样大大减低了生产成本。当供大于需出现时产品就会堆积，增加一定的存储费用，因此在建立数学模型式供大于需存在不等式，所以在使用matlab 编写程序时，假设A为约束条件矩阵，b 为目标函数的系数向量。当存在不等式时A，b 不为空，如没有不等式，而只有等式是，A,b。3.1.4 运输问题“影子价格”定义：基于线性规划中的合理利用有限资源以求得最好的经济效果的规划问题。影子价格是在其它条件不变的情况下，单位资源变化所引起的目标函数的最优值的变化。本文将对运输问题每个约束条件的“影子价格”（一般情况下 lindo给出的是充分条件）。运用 lingo软件建立线性规划数学模型并求解

41、，这也就是通常所说的对目标函数系数的敏感性分析。这里主要对于运输问题中 供大于需 这类问题进行“影子价格”的分析。基本数据获取同上：运用 lingo软件求解模型结构如下：Global optimal solution found.Objective value:1975.000 Total solver iterations:7 Variable Value Reduced Cost X11 0.000000 0.000000 X12 5.000000 0.000000 X13 0.000000 10.00000 X14 0.000000 0.000000 X21 2.000000 0.000

42、000 X22 0.000000 20.00000 X23 2.500000 0.000000 名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 24 页 -16 X24 1.500000 0.000000 X31 0.000000 10.00000 X32 0.000000 50.00000 X33 1.500000 0.000000 X34 0.000000 0.1000000E+11 Row Slack or Surplus Dual Price 1 1975.000-1.000000 2 0.000000 20.00000（1）3 0.000000 40.00000（2）

43、4 3.500000 0.000000（3）5 0.000000-180.0000（4）6 0.000000-150.0000（5）7 0.000000-230.0000（6）8 0.000000-190.0000（7）对于上述运行结果除了告诉我们问题的最优解和最优值以外，还有许多对分析结果有用的信息。结合给予说明。1）7个约束条件的右端不妨看作7种“资源”，输出结果的第 19-25行“Slack or Surplus”给出这 7种“资源”在最优解下是否剩余，（1）-（7）种“资源”的剩余均为零，表明 7种“资源”都已用完。一般称“资源”剩余为零的约束为紧约束（有效约束）。2）目标函数可以看着

44、“效益”，成为紧约束的“资源”一旦增加，“效益”必然跟着增长（减少）。输出结果第 19-25行“Dual Price”给出这 7种资源在最优解下“资源”增加一个单位时“效益”的增量。约束条件影子价格影子价格的含义河流 R1的供量20.00000河流 R1的供量增加 1个单位时，运输的成本降低20个单位。河流 R2的供量40.00000河流 R2的供量增加 1个单位时，运输的成本降低40个单位。河流 R3的供量0.000000河流 R1的供量增加 1个单位时，运输的成本不会发生变化。表（三）这里，“效益”的增量可以看作是“资源”的潜在价格，经济学上称为影子价格，即河流 R1 供应的一个单位的影子

45、价格为20元，河流 R2 供应的一个单位的影子价格为 40元。3.2 选址问题3.2.1 问题概述名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 24 页 -17 某公司原有工厂nAAA,21，现准备新建一个工厂，向mBBB,21仓库提供产品，现有YX,两个选址方案。两个方案除了运输成本以外其他成本都相同。公司考虑选择一个使得成本最小的方案。该问题实际是求最小值的问题，把两个备选方案代入现有条件比较最小运输成本差异，最小运输成本较小的方案入选。假设iA 工厂向jB 仓库运输的运输成本为ijC，iA 工厂向jB 仓库运输的数量为ijxmjni,2,1,2,1。工厂X向仓库jB 运

46、输成本为xjA，工厂X向仓库jB 运输数量为XjA，工厂 Y 向仓库jB 运输成本为yjA，工厂 X 向仓库jB 运输数量为YjA，ija 表示供给量，ijb 表示需求量，xja 表示工厂 X 对仓库jB 的供给量，yja 表示工厂Y 对仓库jB 的供给量，则问题可以表示为：mjnibAAxCaAAaxCtsAAxCzijXjxjmiijijyjmjXjxjijnjijijmjXjxjijij,2,1,2,10.min1111n1im1j，所以参数都大于（7）mjnibAAxCaAAaxCtsAAxCwijYjyjniijijyjmjYjyjijmjijijmjYjyjijij,2,1,2,1

47、0.min1111n1im1j，所以参数都大于（8）3.2.2 实际问题模型建立及求解例3:已有两个物流园区 F1和 F2供应4个销售点 P1,P2,P3，P4,由于需求量不断增加，需再设一个物流园区。可供选择的地点是F3和 F4,试在其中选择一个名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 24 页 -18 作为最佳地址。根据已有资料分析得各物流园区到各销售点的总费用，如表所示:供应地与需求点1p2p3p4p供应量（台）1F8.0 7.8 7.7 7.8 7000 2F7.65 7.50 7.35 7.15 5500 3F7.15 7.05 7.18 7.65 12500

48、4F7.08 7.20 7.50 7.45 需求量（台）4000 8000 7000 6000 25000 表（四）假设供应地向销售点供应的数量为ijx，4,3,2,13,2,1ji。建立模型为：4,3,2,13,2,1,060007000800040001250055007000.65.718.705.715.715.735.75.765.78.77.78.70.8min342414332313322212312111343332312423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxx

49、xzij（9）4,3,2,13,2,1,060007000800040001250055007000.45.75.72.708.715.735.75.765.78.77.78.70.8min342414332313322212312111444342412423222114131211343332312423222114131211jixxxxxxxxxxxxxxxxxxxxxxxxxtsxxxxxxxxxxxxzij（10）利用 matlab编程求解如下：F3 Optimization terminated.名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 24 页 -19 f

50、val=1.8187e+05 ans=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+05 f4 Optimization terminated.fval=1.8287e+05 ans=1.0e+03*0.0000 0.0000 7.0000 0.0000 0.0000 0.0000 0.0000 5.5000 4.0000 8.0000 0.0000 0.5000 则若增加点设在 F3点，运输最小成本为