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

1、-摘 要线性规划是解决稀缺资源最优分配的有效方法，使付出的费用最少或获得的利益最大。它的研究对象是有一定的人力、财力、资源条件下，如何合理安排使用，效益最高；*项任务确定后，如何安排人、财、物，使之最省。它要解决的问题的目标可以用数值指标反映，对于要实现的目标有多种方案可以选择，有影响决策的假设干约束条件。本文主要介绍了线性规划模型在实际生活中的应用，其中包括解线性方程组的各种方法，如图解法、单纯形法、以及对偶单纯形法等等，以及简单介绍了有关灵敏度分析的方法。由于许多问题仅仅利用线性规划的方法还缺乏以解决，因此用到了对偶理论，也因此引出了对偶单纯形法。对偶规划是线性规划问题从另一个角度进展研究

2、，是线性规划理论的进一步深化，也是线性规划理论整体的一个不可分割的组成局部。灵敏度分析是对线性规划结果的再开掘，是对线性规划理论的充要应用，本文以实例验证灵敏度分析的实际应用。 关键词：线性规划；单纯形法；对偶单纯形法. z-ABSTRCTLinear programming is an effective method to solve the optimal allocation of scarce resources, make the cost of pay or receive at least the interests of the largest. Its object of

3、study is the human and financial resources, resource conditions, how to reasonably arrange to use, benefit is supreme; A task is determined, how to arrange people, goods, and make it the most provinces. It to the target can be used to solve the problem of the numerical indicators, to achieve a varie

4、ty of solutions to choose from, have an impact on the decision of some constraint conditions. Through the subject design, can deepen the operations research, optimization method, linear programming, nonlinear programming, to improve the integrated use of knowledge, improve the ability of using the s

5、ensitivity analysis to solve various practical problems. This article mainly introduces the application of linear programming model in real life, including the various methods of solving linear equations, as shown in figure method, simple* method and dual simple* method, etc., and simply introduces

6、the method of sensitivity analysis. Due to many problems just by using the method of linear programming is not enough to solve, so use the duality theory, thus raises the dual simple* method. The dual programming is linear programming problem from another Angle, is the further deepening of linear pr

7、ogramming theory, linear planning theory as a whole is also an integral part of. Sensitivity analysis is to discover, the result of the linear programming is the charge to application of linear programming theory.Keywords: linear programming；Simple* method；The dual simple* method. z-目 录前言线性规划模型的应用与灵

8、敏度分析1第一章 线性规划问题11. 线性规划及灵敏度分析简介12. 线性规划模型应用的开展13. 线性规划模型研究的问题24. 线性规划模型的应用24.1问题24.2线性规划方法的特点及局限性24.3线性规划模型的根本构造34.4线性规划模型的一般形式34.4线性规划的性质5第二章 求解线性规划的方法61. 图解法62. 单纯行法72.1 单纯行法的根本思路72.2 单纯形法的求解步骤112.3 单纯形法的求解过程小结122.3.1人造基、初始根本可行解122.3.2最优解判别定理：142.3.3单纯行过程的两种方法143. 单纯行法143.1对偶问题的提出143.2线性规划的对偶理论153

9、.3对偶单纯形法的步骤154. 单纯行表15第三章 灵敏度分析171. 边际值(影子价)172. 价值向量的灵敏度分析183. 灵敏度的应用19第四章 应用设计实例191. 目标函数系数灵敏度分析192. 右边值敏感性分析19结 论22参考文献23致 24. z-前 言线性规划是运筹学的一个重要分支。1947年，当时正在美国空军担任数学参谋的Dantzig在?最优规划的科学计算?中提出“如何使规划过程机械化问题，并着手建立数学模型。他从改造投入产出模型入手，逐步研究，形成了“单纯形法，并于1953年提出“改良单纯形法，以解决计算机求解过程中的舍入误差问题。之后，线性规划理论逐步趋于成熟，在实用

10、中日益广泛和深入。通过设计该课题，可以加深对运筹学、最优化、线性规划、非线性规划以及MATLAB的认识，提高对这些知识的综合应用水平，提高利用灵敏度分析解决各种线性规划问题的能力。本文章主要介绍了线性规划在实际生活中的应用，包括解线性方程组的各种方法，包括图解法，单纯形法，大M法，二阶段法以及对偶单纯形法，以及简要介绍了有关灵敏度分析的方法。由于线性方程组是解决各种应用问题的主要工具， 而有许多问题仅仅利用线性规划的解决方法还缺乏以解决问题，还用到了对偶理论，也因此引出了对偶单纯形法。本课题当前的研究方向有：LP的点算法，它通过非线性规划解决线性问题，其成功是对数学思想的革新；算法复杂度，评价

