灵敏度分析课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,一,、,灵敏度分析概述,Max f,=,CX,AX=b,X,0,系数矩阵,A,、约束条件右端项,b,和价值系数,C,给定以后，这个线性规划问题就确定了。,一、灵敏度分析概述 Max f=CX系数矩阵A、约,1,1.当这些系数中的一个或几个发生变化时，已求得的最优解,会有什么变化；,2.这些系数在什么范围内变化时，线性规划问题的最优解或,最优基不变；,3.若最优解变化，如何用最简便的方法找到新的最优解。,为了回答这些问题，可以在变化了的条件下重新求解线性规划问题。但是这样做太麻烦，也不必要。本节的目的是讲，,如何在已经得到的最优解的基础上，进行适当的修改计算，即可回答上面的问题。,这就是灵敏度分析的基本内容。,1.当这些系数中的一个或几个发生变化时，已求得的最优解,2,二、灵敏度分析的定义,灵敏度分析,就是研究,c,j,、,b,i,、,a,ij,等参数在什么范围内变化时最优解不变，若最优解发生变化，如何用简便的方法求出新的最优解。,二、灵敏度分析的定义灵敏度分析就是研究cj、bi、aij等参,3,三、灵敏度分析的内容,价值系数,c,j,的变化的分析,约束条件右端项,b,i,变化的分析,系数矩阵,A变化,的分析,系数列向量,P,k,变化的分析,增加新约束条件的分析,增加新变量的分析,三、灵敏度分析的内容价值系数cj的变化的分析,4,实例1,产品,资源,A,B,C,资源拥有量,原料甲,1,1,1,12kg,原料乙,1,2,2,20kg,利润,（元/kg）,5,8,6,实例1产品ABC资源拥有量原料甲11112kg原料乙1222,5,实例1的数学模型,设产品,A,、,B,、,C,的产量分别为,x,1,、x,2,、x,3,，,则该问题的数学模型为,：,实例1的数学模型设产品A、B、C 的产量分别为x1、x2、x,6,用单纯形法求解结果,用单纯形法求解结果,7,1.价值系数,c,j,变化,的分析,c,j,变动可能由于市场价格的波动，或生产成本的变动,。,c,j,的灵敏度分析是在保证最优解的基变量不变的情况下，分析,c,j,允许的变动范围。,c,j,的变化会引起检验数的变化，有两种情况,：,非基变量对应的价值系数变化，不影响其它检验数,基变量对应的价值系数变化，影响所有非基变量检验数,1.价值系数cj变化的分析cj 变动可能由于市场价格的波动，,8,1.1,非基变量 对应的价值系数,c,3,的变化,在实例1中，分析产品丙的利润,C,3,的,变化对最优解的影响,。,由上表可知：当,C,3,-8,0,，,即 0,C,3,8时，最优解不变。,5 8 6 0 0,5,8,C,3,C,3,-8,1.1非基变量 对应的价值系数c3的变化在实例1中，分析产,9,1.2,基变量对应价值系数变化,(1)基变量对应的价值系数,C,1,的,变化,5 8 6 0 0,5,8,C,1,C,1,-2 8-2C,1,C,1,-8 -(64+4C,1,),由上表可知：当 8,-2C,1,0,，,同时,C,1,-8,0，,即,4,C,1,8时，最优解不变。,1.2基变量对应价值系数变化(1)基变量对应的价值系数C1的,10,(2)基变量对应的价值系数,C,2,的,变化,5 8 6 0 0,5,8,C,2,C,2,6-C,2,C,2,-10,5-C,2,-(20+8C,2,),由上表可知：当 6,-C,2,0,，,C,2,-10,0，,同时,5-C,2,0，,即,6,C,2,10时，最优解不变。,(2)基变量对应的价值系数C2的变化5 8,11,价值系数,c,j,变化,的分析总结,c,j,的变化会引起检验数的变化，有两种情况,：,（1）非基变量对应的价值系数变化，不影响其它检验数,（2）基变量对应的价值系数变化，影响所有非基变量检,验数。,要使原来的最优解不变，新的检验数均,0,价值系数cj变化的分析总结cj 的变化会引起检验数的变化，有,12,2.约束条件右端项,b,i,变化,的分析(1),设,X,B,=,B,1,b,是最优解，则有,X,B,=,B,1,b,0,b,的变化不会影响检验数,b,的变化量,b,可能导致原最优解变为非基可行解,设,b,=,b,+,b,为保证最优基不变，必须满足,X,B,=,B,-,1,b,0,2.约束条件右端项bi变化的分析(1)设XB=B1b是最优,13,16,20,12,4,-92,1.分析,b,1,=16和,b,2,=20时，最优基和最优解的变化,16121.分析b1=16和b2=20时，最优基和最优解的,14,当,b,1,=16,b,2,=20时，,最优基不变，,最优解变为：,x,1,=12，,x,2,=4,结论,当b1=16,b2=20时，结论,15,22,20,24,-2,2.分析,b,1,=22和,b,2,=20时，最优基和最优解的变化,5,8,0,0,-104,22242.分析b1=22和b2=20时，最优基和最优解的,16,灵敏度分析课件,17,当,b,1,=22,b,2,=20时，,最优基改变，最优解变为：,x,1,=20，,x,4,=2,结论,当b1=22,b2=20时，结论,18,解之得,：,10,b,1,20,即:当10,b,1,20时，最优基不变,保持b,2,=20,分析,b,1,在什么范围内,变化时，最优基不变?,解之得：10b120即:当10b120时，最优基不变,19,b1,20,2b,1,-20,-b,1,+20,?,5,8,0,0,b12b1-2050,20,解之得,：,12,b,2,24,即:当12,b,2,24时，最优基不变,保持b,1,=12,分析,b,2,在什么范围内,变化时，最优基不变?,解之得：12b224即:当12b224时，最优基不变,21,12,b,2,24-b,2,-12+b,2,?,5,8,0,0,1224-b250,22,练习,最优单纯形表为：,求：,（1）b,1、,b,2,的值；,（2）对偶问题的最优解；,（3）表中f、g、h、d、e的值；,（4）在不破坏最优基的情况下，能否单独增加b,1、,b,2,来增加目标函数f的值，最多能增加到多少？,练习最优单纯形表为：求：,23,3.系数矩阵A变化的分析,系数矩阵,A变化,的分析,包括,系数列向量,P,k,变化的分析,增加新约束条件的分析,增加新变量的分析,3.系数矩阵A变化的分析系数矩阵A变化的分析包括,24,3.1,系数列向量,P,k,变化的,分析,在初始单纯形表上，变量,x,k,的系数列向量,P,k,变为,P,k,，经过迭代后，在最终单纯形表上，,x,k,是非基变量。这时最终单纯形表上,x,k,的系数列就变成,B,-1,P,k,。新的判别数为,若,，,原最优解不变,；,若,，,则最优解改变，继续迭代可以求出新的最优解。,3.1系数列向量Pk变化的分析在初始单纯形表上，变量xk的系,25,实例1,产品,资源,A,B,C,资源拥有量,原料甲,1,1,1,12kg,原料乙,1,2,2,20kg,利润,（元/kg）,5,8,6,实例1产品ABC资源拥有量原料甲11112kg原料乙1222,26,在实例1中，假设产品,C,的资源消耗量由 变为 ，试分析最优解的变化情况。,所有的判别数都非正，故最优解不变,。,2,1,3,-1,5 8 6 0 0,5,8,-1,在实例1中，假设产品C 的资源消耗量由 变为 ，,27,在实例1中，假设产品,C,的资源消耗量由 变为 ，试分析最优解的变化情况。,判别数有正，故最优解变化,。,1,1,1,0,5 8 6 0 0,5,8,1,初始表,最优表,在实例1中，假设产品C 的资源消耗量由 变为 ，,28,最优单纯形表如下：,最优单纯形表如下：,29,3.2,增加新约束条件的分析,产品,资源,A,B,C,资源拥有量,原料甲,1,1,1,12kg,原料乙,1,2,2,20kg,原料丙,1,2,2,18kg,利润,（元/kg）,5,8,6,3.2 增加新约束条件的分析产品ABC资源拥有量原料甲111,30,用单纯形法求解结果,用单纯形法求解结果,31,将原最优解,x,1,=4，,x,2,=8,代入上式知，原最优解不满足该约,束条件，因而原最优解不再是增加约束条件以后的最优解。,这个问题相当于在原问题的基础上增加约束条件,在新的约束条件中引入松驰变量,x,6,，,则有,将该条件填入最优单纯形表中,：,将原最优解x1=4，x2=8代入上式知，原最优解不满足该约,32,将该单纯形表标准化,：,将 填入最优单纯形表中,1 2 2 0 0 1 18,0,0,0,将该单纯形表标准化：将,33,用对偶单纯形方法迭代一次得,：,增加约束条件以后的最优解为：,x,1,=6，,x,2,=6,用对偶单纯形方法迭代一次得：增加约束条件以后的最优解为：x1,34,增加新约束条件的分析总结,1,、将最优解代入新的约束条件，若满足，则最优解不变。,2、若不满足，则当前最优解要发生变化；将新增约束条,件加入最优单纯形表，并变换为标准型。,3、利用对偶单纯形法继续迭代。,为什么可以利用对偶单纯形法?,增加新约束条件的分析总结1、将最优解代入新的约束条件，若满足,35,3.3增加新的决策变量的分析,假如要增加一个新的决策变量,x,n,+,1,，,其对应的系数列向量为,P,n+1,，,价值系数为,c,n,+1,。,在原最优单纯形表中,x,n,+1,对应的检验数为,若,，,则原最优解不变,。,从经济学的观点来看，增加该项活动（或产品）是不利的。,若,，,则原来的最优解不再是最优解,，,表明增加该活动是有利的,。,这时把,x,n,+,1,对应于原最优基,B,的系数列向量,加入到原最优表中，并以,x,n,+,1,作为换入变量按单纯形法进行迭代，即可得到新的最优解。,3.3增加新的决策变量的分析假如要增加一个新的决策变量xn+,36,产品,资源,A,B,C,D,资源拥,有量,原料甲,1,1,1,2,12kg,原料乙,1,2,2,1,20kg,利润,（元/kg）,5,8,6,8,在实例1中，如果该厂还计划生产一种,新产品,D,，问生产产品,D,是否有利,？,产品ABCD资源拥原料甲111212kg原料乙122120k,37,用单纯形法求解结果,初始表,原最优表变成,5 8 6 0 0 8,5,8,3,-1,1,用单纯形法求解结果初始表原最优表变成 5 8,38,新的最优解为,X=(0 28/3 0 0 0 4/3),T,继续迭代，找到新的最优解,新的最优解为X=(0 28/3 0 0 0,39,课后习题36(1、2),最优单纯形表：,3 1 4 0 0,0,4,C,1,C,1,-24/5,课后习题36(1、2)最优单纯形表：3,40,课后习题36(3),最优单纯形表：,3 1 4 0 0 3,0,4,6,2/5,7/5,课后习题36(3)最优单纯形表：3 1,41,课后习题37,最优单纯形表,：,10 6 4 0 0 0,6,10,0,C,3,C3-20/3,课后习题37最优单纯形表：10 6,42,课后习题37（续）,最优单纯形表,：,10 6 4 0 0 0,6,10,0,25/3,5/3,课后习题37（续）最优单纯形表：10 6,43,课后习题37(续）,10 6 4 0 0 0,6,10,0,0 x,7,O 0 -1 0 0 0 1 -10,X,7,0,0,0,0,课后习题37(续）10 6 4,44,课后习题37(续）,10 6 4 0 0 0 0,6,10,0,4,课后习题37(续）10 6 4,45,作业,线性规划问题,maxf=2X,1,+3X,2,+X,3,X,1,+X,2,+X,3,3,X,1,+3X,2,+5X,3,7,X,1,，X,2,X,2,0,（1）用单纯形方法求出最优解和最优目标函数值；,（2）写出上述问题的对偶问题，并求对偶规划的最优解和最优目标函数值；,（3）保持X,1,的系数C,1,=2，X,3,的系数C,3,=1不变，确定X,2,的,系数C,2,的变化范围，使原最优解保持最优；,（4）求出要使原来的最优基不变的b,1,的变化范围，,（5）若b,1,3，b,2,=11，求出新的最优解。,作业线性规划问题,46,