2.7灵敏度分析.ppt

1、第七节 灵敏度分析,本节内容安排,资源数量变化的分析 目标函数中价值系数的变化分析 技术系数的变化分析,线性规划问题中， 都是常数，但这些系数往往是估计值和预测值： 市场的变化 值变化； 工艺的变化 值变化； 资源的变化 值变化。,背景：,灵敏度分析（Sensitivity Analysis） 又称为优化后分析（Postoptimality Analysis）， 就是分析研究线性规划模型参数的取值变化时， 对最优解或最优基的影响。 它在应用线性规划解决实际问题的过程中是非常有用的。,定义:,（1）当这些参数中的一个或多个发生变化时， 原最优解会怎样变化？ （2）当这些参数在什么范围内变化时，

2、原最优解仍保持不变？ （3）若最优解发生变化， 如何用最简单的方法找到现行的最优解？,解决的问题：,研究方法：,图解法 对偶理论分析,仅适用于含2个变量的线性规划问题,在单纯形表中进行分析,2.将参数的改变计算反映到最终单纯形表上来；,3.检验原问题是否仍为可行解;,灵敏度分析步骤,1 求出LP的最终单纯形表,4.按下表所列情况得出结论 和决定继续计算的步骤.,检验对偶问题是否仍为可行解；,系数变化后最终表的几种情况,当LP模型的参数发生变化后， 可不必对线性规划问题重新求解， 直接在原LP取得最优解的基础上进行分析或求解， 既减少计算量， 又可根据参数变化范围及时对原决策作出调整和修正，,注

3、意：,-1b , z=CBB-1b, =C-CBB-1A,由最终单纯形表可知，资源数量 bi 的变化，会影 响到原最优解的可行性与目标函数值，但不会影响检验数。,一 资源数量 bi变化的灵敏度分析,（2）若bi变化后，有-1b，当前基为非可行基 ，又因为bi的变化不影响检验数，所以仍然保持为对偶可行基，此时可以用对偶单纯形法求出新的最优解,（1）若bi变化后，仍保持-1b，则当前基仍为 最优基，最优解的结构不变，但是取值改变,若bi变化后，可行性改变，则原最优解结构改变， 用对偶单纯形法，找出新的最优解。,若bi变化后，可行性不变，则原最优解结构不变。,结论,bi变化后，原最优解怎样变化；若最

4、优解发生变化，则变化后，如何求出新的最优解？,LP与DP的最优解的取值都可能变化,（1）若 ，当前基仍为最优基，最优解的结构 不变，但是取值改变（方法一）,对偶问题：,对DP的最优解没有影响。,（2）若 ，原问题的解为非可行解，此时 可以用对偶单纯形法求出新的最优解,2.如何求出保持最优基不变（最优解结构不变）的bi的范围？,原问题：,原问题的解保持为基可行解的br的范围（方法二）,（1）br 的变化范围是由原基变量 的相反数与 B-1的第r列元素的比值所确定。 （2）公式中，比值的分子都0； br 大于等于比值小于0的最大值， 小于等于比值大于0的最小值。,或,说明,结论：当bi 在上述范围

5、内变化时， 仍保持-1b， 当前基仍为最优基，最优解的结构不变， 但是取值改变,（3）当某air = 0时， br 可能无上界或无下界。,或,（4）若br 不在上述范围变动， 则变化后的基变量所取值XB肯定会出现负分量， 但由于br 不影响检验数的变化，对偶基解仍可行。 因此可用XB取代原最优解XB = B-1 b， 以该解为原LP初始解，用对偶单纯形法继续求解。,保持最优基不变（最优解结构不变）的bi的变化范围的求解方法：,方法二,得bi的变化范围，再得bi的变化范围。,方法一,得bi的变化范围,再得bi的变化范围。,例 对线性规划问题,分别分析1、2、3在什么范围内变化， 问题的最优基不变