11、算法好坏应从平均工作量出发；大型问题的分解算法、近似算法。线性规划的应用正在不断扩大，企业成功确实通过提高生产和有效使用资源的竞争过程来到达。. z-线性规划模型的应用与灵敏度分析第一章 线性规划问题1. 线性规划及灵敏度分析简介线性规划(Linear Programming)问题, 简称LP问题,是运筹学中最根本, 也是最重要的容, 被广泛地应用于军事决策、企业管理、工程设计、交通运输等领域. 特别是经济领域应用更为广泛, 有资料称, 在对500家有相当效益的公司所作的评述中, 有85%的公司都曾应用了线性规划。灵敏度分析对于决策者的重要性不言而喻，在真实世界里，周围的环境、条件是在不断变化

12、的。2. 线性规划模型应用的开展线性规划及其通用解法单纯形法是由美国在1947年研究空军军事规划提出来的。法国数学家傅里叶和瓦莱普森分别于1832和1911年独立地提出线性规划的想法，但未引起注意。1939年联数学家康托罗维奇在?生产组织与方案中的数学方法?一书中提出线性规划问题，也未引起重视1。1947年美国数学家丹齐克提出线性规划的一般数学模型和求解线性规划问题的通用方法单纯形法，为这门学科奠定了根底。1947年美国数学家诺伊曼提出对偶理论,开创了线性规划的许多新的研究领域，扩大了它的应用围和解题能力2。1951年美国经济学家库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975

13、年诺贝尔经济学奖。50年代后对线性规划进展大量的理论研究，并涌现出一大批新的算法。例如，1954年莱姆基提出对偶单纯形法，1954年加斯和萨迪等人解决了线性规划的灵敏度分析和参数规划问题，1956年塔克提出互补松弛定理，1960年丹齐克和沃尔夫提出分解算法等。线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究3。1984年美国贝尔实验室的印度数学家N.卡马卡提出解线性规划问题的新的多项式时间算法。用这种方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。现已形成线性规划多项式算法理论。50年代后线性规划的应用围不断扩大4。3. 线性

14、规划模型研究的问题建立线性规划模型线性规划研究的问题主要有两类:一类是当一项任务确定后，如何统筹安排，尽量做到以最少的人力、物力等资源去完成；另一类是在人力、物力等资源确定的情况下，如何安排使用这些资源，使创造的价值最多，其实质是解决稀缺资源在有竞争环境中如何进展最优分配的问题，即寻求整个问题的*个整体指标最优的问题4。4. 线性规划模型的应用4.1问题a.目标函数最优化单一目标，多重目标问题如何处理.b.实现目标的多种方法，假设实现目标只有一种方法不存在规划问题。 c.生产条件的约束资源是有限的，资源无限不存在规划问题。4.2线性规划方法的特点及局限性 特点：a.可以使研究对象具体化、数量化

15、。可以对所研究的技术经济问题做出明确的结论；b.线性；c.允许出现生产要素的剩余量；d.有一套完整的运算程序；局限性：a. 线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期方案为根底。b.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。c.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经济问题的判断。 4.3线性规划模型的根本构造(1)决策变量 未知数

16、。它是通过模型计算来确定的决策因素。又分为实际变量求解的变量和计算变量，计算变量又分松弛变量上限和人工变量下限。 (2)目标函数经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。 (3)约束条件实现经济目标的制约因素。它包括：生产资源的限制客观约束条件、生产数量、质量要求的限制主观约束条件、特定技术要求和非负限制。4.4线性规划模型的一般形式极大值模型 (1-1) (1-2) (1-3)其简缩形式为 极小值模型 (1-4) (1-5) (1-6)其简缩形式为 模型的简缩形式可用向量表示 例1 生产安排模型，*工厂生产I、II两种产品，生产单位产品所需的设备台时及

17、A、B两种原材料的消耗，如表所示。III资源总量设备128/台时原材料A4016/千克原材料B0412/千克该工厂生产一单位产品I可获利2元，生产产品II可获利3元，问如何安排生产获利最大.解：本问题是目标最大化问题：(1)决策变量，设*1, *2为产品I、II的生产数量；(2)目标函数，2*1+3*2；(3)约束条件，设备限制： *1+2*2 8原材料A限制： 4*1 16原材料B限制： 4*2 12根本要求：*10 ， *20 该模型记为如下形式 ma*Z=2*1+3*2s.t.*1+2*2 84*1 164*2 12*1 ，*2 0其中ma*表示本问题是最大值问题用min表示最小值问题，

