管理运筹学灵敏度分析.ppt

,SensitivityAnalysis,第三节对偶与灵敏度分析,第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，minz=-46/3,得到最终单纯形表：,（2）基变量在目标函数中系数的灵敏度分析,例2：,在下面线性规划问题中，分析c1在什么范围内变化时，原问题的最优基不变。,首先得到以上问题的最优单纯形表：,当c1=c1+时，相应的单纯形表为：,为了表中解为最优，应有，,1/4+/40，1/2-/20,因此-11，即当1c13时，最优基保持不变。当c1的变化超出以上范围时，至少会使一个检验数zj-cj0，这种产品的机会成本和利润必定相等即因而互补松弛条件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,对偶关系