灵敏度分析设计.doc

《灵敏度分析设计.doc》由会员分享，可在线阅读，更多相关《灵敏度分析设计.doc（27页珍藏版）》请在沃文网上搜索。

1、 目录第一章 引言1第二章 主要结论22.1 基本概念和记号22.2 基本定理和结论5第三章 单一变化的灵敏度分析73.1 的灵敏度分析73.1.1 为非基变量73.1.2 为基变量73.2 对的灵敏度分析83.3 对的灵敏度分析93.3.1 为基变量93.3.2 为非基变量93.4 增加约束条件灵敏度分析10第四章 全方位变化的灵敏度分析114.1非基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析124.2基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析13第五章 算例155.1 单一变量的灵敏度分析算例155.1.1 问题1的求解：155.1.2

2、 问题2的求解：175.1.3 问题3的求解：185.1.4 问题4的求解195.1.5 问题5的求解：20第六章 结论24参考文献25致 谢26第一章 引言灵敏度分析是研究与分析一个系统（或模型）的状态或输出变化对系统参数或周围条件变化的敏感程度的方法.在最优化方法中经常利用灵敏度分析来研究原始数据不准确或发生变化时最优解的稳定性.通过灵敏度分析还可以决定哪些参数对系统或模型有较大的影响.因此,灵敏度分析几乎在所有的运筹学方法中以及在对各种方案进行评价时都是很重要的.由于线性规划中所使用的数据大多是估计值和预测值.在实际中尤其是经济问题中常会遇到因市场条件或生产条件改变导致的产品价格、生产工

3、艺或技术条件以及资源限制条件等改变.而灵敏度分析是分析模型的参数变化对求解结果的影响,它是在原最优表的基础上对变化后的规划问题进行分析求解,避免因参数改变而去从头求解,故又称最优化后分析.本文主要介绍线性规划问题中的灵敏度分析问题,以及在灵敏度分析的基础上,对变量目标函数系数,变量约束系数向量以及约束右端项向量发生变化时,进行分析讨论.由于以往人们对灵敏度分析的讨论仅限于单个参数、单一系数或单一限制条件的变化对结果的影响,而实际中多是规划问题中各参数同时变化,如前所述因市场条件变化导致产品价格、生产工艺以及资源限制条件同时发生改变等,本文又讨论了参数同时变化的情况.文章大体分为三个部分：第一部

4、分总结概述了基本概念、主要理论和灵敏度分析的算法基础；第二部分讨论分析变量目标函数系数、变量约束系数向量、约束右端项向量这些单一参数发生变化时,最优解的求的方法；第三部分讨论各种参数同时发生变化时求解最优解的方法.第四部分是在上述理论基础上以投入产出问题进一步说明.第二章 主要结论2.1 基本概念和记号l 线性规划问题求线性目标函数在线性约束条件下的最大值或最小值的问题,统称为线性规划问题.线性规划问题的标准型为：（2.1.1）这里,max表示求最大值,s.t.表示受约束于,X是目标函数, 是决策变量.通常假定,和都是已知常数.为讨论方便,将线性规划问题的标准型以矩阵形式给出:（2.1.2）l

5、 基若系数矩阵A的秩为,称A的任一非奇异子矩阵为线性规划问题（LP）的一个基.l 基变量、非基变量当确定为（LP）的一个基,称为基向量,A中的其余向量称为非基向量；与基向量对应的变量称为基向量,其余的变量称为非基变量.l 解若B是（LP）的一个基,令所有非基变量等于0得到的解称为对应于基B的基本解；若满足,这时称为对应于基B的一个基可行解；称B为（LP）的一个可行基.使目标函数达到最大值的基可行解称为基最优解.l 单纯形变换对于线性规划问题将矩阵A,C,X分别按“基”和“非基”分成2块,即有,其中：；.由此可建立单纯形初表：表1 单纯形初表基非基变量基变量解 b 0用单纯形法对上初表做单纯形变

6、换,变换后得到单纯形终表：表2 单纯形终表基基变量非基变量解 0 为非基变量的检验数向量,最优基本可行解,对应的基可行基为,为一单位矩阵.最优结果为.l 对偶问题对偶问题与原问题的关系：表3 对偶问题与原问题的关系原问题（或对偶问题）对偶问题（或原问题）目标函数变量目标函数约束条件约束条件约束条件右端项目标函数变量的系数变量目标函数变量的系数约束条件右端项l 对偶单纯形法的计算步骤（1）将问题化为标准型,列出初始单纯形表；（2）若存在初始对偶可行的基本解,则进行迭代；（3）检验常数列b中的分量,若检验数全部非正而常数列b中的分量都为非负,则问题已得到最优解,终止迭代；否则,若检验数全部非正而常