18、 s.t.(subject to的缩写)表示约束条件。这就是一个线性规划模型5。4.4线性规划的性质定理1 线性规划问题的可行解*是基可行解的充要条件是*的非零分量对应的系数矩阵A的列向量线性无关6。定理2 假设一个线性规划问题有可行解，则它必有根本可行解7。定理3 假设可行域有界，线性规划问题的目标函数一定可以在其可行域的顶点到达最优。第2章 求解线性规划的方法1. 图解法图解法是求解线性规划模型的一种重要方法，线性规划中一些重要的性质、概念和求解思想都来源于此。当只有两个决策变量时，可以用图解法求解。它具有简单直观的特点。为了给后面的线性问题的根本理论提供较直观的几何说明，先介绍线性规划问

19、题的图解法8。图解法的求解步骤如下：第一步，根据约束画出可行域，先以决策变量为坐标，建立直角坐标系，再根据各约束条件，作出可行域。第二步，作出一条目标函数等值线，并确定增值方法。第三步，沿等值线的法线方向值增大方向移动，从而找到最大值。图解法得出线性规划的几种情况：表2-1 解旳几种情况解旳几种情况约束条件图形特点方程特点唯一解一般围成有限区域，最优值只在一个顶点到达无穷多解在围成的的区域边界上，至少有两个顶点处到达优解目标和*一约束方程成比例无可行解无解围不成区域有矛盾方程无界解(无解围成无界区域，且无有限最优解缺少一必要条件的方程例：Min Z=10*1+20*22. 单纯形法单纯形法是美

20、国数学家于1947年首先提出的。它的理论根据是：线性规划问题的可行域是n维向量空间nR中的多面凸集，其最优值如果存在必在该凸集的*顶点处到达9。它的原理涉及到较多的数学理论上的推导和证明，我们在此仅介绍这种方法的具体操作步骤及每一步的经济上的含义。为更好地说明问题，我们仍结合实例介绍这种方法。 单纯形法simple* methods，求解线性规划的通用方法。 2.1单纯形法的根本思路单纯形法的根本思路是：根据线性规划问题的标准型，从可行域中*个根本可行解一个顶点开场，转换到另一个根本可行解顶点，并且当目标函数到达最大值时，问题就得到了解决，其根本思路的框架图如以下图2-1。图2-1.单纯行法的

21、根本思路用单纯行法讨论例1的求解解：例1的标准型为2-12-2约束条件2-2的系数矩阵显然，*3，*4，*5的系数列向量 2-3是线性独立的，因而这些向量构成一个基(2-4)对应于B的基变量为*3,*4,*5，从约束条件2-2中可以看到2-5当令非基变量这时得到一个根本可行解*02-6将式(2-3)代入目标函数(2-1)得到2-7这个根本可行解表示：工厂没有安排生产产品；资源都没有被利用，所以工厂的利润Z=0。分析目标函数的表达式(2-7)可以看到：非基变量*1,*2的系数都是正数，因此将非基变量变为基变量，目标函数的值就可能增大，从经济意义上讲，安排生产产品或，就可以使工厂的利润指标增加，所

22、以只要在目标函数(2-7)的表达式中还存在有正系数的非基变量，这表示目标函数值还有增加的可能，就需要将非基变量与*个基变量进展对换，一般选择正系数最大的那个非基变量*2为换入变量，将它换入到基变量中区，同时还有确定基变量中有一个要换出来成为非基变量，可按以下方法来确定换出变量。现分析式(2-5)，当将*2定为换入变量后，必须从*3,*4,*5中换出一个，并保证其余的都是非负，即*3,*4,*5。当*1=0，由式(2-5)得到 2-8可以看出，只有选择 2-9 时，才能使式(2-8)成立。以上数学模型说明了每生产一件产品，需要用掉的各种资源数为(2,0,4)。这些资源中的薄弱环节确定了产品的产量

23、。原材料B的数量决定产品的产量只能是*2=12/4=3件。为了求得以*3，*4，*2为基变量的一个根本可行解和进一步分析问题，需将方程(2-5)中*2的位置对换。得到 2-10用高斯消去法求解，得到以非基变量表示的基变量 2-11代入目标函数得到 (2-12) 令非基变量得到并得另一个根本可行解。从目标函数的表达式(2-12)中可以看到，非基变量的系数是正的，说明目标函数的值还可以增大，还不是最优解。于是用上述方法，确定换入、换出变量，继续迭代，再得到另外一个根本可行解。再经过一次迭代，得到一个根本可行解。而这时得到的目标函数的表达式是 2-13再分析目标函数(2-13),可知所有非基变量的系

24、数都是负数，这说明假设要用剩余资源就必须支付附加费用。所以当时，即不再利用这些资源时，目标函数到达最大值，则是最优解。这说明当产品生产4件，产品生产2件，工厂才能得到最大利润。通过上例，可以了解利用单纯形法求解线性规划问题的思路。 2.2单纯形法的求解步骤 线性规划问题的求解有以下几个步骤： (1)确定初始根本可行解。为了确定初始根本可行解，首先要找出初始可行解。设一线性规划问题为 2-14可分为两种情况讨论。假设中存在一个单位基，则将其作为初始可行基 2-15假设中不存在一个单位基，则人为地构造一个单位初始基。(2)检验最优解。得到初始根本可行解后，要检验该解是否为最优解。如果是最优解，则停

25、顿运算；否则转入3基变换。下面给出最优性判别定理。一般情况下，经过迭代后可以得到以非基变量表示基变量的表达式 2-16将式(2-11)代入式(2-10)的目标函数，整理后得 2-17令 2-18于是2-19再令2-20则得到以非基变量表示目标函数的表达式2-21 (3)基变换。假设初始根本可行解不是最优解，又不能判别无界时，由目标函数(2-10)的约束条件可看到，当*些增加则目标函数值还可能增加这时就要将其中*个非基变量换到基变量中去称为换入变量，同时，*个基变量要换成非基变量称为换出变量，随之会得到一个新的根本可行解。从一个根本可行解到另一个根本可行解的变换，就是进展一次基变换。从几何意义上

26、就是从可行域的一个顶点转向另一个顶点。 (4)迭代。在确定了换入变量和换出变量后，要把和的位置进展对换，就是说要把对应的系数列向量变成单位列向量。这可以通过对约束方程组的增广矩阵进展初等行变换来实现，变换结果得一新的根本可行解。 2.3单纯形法的求解过程小结2.3.1人造基、初始根本可行解 (1)假设从线性规划问题的Pj中能直接观察到存在m个线性独立的单位向量，经过重新安排次序便得到一个可行基。 (2)“标准化的方法，引入非负的松弛变量重新对及编号，经整理则可得到以下方程显然得到一个单位阵我们就将B作为可行基。 我们就将B作为可行基。将每个等式进展移项得 令由等式可得 得到一个初始根本可行解

27、2.3.2最优性检验得到初始可行解后，要检验一下是否是最优解，如果是则停顿迭代，如果不是，则继续迭代。但每次迭代后都要检验是否是最优解，为此需要建立一个判别准则。一般情况下，经过迭代后式变成将上式代入目标函数，整理后得2.3.3最优解判别定理：假设 为对应于B的根本可行解，且对于一切有*0为最优解。无有限最优解判别定理：假设为对应于B的根本可行解，有一个并且对于一切i=1,2,3,m有则该线性规划没有有限最优解。 a.换入变量确实定 则对应的为换入变量 b.换出变量确实定为换入变量。2.3.4单纯形法过程的两种方法在单纯形迭代过程中，要求人工变量逐步从基变量被替换出，变为非基变量，这有两种方法

28、：大M法和两阶段法10。3. 对偶单纯形法对偶规划是线性规划问题从另一个角度进展研究，是线性规划理论的进一步深化，也是线性规划理论的进一步深化，也是线性规划理论整体的一个不可分割.3.1对偶问题的提出每个线性规划都有另一个线性规划对偶问题与它密切相关，对偶理论提醒了原问题与对偶问题的在联系11。考虑到对偶模型的约束与原问题模型的变量相对应，变量则是与原问题模型的约束相对应。原问题是最小化，则可将对偶问题看做原问题12。3.2线性规划的对偶理论定理2-1(对称性定理) 对偶问题的对偶是原问题。定理2-2(弱对偶定理) 设*和Y分别是原问题P和对偶问题D的可行解，则有13。定理2-3(对偶原理)

29、定理2-4(互补松弛定理) 如果*和Y分别为P和D的可行解，它们分别为P和D的最优解的充要条件是3.3对偶单纯形法的步骤对偶单纯形法是用对偶理论求解原问题的一种方法，而不是求解对偶问题解的单纯形法。与对偶单纯形法相对应，已有的单纯形法称原始单纯形法14。（1） 建立初始单纯形表，计算检验数行（2） 先确定换出变量-解答列中的负元素一般选最小的负元素对应的基变量出基；（3） 将主元素进展换基迭代旋转运算、枢运算)，将主元素变成1，主元列变成单位向量，得到新的单纯形表。继续以上步骤，直至求出最优解15。4. 单纯形表表2-2 单纯形表也可以反映线性规划在现实生活中的运用初单纯形表实际活动松弛活动比

