线性规划模型的应用及灵敏度分析范文

./摘要线性规划是解决稀缺资源最优分配的有效方法,使付出的费用最少或获得的利益最大。它的研究对象是有一定的人力、财力、资源条件下,如何合理安排使用,效益最高；某项任务确定后,如何安排人、财、物,使之最省。它要解决的问题的目标可以用数值指标反映,对于要实现的目标有多种方案可以选择,有影响决策的若干约束条件。本文主要介绍了线性规划模型在实际生活中的应用,其中包括解线性方程组的各种方法,如图解法、单纯形法、以及对偶单纯形法等等,以及简单介绍了有关灵敏度分析的方法。由于许多问题仅仅利用线性规划的方法还不足以解决,因此用到了对偶理论,也因此引出了对偶单纯形法。对偶规划是线性规划问题从另一个角度进行研究,是线性规划理论的进一步深化,也是线性规划理论整体的一个不可分割的组成部分。灵敏度分析是对线性规划结果的再发掘,是对线性规划理论的充要应用,本文以实例验证灵敏度分析的实际应用。关键词：线性规划；单纯形法；对偶单纯形法.ABSTRCTLinearprogrammingisaneffectivemethodtosolvetheoptimalallocationofscarceresources,makethecostofpayorreceiveatleasttheinterestsofthelargest.Itsobjectofstudyisthehumanandfinancialresources,resourceconditions,howtoreasonablyarrangetouse,benefitissupreme;Ataskisdetermined,howtoarrangepeople,goods,andmakeitthemostprovinces.Ittothetargetcanbeusedtosolvetheproblemofthenumericalindicators,toachieveavarietyofsolutionstochoosefrom,haveanimpactonthedecisionofsomeconstraintconditions.Throughthesubjectdesign,candeepentheoperationsresearch,optimizationmethod,linearprogramming,nonlinearprogramming,toimprovetheintegrateduseofknowledge,improvetheabilityofusingthesensitivityanalysistosolvevariouspracticalproblems.Thisarticlemainlyintroducestheapplicationoflinearprogrammingmodelinreallife,includingthevariousmethodsofsolvinglinearequations,asshowninfiguremethod,simplexmethodanddualsimplexmethod,etc.,andsimplyintroducesthemethodofsensitivityanalysis.Duetomanyproblemsjustbyusingthemethodoflinearprogrammingisnotenoughtosolve,sousethedualitytheory,thusraisesthedualsimplexmethod.ThedualprogrammingislinearprogrammingproblemfromanotherAngle,isthefurtherdeepeningoflinearprogrammingtheory,linearplanningtheoryasawholeisalsoanintegralpartof.Sensitivityanalysisistodiscover,theresultofthelinearprogrammingisthechargetoapplicationoflinearprogrammingtheory.Keywords:linearprogramming；Simplexmethod；Thedualsimplexmethod.目录TOC\o"1-3"\h\u202前言1034线性规划模型的应用与灵敏度分析………………12000第一章线性规划问题……………175801.线性规划及灵敏度分析简介…………………1235072.线性规划模型应用的发展……………………1147293.线性规划模型研究的问题……………………2209324.线性规划模型的应用…………2178394.1问题………………25254.2线性规划方法的特点及局限性………………2232344.3线性规划模型的基本结构……………………3257624.4线性规划模型的一般形式……………………347914.4线性规划的性质…………………520039第二章求解线性规划的方法………………………639291.图解法……………6249122.单纯行法…………………………768072.1单纯行法的基本思路…………7218052.2单纯形法的求解步骤………………………11221062.3单纯形法的求解过程小结…………………12213692.3.1人造基、初始基本可行解…………………12245382.3.2最优解判别定理：…………14241722.3.3单纯行过程的两种方法…………………14109563.单纯行法…………………………1450773.1对偶问题的提出………………14150803.2线性规划的对偶理论…………15309983.3对偶单纯形法的步骤…………15221544.单纯行表…………………………158107第三章灵敏度分析…………………17254721.边际值<影子价>……………17121032.价值向量的灵敏度分析………………………18264463.灵敏度的应用…………………192452第四章应用设计实例………………19118741.目标函数系数灵敏度分析……………………1974332.右边值敏感性分析……………1931247结论………………2226497参考文献………………2321324致谢………………24.前言线性规划是运筹学的一个重要分支。1947年,当时正在美国空军担任数学顾问的Dantzig在《最优规划的科学计算》中提出"如何使规划过程机械化"问题,并着手建立数学模型。他从改造投入产出模型入手,逐步研究,形成了"单纯形法",并于1953年提出"改进单纯形法",以解决计算机求解过程中的舍入误差问题。之后,线性规划理论逐步趋于成熟,在实用中日益广泛和深入。通过设计该课题,可以加深对运筹学、最优化、线性规划、非线性规划以及MATLAB的认识,提高对这些知识的综合应用水平,提高利用灵敏度分析解决各种线性规划问题的能力。本文章主要介绍了线性规划在实际生活中的应用,包括解线性方程组的各种方法,包括图解法,单纯形法,大M法,二阶段法以及对偶单纯形法,以及简要介绍了有关灵敏度分析的方法。由于线性方程组是解决各种应用问题的主要工具,而有许多问题仅仅利用线性规划的解决方法还不足以解决问题,还用到了对偶理论,也因此引出了对偶单纯形法。本课题当前的研究方向有：LP的内点算法,它通过非线性规划解决线性问题,其成功是对数学思想的革新；算法复杂度,评价算法好坏应从平均工作量出发；大型问题的分解算法、近似算法。线性规划的应用正在不断扩大,企业成功确实通过提高生产和有效使用资源的竞争过程来达到。.线性规划模型的应用与灵敏度分析第一章线性规划问题线性规划及灵敏度分析简介线性规划<LinearProgramming>问题,简称LP问题,是运筹学中最基本,也是最重要的内容,被广泛地应用于军事决策、企业管理、工程设计、交通运输等领域.特别是经济领域应用更为广泛,有资料称,在对500家有相当效益的公司所作的评述中,有85%的公司都曾应用了线性规划。灵敏度分析对于决策者的重要性不言而喻,在真实世界里,周围的环境、条件是在不断变化的。2.线性规划模型应用的发展线性规划及其通用解法——单纯形法是由美国在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱－普森分别于1832和1911年独立地提出线性规划的想法,但未引起注意。1939年苏联数学家康托罗维奇在《生产组织与计划中的数学方法》一书中提出线性规划问题,也未引起重视[1]。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法──单纯形法,为这门学科奠定了基础。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域,扩大了它的应用范围和解题能力[2]。1951年美国经济学家库普曼斯把线性规划应用到经济领域,为此与康托罗维奇一起获1975年诺贝尔经济学奖。50年代后对线性规划进行大量的理论研究,并涌现出一大批新的算法。例如,1954年莱姆基提出对偶单纯形法,1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题,1956年塔克提出互补松弛定理,1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究[3]。1984年美国贝尔电话实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用范围不断扩大[4]。3.线性规划模型研究的问题建立线性规划模型线性规划研究的问题主要有两类:一类是当一项任务确定后,如何统筹安排,尽量做到以最少的人力、物力等资源去完成；另一类是在人力、物力等资源确定的情况下,如何安排使用这些资源,使创造的价值最多,其实质是解决稀缺资源在有竞争环境中如何进行最优分配的问题,即寻求整个问题的某个整体指标最优的问题[4]。线性规划模型的应用4.1问题a.目标函数最优化——单一目标,多重目标问题如何处理？b.实现目标的多种方法,若实现目标只有一种方法不存在规划问题。c.生产条件的约束——资源是有限的,资源无限不存在规划问题。4.2线性规划方法的特点及局限性特点：a.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论；b.线性；c.允许出现生产要素的剩余量；d.有一套完整的运算程序；局限性：a.线性规划它是以价格不变和技术不变为前提条件的,不能处理涉及到时间因素的问题。因此,线性规划只能以短期计划为基础。b.在生产活动中,投入产出的关系不完全是线性关系,由于在一定的技术条件下,报酬递减规律起作用,所以要满足线性假定是不可能的。在线性规划解题中,常常把投入产出的非线性关系转化为线性关系来处理,以满足线性的假定性,客观上产生误差。c.线性规划本身只是一组方程式,并不提供经济概念,它不能代替人们对现实经济问题的判断。4.3线性规划模型的基本结构<1>决策变量——未知数。它是通过模型计算来确定的决策因素。又分为实际变量——求解的变量和计算变量,计算变量又分松弛变量〔上限和人工变量〔下限。<2>目标函数——经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。<3>约束条件——实现经济目标的制约因素。它包括：生产资源的限制〔客观约束条件、生产数量、质量要求的限制〔主观约束条件、特定技术要求和非负限制。4.4线性规划模型的一般形式极大值模型<1-1><1-2><1-3>其简缩形式为极小值模型<1-4><1-5><1-6>其简缩形式为模型的简缩形式可用向量表示例1生产安排模型,某工厂生产I、II两种产品,已知生产单位产品所需的设备台时及A、B两种原材料的消耗,如表所示。III资源总量设备128/台时原材料A4016/千克原材料B0412/千克该工厂生产一单位产品I可获利2元,生产产品II可获利3元,问如何安排生产获利最大？解： 本问题是目标最大化问题： <1>决策变量,设x1,x2为产品I、II的生产数量；<2>目标函数,2x1+3x2；<3>约束条件,设备限制：x1+2x2≤8原材料A限制：4x1≤16原材料B限制：4x2≤12基本要求：x10,x20该模型记为如下形式maxZ=2x1+3x2s.t. x1+2x2≤8 4x1≤16 4x2≤12x1,x20其中max表示本问题是最大值问题〔用min表示最小值问题,s.t.<subjectto的缩写>表示约束条件。这就是一个线性规划模型[5]。4.4线性规划的性质定理1线性规划问题的可行解X是基可行解的充要条件是X的非零分量对应的系数矩阵A的列向量线性无关[6]。定理2若一个线性规划问题有可行解,则它必有基本可行解[7]。定理3若可行域有界,线性规划问题的目标函数一定可以在其可行域的顶点达到最优。求解线性规划的方法1.图解法图解法是求解线性规划模型的一种重要方法,线性规划中一些重要的性质、概念和求解思想都来源于此。当只有两个决策变量时,可以用图解法求解。它具有简单直观的特点。为了给后面的线性问题的基本理论提供较直观的几何说明,先介绍线性规划问题的图解法[8]。图解法的求解步骤如下：第一步,根据约束画出可行域,先以决策变量为坐标,建立直角坐标系,再根据各约束条件,作出可行域。第二步,作出一条目标函数等值线,并确定增值方法。第三步,沿等值线的法线方向值增大方向移动,从而找到最大值。图解法得出线性规划的几种情况：表2-1解旳几种情况解旳几种情况约束条件图形特点方程特点唯一解一般围成有限区域,最优值只在一个顶点达到无穷多解在围成的的区域边界上,至少有两个顶点处达到优解目标和某一约束方程成比例无可行解〔无解围不成区域有矛盾方程无界解<无解围成无界区域,且无有限最优解缺少一必要条件的方程例：MinZ=10x1+20x22.单纯形法单纯形法是美国数学家于1947年首先提出的。它的理论根据是：线性规划问题的可行域是n维向量空间nR中的多面凸集,其最优值如果存在必在该凸集的某顶点处达到[9]。它的原理涉及到较多的数学理论上的推导和证明,我们在此仅介绍这种方法的具体操作步骤及每一步的经济上的含义。为更好地说明问题,我们仍结合实例介绍这种方法。单纯形法〔simplexmethods,求解线性规划的通用方法。2.1单纯形法的基本思路单纯形法的基本思路是：根据线性规划问题的标准型,从可行域中某个基本可行解〔一个顶点开始,转换到另一个基本可行解〔顶点,并且当目标函数达到最大值时,问题就得到了解决,其基本思路的框架图如下图2-1。图2-1.单纯行法的基本思路用单纯行法讨论例1的求解解：已知例1的标准型为〔2-1〔2-2约束条件〔2-2的系数矩阵显然,x3,x4,x5的系数列向量〔2-3是线性独立的,因而这些向量构成一个基<2-4>对应于B的基变量为x3,x4,x5,从约束条件〔2-2中可以看到〔2-5当令非基变量这时得到一个基本可行解X〔0〔2-6将式<2-3>代入目标函数<2-1>得到〔2-7这个基本可行解表示：工厂没有安排生产ⅠⅡ产品；资源都没有被利用,所以工厂的利润Z=0。分析目标函数的表达式<2-7>可以看到：非基变量x1,x2的系数都是正数,因此将非基变量变为基变量,目标函数的值就可能增大,从经济意义上讲,安排生产产品Ⅰ或Ⅱ,就可以使工厂的利润指标增加,所以只要在目标函数<2-7>的表达式中还存在有正系数的非基变量,这表示目标函数值还有增加的可能,就需要将非基变量与某个基变量进行对换,一般选择正系数最大的那个非基变量x2为换入变量,将它换入到基变量中区,同时还有确定基变量中有一个要换出来成为非基变量,可按以下方法来确定换出变量。现分析式<2-5>,当将x2定为换入变量后,必须从x3,x4,x5中换出一个,并保证其余的都是非负,即x3,x4,x5。当x1=0,由式<2-5>得到〔2-8可以看出,只有选择〔2-9时,才能使式<2-8>成立。以上数学模型说明了每生产一件产品Ⅱ,需要用掉的各种资源数为<2,0,4>。这些资源中的薄弱环节确定了产品Ⅱ的产量。原材料B的数量决定产品Ⅱ的产量只能是x2=12/4=3件。为了求得以x3,x4,x2为基变量的一个基本可行解和进一步分析问题,需将方程<2-5>中x2的位置对换。得到〔2-10用高斯消去法求解,得到以非基变量表示的基变量〔2-11代入目标函数得到<2-12>令非基变量得到并得另一个基本可行解。从目标函数的表达式<2-12>中可以看到,非基变量的系数是正的,说明目标函数的值还可以增大,还不是最优解。于是用上述方法,确定换入、换出变量,继续迭代,再得到另外一个基本可行解。再经过一次迭代,得到一个基本可行解。而这时得到的目标函数的表达式是〔2-13再分析目标函数<2-13>,可知所有非基变量的系数都是负数,这说明若要用剩余资源就必须支付附加费用。所以当时,即不再利用这些资源时,目标函数达到最大值,那么是最优解。这说明当产品Ⅰ生产4件,产品Ⅱ生产2件,工厂才能得到最大利润。通过上例,可以了解利用单纯形法求解线性规划问题的思路。2.2单纯形法的求解步骤线性规划问题的求解有以下几个步骤：<1>确定初始基本可行解。为了确定初始基本可行解,首先要找出初始可行解。设一线性规划问题为〔2-14可分为两种情况讨论。①若中存在一个单位基,则将其作为初始可行基〔2-15②若中不存在一个单位基,则人为地构造一个单位初始基。<2>检验最优解。得到初始基本可行解后,要检验该解是否为最优解。如果是最优解,则停止运算；否则转入〔3基变换。下面给出最优性判别定理。一般情况下,经过迭代后可以得到以非基变量表示基变量的表达式〔〔2-16将式<2-11>代入式<2-10>的目标函数,整理后得〔2-17令〔〔2-18于是〔2-19再令〔2-20则得到以非基变量表示目标函数的表达式〔2-21<3>基变换。若初始基本可行解不是最优解,又不能判别无界时,由目标函数<2-10>的约束条件可看到,当某些增加则目标函数值还可能增加这时就要将其中某个非基变量换到基变量中去〔称为换入变量,同时,某个基变量要换成非基变量〔称为换出变量,随之会得到一个新的基本可行解。从一个基本可行解到另一个基本可行解的变换,就是进行一次基变换。从几何意义上就是从可行域的一个顶点转向另一个顶点。<4>迭代。在确定了换入变量和换出变量后,要把和的位置进行对换,就是说要把对应的系数列向量变成单位列向量。这可以通过对约束方程组的增广矩阵进行初等行变换来实现,变换结果得一新的基本可行解。2.3单纯形法的求解过程小结2.3.1人造基、初始基本可行解<1>若从线性规划问题的Pj中能直接观察到存在m个线性独立的单位向量,经过重新安排次序便得到一个可行基。<2>"≤"标准化的方法,引入非负的松弛变量重新对及编号,经整理则可得到下列方程显然得到一个单位阵我们就将B作为可行基。我们就将B作为可行基。将每个等式进行移项得令由等式可得得到一个初始基本可行解2.3.2最优性检验得到初始可行解后,要检验一下是否是最优解,如果是则停止迭代,如果不是,则继续迭代。但每次迭代后都要检验是否是最优解,为此需要建立一个判别准则。一般情况下,经过迭代后式变成将上式代入目标函数,整理后得2.3.3最优解判别定理：若为对应于B的基本可行解,且对于一切有X〔0为最优解。无有限最优解判别定理：若为对应于B的基本可行解,有一个并且对于一切i=1,2,3,……,m有那么该线性规划没有有限最优解。a.换入变量的确定则对应的为换入变量b.换出变量的确定为换入变量。2.3.4单纯形法过程的两种方法在单纯形迭代过程中,要求人工变量逐步从基变量被替换出,变为非基变量,这有两种方法：大M法和两阶段法[10]。3.对偶单纯形法对偶规划是线性规划问题从另一个角度进行研究,是线性规划理论的进一步深化,也是线性规划理论的进一步深化,也是线性规划理论整体的一个不可分割.3.1对偶问题的提出每个线性规划都有另一个线性规划〔对偶问题与它密切相关,对偶理论揭示了原问题与对偶问题的内在联系[11]。考虑到对偶模型的约束与原问题模型的变量相对应,变量则是与原问题模型的约束相对应。原问题是最小化,则可将对偶问题看做原问题[12]。3.2线性规划的对偶理论定理2-1<对称性定理>对偶问题的对偶是原问题。定理2-2<弱对偶定理>设X和Y分别是原问题P和对偶问题D的可行解,则有[13]。定理2-3<对偶原理>定理2-4<互补松弛定理>如果X和Y分别为P和D的可行解,它们分别为P和D的最优解的充要条件是3.3对偶单纯形法的步骤对偶单纯形法是用对偶理论求解原问题的一种方法,而不是求解对偶问题解的单纯形法。与对偶单纯形法相对应,已有的单纯形法称原始单纯形法[14]。建立初始单纯形表,计算检验数行先确定换出变量--解答列中的负元素一般选最小的负元素对应的基变量出基；将主元素进行换基迭代〔旋转运算、枢运算>,将主元素变成1,主元列变成单位向量,得到新的单纯形表。继续以上步骤,直至求出最优解[15]。单纯形表表2-2单纯形表也可以反映线性规划在现实生活中的运用初单纯形表实际活动松弛活动比值x1x2x3x4x5R0x382300060x4161210040x51240010-目标系数行23000检验数行023000第二单纯形表实际活动松弛活动比值x1x2x3x4x5R0x362010030x421210020x5164001043x2304001-检验数行20000903000第三单纯形表实际活动松弛活动比值x1x2x3x4x5R0x32001-2042x1212010-0x58000-4143x230100012检验数行000-201323020第三章灵敏度分析灵敏度分析是研究与分析一个系统<或模型>的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此,灵敏度分析几乎在所有的运筹学方法中以及在各种方案进行评价时都是很重要的[16]。1.边际值<影子价>是指在最优解的基础上,当第i个约束行的右端项减少一个单位时,目标函数的变化量机会成本因此机会成本的另外表达形式关于影子价的一些说明①影子价是资源最优配置下资源的理想价格,资源的影子价与资源的紧缺度有关；②松弛变量增加一个单位等于资源减少一个单位；③剩余变量增加一个单位等于资源增加一个单位；④资源有剩余,在最优解中就有对应松弛变量存在,且其影子价为0；⑤影子价为0,资源并不一定有剩余。2.价值向量的灵敏度分析价值向量<即目标函数系数>的灵敏度分析分为原最终单纯形表中jc与非基变量和基变量对应两种情况来讨论[17]。若是非基变的系数,则其对应的最终单纯形表中的检验数为当变化,要保证最终单纯形表的最优解不变,必有保证最终单纯形表最优解不变,可得的允许变化值〔2若是基变量的系数,应有,当变化时,就引起的变化这时若要求原最优解不变,必须满足。于是得到可变化的范围是3.灵敏度的应用<1>投入产出法中灵敏度分析可以用来研究采取某一项重大经济政策后将会对国民经济的各个部门产生怎样的影响。<2>方案评价中灵敏度分析可以用来确定评价条件发生变化时备选方案的价值是否会发生变化或变化多少。应用设计实例某农户计划用12公顷耕地生产玉米,大豆和地瓜,可投入48个劳动日,资金360元。生产玉米1公顷,需6个劳动日,资金36元,可获净收入200元；生产1公顷大豆,需6个劳动日,资金24元,可获净收入150元；生产1公顷地瓜需2个劳动日,资金18元,可获净收入1200元,问怎样安排才能使总的净收入最高。设种玉米,大豆和地瓜的数量分别为x1、x2和x3公顷,根据问题建立线性规划问题模型如下：MaxZ=200x1+150x2+100x3x1+x2+x3≤126x1+6x2+2x3≤48 <4-1>36x1+24x2+183≤360 <4-2>x1≥0,x2≥0,x3≥01.目标函数系数灵敏度分析表4-1目标系数的允许变动范围活动目标系数可减上限可增上限可变范围玉米种植x1大豆种植x2地瓜种植x320015010050无穷大100/310050100150~300-~200200/3~200当仅有一种目标系数在允许范围内变动时,最优方案不会变动,但最优目标值会随之变化。2.右边值敏感性分析由线性规划的原理可知,影子价格不变的条件是最优解的松弛变量矩阵与右边值矩阵的乘积大于和等于0,即：当右边值发生变化时,如耕地变化△,此时,影子价格不变的条件是得到6+3/2△1≥06-1/2△1≥0-4≤△1≤436-9△1≥0因此耕地影子价格不变的耕地数量范围为：[8,16]得到6－1/4△2≥06+1/4△2≥0-24≤△2≤836-9/2△2≥0因此劳动力影子价格不变的劳动力数量范围为：[24,56]得到6≥0△3≥－3636＋△3≥0因此资金影子价格不变的资金数量范围为：[324,-]表4-2常数项的允许变动范围资源现有数量可减上限可增上限可变范围影子价格耕地12448～165