7、数列b中的分量至少还有一个负分量,则进行下一步；（4）确定换出变量,即按对应的基变量为换出变量；（5）确定换入变量：检查的所在行的各系数.若所有,则无可行解,停止迭代；若存在,按法则,即所对应的列的非基变量为换入变量.（6）实施枢轴运算,即以为主元素按原单纯形法在表中进行迭代运算,得新的单纯形表：转入（3）继续迭代.2.2 基本定理和结论l 定理对于线性规划问题（LP）的基B,若满足,则称基B为可行基；若满足且,则对应的基B最优基,对应的基可行解为最优解,.l 定理对于可行基B所对应的单纯形表中,若某个,且非基变量所对应的列向量,则该线性规划问题无有界的最优解,即.l 定理换基后,目标函数值不

8、降（上升）,只有当时,目标函数值不变.l 性质可行解是最优解时的性质 设 是原问题的可行解, 是对偶问题的可行解, 当 时,是最优解. l 定理若原问题有最优解, 那么对偶问题也有最优解; 且目标函数值相等.第三章 单一变化的灵敏度分析3.1 的灵敏度分析对的灵敏度分析,就是在不改变原来最优解基变量及其取值的条件下,求出的允许变动范围,也就是求出变动值的上下限.因的变化仅影响检验数,因此灵敏度分析的基础是：的变化仍使单纯形表中非基变量检验数都保持为小于0.为便于为非基变量讨论,下面记.下面分两种情况分别讨论：3.1.1 为非基变量若为非基变量,即是非基变量的系数,这种情况下不变,也不变,其中是

9、初始表中的第j列,的变化只引起一个检验数的变化.设新的检验数.若,即,则最优解不变；若,则最优基不再是最优的了,以为换入变量,将最终表上的换成,换成,继续用单纯形法迭代.3.1.2 为基变量若为基变量,这种情况下,最终表内的要改变,因此影响到各个检验数.假设最终表内是第k行约束式的基变量,即有.设原检验数为,新的检验数为,则是初始表中的第j列,是最终表中的第j列.即,且有. （3.1.1）若,则所有,即最优解不变.若超出上述允许的范围,即,则以原最终表为基础,换上变化后的价值数和检验数,继续迭代,可求出新的最优解.若变化时,也可根据（5）式,在最终表上用检验数减去第k行上相应元素的倍,得到新的

10、检验数行,因为是基变量,所以,则最优解不变；如果,则用新的检验数和变化后的价值系数,继续迭代,可求出新的最优解.3.2 对的灵敏度分析对值的灵敏度分析,就是求在最优解基变量保持不变但基变量的取值可以变动的条件下的变动范围.因为的变化仅影响基变量的取值,因此分析的基础是：在的允许变动范围内,新的基变量的取值要满足非负约束.若有变量不满足非负约束,就是说的变动超出了灵敏度的范围.设变化为,根据前面的讨论：最优解的基变量,那么只要保持,最优基不变,即基变量保持,只有值的变化；否则,需要利用对偶单纯形法继续计算.3.3 对的灵敏度分析对的灵敏度分析,是指在不改变最优解基变量及其取值的条件下,求系数的允

11、许变动范围.由,知的变化,对最优解的取值和检验数都有影响.下面分情况进行讨论.3.3.1 为基变量若属于基变量时,设是最优基,则LP的单纯形法实施步骤为为单位矩阵,在LP中,A中的某个基变量所在列发生变化.设,.若,则得到新的LP问题：在原LP的终表中将所在列换成,但为基变量,故应以为换入变量,作初等变换,将,使,再用单纯形法求最优解.3.3.2 为非基变量若属于非基变量时,它的改变不会影响最优解的可行性,为初始表上的非基向量列,为改变后的.当变为时,有由前面知道.若系数处于第r行k列的系数增加后,只要第k列的检验数继续保持负值,最优解就没有变,如中的第k列为,则的范围为.若,则.若,则.此时