30、值*1*2*3*4*5R0*382300060*4161210040*51240010-目标系数行23000检验数行023000第二单纯形表实际活动松弛活动比值*1*2*3*4*5R0*362010030*421210020*5164001043*2304001-检验数行20000903000第三单纯形表实际活动松弛活动比值*1*2*3*4*5R0*32001-2042*1212010-0*58000-4143*230100012检验数行000-201323020第三章 灵敏度分析灵敏度分析是研究与分析一个系统(或模型)的状态或输出变化对系统参数或周围条件变化的敏感程度的方法。在最优化方法中经

31、常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性。通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响。因此，灵敏度分析几乎在所有的运筹学方法中以及在各种方案进展评价时都是很重要的16。1. 边际值(影子价) 是指在最优解的根底上，当第i个约束行的右端项减少一个单位时，目标函数的变化量时机本钱 因此时机本钱的另外表达形式关于影子价的一些说明影子价是资源最优配置下资源的理想价格，资源的影子价与资源的紧缺度有关；松弛变量增加一个单位等于资源减少一个单位；剩余变量增加一个单位等于资源增加一个单位；资源有剩余，在最优解中就有对应松弛变量存在，且其影子价为0；影子价为0，资源并不一定有

32、剩余。2. 价值向量的灵敏度分析价值向量(即目标函数系数)的灵敏度分析分为原最终单纯形表中jc与非基变量和基变量对应两种情况来讨论17。（1） 假设是非基变的系数，则其对应的最终单纯形表中的检验数为当变化，要保证最终单纯形表的最优解不变，必有保证最终单纯形表最优解不变，可得的允许变化值2假设是基变量的系数，应有,当变化时，就引起的变化这时假设要求原最优解不变，必须满足。于是得到可变化的围是3. 灵敏度的应用 (1)投入产出法中灵敏度分析可以用来研究采取*一项重大经济政策后将会对国民经济的各个部门产生怎样的影响。 (2)方案评价中灵敏度分析 可以用来确定评价条件发生变化时备选方案的价值是否会发生