6、.,先分析1的变化.,解：,方法一：,最终表:,使问题最优基不变的条件是,由此推得612.,方法二：,由此推得42.,由此推得5315.,使问题最优基不变的条件是,同理有：,方法三：,例：（P64) 求第1章例1中第二个约束条件 b2的变化范围，使最优解的结构不变。,解：可以利用第1章例1的最终计算表（P32）中的数据：,可计算b2：,由上式，可得b2-4/0.25=-16， b2-4/0.5=-8， b22/0.125=16。 所以b2的变化范围是-8，16； 原b2 =16，b2的变化范围是8，32， 即b2的变化范围是8，32时，最优解保持不变。,例7 从表1-5（P32）得知第1章例1

7、中，每设备台时的影子价格为1.5元，若该厂又从其他处抽调4台时用于生产产品，。求这时该厂生产产品，的最优方案。,解: 先计算B-1b,将结果反映到最终表1-5中， 得 表2-10。,由于表2-10中b列有负数，故用对偶单纯形法求新的最优解。计算结果见表2-11。,表2-11,即该厂最优生产方案应改为生产4件产品，生产3件产品，获z*=42+33=17(元) 从表2-11 看出x3=2，即设备还有2小时未被利用,例:,在线性规划问题中，对b1进行灵敏度分析 。,解:,cj-zj,对于上述最优解，最优基为：,当b1=b1+b1 =9+ b1时，最后一张单纯形表 中的右边常数将成为,最后一张单纯形表

8、中的右边常数将成为（令b1=),cj-zj,原始可行条件为：,-1，b1=b1+=9+8 时，最优基不变,但是最优解的值发生变化.,例: 已知线性规划问题 （1）求b1 , b2 , b3 分别在什么范围内变化时，原最优基不变。 （2）若b2 变为30，求新的最优解,(1) 由表知，最优基B , B-1 ,XB 分别为：,得b1 -5 , b1 35 时，最优基不变； -5 b2 5 ， 即15 b2 25 时，最优基不变 -15 b3 5 ， 即0 b3 20 时，最优基不变,另解：,得b1 -5 即b1 35 时，最优基不变,得-5 b2 5 即15 b2 25 时，最优基不变,得-15

9、b3 5 即0 b3 20 时，最优基不变,（2）若b2 变为30，求新的最优解 15 b2 25 时，最优基不变。变化后基变量的 取值为:,不是可行解，须替换原最优表中基变量的值，并采用对偶单纯形法继续求解，结果如下：,-5,15,15,最优解（10，0，15）最优值Z = 55,目标函数系数cj的改变,(1)当cj是非基变量的价值系数时,它的变化只影响j 一个检验数；不影响最优解和目标函数值。 (2)当cj是基变量的价值系数时,它的变化将影响所有 非基变量的检验数；影响目标函数值；不影响最优解 (3)当cj的变化时,如能保持j0,则当前的解仍为最优解,否则可用普通单纯形法继续迭代，求出新的

10、最优解.,二 目标函数中价值系数cj变化的灵敏度分析,1 cj是非基变量的价值系数,原问题的解:,对偶问题的解:,当cj变化时,原问题的解仍保持为基可行解, 对偶问题解的取值受到影响。,即保持对偶问题的解为基可行解的 cj的范围,此时z=CB B-1 b及XB=B-1 b的值都不变，只有j 的值发生变化,为使原最优解不变，则最终表中xj 的新检验数j0,（其他变量检验数不变）,在其他参数保持不变时，求cj 的变化范围使原最优解不变,非基变量在目标函数中系数的灵敏度分析例子,例: 在线性规划问题中，对c2进行灵敏度分析 。,得到以上问题的最优单纯形表：,当c2= c2+ 时，相应的单纯形表为：,

11、-1+ ,- 47/12,要使原来的解仍保持最优解，就要cj-zj0（j=1,2,3,4,5），即,由此得到， ,即当c235/12时，最优解保持不变,（方法一）,最优单纯形表：,方法二：,不受影响。,原问题的解,对偶问题的解,2 cr是基变量的价值系数,受到影响,求保持对偶问题的解为基可行解的cr的范围,当cr是基变量xr的价值系数,且cr有增量cr 时， XB=B-1 b的值不变， 但z=CB B-1 b的值变化， 且所有非基变量的检验数 j =cj - CBB-1Pj 都变化.,目标函数值 z=CB B-1 b 受到影响,具体计算时，可按arj 的符号分成两部分， 分别求比值， 然后在比

