运筹学课件第五节灵敏度分析.ppt

第五节 灵敏度分析 一、灵敏度分析的含义和内容 1、灵敏度分析：对系统或事物因周围条件变化显示出来的敏感程度。 研究线性规划模型某些参数或限制量的变化对最优解的影响称为灵敏度分析。,2、灵敏度分析的内容： 目标函数的系数变化对最优解的影响； 约束方程右端系数变化对最优解的影响； 约束方程组系数阵变化对最优解的影响 ；,回答两个问题：,这些系数在什么范围内发生变化时，最优基不变（即最优解或最优解结构不变）？ 系数变化超出上述范围时，如何用最简便的方法求出新的最优解？,二、 进行灵敏度分析的基本原则 1、在最优单纯形表的基础上进行； 2、尽量减少附加计算工作量；,3、灵敏度分析的步骤：,（1）将参数的改变通过计算反映到单纯形表。,参数aij,bi,cj的变化引起的单纯形表上的有关数字的变化：,（2）、检查原问题是否仍为可行解。,（3）、检查对偶问题是否仍为可行解。,三、 灵敏度分析举例： 例1-1,引入非负的松弛变量x3, x4,x5, 将该LP化为 标准型：,用单纯形法求解如下：,1、价值系数Cj变化 （1）当cj是非基变量的价值系数它的变化只影响 一个检验数。,例：c4发生变化时， ，最优解不变 否则 0,可使用原单纯形法继续迭代求出新的最优解。,（2）当cj是基变量的价值系数它的变化将影响所有非基变量的检验数.,例1-1:(1)如果产品1的利润降至1.5元/件，产品2的利润增加至2元/件，工厂的最优生产计划？ （2）如果产品1的利润不变，则产品的利润在什么范围内变化，工厂的最优生产计划不变？,解（1）将产品1，2的利润变化直接反映到单纯形表,随利润的变化，调整如下： 生产产品1为2件，产品2为3件。,解（2）设产品2的利润1+ 直接反映到单纯形表,2、分析bi（右端常数）变化： 当bi发生变化时，将影响所有基变量的取值。,因为：,若bi的变化,保持B-1b0,当前的基仍为最优基，最优解的结构不变（取值改变）； （B-1b）0,当前基为非可行基,但是仍保持为对偶可行基, 可用对偶单纯形法求出新的最优解；,仍然来看例1-1： （1）如果设备A和调试工序的每天的能力不变，设备B每天的能力增加到32h，分析公司最优的生产计划的变化； （2）如果设备A和设备B每天的能力不变，则调试工序在什么范围内变化，问题的最优基不变。,将其反映到最终的单纯形表，原问题非可行解，采用dual单纯形法,工厂的最优生产计划改为只生产产品1，每天的生产数量5件。,当b0问题的最优基不变， 解得： 所以调试能力在46h,3、增加一个变量xj的分析,如果该厂计划推出新产品3，生产一件所需要设备A,B 以及调试工序的时间分别是3h,4h,2h，该产品的预期利润3元/件，分析该种产品是否值得投产？如投产，对该公司的最优生产计划有何改变？,解：设该厂生产新产品3为x6件，C=3,P6=(3,4,2)T,检验数大于0，继续迭代计算,新的最优生产计划为每天生产1产品：7/2件 生产2产品：0件；生产3产品：3/4件。,4、分析参数 aij的变化 参数 aij的变化导致系数阵A的元素发生变化。相当于增加1个新变量（系数阵A增加1列），如果 xj在最终单纯形表中为基变量，则aij的变化会使相应的B ,B-1发生变化，有可能出现原问题与对偶问题无可行解的情况。引进人工变量，使用单纯形法计算。,如果该厂生产的产品2，生产一件所需要设备A,B 以及调试工序的时间分别变为8h,4h,1h，该产品的利润变为3元/件，对该公司的最优生产计划有何改变？,解：将改变的产品看作是一件新的产品，生产量X2,将其反映到单纯形表,删除X2所在列,原问题与对偶问题均为非可行解，先使原问题转化为可行解 第一行的约束：x3+4x4-24x5=-9,乘以（-1），加上人工变量 -x3-4x4+24x5 +x6 =9,对偶问题为非可行解，单纯形法继续计算,最优生产计划每天生产1产品11/4件； 新产品15/8件。,5、 增加1个约束条件： 相当于系数阵A增加1行,首先将原最优解代入新增约束检查是否满足？是，则说明新增约束不影响最优解。否则再作下面的讨论： 将新增约束标准化，添加到原最优表格中（相当于约束矩阵新增1行）； 用矩阵的初等行变换将当前基变成单位阵；,进行迭代求出新的最优解。,设产品1，2经过调试后，必须增加环境调试工序，1产品每件须环境调试3h， 2产品每件须环境调试2h，环境调试可用能力12h，分析增加工序后的最优生产计划。 增加约束：3x1+2x212,当前最优解x1=7/2,x2=3/2代入约束条件3 (7/2)+2 (3/2)=27/212，不满足该约束，所以原问题的最优解不是现在LP的最优解；将约束条件标准化后加入原最优表格， 3x1+x2 +x6 =12，进行初等行变换，然后用对偶单纯形法迭代求出新的最优解。,X1,x2列非单位向量,r2x(-3)+r4 r3x(-1)+r4,对偶问题为可行解，原问题为非可行解，采用对偶单纯形法计算。,添加试验工序后，最优的生产计划仅生产1产品4件。,小结： 1、线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析。 2、分析价值系数Cj的变化、bi（右端常数）变化、增