灵敏度分析教学课件PPT.ppt

2.3 灵敏度分析 一、灵敏度分析的含义和内容 1、什麽是灵敏度分析？ 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析（或优化后分析）。,2、灵敏度分析的内容： 目标函数的系数变化对最优解的影响； 约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响 ；,回答两个问题：,这些系数在什麽范围内发生变化时，最优基不变（即最优解或最优解结构不变）？ 系数变化超出上述范围时，如何用最简便的方法求出新的最优解？,二、 手工进行灵敏度分析的基本原则 1、在最优表格的基础上进行； 2、尽量减少附加计算工作量；,三、 灵敏度分析举例： 研究例1-7,引入非负的松弛变量x4,x5, 将该lp化为 标准型：,用表格单纯形法求解如下：,1、研究最优表格中的数据来源： （1）如果选b=（p1，p2）为初始可行基，能否从表格中直接看出b-1？,（2） =？,舍弃中间计算过程， 只考察初始表和最终表：,=（-1，-5/3，-1/3）,2、价值系数c发生变化的情况： （1）当cj是非基变量的价值系数它的变化只影响 一个检验数。为什麽？,例：c3发生变化时， =c3-z3=c3-2（-1）+32=c3-40，,令,得c34。即当c34时，最优解不变；,否则 0,可使用原始单纯形法继续迭代求出新的最优解。,（2）当cj是基变量的价值系数它的变化将影响所有非基变量的检验数，为什麽？,解这n-m个不等式，可算出保持最优解不变时cj的变化范围 ！,例：当c1发生变化时，仍用c1代表x1的价值系数（看成待定参数），原最优表格即为：,令所有检验数小于0，得不等式组：,解该不等式组得：,说明当 时，最优解不变。,3、右端常数b发生变化： 当bi发生变化时，将影响所有基变量的取值。为什麽？,因为：,若bi的变化,保持b-1b0,当前的基仍为最优基，最优解的结构不变（取值改变）； （b-1b）i0,当前基为非可行基,但是仍保持为对偶可行基,(为什麽?),可用对偶单纯形法求出新的最优解； 如何求出保持最优基不变的bi的范围? 把bi看作待定参数,令b-1b0,求解该不等式组即可；,仍然来看上例的最优表格：,原b1=3，现用待定参数b1代替3，则最优表中的解答列应为：,若b1的变化超出这个范围，则解答列中至少有一个元素小于0，可用对偶单纯形法迭代求出新的最优解。,4、系数阵a的元素发生变化： （1）增加1个新变量：相当于系数阵a增加1列,如开发出一种新产品，已知其有关工艺参数（或消耗的资源量）和单位产品利润，设该种产品的产量为xk，则ck和pk已知，需要进行“是否投产”的决策。,如例中欲增加产品d，单件利润为c6=5千元，工时消耗与材料消耗为,相当于在原始表中增加1列p6，则在最优表中p6应变成,相应的检验数：,在此基础上继续迭代，直至求出最优解：,说明新产品d应于投产，新的生产计划为x*=(0,9/5,0,0,0,3/5)t,即生产b产品5/9吨,生产d产品3/5吨,两种资源全部用完,可得到最大利润为8.4 (千元) ( 42/5=8.4)。 如果算出的60,说明新产品d不宜投产，否则会使产品总利润下降！,(2) 增加1个约束条件： 相当于系数阵a增加1行,首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论： 将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）； 进行规格化处理用矩阵的行变换将当前基变成单位阵；,用适当方法（通常是对偶单纯形法）进行迭代求出新的最优解。,如在上例中增加约束：2x1+2x2+x35,当前最优解x1=1,x2=2,x3=0不满足该约束，将约束条件标准化后加入原最优表格，进行规