33、变化或变化多少。第4章 应用设计实例*农户方案用12公顷耕地生产玉米，大豆和地瓜，可投入48个劳动日，资金360元。生产玉米1公顷，需6个劳动日，资金36元，可获净收入200元；生产1公顷大豆，需6个劳动日，资金24元，可获净收入150元；生产1公顷地瓜需2个劳动日，资金18元，可获净收入1200元，问怎样安排才能使总的净收入最高。设种玉米，大豆和地瓜的数量分别为*1、*2和*3公顷，根据问题建立线性规划问题模型如下：Ma* Z=200*1+150*2+100*3*1+*2+*312 6*1+6*2+2*348 (4-1) 36*1+24*2+183360 (4-2)*10，*20，*301.

34、 目标函数系数灵敏度分析表4-1 目标系数的允许变动围活动目标系数可减上限可增上限可变围玉米种植*1大豆种植*2地瓜种植*320015010050 无穷大100/310050100150300-200200/3200 当仅有一种目标系数在允许围变动时，最优方案不会变动，但最优目标值会随之变化。2. 右边值敏感性分析由线性规划的原理可知，影子价格不变的条件是最优解的松弛变量矩阵与右边值矩阵的乘积大于和等于0，即：当右边值发生变化时，如耕地变化，此时，影子价格不变的条件是得到 6+3/210 6-1/210 -414 36-910因此耕地影子价格不变的耕地数量围为：8，16得到 61/420 6+1/420 -2428 36-9/220因此劳动力影子价格不变的劳动力数量围为：24，56得到 60 3 36 3630因此资金影子价格不变的资金数量围为：324，-表4-2 常数项的允许变动围资源现有数量可减上限可增上限可变围影子价格耕地124481650劳动48248245625资金36036+324+0常数项的允许变动围这一结果也还有另外一种意义，即它给出了资源影子价格