第五章 灵敏度分析1.ppt

第五章 线性规划问题的灵敏度分析 什么是灵敏度分析？ 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析（优化后分析）。 灵敏度分析研究内容： 目标函数系数的变化对最优解的影响； 约束方程右端系数的变化对最优解的影响； 约束方程组系数矩阵的变化对最优解的影响。 * 需要关注两个问题： 这些系数在什么范围内波动将不影响最优解或最优基？? 若最优解发生变化，应如何用最简单的方法找到新的最优解。 为讨论方便，以下列出标准型线性规划问题最优单纯形表的一般形式，其中B为线性规划问题的最优基： cj c1 c2 … cn cB cB b x1 x2 … xn cB1 xB1 B-1b B-1A=B-1(P1，P2，…，Pn) cB2 xB2 : : cBm xBm cj-zj c-cBB-1A 第一节 边际值及其应用 边际值 第i种资源的边际值是将一单位的第i行约束条件方程所代表的资源从现在用途中抽出来而使利润减少的数字，用qi表示。 将一单位的第i个约束条件方程所表示的资源从现在的用途抽出，意味着使第i个约束条件方程的松弛变量xn+i增加一个单位。xn+i增加一单位而损失利润 ，所以有qi =zn+i 单纯形表中第i种资源的边际值qi等于该表中第i行约束条件方程的松弛变量xn+i的机会费用。 为了生产一个单位的xj必须消耗aij个单位的第i行约束条件方程对应的资源i，及需将aij个单位的第i种资源从现有用途中抽出，此时损失的利润为aijqi，zj可直接用下式表示 机会费用zj 令x5,x6,x7分别为资源1，2，3的松弛变量，下表给出此问题的最优解。 在一定范围内，资源i增加1单位，利润增加qi，资源2增加1单位，利润增加1/4元，资源3增加一单位，利润增加1元，资源1增加1单位，利润不增加。 例1 增加新变量的灵敏度分析 增加一个新变量，相当于系数矩阵A增加一列，这种在现实的管理中经常发生，例如经过调查研究，获得某一种新产品的消耗系数和价格等参数，如何决定该产品是否值得投入生产。 设新增的变量为xN，它对应的价值系数为cN，消耗各种资源的单位消耗系数为ai,N,即在系数矩阵A中增加的系数列向量为PN=(a1,N, a2,N…, am,N)T,则把xN看成非基变量，在原来的最优单纯形表中增加一列，系数向量为 （ 5-1 ） 非基变量的技术系数的变化将会影响其最优性，则非基变量xN的检验数 （ 5-2 ） 若 则原问题最优解不变，说明增加这种新产品不能使原最优目标函数值得到改进，所以增加该新产品不利；反之， ，则原问题最优解变化，生产该新产品有利，其新的最优解可将式（ 5-2 ）加入原最优单纯形表继续迭代求解。 例2 建议增加一新产品，设产量为xN，PN=(5,4,3)T，cN=9，问该产品是否值得投产？ 已知a18=5, a28=4 a38=3, c8=9,由最优单纯形表知 q1=0, q2=1/4, q3=1. z8=5*0+4 *(?)+3*1=4 c8-z8=9-4=50 所以该产品值得生产。 * 第2节 价值系数 cj 的灵敏度分析 cj变动可能由于市场价格的波动，或生产成本的变动 cj的灵敏度分析是在保证最优解的基变量不变的情况下，分析cj 允许的变动范围?cj cj的变化会引起检验数的变化，有两种情况： 非基变量对应的价值系数变化，只影响 一个检验数 基变量对应的价值系数变化，影响所有非基变量检验数 1、非基变量xj的价值系数的灵敏度分析 若xj为非基变量，则cj的变化仅影响xj对应的检验数。当cj变化为cj +?cj 后，为使最优解基变量及其取值不变，xj对应的检验数满足 例3 设有以下线性规划问题: * 令x5,x6,x7分别为资源1，2，3的松弛变量，下表给出此问题的最优解 若超出稳定范围，非基变量　的检验数 ，当前解已不是最优解。此时必须以修改后的单纯形表出发，重新进行单纯形迭代，直至求出新的最优解。 * 2、基变量xj对应的价值系数的灵敏度分析 由于基变量xj对应的价值系数cj在cB中出现，它会影响所有非基变量的机会费用和检验数。 设xj为第r个约束方程对应的基变量，SN为非基变量下标的集合。 当cj变化为cj +?cj 时，则cB变化为cB+?cB,其中 非基变量xk的检验数应满足 * 其中xj为第r个约束条件对应的