12、值为负号中取最大者为上限， 比值为正号中取最小者为下限， 当出现arj =0时，cr 可能无上界或无下界。 Cj无论作为基变量还是非基变量， 它的变化影响到非基变量的检验数j =cj - CBB-1Pj的变化， 不会引起XB =B-1b的 变化， 反映到最终单纯形表中，只能出现前面两种情况。,基变量在目标函数中系数的灵敏度分析例子,例： 在线性规划问题中，对c1进行灵敏度分析 。,得到以上问题的最优单纯形表：,当c1=c1+时，相应的单纯形表为：,-1+ ,/4- 47/12,-1+ ,-1+/3,-2-2/3,要使原来的基仍保持最优基，就要cj-zj0（j=1,2,3,4,5），即,由此得到

13、，-33，即当-4c12时， 最优基保持不变,方法一,最优单纯形表：,方法二,例8 试以第1章例1的最终表1-5为例。设基变量x2的系数c2变化c2，在原最优解不变条件下，确定c2的变化范围。,解： 这时表1-5最终计算表便成为表2-12所示。,由此可得c2-3 和c21。 则c2的变化范围为 ：-3c21 即x2的价值系数c2可以在0，4之间变化，而不影响原最优解。,若保持原最优解，从表2-12的检验数行可见应有,例： 已知线性规划问题,试分析1和2分别在什么范围变化，问题的最优解不变.,解：当1=2=0时，最终表为,表中解为最优的条件是：,由此推得 211,当2=0时，,当1=0时，,表中

14、解为最优的条件是：,由此推得,例: 已知线性规划问题 （1）求最优解 （2）分别求C1 ,C2 ,C3 的变化范围，使最优解不变 (3)若c1 变为4，求新的最优解 解：加入松弛变量X4, X5 , X6 用单纯形法，得最优表,最优解为X=(5,0,15)T 最优值为Z=50 （2）分别求C1 ,C2 ,C3 的变化范围，使最优解不变 x2 为非基变量 ，x 1 ，x3 为基变量 则c2 -2 =3, c2* 4 -1 c1 2, 0 c1* 3 c3 -2, c3* 1 另解c3* ： c3* = c3+ c3 非基变量检验数0，则有： 2*= c2 CB* B-1 P2=1 - (0, 1

15、, 3 + c3 ) = - 3 - c3 0 5*= c5 CB* B-1 P5= - (0, 1, 3 + c3 ) = -1 6*= c6 CB* B-1 P6= - (0, 1, 3 + c3 ) = - 2- c3 0 则有： c3 - 2 同理可得c2 , c1 的变化区间,（3） 若c1 变为4，求新的最优解0 c1* 3,4,4,-6,-4,1,最优解 （20，0，0） 最优值 Z=8 0,个要点 （）某非基变量技术系数aij的改变会影响该非基变量的检验数，如果检验数仍然可以满足，则最优解保持不变否则继续迭代 （）某基变量技术系数aij的改变的灵敏度分析比较复杂，因为某基变量技

16、术系数aij的改变对最终表解的可行性和检验数行的检验系数都可能产生影响,三 技术系数aij变化的灵敏度分析,-1b , z=CBB-1b, =C-CBB-1A,下面来讨论技术系数ij的变化。,设xn+1 是新增加的变量， 其对应的系数列向量为Pn+1 , 价值系数为Cn+1 ， 试讨论原最优解有无改变？ 及如何尽快求出新的最优解。 若原问题增加一个新变量， 则系数矩阵增加一个列， 在以B为基的最终单纯形表中， 新增加的列Pn+1应变为 B-1 Pn+1 ， xn+1 的检验数应变为n+1 = Cn+1 - CB B-1 Pn+1 ， 若n+1 0，则原最优解不变， 反之可将B-1 Pn+1 增