12、,那么最优解不变.3.4 增加约束条件灵敏度分析设增加的一个约束条件为 （3.4.1）其中.增加一个约束,或使可行域减少或保持不变,而绝不会使可行域增加.因此,若原最优解满足新约束,则它就是新问题的最优解；否则,需要寻找新的最优解.对于后者,因增加约束后的新问题在现行基的对应变量（,其中为式（6）的松弛变量）的检验数与原问题的相同,又因为是基变量,故.因此,现行的基本解是对偶可行的.若,则现行的对偶可行的1基本解是新问题的可行解,即最优解；反之,若,则在原最终单纯形表的基础上增加新约束（3.4.2）的数据,再对矩阵实施新的行变换,将原最终表上的各基向量列及新增列化为单位矩阵,再由对偶单纯形法继

13、续求解.第四章 全方位变化的灵敏度分析以往人们对分析的讨论仅限于单个参数,单一系数或单个限制条件的变化对结果的影响,而实际中多是规划问题中各参数同时变化,如前述因市场条件变化导致产品价格、生产工艺以及资源限制条件同时发生改变等.对于一般线性规划问题：上述情况既是目标函数系数向量C、变量约束系数向量即A中的列向量记为以及约束右端项向量b同时变化.对上述模型有如下最优单纯形表：表4 单纯形表基变量 0 0 0 注：其中目标函数最优值,最优解最优基变量记为；变量检验数向量：；约束系数矩阵且,其中表示矩阵的第个列向量,其变化后向量记为；目标函数系数向量,其变化后的向量记为；为约束右端项列向量,其变化后

14、的列向量记为.各参数变化后的符号分别记为.4.1非基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析不失一般性,设非基变量的目标函数系数发生变化、约束系数向量,变化后记为,；同时约束右端项向量变化为.则表中各参数相应修改为：,其中相应的,上表修改为如下表：表5 单纯形表修改表基变量 0 0 0 (1) 若且对偶可行性和可行性都满足,原最优基不变,最优解为,最优值为.(2) 若且对偶可行性不满足而可行性仍满足.若所对应列向量,则该问题无有限最优解.否则用单纯形法求新的最优解,即可按最小比值原则先在所对应列中选择主元进行换基迭代,依此继续用单纯形求解新的最优解.(3) 若且不全

15、为负这种情况为对偶可行性满足而可行性不满足.因为中至少有一个分量不满足非负,这时做如下处理：取中不满足非负的分量（设中分量为）的变量为出基变量,若对所有,则该问题无可行解,否则用对偶单纯形法求解新的最优解.(4) 若且不全为正对偶可行性和可行性均不满足.此种情况,我们采取了将单纯形法与对偶单纯形法结合起来的联合算法进行求解,其步骤如下所述：以乘常数项为负数的行,并去掉该行左边的基变量,此行简称无基行.若无基行有多个,可用下述方法使之只剩一个,取一无基行,比如常数项最小的,分别以该行的适当倍数加于其它无基行,使后者的常数项变为0,然后相继在每一个常数为0的无基行中取一非零元为主元,实行一次高斯消

16、元,该无基行即变为有基行.如此进行,直到常数项为0的那些无基行全变为有基行为止.这样只剩下一个无基行,设它的行号为,则其常数项,然后针对检验数所在列进行单纯形迭代,若所有检验数均为正,说明满足最优性条件满足,可用对偶单纯形法进行迭代；若有正检验数,但该j列系数,令,其中是取定的适当小的正数,然后把r行的Q倍加于目标函数行,其余不变,并重复上部骤.最后按单纯形法继续迭代,求优.4.2基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析不失一般性,设基变量的目标函数系数发生变化、约束系数向量,变化后记为,；同时约束右端项向量变化为.则表中各参数相应修改为,其中并且,即从基变量中去

17、掉,使所在的行成为无基行.相应的,表修改为如下表：表6 修改后的单纯形表基变量 0 0 （1）若则当时,所对应列向量,则该问题无有限最优解,否则无论的正负如何,按照最小比值原则,取中正分量进行迭代.以后步骤同联合算法.（2）不全为负同非基变量中的处理方法.第五章 算例5.1 单一变量的灵敏度分析算例某工厂在计划期内要安排生产A,B两种产品,已知生产单位产品所需设备台时及对甲,乙两种材料的消耗,有关数据如表所示.表7 数据AB可利用资源设备（台时）128甲（kg）4016乙(kg)0412单位利润（元）23问：1.应如何安排生产计划,使工厂获利最大？2.在什么范围变化时,保持最优解不变；若由,最

