灵敏度分析.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第四章灵敏度分析,1,在根据一定数据求得最优解后，当这些数据中某一个或某几个发生变化时，对最优解会产生什么影响。或者说，要使最优解保持不变，各个数据可以有多大幅度的变动。这种研究线性规划模型的原始数据变化对最优解产生的影响就叫做线性规划的灵敏度分析。,2,目标函数的系数变化对最优解的影响；,约束方程右端系数变化对最优解的影响；,约束方程组系数阵变化对最优解的影响,；,回答两个问题,：,灵敏度分析的内容,3,这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？,系数变化超出上述范围时，如何用最简便的方法求出新的最优解？,4,灵敏度分析的基本原理,对于标准线性规划问题,设为基本解，是基对应的目标系数向量，是基的逆矩阵，则原问题可表示为：,5,是最优解的条件是：,在线性规划的灵敏度分析中，我们主要用到以下两条性质：,（）,可行性,：指标准型线性规划问题的基本解满足非负性。,（）,正则性,：指标准型线性规划问题的非基变量所对应的检验数向量满足非正性。,6,线性规划问题的任何参数变化，对解将产生以下种影响：,（）发生变化，即对解的可行性可能有影响，而对解的正则性无影响。此时，若解的可行性仍满足，则最优解不变,（）检验数，即发生变化，即对解的正则性有影响，而对解的可行性没有影响。此时若解的正则性满足，则最优解不变,（）和同时发生变化,7,一、目标系数的灵敏度分析,、非基变量的目标系数的灵敏度分析,8,例1.1已知线性规划问题,问当的系数由提高到时，最优解是否发生变化？,9,10,从最优单纯形表中我们可以看到为非基变量，则由上面分析结论可知只要最优解不会发生变化，仍然为非基变量。,因为，则，即时最优解不会发生变化。从而，当的系数由提高到时，最优解不会发生变化。,11,、基变量的目标系数的灵敏度分析,12,13,例,2.1,已知线性规划问题,问当的系数由降到时，最优解是否发生变化？,14,15,解：设发生的变化，则可得到：,即,从而，,这说明只要的系数在到变动时，最优解不变化。,16,例2.2已知线性规划问题,求（）使原最优解不变的的变化范围；（）若变为，求新的最优解。,17,求（）使原最优解不变的的变化范围；（）若变为，求新的最优解。,18,（）若C,1,变为，求新的最优解。,19,1 已知线性规划问题：,课 堂 练 习,P153(4),求,（1）,为使最优解不发生变化时目标函数系数 允许变化的范围。（2）每个约束条件的影子价格,20,21,二、约束常数的灵敏度分析,22,23,24,25,例3.1已知线性规划问题,问当的系数由降到时，最优基是否发生变化？当的系数由增到时，最优基是否发生变化？,26,27,28,29,例3.2已知线性规划问题,求（）使原最优解基不变的的变化范围；（）若变为200，求新的最优解。,30,31,32,33,课 堂 练 习（续）,P153(4),求,（1）,为使最优解不发生变化时目标函数系数 允许变化的范围。（2）如第二个约束条件右端常数变为60，确定新的最优目标函数值。,34,35,由单纯形表可知，,为使最优基不发生变化，,220,36,三、增加新的变量的灵敏度分析,37,例4.1已知线性规划问题,问当新增变，且最优基是否发生变化？,38,39,则最优基不发生变化,40,例4.2已知线性规划问题,问当新增变，且最优基是否发生变化？,41,42,最优单纯形中变量x,5,所对应的列P,5,43,44,课 堂 练 习（续）,P153(4),问当新增变量 ，且最优基是否发生变化？如变化给出变化后的最优值。,45,46,3,2,0,0,10,CB,XB,X1,X2,X3,X4,X5,b,2,X2,0,1,2/3,-1/3,0,10,3,X1,1,0,-1/3,2/3,3,20,0,0,-1/3,-4/3,1,2,X2,0,1,2/3,-1/3,0,10,10,X5,1/3,0,-1/9,2/9,1,20/3,-1/3,0,-2/9,-14/9,0,260/3,47,四、增加新的约束条件的灵敏度分析,48,49,例5.1已知线性规划问题,问当新增约束 ，最优解是否发生变化？如果有求出新的最优解。,50,51,52,53,例5.2已知线性规划问题,问当新增约束最优解是否会发生变化,54,第一个约束条件满足，最优解不变；第二个约束条件不满足，最优解发生变化。,55,30,25,35,0,0,0,0,CB,XB,X1,X2,X3,X4,X5,X6,X7,b,30,X1,1,3,0,2,-1,0,0,600,35,X3,0,-1,1,-1,1,0,0,200,0,X6,0,-4,0,-3,1,1,0,600,0,X7,3,1,2,0,0,0,1,1600,0,-30,0,-25,-5,0,0,30,X1,1,3,0,2,-1,0,0,600,35,X3,0,-1,1,-1,1,0,0,200,0,X6,0,-4,0,-3,1,1,0,600,0,X7,0,-6,0,-4,3,0,1,-600,0,-30,0,-25,-5,0,0,56,30,25,35,0,0,0,0,CB,XB,X1,X2,X3,X4,X5,X6,X7,b,30,X1,1,3,0,2,-1,0,0,600,35,X3,0,-1,1,-1,1,0,0,200,0,X6,0,-4,0,-3,1,1,0,600,0,X7,0,-6,0,-4,3,0,1,-600,0,-30,0,-25,-5,0,0,30,X1,1,0,0,0,-1/2,0,-1/2,900,35,X3,0,0,1,-1/3,-5/6,0,-1/6,300,0,X6,0,0,0,-1/3,1/3,1,-2/3,1000,0,X7,0,1,0,2/3,-1/6,0,-1/6,100,0,0,0,-6,-10,0,25,37500,57,课 堂 练 习（续）,P153(4),问当新增约束最优解是否会发生变化，如变化给出新的最优解。,58,3,2,0,0,0,0,CB,XB,X1,X2,X3,X4,X5,b,2,X2,0,1,2/3,-1/3,0,10,3,X1,1,0,-1/3,2/3,0,20,0,X5,3,1,0,0,1,30,0,0,-1/3,-4/3,0,2,X2,0,1,2/3,-1/3,0,10,3,X1,1,0,-1/3,2/3,0,20,0,X5,0,0,1/3,-5/3,1,-40,0,0,-1/5,-4/3,0,59,3,2,0,0,0,0,CB,XB,X1,X2,X3,X4,X5,b,2,X2,0,1,2/3,-1/3,0,10,3,X1,1,0,-1/3,2/3,0,20,0,X5,0,0,1/3,-5/3,1,-40,0,0,-1/5,-4/3,0,2,X2,0,1,3/5,0,-1/5,18,3,X1,1,0,-1/5,0,2/5,4,0,X4,0,0,-1/5,1,-3/5,24,0,0,-3/5,0,-4/5,60,60,五、技术系数的灵敏度分析,、非基变量的技术系数的灵敏度分析,61,62,63,例6.1已知线性规划问题,问当变为时最优解是否会发生变化,64,65,66,、基变量的技术系数的灵敏度分析,67,68,例6.2已知线性规划问题,问当的系数变为 ，最优解是否发生变化？如果有求出新的最优解。,69,70,71,72,下表结果是错误的，继续求解只是为了说明如何求解此种情况！,73,74,灵敏度分析小结,75,76,参数线性规划,灵敏度分析研究了个别数据变动之后，原来的最优解条件是否受到影响，研究这些数据的变化对最优解的变化是否“敏感”。在灵敏度分析中每次只考虑一个数据的变化，如果几个数据同时发生变化，又将产生什么结果呢？参数规划就是用来研究这类问题的。参数规划研究这些参数中某一个数连续变化时，使最优解发生变化的各临界点的值。,在一般情况下，众多的数据均可以有各种形式的离散性或连续性变化。但是迄今为止，,参数规划中有效的分析方法还都局限于数据的,线性变化,。,因此讨论的内容实质上是线性参数规划。参数规划同灵敏度分析一样是,在已有的最优解的基础上,进行分析。,77,（1）对含有某参数变量t的参数线性规划问题，先令t=0,用单纯形法求出最优解。,（2）用灵敏度分析方法，将参数变量t直接反映到最终表中,并重新计算检验数。,（3）当参数变量接连变大或变小时，观察基变量值和检验数的变化，若某基变量首先出现负值时，则以该变量为换出变量，用对偶单纯形法迭代；若在检验数中首先出现某正值时，则以它对应的变量为换入变量，用单纯形法迭代下一步。,（4）在经迭代一步后的新表上，令参变量t继续变大或变小，重复（3）直到基变量不再出现负值，检验数行不再出现正值为止。,分析参数线性规划问题的步骤是：,78,例7.1 试分析下列参数线性规划问题，当 参数时,最优解的变化。,参数 C 的变化分析,79,80,81,82,83,例7.2 试分析下列参数线性规划问题，当 参数时,最优解的变化。,参数 b 的变化分析,84,85,86,87,1 某公司制造三种产品A,B,C，需要两种资源（劳动力和原材料），要求确定总利润最大的最优生产计划，该问题的线性规划模型如下：,其中是产品A,B,C的产量。,作业,88,这个线性规划问题的最优单纯形表如下所示：,89,（）求出使得最优解不变的产品A的单位利润变动范围。问时最优解是否会发生变化。,（）求出使得最优解不发生变化的劳动力资源变动范围。,（）由于技术上的突破，每单位产品B原材料的需要减少为单位，这时是否需要改变生产计划？为什么？,（）假如这时，又试制成新产品D，生产一个单位新产品D需要劳动力单位，原材料单位，而每单位的新产品D的利润为1元，请问这时生产计划是否要进行修改？为什么？,90,2 已知线性规划问题,先用单纯形方法求出最优解，然后分析在下列各条件下，最优解分别有什么变化？,91,约束条件(a)的右端常数由变为；,约束条件(b)的右端常数由变为；,目标函数中的系数由变为；,的系数列向量由变为,新增一个约束条件；,92,3 试分析下列参数线性规划问题，当 参数时,最优解的变化。,93,4 试分析下列参数线性规划问题，当 参数时,最优解的变化。,94,