17、添到原最优表的后面， 用普通单纯形法继续迭代。,1 增加一个新的变量的分析（非基变量技术系数aij的改变),（1）计算n+1 = Cn+1 - CB B-1 Pn+1 (2) 计算Pn+1=B-1Pn+1 (3) 若n+10，只需将Pn+1和n+1的值直接反映到最终 单纯形表中，原最优解不变； 若n+10，则按普通单纯形法继续迭代计算.,步骤如下：,例9 分析在原计划中是否应该安排一种新产品。 以第1章例1为例。设该厂除了生产产品， 外，现有一种新产品III。 已知生产产品III，每件需消耗原材料A，B各为6kg，3kg，使用设备2台时；每件可获利5元。 问该厂是否应生产该产品和生产多少?,解

18、: 分析该问题的步骤：,(1) 设生产产品III为x6台，其技术系数向量P6=(2,6,3)T，然后计算最终表中对应x6的检验数 6 = C6 - CB-16= 5 - ( 1.5 , 0.125 , 0 ) ( 2 , 6 , 3 )T =1.25 0 说明安排生产产品III是有利的。,表 2-13(a),由于b列的数字没有变化，原问题的解是可行解。 但检验数行中还有正检验数，说明目标函数值还可以改善。,（2）,(3) 将x6作为换入变量，x5作为换出变量，进行迭代，求出最优解。 计算结果见表2-13(b)，这时得最优解：x1=1,x2=1.5，x6=2。总的利润为16.5元。比原计划增加了

19、2.5元。,表2-13(b),解 ： 把改进工艺结构的产品看作产品，设x1为其产量。于是在原计算的最终表中以x1代替x1，计算对应x1的列向量。,例10 分析原计划生产产品的工艺结构发生变化。 仍以第1章例1为例， 若原计划生产产品的工艺结构有了改进， 这时有关它的技术系数向量变为P1=(2,5,2)T， 每件利润为4元， 试分析对原最优计划有什么影响?,同时计算出x1的检验数为 c1- CBB-1P1= 4 - (1.5 , 0.125 , 0) (2,5,2)T=0.375,2.基变量技术系数aij的改变的灵敏度分析,表 2-14,可见x1为换入变量，x1为换出变量，经过迭代。 得到表2-

20、15,将以上计算结果填入最终表x1的列向量位置,表 2-15,表2-15表明原问题和对偶问题的解都是可行解。 所以表中的结果已是最优解。 即应当生产产品，3.2单位； 生产产品，0.8单位。 可获利15.2元。 注意：若碰到原问题和对偶问题均为非可行解时，就需要引进人工变量后重新求解。(下面例题说明）,例11 假设例10的产品的技术系数向量变为P1=(4,5,2)T，而每件获利仍为4元。试问该厂应如何安排最优生产方案?,解： 方法与例10相同，以x1代替x1，并计算列向量,x1的检验数为 c1- CBB-1P1=4 -（ 1.5 , 0.125 ,0 ) ( 4,5,2 )T = -2.625

21、。 将这些数字填入最终表1-15的x1列的位置，得到 表2-16。,表 2-16,将表2-16的x1变换为基变量，替换x1，得表2-17。,表 2-17,从表2-17可见原问题和对偶问题都是非可行解。 于是引入人工变量x6。 因在表2-17中x2所在行，用方程表示为 0 x1+x2+0.5x3-0.4x4+0 x5= -2.4,引入人工变量x6后，便为 -x2-0.5x3+0.4x4+x6=2.4 将x6作为基变量代替x2，填入表2-17，得到表2-18。,表 2-18,这时可按单纯形法求解。 X4为换入变量，x6为换出变量。经基变换运算后，得到表2-19的上表。,表 2-17,-x2-0.5