18、优解有什么变化？3. 在什么范围变化时,保持最优解不变；若,最优生产方案有什么变化？4. 由于调整工艺,产品A所需设备台时、对甲,乙两种材料的消耗以及利润变为.应如何安排生产计划,使工厂获利最大？5.增加一个约束条件：,最优解有什么变化？5.1.1 问题1的求解：解 设计划生产A,B两种产品的数量分别为,因此建立线性规划模型为 （3）下面我们用单纯形法来解决这个问题；首先,引入松弛变量,将（3）式化标准型（5.1.1）建立单纯形初表：表8 单纯形初表基 b1 2 1 0 084 0 0 1 0160 4 0 0 1122 3 0 0 0为进基变量,为出基变量,得新的单纯形表表9 新的单纯形表基

19、 b1 0 1 0 -1/224 0 0 1 0160 1 0 0 1/432 0 0 0 -3/4重复上部骤,直到有明确结论,最后得单纯形终表表10 单纯形终表基 b1 0 0 1/4 040 0 -2 1/2 140 1 1/2 -1/8 020 0 -3/2 -1/8 0 所有非基变量检验数均小于0,达到最优为唯一最优解,有上计算可知,计划生产A,B两种产品的数量分别为4,4时,工厂获利最大,为14.5.1.2 问题2的求解：解由上的求解过程可以看出,是基变量的系数,的变化会影响所有非基变量的检验数,将变化反应到单纯形终表上：表11 变化后的单纯形表基 b1 0 0 1/4 040 0

20、-2 1/2 140 1 1/2 -1/8 022 3+ 0 0 00 0 -3/2 -/2 -1/8+/8 014+2从表中可以看到 即 即可得到时,原最优解不变.同理.可以求出当的取值由3变化到5时最优解的变化.5.1.3 问题3的求解：解 为保持最优解不变,要求,即得到的取值范围为即再由单纯形表可知,当时,将其反映到单纯形终表中,得表12基 b1 0 0 1/4 04+00 0 -2 1/2 14-80 1 1/2 -1/8 02+20 0 -3/2 -1/8 01 0 0 1/4 040 0 1 -1/4 -1/220 1 0 0 1/430 0 0 -1/2 -3/4此时,最优生产方

21、案为生产A产品4个单位,B产品3个单位,最大利润为z=17.从上表可以看出,即设备有2小时未被利用.5.1.4 问题4的求解解 由单纯形终表可以看出改变的是基变量系数列向量发生改变.则设新工艺后A的生产量为同时计算出的检验数：反应到终表上,得表13基 b5/4 1 0 0 1/4 041/2 0 0 -2 1/2 143/8 0 1 1/2 -1/8 023/8 0 0 -3/2 -1/8 0表14 终表基 b1 0 0 1/5 016/50 0 -2 2/5 112/50 1 1/2 -1/5 04/50 0 -3/2 -1/5 0由上表可得此时,最优生产方案为生产A产品16/5个单位,B产

22、品4/5个单位,最大利润为z=44/5元.5.1.5 问题5的求解：解 由于原最优解不满新的约束条件即,所以原最优解不再是最优解,故引入松弛变量,此时LP问题的标准型为：反应到单纯形终表上表15基 b1 0 0 1/4 0 040 0 -2 1/2 1 040 1 1/2 -1/8 0 020 -3 0 0 0 1-30 0 -3/2 -1/8 0 0将,所在列换成单位向量,经变换得到最终表,结果为,5.2 全方位变化的灵敏度分析算例求解下列线性规划问题（5.2.1）通过单纯形法解得最优解,最优值.若上述问题的变量目标函数系数、约束系数向量以及约束右端项向量同时改变,且变化后分别为,则改变后的

23、问题最优解和最优值是多少？解原问题（5.2.1）的最优表如下：表16 最优表基变量 b3 0 0 1 1188 1 0 0 0163 0 1 -1 04-10 0 0 -1/2 0-30由上表可见,是基变量,所以是基变量目标函数系数、约束系数向量以及约束右端项向量同时变化的灵敏度分析.由原问题的最优解和最优值,可得以下已知条件：,所以,由不全大于等于0,我们可以采用1联合算法,即非基变量（4）中的处理步骤.则单纯形表修改后的下表：表17 修改后的表基变量 b3 2 0 1 14 8 4 0 0 003 1 1 -1 0-1-10 -6 0 -1/2 0-5根据本文第一部分情况（4）的处理步骤,

