线性规划算法的应用及其MATLAB实现讲解.docx
- 文档编号:9862743
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:30
- 大小:186.97KB
线性规划算法的应用及其MATLAB实现讲解.docx
《线性规划算法的应用及其MATLAB实现讲解.docx》由会员分享,可在线阅读,更多相关《线性规划算法的应用及其MATLAB实现讲解.docx(30页珍藏版)》请在冰点文库上搜索。
线性规划算法的应用及其MATLAB实现讲解
理学院
毕业设计(论文)
题目:
线性规划算法的应用及其MATLAB实现
专业数学与应用数学
班级10122111
学号1012211139
姓名蒋芬
指导教师许建强
2013年5月2日
线性规划算法的应用及其MATLAB实现
摘要:
线性规划作为一种优化工具,50年代后线性规划的应用范围不断扩大。
已被广泛的运用于军事,经济等部门,是辅助人们进行科学管理的一种数学方法。
它广泛应用现有的科学技术和数学方法,解决实际中的问题,帮助决策人员选择最优方案和决策。
本篇文章主要论述了线性规划的算法及其在实际生活中的几种典型的应用及算法在Matlab中的实现。
如在运输中的应用,通过线性规划计算出的方案合理安排人力物力等资源,使经济效果达到最好。
利用lingo软件得出模型运行结果,分析模型的影子价格。
关键词:
线性规划的算法、最优方案、Matlab、应用、lingo、影子价格
ApplicationofMATLABlinearprogrammingalgorithm
Abstract:
Linearprogrammingasanoptimizationtool,Afterthe1950s,thescopeofapplicationoflinearprogrammingcontinuestoexpand.Hasbeenwidelyusedinmilitary,economicandothersectors,IsamathematicalmethodtohelppeopletoachieveascientificmanagementItiswidelyusedintheexistingscienceandtechnologyandmathematicalmethodstosolvepracticalproblemsandhelpdecisionmakerschoosethebestsolutionanddecisionmaking.ThisarticlediscussesthelinearprogrammingalgorithmandsometypicalapplicationsandalgorithmsinreallifeimplementationsinMatlab.Suchastransportation,computedbylinearprogrammingoftheprogramreasonablearrangementmanpowermaterialresources,maketheeconomiceffectisthebest.Theresultsofmodelrunsusingthelingosoftware,theanalysismodelofshadowprice.
Keywords:
Linearprogrammingalgorithm,theoptimalscheme,Matlab,Application,LingoTheshadowprice
目录
1引言4
1.1课题的目的和意义4
1.2国内外研究现状与发展趋势4
1.3文献综述5
1.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
1引言
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%的生产费用。
此外还可用于生产作业计划、日程表的编排等。
此外还有在合理下料、配料问题、物料管理等方面的应用。
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论文研究主要内容
本课题主要是研究利用线性规划分析运输问题、选址问题,以寻找在成本和收益按一定的比例组合最优的决策。
建立数学模型,即用数学符号和式子表述决策变量,构造目标函数、确定约束条件。
本文主要对线性规划,0-1规划,整数规划进行梳理,了解这些方法的理论基础和应用背景。
了解线性规划的算法,运用实例忽略不必要、次要的因素,主要考虑运输成本建立相应的数学模型。
选择运输成本最小最优方案,运用matlab进行线性规划的算法的实现。
运输问题考虑的是将某种物质从若干供应点运往一些需求点,在供需量约束条件下使总费用最小,或者利润最大。
运输问题是线性规划应用最广泛的领域之一。
在标准的运输问题中,供需两通常是平衡的,即供应点的总供应量等于需求点的总需求量。
本文中涉及供大于需,单这并不会引起本质的区别,一样可以方便地建立线性规划模型求解。
选址问题研究内容十分广泛,从城市、产业带、经济技术开发区、跨国经济集团分公司到机场、水利设施、人类居住区、销售网点以及仓库、配送中心等的区位决策都是选址问题研究的范畴,涉及经济、政治、社会、管理、心理及工程地质等多门学科。
设施选址是众多选址问题的一个重要研究领域。
所研究的设施是指与生产、商业流通及人类生活有关的用地规模相对较小的具体网点、场所,如工厂、仓库、消防站、变电站、污水处理中心,加油(气)站等。
研究方法主要依靠运筹学、拓扑学、管理学等计量方法,这是设施选址与其他选址问题的重要区别。
本文研究的选址问题属于覆盖问题,由于原有公司不能满足顾客的需求量,因此需要研究满足覆盖所有需求点顾客的前提下,使得运输费用最小。
2背景知识介绍
2.1线性规划
线性规划的广泛应用是计算机时代的产物。
早在1939年苏联学者康托洛维奇(JI.B.KaHToPoBHY)在解决工业生产组织和计划问题时,已提出了类似线性规划的模型,并给出了“解乘数法”的求解方法。
由于当时未被重视,直到1960年康托洛维奇再次发表了《最佳资源利用的经济计算》一书后,才受到国内外的一致重视。
为此康托洛维奇获得了诺贝尔经济学奖。
1947年,美国学者George Dantzig(丹茨格)发明了求解线性规划的单纯形法,从而为线性规划的推广奠定了基础。
有人认为,求解线性规划的单纯形算法可与求解线性方程组的高斯消元法相媲美。
1947年,美国数学家丹捷格(G.B.Dantizg)发表了关于线性规划的研究成果,所解决的问题是美国空军军事规划时提出的,并给出了求解线性规划问题的单纯形算法。
在能用计算机来处理成千上万个约束条件和变量的大规模线性规划问题之后,它的适用领域更广泛了。
从解决技术问题中的最优化设计到工业、农业、商业、交通输业、军事、经济计划与管理、决策等各个领域均可发挥作用;从范围来看,小到一个小组的日常工作和计划安排,大至整个部门以致国民经济计划的最优方案的提出,都有用武之地。
它具有适应性强、应用广泛、计算技术比较简单的特点,是现代管理科学的重要基础和手段之一。
线性规划:
线性规划数学模型是由一组含有等式或者不等式的代数方程以及一个具有求极值关系的目标函数表达式构成的符合抽象数学模型。
线性规划研究的问题主要有两类:
1、任务确定后,如何统筹安排,尽量做到用尽量少的人力和物力资源来完成任务;
2、有一定量的人力、物力资源,如何安排使用他们,使完成的任务(创造的利润)最多。
在生产管理和经济活动中经常提出这样一类问题,即如何合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果。
2.2运输问题
在处理产、供、销的经济活动中,会经常遇到物资调拨的运输问题,如粮、棉油、煤炭、钢铁、水泥、化肥、木材等物资要由若干个产地调运到若干个销售地。
因此问题出现了,怎样制定合理的调运方案才能使总运费最小?
对企业来说,生产决策的主要目标是:
在现有条件下,如何最有效地利用人力、物力、财力等各种资源,以取得最大的经济效益。
在21世纪物资短缺年代,企业可以靠扩大产量、降低制造成本去攫取第一利润。
在物资丰富的年代,企业又可以通过扩大销售攫取第二利润。
可是在新世纪和新经济社会,第一利润源和第二利润源已基本到了一定极限,目前剩下的一"未开垦的处女地"就是运输。
降价是近几年家电行业企业之间主要的竞争手段,降价竞争的后盾是企业总成本的降低,即功能、质量、款式和售后服务以外的成本降价,也就是降低运输成本。
国外的制造企业很早就认识到了货运是企业竞争力的法宝,搞好运输可以实现零库存、零距离和零流动资金占用,是提高为用户服务,构筑企业供应链,增加企业核心竞争力的重要途径。
在经济全球化、信息全球化和资本全球化的21世纪,企业只有建立现代货物运输结构,才能在激烈的竞争中,求得生存和发展。
在此,运输对企业的重要性可窥一斑。
日常生活中,人们经常需要将某些物品由一个空间位置移动到另一个空间位置,这就产生了运输,如何判定科学的方案,使运输所需的总费用最少,就是运输的最优化决策问题。
运输的最优化决策问题可以建立相应的数学模型,即通过数学运算进行解决。
运输问题是经常出现在社会经济生活和军事中的优化问题,是一种特殊的线性规划问题,它是早期的线性网络中优化的一个例子.运输问题不仅仅代表了物资合理调运、车辆合理调度等常见问题,一些些其他类型的实际问题经过适当假设变换后也可以归结为运输问题,如最小费用流问题、最短路问题、指派问题可转化为运输问题或转运问题。
运输问题在运筹学教学过程中占有及其重要地位,并且得到了许多学者的广泛关注,取得了众多重要的研究成果.
2.3选址问题
1909年,Weber研究了在平面上确定一个仓库的位置使得仓库与多个顾客之间的总距离最小的问题(称为韦伯问题),正式开始了选址理论的研究。
1964年,Hakimi提出了网络上的p-中值问题与p-中心问题,这篇具有里程碑意义的论文大大激发了选址问题的理论研究,从此,选址理论的研究开始活跃起来,文献数目也急剧增多。
选址问题:
基本问题
(1)P-中位问题(p-medianproblems):
P-中位问题(也叫P-中值问题)是研究如何选择P个服务站使得需求点和服务站之间的距离与需求量的乘积之和最小。
(2)P-中心问题(p-centerproblems)
(3)P-中心问题也叫minmax问题,是探讨如何在网络中选择P个服务站,使得任意一需求点到距离该需求点最近的服务站的最大距离最小问题。
(4)覆盖问题(coveringproblems)
(5)覆盖问题分为最大覆盖问题和集覆盖问题两类。
集覆盖问题研究满足覆盖所有需求点顾客的前提下,服务站总的建站个数或建设费用最小的问题。
选址问题的扩招问题:
在前面三个基本选址问题的基础上考虑其它因素就形成了扩展选址问题。
由于扩展选址问题是由不同的分类方法根据实际应用需要组合而成,所以各类型之间存在较大的交叉,这里仅以最具代表特征的部分对不同的类型命名并进行综述。
(1)带固定费用和容量限制的选址问题
最容易也最常想到也最有实际意义的就是考虑服务站建站的固定费用和服务站的容量(服务能力)限制这两个因素,所以早期对基本选址问题的扩展研究较多地集中在将这两个因素加进基本选址问题上。
无容量限制固定费用下的选址问题(UFLP)就是将固定建站费用加到P-中位问题的目标函数上,并且去掉对服务站建站个数的约束。
(2)截流问题
截流问题研究顾客需求产生在路线上的问题,根据服务站工作性质可以分为服务型和对抗型两大类。
服务型截流问题广泛应用于交通规划、交通服务、交通监测等方面,比如如何在交通路网中设立交通量观测点使监测到的交通流量最大的问题就是服务型截流问题。
对抗型截流问题用于解决收费、检查、缉私等站点的选址问题。
(3)Hub选址问题
Hub选址问题是和截流问题有些类似的选址问题,需求也是产生在OD对上,在顾客从O点出发到D的过程中要接受Hub的服务。
同截流问题不同的是,OD流并不是走最短路从O点到D点,经过Hub中转服务后要比直接从O点到D点要快
(4)选址-分配问题
选址-分配问题的一般形式类似于P-中位问题
(5)随机选址问题
随机选址问题中考虑到现实世界的复杂性,把服务站的运行时间、建设成本、需求点位置、需求数量等部分或全部输入参数看作是不确定的。
随机选址问题分为随机概率问题和随机情景问题。
随机概率问题是指输入参数是服从某种分布时的随机选址问题。
。
随机情景问题是将不确定的性分解成多个可能在将来发生的状态,同随机概率选址问题相区别的是它是离散的随机问题,模型的目标是在所有可能的情况下达到最佳。
(6)动态选址问题
现实世界中不仅存在着不确定性,也存在着动态性,因此动态模型能更准确地反映实际问题,当然,考虑动态因素不可避免地会增加模型的复杂性和求解的难度。
动态选址问题研究的是在未来若干时间段内服务站的最优选址问题,在不同的时间段内动态选址模型的参数值是不同的,但在某一具体的时间段内模型参数是确定的。
(7)竞争选址问题
竞争选址问题考虑市场上存在两个以上的同类产品或服务的提供者,或服务站提供多个产品或服务。
目前的竞争选址研究集中在静态问题上,考虑确定和随机两种情况,研究背景多以连锁零售业为主。
静态确定型的竞争选址问题是在现存的竞争者已知而且确定,顾客只到最有吸引力的服务站的“全有全无”假设的条件下研究的,静态随机竞争选址问题是在Huff的引力模型的基础上研究的。
2.4线性规划几种常见的模型
线性规划时运筹学的一个重要分支。
自1947年丹捷格(G.B.Gantzig)提出了一般线性规划问题求解的方法——单纯形法之后,线性规划在理论上趋向成熟,在实际中日益广泛与深入。
特别是在电子计算机能处理成千上万个约束条件个决策变量的线性规划问题之后,线性规划的适用领域更为广泛了。
从解决技术问题的最优设计到工业、农业、交通运输业、军事、经济计划和管理决策等领域都能发挥作用。
长期以来,建立线性规划的数学模型来合理地利用有限的人力、物力、财力等资源,以便得到最好的经济效果,一直是各国有关专家和官员关注的课题。
一个理想的数学模型能够准确的使得有限的资源能得到最大化的使用,不同类型线性规划模型有各自不同的特点,能解决不同的实际问题,弄清这些特点根据不同的实际问题建立几种模型。
线性规划模型主要有以下几种,一般模型,整数模型,0-1模型等等。
下面将逐一介绍。
模型1线性规划一般模型
在这个模型中
(1)每一个问题都用一组决策变量(
)表示某一方案,这组决策变量的值就代表一个具体方案。
一般这些变量取值都是非负且连续的。
(2)存在有关的数据,同决策变量构成互不矛盾的约束条件,这些约束条件可以用一组线性等式或不等式表示。
(3)都有一个要求达到的目标,它可以用决策变量及其有关的价值系数构成的线性函数(称为目标函数)来表示。
按问题的不同,要求目标函数实现最大化或最小化。
一般形式为 :
(1)
模型2整数规划模型
在有些线性规划问题中,对于某些具体问题,常有要求解答必须是整数的情形,例如,所求解是机器的台数、完成工作的人数或者装卸的车数等,分数或小数的解答就不合要求。
因此,对求最优整数解的问题,有必要另行研究,这样的问题称为整数规划。
整数规划中如果所有的便是都限制为(非负)整数,就称为纯整数规划或者为全整数规划;如果一部分变数限制为整数,则称为混合整数规划。
整数规划的一般形式:
(2)
模型30-1规划模型
0-1规划是决策变量仅取值0或1的一类特殊的整数规划。
0-1规划的一般形式
(3)
2.5小结
现实生活中很多问题都能运用线性规划的数学模型来解决,通过忽略次要因素或者给不能忽略的因素加一定的权重建立数学模型。
得到最优的方案。
对于线性规划问题有以下步骤:
1)明确问题:
何种方案使得所解最大化或最小化;2)确定决策变量:
是问题中要确定的未知量,表明规划中用数量表示的方案或决策;3)定义目标函数:
或
;4)根据问题表示约束条件;5)确定数学模型,求解。
3线性规划求解实际问题
3.1运输问题
3.1.1问题概述
现在人们生产活动中,不可避免的要进行物资调运工作,如某时期内将生产基地的蔬菜,粮食等各类物资,分别运到需要这些物资的地区。
如何根据各地的生产量和需求量及各地之间的运输费用,如何制定一个运输方案,使总的运输量费用最小,这类的问题称为运输问题。
假设有
个产地,记为
,生产某种物资,可供应的产量分别为
有n个销地,记为
,其需求量分别为
,假设在供需平衡的情况下,即
=
,从第
个产地到
个销地的单位物资的运费为
,在满足各地需求的前提下,求运费最小的方案。
设
为第
个产地到第
个销地的运量,则运输问题的数学模型为
(4)
当目标是利益时,目标式改为最大值,在供需平衡条件下,有
个等式约束,有
个变量,约束条件的系数矩阵
有
行
列,目标函数由运价矩阵
与变量矩阵
对应元素相乘求和构成。
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
70
85
表
(一)
数学模型为:
(5)
利用matlab编写程序求解得:
>>gxph
Optimizationterminated.
fval=
1.5254e+05
ans=
0.000020.00000.000055.0000
80.000
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 算法 应用 及其 MATLAB 实现 讲解