22、x3+0.4x4+x6=2.4,表 2-19,在表2-19的上表中，确定x2为换入变量，x5为换出变量。经基变换运算后，得到表2-19的下表。 此表的所有检验数都为非正，已得最优解。 最优生产方案为生产产品，0.667单位； 产品，2.667单位，可得最大利润10.67元。,例,若增加一个变量x6， 有c6=4， P6=(2，4，5)T， 试分析问题最优解的变化,故新的最优解为 x1=3， x2=2，x6=1， 最优值为： z*=16.,将其代入表2-3得表2-11,表2-11,表2-12,解：,4,0,4,1,1,例：,增加一个约束条件 3x1+2x214， 要求分析最优解的变化.,解： 因

23、为33+23=1514， 所以将约束条件加上松弛变量后的方程3x1+2x2+x6=14直接反映到最终单纯形表2-3得下列各表,3 增加一个新约束条件的分析,故新的解为： x1=8/3，x2=2，z*=34/3.,设am+1,1 x1 +a m+1 ,2 x2 + +a m+1 ,n x n bm+1 是新增加 的约束条件，分析原问题的最优解有无变化？ (1)将原最优解带入新约束中，如果满足新约束条件，则原最优解不变，反之，则需要进一步求出新的最优解。 (2)在单纯形算法中，每步迭代得到的单纯形表对应的约束方程组都与原约束方程组等价，因此，可以将新约束方程 am+1,1 x1 +a m+1 ,2

24、 x2 + + a m+1 ,n x n +xn+1 = bm+1 填到原最优表的下面，变化后的单纯形表增加一个行，一个列 新约束对应的基变量是x n+1 .在单纯表中，由于增加了新的约束，原基变量对应的列向量可能不再是单位列向量， 所以需用初等行变换将表中基变量对应的列向量变为单位列向量。 变换后，原最优表中的检验数不变，但基变量x n+1 所取得的值一般要变。 (3)若x n+1 = B-1 b m+1 0 , 则已得最优解； 若x n+1 = B-1 b m+1 0 ，则用对偶单纯形法继续求解,3 增加一个新约束条件的分析,增加一个新的约束：-x1+2x22，求新的最优基和最优解。,-x

25、1+2x22,-x1+2x2-x7=2,x1-2x2+x7=-2,例：,在原最优单纯形表中加入新方程：,-2,x7,0,x6,x5,b,x4,x3,x2,x1,XB,CB,cj,0,0,0,4,-1,-1,13/3,6,1/3,x3,x5,x1,4,0,-1,1/3,0,1/3,1,2/3,0,1,1,0,0,2,0,-2/3,0,1/3,0,-1/4,1,1,2/3,0,1/3,0,-7/4,0,0,0,0,x7,0,-7/3,x7,0,变成单纯形表：,cj-zj,1、求加入新列Pn+1B-1Pn+1 2、求对应新列的检验数 n+1 = Cn+1 - CB B-1Pn+1 ， 如n+1为正，

26、则再应用单纯形法进行迭代,1、产生一个新列 2、该列可能会出现正 的检验数,增加一种新产品,增加一个变量,1、先检验原最优解是否满足新增加的条件 2、否，用初等行变换将表中基变量对应的列向量变为单位列向量, 若x n+1 = B-1 b m+1 0再应用对偶单纯形法迭代,1、增加一个新行和一个新列 2、该行可能会出现负的b值，,增加一道工序,增加一个约束条件,用对偶单纯形法 求XB*B1b*， 使XB*0,基变量有影响 检验数无影响,资源数量变化,bj,用单纯形法求行，使 0,检验数有影响 基变量无影响,J产品产生的利润发生变化,Cj,对终表的处理方法,终表中受影响的量,经济意义,变量,判断:,任何线性规划问题存在并具有唯一的对偶问题. 已知y*i为线性规划的对偶问题的最优解,如果y*i=0,说明在最优生产计划中第i种资源一定有剩余. 已知y*i为线性规划的对偶问题的最优解,如果y*i0,说明在最优生产计划中第i种资源已经完全耗尽.,判断:,若线性规划的原问题有无穷多最优解,则其 对偶问题也一定具有无穷多解. 根据对偶的性质,当原问题无界解时,其对偶问题无可行解,反之,当对偶问题无可行解,其原问题具有无界解