管理运筹学026灵敏度分析课件.pptx

,Sensitivity Analysis,第三节 对偶与灵敏度分析,第3节 对偶与灵敏度分析,2,一、 线性规划的对偶关系二、 线性规划的对偶性质三、灵敏度分析四、对偶关系的经济解释,第3节 对偶与灵敏度分析,灵敏度分析,以前讨论线性规划问题时，假定ij，bi,cj都是常数。但实际上这些系数往往是估计值和预测值。如市场条件一变，cj值就会变化；ij往往是因工艺条件的改变而改变；bi是根据资源投入后的经济效果决定的一种决策选择。显然，当线性规划问题中某一个或几个系数发生变化后，原来已得结果一般会发生变化。因此，所谓灵敏度分析，是指当线性规划问题中的参数发生变化后，引起最优解如何改变的分析。,灵敏度分析,灵敏度分析是要在求得最优解以后，解决以下几方面的问题：（1）线性规划问题中的各系数在什么范围内变化，不会影响已获得的最优基。（2）如果系数的变化超过以上范围，如何在原来最优解的基础上求得新的最优解。（3）当线性规划问题增加一个新的变量或新的约束，如何在原来最优解的基础上获得新的最优解。,1.目标函数系数C的变化范围,目标函数系数变化，只会影响最优解中检验数行，不会影响基变量的取值。即C中元素的变化只会影响最优解的对偶可行性而不会影响原始可行性。,（1）非基变量在目标函数中系数的灵敏度分析,m个基变量xBr（r=1,2,m）在目标函数中的系数为：,n-m个非基变量xj在目标函数中的系数为：,因此，当非基变量xk的系数ck 变化成为ck=ck+ 时，基变量的检验数仍为0。在最优解中只会影响这个非基变量XK的检验数，其他非基变量的检验数不会变化。,针对目标函数极大化的线性规划问题：如果变化后的xk的检验数仍然为非负，则原来的最优基仍保持为最优基。如果变化后的xk的检验数为负数，则原来的最优基不再是最优基，新的最优基可以通过将xk进基，并进行后续的单纯形迭代，得到新的最优基和最优解。,目标函数,约束条件：,求c2在什么范围内变化，原来的最优基保持不变；当c2=-3时，最优基是否变化，如果变化，求新的最优基和最优解。,线性规划问题例题,例1,首先用单纯形法得到原问题的最优单纯形表，,由于x2在最优单纯形表中是非基变量，因此只影响它本身的检验数,得到,由于最优解XB=B-1b以及最优解的目标函数值z=CBB-1b与非基变量在目标函数中的系数CN无关，其他变量在目标函数中的系数都不变。x2在目标函数中的系数从原来的值1减少到 -2时，最优基保持不变。相应的单纯形表如下：,当c2=-3时，已经超出保持最优基不变的范围，因此单纯形表不再是最优单纯形表。将c2=-3代入单纯形表，得到以下单纯形表：,x2进基,X5离基,得到新的最优解：x1=8/3，x2=10/3，x3=0，x4=0，x5=0，min z=-46/3,得到最终单纯形表：,（2）基变量在目标函数中系数的灵敏度分析,例2：,在下面线性规划问题中，分析c1在什么范围内变化时，原问题的最优基不变。,首先得到以上问题的最优单纯形表：,当c1=c1+时，相应的单纯形表为：,为了表中解为最优，应有，,1/4+/40 ，1/2-/20,因此 -11，即当1c13时，最优基保持不变。当c1的变化超出以上范围时，至少会使一个检验数zj-cj0，用单纯形法继续运行，就可以得到新的最优基和最优解。,2、常数项的灵敏度分析,当右边常数向量b发生变化，成为b时，对变量的检验数,没有影响，而单纯形表中的右边常数将变成,。,即右边常数向量的变化只会影响最优基的原始可行性而不会影响其对偶可行性。,当变化以后的,原来的最优基仍为最优基，否则，原来的基成为对偶可行基但不是原始可行基，这时要用对偶单纯形法求得新的最优基。,例3,对以下线性规划问题中第一个约束右边常数b1=9进行灵敏度分析。,先求得最优单纯形表：,由于初始单纯形表中，约束矩阵中松弛变量x4，x5，x6的系数构成一个单位矩阵，因此最优单纯形表中松弛变量在约束矩阵中的系数就是最优基的逆矩阵。即,当b1=b1+=9+时，最后一张单纯形表中的右边常数将成为,这时，最后单纯形表中目标函数的值也将发生变化，成为：,单纯形表成为:,由此可以看出，当第一个约束的右边常数b1变化时，新的单纯形表的RHS列就是原来最优单纯形表的RHS列加上第一个松弛变量x4在原来单纯形表中对应的列与的乘积。,根据这个规则，容易得到第二个约束的右边常数b2=2变为b2=2+时的单纯形表：,以及第三个约束的右边常数b3=4变为b3=4+时的单纯形表：,这样就可以分别求出在保持原来最优基原始可行性条件下，b1=9，b2=2，b3=4的变化范围。,对于b1=9+，由第一张单纯形表约束条件的原始可行条件可以得到，当,，推出,即-1，b1=b1+8时，原来的最优基仍为原始可行基。,当b1的变化超过以上范围，例如b1=7，即=b1-b1=7-9=-2时，单纯形表成为：,x6进基,X1离基,得到新的最优解为：（x1,x2,x3,x4,x5,x6）=（0,0,7/2,0,11/2,1/2）max z=14。,3、增加一个新的变量,当前最优基是B。设新增加的变量xj在目标函数中的系数为cj，在约束中的系数向量是aj，计算,，,在原单纯形表中增加一个新的变量以及新的一列，将以上系数置于原单纯形表中，构成新的单纯形表。若新变量的检验数zj-cj0，则原来的基仍为最优基，原来的基变量以及基变量的值保持不变，新的变量xj=0是非基变量。否则xj进基，用单纯形法继续运行，直至获得新的最优基和最优解。,在上面的线性规划模型中，增加一个新的变量x6，它在目标函数中的系数c6=1，在约束条件中的系数向量为,，求新的最优基和最优解。,例4,列出原问题的最优单纯形表：,从中可以看出，,新的单纯形表为：,x6进基x5离基，得到下一个单纯形表:,得到新的最优解为:,(x1,x2,x3,x4,x5,x6)T=（16,0,0,0,0,10）T，max z=42。,4、增加一个新的约束,增加一个新的约束以后，如果原来的最优解满足新的约束，则原来的最优解仍是新问题的最优解，否则，最优解将发生变化。,例5,最优单纯形表为:,现在，增加一个约束-x1+2x32，试分析最优解的变化。,先将原问题最优解变量值代入，因有-6+20=-6 2 故将约束条件写成：-x1+2x3-x6=2两边同乘以-1，得到x1-2x3+x6=-2并取x6作为新的基变量，得到新的单纯形表：,X6离基,消去x1在第三个约束中的系数，使得基变量x1在约束条件中的系数成为单位向量：,用对偶单纯形法继续求解：,x3进基,新的最优解为（x1,x2,x3,x4,x5,x6）T=（10/3,0,8/3,0,22/3,0）T，max z=28/3。,如果新增加的约束是等号约束，则需要在这个约束中增加一个人工变量作为新的基变量，然后用两阶段法求得新的最优解.,5、矩阵中系数的灵敏度分析,A矩阵中元素的变化情况比较复杂，如果这个元素不包含在最优基B中，它的变化只会影响这个非基变量的检验数,如果这个元素包含在最优基B中，它的变化不仅会影响这个所有变量的检验数,而且同时会影响最优解的右边常数,在上面线性规划问题中，分析变量x2在第一个约束中的系数a12=1在什么范围内变化时原问题的最优基不变。,这个问题的最优单纯形表如表：,例6,设a12=a12+,则,即当,-4,或,a12-3,时，原问题的最优基保持不变。,对于上面的线性规划问题，已经得到它的最优单纯形表为：,例7,时，,其中x1是基变量，当x1在约束条件中的系数向量,变为,求新的最优解。,引进一个新的变量x1，它在目标函数中的系数与x1的系数相同为2，在约束中的系数向量为,。,对于x1，计算它在目标函数中的系数,以及x1在约束矩阵中的列向量,在原最优单纯形表中增加新的变量x1：,用x1替代x1，将x1的列向量变换为单位列向量，在单纯形表中删除x1及所在列：,注意到此处既不适于单纯形法，也不适用于对偶单纯形法。,运用矩阵行变换，x3进基，x5离基，得到,用单纯形法继续迭代,得到新的最优解为（x1,x2,x3,x4,x5）T=（2/3,0,4,0,0）T，max z=6。,4.对偶关系的经济解释,例题2-20从企业制定生产计划和出售资源的两个角度建模分析。当原问题和对偶问题都取得最优解时：对偶变量yi的意义代表对一个单位的第i种资源的估价，为区别资源的市场价格，称yi为影子价格。,最大利润问题以及对偶问题的经济解释,最大利润问题以及对偶问题的经济解释,各种设备能力的边际利润率的计算方法为因此，对偶问题最优解中对偶变量yi的值就是相应设备的能力对总利润的边际贡献。yi越大，表明相应的设备能力增加一个单位，引起总利润的增加越大，也就是说，相对于最优生产计划来说，这种设备能力比较紧缺；yi较小，表明设备能力相对不紧缺；yi=0，说明在最优生产计划下第i种设备能力有剩余。,互补松弛条件的经济解释,若在最优生产计划下，第i种设备的能力大于这种设备实际耗用，即或者说第i种设备能力有剩余，这种设备的微小增加对利润没有影响，按边际贡献的概念，有满足互补松弛条件xn+iyi=0,互补松弛条件的经济解释,若yi0可以断定这种设备能力没有剩余，即 也就是xn+i=0，从而同样满足互补松弛条件xn+iyi=0。,对偶问题约束的左边 表示生产每单位j产品（j=1,2,n）所耗用的各种设备能力应能产生的利润，称为j种产品的机会成本。若某种产品的机会成本高于这种产品的利润，即,互补松弛条件的经济解释,则在最优解中这种产品一定不会安排生产，即xj=0，从而满足互补松弛条件xjym+j=0如果在最优解中第j种产品投入生产，即xj0，这种产品的机会成本和利润必定相等即因而互补松弛条件xjym+j=0成立。,弱对偶性的经济解释,对于最大利润问题，由弱对偶性可知CXYAXYb左边：是由于某些产品的利润率和机会成本不相等引起的，即CYA。当取得最优解时，由于互补松弛条件的作用，凡机会成本和利润率不相等的产品都将不安排生产，因而使得不等式成为等式。右边：是由于某些设备的实际耗用小于设备的实际能力引起的，即AXb同样由于互补松弛条件，实际耗用和能力不等的这些设备，影子价格都等于零，从而使右边的不等式也成为等式。当原始和对偶问题都取得最优解时CX=YAX=Yb,对偶关系的经济解释案例,例2-34 生产计划问题某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如表2-1所示，试用线性规划制订使总利润最大的生产计划。,对偶关系的经济解释案例,设变量xi为第i种产品的生产件数（i1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。,分析最优解中利润率最高的产品丙不安排生产的原因：求解该问题的对偶问题得到三种设备的影子价格分别为：y1=1.9535，y2=0.2423，y3=1.3792这说明三种设备在最优生产计划下，能力都没有剩余，并且第一种设备能力最为紧缺。,对偶关系的经济解释案例,分别计算四种产品的机会成本，得到：产品甲： 1.5y1+1.0y2+1.5y3=5.24=C1产品乙：7.30=C2产品丙：9.75C3产品丁：4.18=C4,对偶关系的经济解释案例,例2-35设利润最大问题如表所示：,对偶关系的经济解释案例,利润最大问题的线性规划模型为,对偶关系的经济解释案例,引入的松弛变量表示资源的剩余量，即设备未消耗的工时数。求得以上问题的最优生产计划为：x1=4（件），x2=2（件） ，最大利润z=14（千元），A、B、C、D四种设备的剩余工时数：x3=0, x4=0，x5=0，x6=4,对偶关系的经济解释案例,由对偶问题进一步分析,由此可以清楚地看出，资源剩余量和影子价格之间以及“机会成本利润率”和产品产量之间的互补松弛关系（表中箭头表示“一个变量大于零，导致另一个变量等于零”的互补松弛关系）。,对偶关系的经济解释案例,