【教学课件】第四节灵敏度分析(优化后分析).ppt

第四节第四节 灵敏度分析（优化后分析）灵敏度分析（优化后分析）一、参数的可变性一、参数的可变性 (cj,bi,aij)二、灵敏度分析的内容二、灵敏度分析的内容1、参数的变化对原最优解有什么影响？原最优解是否、参数的变化对原最优解有什么影响？原最优解是否 仍为最优解。仍为最优解。2、参数在什么范围变化时，原最优解保持不变？、参数在什么范围变化时，原最优解保持不变？3、当原最优解已不再最优时，应如何利用原单纯形表，、当原最优解已不再最优时，应如何利用原单纯形表，以最简捷的方法求得新的最优解。以最简捷的方法求得新的最优解。三、最优性分析三、最优性分析一、价值系数向量一、价值系数向量c的变化的变化设设(L)的最优解为的最优解为xB=B-1b,xN=0,fmin=cBB-1b1、非基变量、非基变量xk的系数的系数ck改变为改变为ck考虑检验数：考虑检验数：zj-cj=cBB-1Pj-cj j为非基变量下标为非基变量下标 在原单纯形表中将在原单纯形表中将zk-ck换成换成zk-ck,然后在然后在原表中用单纯性法求新问题的解。原表中用单纯性法求新问题的解。2、基变量、基变量xr的系数的系数cr改变为改变为cr=cr+crcr变为变为cr 后，只要把原单纯形表中后，只要把原单纯形表中xr所在的行乘以所在的行乘以(cr-cr)加到加到判别数行，并使判别数行，并使xr对应的判别数为对应的判别数为0，既可用单纯形法继续做下去。，既可用单纯形法继续做下去。引入松弛变量引入松弛变量x4，得它的最优单纯形表为，得它的最优单纯形表为x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-81.c3由由1变为变为-3时时x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-8由于由于z3-c3=cBB-1P3-c3=z3-c3+(c3-c3)=-3+(1+3)=1x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 1 0414-81 1 1 03 -2 0 1-4 -1 0 0 x3x446-12问题：问题：c3在什么范围变化时，最优解不变？在什么范围变化时，最优解不变？若要保持最优性不变若要保持最优性不变一般情况：一般情况：2.c2由由-2变为变为3,此时此时 c2=3-(-2)=5x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3 0 -3 0414-8x1 x2 x3 x4x2x41 1 1 05 0 2 1 -3+5 0 -3+5 0414-8+201 1 1 03 -2 0 10 -2 0 0 x3x4464问题：问题：c2在什么范围变化时，最优解不变？在什么范围变化时，最优解不变？二、改变右端向量二、改变右端向量b设设bb,设改变前的最优基为设改变前的最优基为B。二、改变右端向量二、改变右端向量b设设bb,设改变前的最优基为设改变前的最优基为B。例：某工厂在计划期内要安排生产两种产品，已知生产例：某工厂在计划期内要安排生产两种产品，已知生产单位产品所需的设备台时及单位产品所需的设备台时及A、B两种原材料的消耗为：两种原材料的消耗为：产品产品1 产品产品2设备设备原材料原材料A原材料原材料B1 24 00 48台时台时16kg12kg该工厂每生产一件产品该工厂每生产一件产品1可获利可获利2元，每生产一件产品元，每生产一件产品2可获利可获利3元，问应如何安排计划，使该工厂获利最多？元，问应如何安排计划，使该工厂获利最多？最优表为：最优表为：x1 x2 x3 x4 x5x1x5x21 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 -3/2 -1/8 0442-14x1 x2 x3 x4 x5x1x5x21 2 1 0 04 0 0 1 00 4 0 0 12 3 0 0 0816120若该厂又从别处抽出若该厂又从别处抽出4台时用于生产产品台时用于生产产品1和和2，求这时该厂生产产品求这时该厂生产产品1和和2的最优方案。的最优方案。x1 x2 x3 x4 x5x1x5x21 0 0 1/4 00 0 -2 1/2 10 1 1/2 -1/8 00 0 -3/2 -1/8 04-44-20 x1x3x21 0 0 1/4 00 0 1 -1/4 -1/20 1 0 0 1/40 0 -1/2 -3/4 0423-17-2问题：问题：b1在什么范围变化时，最优基不变？在什么范围变化时，最优基不变？3、一般情况、一般情况三改变约束矩阵三改变约束矩阵A1.非基列非基列PjPj，影响，影响yj=B-1 1Pj及及zj-cj最优表为：最优表为：x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8x1 x2 x3 x41 1 1 03 -2 0 10 3 0 0 x3x4464x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8所以，最优基、最优解保持不变。所以，最优基、最优解保持不变。x1 x2 x3 x41 1 1 03 -2 0 10 3 0 0 x3x4464x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8x1 x2 x3 x4-2 1 1 0-3 0 2 13 0 -3 0 x2x4414-8无界！无界！一般的，当非基列一般的，当非基列PjPj，若若zj-cj0，则原最优解也是新问题的最优解。，则原最优解也是新问题的最优解。若若zj-cj 0，则把，则把yjyj,zj-cj zj-cj 迭代。迭代。2.基列基列PjPj重新计算重新计算四增加新的约束四增加新的约束增加新的约束：增加新的约束：1.若原最优解满足新增加的约束，则它也是若原最优解满足新增加的约束，则它也是2.新问题的最优解。新问题的最优解。2.若原最优解不满足新增加约束若原最优解不满足新增加约束设原问题最优基为设原问题最优基为B，则有，则有xB xN xn+1I B-1N 00 cBB-1N-cN 0B-1bbm+1cBB-1bxB xN xn+1I B-1N 00 cBB-1N-cN 0引入松弛变量引入松弛变量x4，得最优表，得最优表x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8增加新约束：增加新约束：x1 x2 x3 x41 1 1 05 0 2 1-3 0 -3 0 x2x4414-8引入松弛变量引入松弛变量x5x1 x2 x3 x4 x51 1 1 0 05 0 2 1 0-3 0 -3 0 0 x2x4x5414-2-8-1 1 2 0 11 1 1 0 05 0 2 1 0-3 0 -3 0 0 x2x4x5414-6-8-2 0 2 0 10 1 3/2 0 1/20 0 9/2 1 5/2-3 0 -3 0 0 x2x4x11-1311 0 -1/2 0 -1/2无可行解！无可行解！-2有两个有两个LP问题如下：问题如下：分析分析LP1与与LP2最优解之间的关系。最优解之间的关系。