运筹学单纯形法的灵敏度分析ppt课件.ppt

5 2单纯形法的灵敏度分析 目标函数系数Cj的改变对原问题的影响约束条件右侧常数bi改变对原问题的影响约束条件系数矩阵A发生变动对原问题的影响 1 例 某工厂计划生产甲 乙 丙三种产品 这三种产品的单位利润分别为2元 3元 1元 生产单位产品所需要的劳动力和材料如下表所列 现工厂计划部门列出线性规划的模型 以确定最优的生产方案 2 设计划生产三种产品产量分别为x1 x2 x3引入松弛变量x4 x5 得如下单纯形表 3 解到第三段得到最优解 x1 1 甲产品生产1单位 x2 2 乙产品生产2单位 x3 0 丙产品不生产 maxZ 8 最大利润达到8元 4 一 目标函数系数Cj的改变对原问题的影响 讨论 上例中甲 乙 丙三种产品单位利润发生变化时对原问题的影响 思考 数学模型中 cj变化将影响数学模型中哪些因素 如 丙产品单位利润的变化将影响到模型中哪些因素 c3 1c3 2或c3 1c3 6再如 甲 乙产品单位利润发生变化时 将影响到哪些因素 c1 2c1 4或c2 3c2 2 5 结论 在单纯形法中 cj的变化 cj zj变化 基变量的调出 入 分两种情况 非基变量的cj发生变化只影响其本身对应的检验数cj zj 如上例中x3为非基变量 则丙产品单位利润发生变化只影响本身的检验数 基变量的cj发生变化 由于影响到cB 从而所有非基变量的检验数均受到影响 基变量的检验数仍保持为0 如上例中x1 x2为基变量 则甲 乙产品单位利润变化 将影响除甲 乙外其他变量的检验数 6 一 非基变量目标函数系数的改变 上例中 x1 x2为基变量 x3为非基变量 它的最优解为x3 0 既不安排生产 为什么不生产丙产品呢 因为x3所对应的检验数Cj Zj不是绝对值最大者 无法调入成为基变量 如果要生产丙产品 意味着x3 0 则必须将x3调入成为基变量 考察单纯形表最后一段 此时检验数Cj Zj均为非正 如果此时改变c3 则C3 Z3会发生变化 当它变成 0时 就可以调入 所以 分析c3 z3的变动 7 C3变动范围 当C3 Z3 0即C3 4时 调入成为基变量 则x3 0 也就是说 此时当改变丙产品的单位利润c3到大于4元时 它的产量就大于零 即需考虑生产丙产品了 8 所以 丙产品单位利润的变动范围是c3 4 讨论 假设此时c3增加到6元 产量应为多少 9 C3已超出变动范围 代入单纯形表最后一段继续计算 即当丙产品利润增加到6元时 最优解为x1 2 x3 1 x2 0 最优值为maxZ 10 10 二 基变量目标函数系数的改变 讨论 甲产品单位利润的变化对原问题的影响 单纯形法最后一段如下 11 分析结果 从单纯表最后一段可知 x1为基变量 x1 0 意味着生产甲产品 再进一步分析 如果C1降到某一程度之后 即利润非常小 从实际意义上讲 是不应该安排甲产品生产的 另一方面 当甲产品利润增加到很高一个水平时 就可以考虑只生产甲产品而不生产其他产品 那么究竟甲产品利润必须变动到什么程度才可能发生以上变化呢 12 二 基变量目标函数系数的改变 x1是基变量 基变量的检验数C1 Z1 0 而C1变化会影响到非基变量的检验数 我们可以分析所有非基变量的检验数 13 C1的变动范围 C1的变动范围为 3 4 3 也就是说 当甲产品利润在3 4到3之间变动时 它不会影响到基变量 即仍安排生产甲产品和乙产品 不生产丙产品 只是随着C1的变化 最优解即甲 乙产品的产量不会改变 而总利润会发生变动 如当C1 1时 最优解为x1 1 x2 2 而最优值Z 7 若C1变动超过以上界限 则需重新计算 14 三 基变量和非基变量的目标函数系数同时发生变化时 思路 参考以上两种情况 在单纯形表最后一段中 用变化后的新Cj代入计算检验数Cj Zj 若满足符号条件 则最优解不变 最优值变动 若不满足符号条件 则用变化后的Cj代入最后一段 继续进行迭代计算 15 如上例 当Cj变为 C2 4 C3 4 代入最后一段 得 Cj Zj 0 均满足符号条件 最优解不变 x1 1 x2 2最优值Z 10 16 当Cj变为C2 4 C3 8 代入最后一段 得 Cj Zj 0 均满足符号条件 经过两段计算 得到最优解 x1 2 x2 1最优值Z 12 17 二 约束条件右侧常数bi改变对原问题的影响 讨论 例中资源最高限制量改变时将影响数学模型中的哪些因素 18 Bi变化影响哪些因素 当bi变化时 从单纯形法计算过程可知 它不影响检验数 只影响b列本身 也就是说 它不影响基变量但会改变最优解的具体数值 如上例中 假设b1发生变化 劳动力使用从一个劳动力增加到2个劳动力 即b1 2 则 b变化不影响检验数 单纯形表最后一段基变量结构不变 仍是x1 x2 改变的是x1 x2的数值用公式表示如下 19 20 分析 从以上计算结果表明 增加一个单位b1 劳动力数量 会使总利润增加 但在实际经济工作中 b1增加不可能是无限的 因为劳动力增加太多 而其他条件不变时 势必造成劳动力过剩 影响生产率 进而影响利润率 即Cj会变化 因此 b1的变化也是有范围的 从数学模型上思考 b取值的制约条件 21 bi变动的制约条件 当我们用单纯形法解线性规划问题时 要求b 0 b的变化必须首先满足这个条件用公式表示如下 22 设基变量不变 意味着生产产品结构不变 即B P1P2 保持不变 则 b1变动的范围是 3 4 3 也就是说 b1在3 4 3之间变动时 基变量结构不变 仍是生产甲 乙两种产品 不生产丙产品 但变量值发生变动 产量变化 最优值也会变动 总利润变化 即 23 24 分析 例中第二个资源 材料的最高限制变化时对原问题的影响 即讨论 b2变动的范围 25 B2变动的范围 B2的变动范围是 14 26 影子价格的概念 影子价格 是经济领域的概念 影子价格 是指当其他原料数量都保持不变时 第k种原料由bk增加一个单位时 由此而产生的目标函数值的增加 它对应于单纯形表最后一段松弛变量所对应的检验数 取正值 27 如例中 b1表示劳动力资源 当b1变动时 28 从以上计算结果表明 b1的影子价格即松弛变量x4的检验数的相反数Z4 C4 5 说明每增加一个单位的劳动力会使得目标函数值Z增加5个单位 29 b2表示材料资源 当b2变动时 30 计算结果表明 b2的影子价格即松弛变量x5的检验数的相反数Z5 C5 1 说明每增加一个单位的材料会使得目标函数值Z增加1个单位 31 影子价格的经济意义 当影子价格Zj Cj 0时 表明当各种产品的数量按照最优决策 分别生产数量x1 x2 xn并达到最大收益时 第j种原料尚有剩余 如果单独增加第j种原料的数量不会使总收益增加 故影子价格Zj Cj 0 当影子价格Zj Cj 0时 表明第j种原料已经在达到最大收益时全部耗尽 生产组织者如果要扩大生产增加收益 必须增加第j种原料的购买量 如果市场上该种原料的市场价格小于或等于Zj Cj时 则用增加第j种原料来增加收益是合算的 反之 若市场价格大于影子价格时 那么用增加第j种原料来增加收益的办法是不利的 所以影子价格能为企业或部门提供今后 活动 的一种经济信息 32 三 约束条件系数矩阵A发生变动对原问题的影响 增加新的产品生产 使A矩阵多一列aj现行的产品生产资源消耗量发生改变 即aij变化时增加新的约束条件 即增加新的一行ai 33 一 增加新的产品生产 使A矩阵多一列aj 设该厂研究出新的产品丁 每生产一单位产品丁 需要一个劳动力和一单位原料 单位利润为3单位 丁产品销路良好 现在想知道 在原有资源不变的情况下 安排丁生产是否有利 结合数学模型分析 34 分析 要判断是否安排丁生产 就看丁所对应的检验数Cj Zj是否满足符号条件 若满足符号条件 说明原问题最优解不变 丁变量不会成为基变量 解仍为零 即不应安排丁产品的生产 相反的 若Cj Zj不满足符号条件 则丁变量就有可能被调入成为基变量 即应考虑生产丁 如例中 原问题变为 多一个变量x6 35 多一个变量x6 使A矩阵多了一列 若加入最后一段计算 不能直接用p6 而应将p6线性变化后带入 36 根据单纯形表最后一段有关数据 得 37 分析检验数符号 C6 Z6满足符号条件 原问题最优解不变 仍是x1 1 x2 2 x3 x6 0即不安排丁产品生产 注意区别和的不同 38 若将以上丁产品利润改为C6 7 其他条件不变 情况会有什么变化 39 分析检验数符号 C6 Z6不满足符号条件 原问题最优解将变动 将C6代入单纯形表最后一段重新计算 注意 40 对p6进行线性变化 41 此时得到最优解 x1 0 x2 2 x3 x4 x5 0 x6 1 3 最优值Z 25 3 说明由于丁产品利润的增加 应考虑生产丁产品 42 二 现行的产品生产资源消耗量发生改变 即aij变化时 1 当非基变量的aij变化时 如上例 丙产品的技术条件发生变化 单位丙产品所需的劳动力数量不变 a13 1 3 所需的材料数量减少为a23 5 3即 43 分析方法 非基变量的aij的变化只影响本列的数值 只影响本列的检验数 所以与增添新产品的情况相同 只要重新计算发生变化的aij对应的Cj Zj 根据Cj Zj的符号判断最优解有否改变 如例中 丙产品的技术条件发生变化 单位丙产品所需的劳动力数量不变 a13 1 3 所需的材料数量减少为a23 5 3 44 计算检验数 C3 Z3满足符号条件 原问题最优解不变 最优值也不变 45 2 当基变量对应的aij变化时 当基变量对应的aij变化时 由于此时基矩阵CB受到影响 进而影响所有检验数 即 所以 应对规划问题重新计算 46 如上例 甲产品 乙产品的技术条件发生变化时 即a11 a21 a12 a22变化时将影响到则应重新计算 47 三 增加新的约束条件 即增加新的一行ai 如上例 若增加一个约束条件分析 最优解是否要改变 48 对比数学模型 49 分析 将最优解带入新加入的约束条件中 看看是否满足若满足新的约束条件 最优解不变 若不满足新的约束条件 则应加入新的约束条件于单纯形表最后一段 标准化后 继续进行迭代计算直至求出最优解或判断无解 50 将最优解x1 1 x2 2代入上式 得左边 1 2 2 0 5 右边 4显然不满足约束条件 则应重新计算最优解 51 分析 加入松弛变量x6 得将标准化后的式子代入单纯形表最后一段 52 分析 思考 以上单纯形表可否直接计