24、上表中的所在行常数项为负,所以去掉,使之成为无基行,且用-1乘该行得下列求解迭代过程.表18基变量 b3 2 0 1 148 4 0 0 00-3 -1 -1 1 01-10 -6 0 -1/2 0-5-1 0 0 1 142 1 0 0 00-1 0 -1 1 012 0 0 -1/2 0-50 1/2 0 1 141 1/2 0 0 000 1/2 -1 1 010 -1 0 -1/2 0-50 0 1 0 131 1/2 0 0 000 1/2 -1 1 010 -3/4 -1/2 0 0-9/2由上表可见新问题的最优解,最优值第六章 结论本文首先对灵敏度分析问题的相关概念和主要定理进行

25、概述,其后分别讨论分析了变量目标函数系数、变量约束系数向量、约束右端项向量这些单一参数发生变化时,最优解的求的方法,接着就各种参数同时发生变化时的情况进行了讨论,最后以运筹学上投入产出问题对灵敏度分析的上述理论进行验证和进一步的说明.当然,对于灵敏度分析问题,我们认为还有以下几个方面可以进一步研究：（1）参数、中任何两个同时发生改变时,对最优解有何种的影响；（2）在本文中,只讨论了增加约束条件的情况,但现实生活不仅只有增加,还会出现减少约束的情况,这种情况又该如何处理；（3）在全方位的灵敏度分析中,同时变化的既有基变量的目标函数系数、约束系数向量以及约束右端项向量,又有非基变量的,这种情况下,

26、最优解又会发生什么变化.这些都是我们今后可以讨论的问题.参考文献1 陈友华.运筹学M.安徽:中国科技技术大学出版社,2008.2 胡运权.运筹学教程M.北京:清华大学出版社,1998.3 夏少刚.运筹学经济优化方法与模型M.北京:清华大学出版社,2005.4 运筹学教材编写组.运筹学(第三版)M.北京:清华大学出版社,2005.5 陈宝林.最优化理论与算法M.北京:清华大学出版社,2003.6 夏少刚.有界变量线性规划的一种简易解法J.运筹与管理,2005,14(6):12-18.7 杨玉英.线性规划问题的灵敏度分析及其应用J.吉林大学学报,2009,30（5）：32-358 夏少刚,费威.目

27、标函数系数、约束右端项及系数矩阵A同时变化的灵敏度分析J.经济数学,2008,25（3）：319-324.9 夏少刚,刘心.线性规划增减约束条件的灵敏度分析J.运筹与管理,2007,16（2）：1-5.10 夏少刚,费威.线性规划全方位变化的灵敏度分析J. 运筹与管理,2009,18(5):33-37.11 夏少刚.线性规则联合算法的理论和应用J.运筹与管理,2004,13(1):3-8.12 孙玉华,刘艳敏.目标函数系数与约束右端项同时变化的灵敏度分析J.经济数学,2007,24(9):321-326.13 李慧.线性规划消耗数矩阵灵敏度分析的某些探讨J.数学的实践与认识,2004,34 (

28、9):119-126.14 薛意志,曹明华.线性分式规划消耗系数矩阵灵敏度健析及应用J.数学的实践与认识,2006,36(5):273-279.15 方秋莲,刘再明,阮国桢.基于改进基线算法的线性规划灵敏度问题研究J.数学的实践与认识,2007(12).16 吴延东.求线性规划问题对偶问题最优解的一种方法J.运筹与管理,2000,9(1): 84-87.17 杨德权,等.线性经济系统管理创新的数量方法研究J.预测,2002,21(6):32-35.致 谢光阴似箭,岁月如梭,在合肥学院的时光即将成为美好的回忆.这段经历使我终身受益,终身难忘.谨以此文向所有关心和支持我的人致以最诚挚的敬意！在我论

29、文的完成过程中,要感谢我的导师管梅老师.管老师花费了大量的心血对我指导,她思想的活跃、思想的深度以及对问题敏锐的洞察使我受益匪浅,她对数学研究的严谨态度深深的影响了我.她对我一如既往的支持使我不断在完成论文的道路上前进,她对我深切的关怀让我体会到亲情的温暖.本论文的主要思想正是来源于她的启发和鼓励.感谢管老师对我论文的多次审阅并提出宝贵建议.还要感谢所有老师们,这四年来在学习上和生活上给予的悉心指导和热心帮助,在许多问题上给我及时的指导和启迪,指引我克服了很多生活和学习中遇到的困难.四年来,老师们渊博的专业知识,严谨的治学态度,谦逊的为人和孜孜不倦的探索精神给我留下了深深的印象,并深深的影响了我,这些必将惠及我将来的学习、工作和生活.同时感谢四年里同学们给我的帮助.徐戈 2011年5月于合肥学院.忽略此处.26