024灵敏度分析.ppt

2 4灵敏度分析 因此就会提出以下问题 1 当参数中的一个或者几个发生变化时 导致决策变量的最优解X的变化情况 2 参数在什么范围内变化时 最优解 最优基 不会发生变化 这就是线性规划的灵敏度分析所要研究解决的问题 一 问题简介 以前讲的线性规划问题中 都假定问题中的A b C是已知常数 但实际上这些数往往是一些估计和预测的数字 如市场条件一变C值就会变化 A是随工艺技术条件的改变而改变 而b值则是根据资源投入后能产生多大经济效果来决定的一种决策选择 灵敏度分析的含义是指对系统或事物因周围条件变化显示出来的敏感程度的分析 灵敏度分析 Sensitivityanalysis 又称为优化后分析 Postoptimalityanalysis 因为它是在已求得线性规划最优解的基础上 来讨论这些数据的变化对最优解的影响 一企业计划生产甲 乙两种产品 资源如下 设备总机时 18小时原料A 4吨 原料B 12吨 生产甲产品 3万元 1吨A 3机时 吨 乙产品 5万元 2吨B 2机时 吨 问 如何安排生产可以使得获利最大 结论 目标系数C 3 5 的变动 实际上就是目标直线Z 3x1 5x2的斜率k 3 5的变动 从图示可以看出 只要目标直线的斜率在一定范围内变动 问题的最优解就不会改变 但是最优值会变化 约束条件的资源系数b的变动 将造成规划可行域边界的平移 进而对最优解产生影响 约束条件的资源消耗系数A的变动 将造成规划可行域边界斜率的变化 这个对最优解的影响将更加复杂 当然 当线性规划问题中的一个或几个参数变化时 可以用单纯形法从头计算 看最优解有无变化 但这样做既麻烦又没有必要 因为前面已经讲到 单纯形法的迭代计算是从一组基变量变换为另一组基变量 表中每步迭代得到的数字只随基变量的不同选择而改变 因此有可能把个别参数的变化直接在计算得到最优解的最终单纯形表上反映出来 这样就不需要从头计算 而直接对计算得到最优解的单纯形表进行审查 看一些数字变化后 是否仍满足最优解的条件 如果不满足的话 再从这个表开始进行迭代计算 求得最优解 1 将参数的改变计算反映到最终单纯形表上来 2 检查原问题是否仍为可行解 3 检查对偶问题是否仍为可行解 4 按下表所列情况得出结论和决定继续计算的步骤 灵敏度分析的步骤可归纳如下 二 灵敏度分析 1 价值系数cj的灵敏度分析 从上面的典式的推导可以看出 目标函数的价值系数cj的改变仅仅影响到检验数和最优值 非基变量的价值系数cj的灵敏度分析 设cj有变化量 cj 则记 因此求出对检验数的影响 如果要求最优解保持不变 即 结论 例 基变量的价值系数cj的灵敏度分析 设xi是基变量 ci是CB的一个分量 当ci发生变化产生 ci时 则多个检验数都会受到影响 其中 可以得到 为了不破坏最优基的情况 即要求 当aij 0时 当aij 0时 令 则当Di 1 ci Di 2时 最优基不变 结论 例 Di 1 ci Di 2 2资源系数bi的灵敏度分析 当资源系数bi改变时 仅影响最优解和最优值 设bi改变量为 bi 为保证最优基不变 应满足 所以若 若 令 则当Ti 1 bi Ti 2时 最优基不变 结论 例 Ti 1 bi Ti 2 3技术系数 资源消耗系数 aij的灵敏度分析 非基变量的系数向量的灵敏度分析 Xj是非基变量 pj是其对应的系数列向量 pj是变化量 由 可见变化仅影响xj的检验数 记 为保证最优基不变 即 记 有 令 则当Sij aij Sij时 最优基不变 则最优基地位不变 若仅限pj的一个分量有变动 如aij变动 aij 则 结论 结论 对于最优基B而言 当基变量的系数列向量发生变化时 对基B及其逆矩阵都有影响 即不仅影响原先最优解的可行性 也影响到它的最优性 这里不介绍求变化范围的一般公式 而建议按具体的最优化表格进行分析 我们不做讨论 基变量的系数向量的灵敏度分析 4增加新变量的灵敏度分析如果增加一个新的变量 它对应的价值系数为对应系数列向量为 则把看成非基变量 在原来的最优单纯行中增加一列及检验数就得到了新的问题的单纯形表 若则原问题最优解不变 否则可继续用单纯形法迭代求解 若在原线性规划问题中 再增加一个新的约束条件其中及均为已知常数 则首先把已求得的原问题的最优解代入新增加的约束条件 如果满足 则原问题的最优解仍为新问题的最优解 计算停止 如果不满足 则将新的约束条件加入系统 继续求解 5 增加新的条件的灵敏度分析 具体做法是在原最优单纯形表上增加一行和一列 增加的行中以 松弛变量 为基变量 并在变量下面填入增加的列是一个单位列向量 它的最下面的一个元素为1 其余元素均为0 包括 0 这样增加一行以后 可能破坏了原最优表上的单位矩阵 最优基 要用矩阵的初等行变换将原单位矩阵恢复 然后再继续迭代求解 若在原线性规划中 再增加一个新的等式约束条件其中及均为已知常数 如果原问题的最优解满足新增加的条件 则也是新问题的最优解 计算停止 否则不妨设则引入新的人工变量将新增加的约束条件化为然后再用大M法或两阶段法求解新问题 增加等式约束条件 一般地将使约束矩阵A的秩增加 故需增加基变量