第四节灵敏度分析优化后分析.ppt

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