第78节-灵敏度分析.ppt

线性规划问题中某一个或几个系数发生变化 显然 当线性规划问题中某一个或几个系数发生变化后 原来已得结果一般会发生变化 当然可以用单纯形法从头计算 以便得到新的最优解 这样做很麻烦 而且也没有必要 因在单纯形法迭代时 每次运算都和基变量的系数矩阵B有关 因此可以把发生变化的个别系数 经过一定计算后直接填入最终计算表中 并进行检查和分析 可按表2 9中的几种情况进行处理 表2 9 下面就各种情况分别按节进行讨论 7 1资源数量变化的分析 资源数量变化是指资源中某系数br发生变化 即br br br 并假设规划问题的其他系数都不变 这样使最终表中原问题的解相应地变化为XB B 1 b b 这里 b 0 br 0 0 T 只要XB 0 因最终表中检验数不变 故最优基不变 但最优解的值发生了变化 所以XB 为新的最优解 新的最优解的值可允许变化范围用以下方法确定 B 1是最终计算表中的最优基的逆 b列的元素变化 例如求第1章例1中第二个约束条件b2的变化范围 解 可以利用第1章例1的最终计算表中的数据 可计算 b2 由上式 可得 b2 4 0 25 16 b2 4 0 5 8 b2 2 0 125 16 所以 b2的变化范围是 8 16 显然原b2 16 加它的变化范围后 b2的变化范围是 8 32 例7从表1 5得知第1章例1中 每设备台时的影子价格为1 5元 若该厂又从其他处抽调4台时用于生产产品 求这时该厂生产产品 的最优方案 解先计算B 1 b 将结果反映到最终表1 5中 得表2 10 由于表2 10中b列有负数 故用对偶单纯形法求新的最优解 计算结果见表2 11 表2 11 即该厂最优生产方案应改为生产4件产品 生产3件产品 获利z 4 2 3 3 17 元 从表2 11看出x3 2 即设备还有2小时未被利用 7 2目标函数中价值系数cj的变化分析 分别就cj对应的非基变量和基变量两种情况讨论 1 若cj是非基变量xj的系数 这时它在计算表中所对应的检验数是 j cj CBB 1Pj或当cj变化 cj后 要保证最终表中这个检验数仍小于或等于零 即 j cj cj CBB 1Pj 0那么cj cj YPj 即 cj的值必须小于或等于YPj cj 才可以满足原最优解条件 确定 cj的范围 2 若cr是基变量xr的系数 因cr CB 当cr变化 cr时 就引起CB的变化 这时 CB CB B 1A CBB 1A 0 cr 0 B 1A CBB 1A cr ar1 ar2 arn cr可变化的范围 例8试以第1章例1的最终表表1 5为例 设基变量x2的系数c2变化 c2 在原最优解不变条件下 确定 c2的变化范围 解这时表1 5最终计算表便成为表2 12所示 若保持原最优解 从表2 12的检验数行可见应有由此可得 c2 3和 c2 1 c2的变化范围为 3 c2 1即x2的价值系数c2可以在 0 4 之间变化 而不影响原最优解 7 3技术系数 ij的变化 分两种情况来讨论技术系数 ij的变化 下面以具体例子来说明 例9分析在原计划中是否应该安排一种新产品 以第1章例1为例 设该厂除了生产产品 外 现有一种新产品 已知生产产品 每件需消耗原材料A B各为6kg 3kg 使用设备2台时 每件可获利5元 问该厂是否应生产该产品和生产多少 解分析该问题的步骤是 1 设生产产品 为x3 台 其技术系数向量P3 2 6 3 T 然后计算最终表中对应x3 的检验数 3 c3 CB 1 3 5 1 5 0 125 0 2 6 3 T 1 25 0说明安排生产产品 是有利的 分析该问题的步骤 2 是 表2 13 a 由于b列的数字没有变化 原问题的解是可行解 但检验数行中还有正检验数 说明目标函数值还可以改善 分析该问题的步骤 3 是 3 将x3 作为换入变量 x5作为换出变量 进行迭代 求出最优解 表2 13 b 计算结果见表2 13 b 这时得最优解 x1 1 x2 1 5 x3 2总的利润为16 5元 比原计划增加了2 5元 例10分析原计划生产产品的工艺结构发生变化 仍以第1章例1为例 若原计划生产产品 的工艺结构有了改进 这时有关它的技术系数向量变为P1 2 5 2 T 每件利润为4元 试分析对原最优计划有什么影响 解把改进工艺结构的产品 看作产品 设x1 为其产量 于是在原计算的最终表中以x1 代替x1 计算对应x1 的列向量 同时计算出x1 的检验数为c1 CBB 1P1 4 1 5 0 125 0 2 5 2 T 0 375将以上计算结果填入最终表x1 的列向量位置 得表2 14 表2 14 可见x1 为换入变量 x1为换出变量 经过迭代 得到表2 15 表2 15 表2 15表明原问题和对偶问题的解都是可行解 所以表中的结果已是最优解 即应当生产产品 3 2单位 生产产品 0 8单位 可获利15 2元 注意 若碰到原问题和对偶问题均为非可行解时 就需要引进人工变量后重新求解 例11假设例10的产品 的技术系数向量变为P1 4 5 2 T 而每件获利仍为4元 试问该厂应如何安排最优生产方案 解方法与例10相同 以x1 代替x1 并计算列向量 x1 的检验数为c1 CBB 1P1 4 1 5 0 125 0 4 5 2 T 2 625 将这些数字填入最终表1 15的x1列位置 得到表2 16 表2 16 将表2 16的x1 变换为基变量 替换x1 得表2 17 表2 17 从表2 17可见原问题和对偶问题都是非可行解 于是引入人工变量x6 因在表2 17中x2所在行 用方程表示时为0 x1 x2 0 5x3 0 4x4 0 x5 2 4引入人工变量x6后 便为 x2 0 5x3 0 4x4 x6 2 4将x6作为基变量代替x2 填入表2 17 得到表2 18 表2 18 这时可按单纯形法求解 X4为换入变量 x6为换出变量 经基变换运算后 得到表2 19的上表 在表2 19的上表中 确定x2为换入变量 x5为换出变量 经基变换运算后 得到表2 19的下表 表2 19 除以上介绍的几项分析以外 还可以作增减约束条件等分析 留给读者自己考虑 此表的所有检验数都为非正 已得最优解 最优生产方案为生产产品 0 667单位 产品 2 667单位 可得最大利润10 67元 第8节 参数线性规划 灵敏度分析时 主要讨论在最优基不变情况下 确定系数aij bi cj的变化范围 而参数线性规划是研究这些参数中某一参数连续变化时 使最优解发生变化的各临界点的值 即把某一参数作为参变量 而目标函数在某区间内是这个参变量的线性函数 含这个参变量的约束条件是线性等式或不等式 因此仍可用单纯形法和对偶单纯形法分析参数线性规划问题 其步骤是 1 对含有某参变量t的参数线性规划问题 先令t 0 用单纯形法求出最优解 2 用灵敏度分析法 将参变量t直接反映到最终表中 3 当参变量t连续变大或变小时 观察b列和检验数行各数字的变化 若在b列出现某负值时 则以它对应的变量为换出变量 用对偶单纯形法迭代 若在检验数行出现某正值时 则将它对应的变量为换入变量 用单纯形法迭代 4 在经迭代一步后得到的新表上 令参变量t继续变大或变小 重复步骤 3 直到b列不能再出现负值 检验数行不能再出现正值为止 8 1参数c的变化 例12试分析以下参数线性规划问题 当参数t 0时的最优解变化 解将此模型化为标准型 令t 0 用单纯形法求解的结果 见表2 20 将c的变化直接反映到最终表2 20中 得表2 21 计算t的变化范围 当t增大 在 4 0 即0 t 9 7时 为最优解 2 6 2 0 0 T 当t继续增大 t 3 2 7 6 9 7时 在检验数行首先出现 4 0 表示还可以继续改进 t 9 7为第一临界点 当t 9 7时 4 0 这时x4作为换入变量 用单纯形法迭代一步 得表2 22 当t继续增大t 5 2 1 2 5时 在检验数行首先出现 5 0 在 5 0 即9 7 t 5时 最优解 4 3 0 6 0 T t 5为第二临界点 当t 5时 5 0 这时x5作为换入变量 用单纯形法迭代一步 得表2 23 t继续增大时 在检验数行恒有 2 3 0 故当t 5时 最优解为 4 0 0 12 6 T 8 2参数b的变化分析 例13分析以下线性规划问题 当t 0时 其最优解的变化范围 解将上述模型化为标准型 令t 0 用单纯形法迭代两次 求解的结果 见表2 24 将此计算结果反映到最终表2 24 得表2 25 在表2 25中进行分析 当t增大至t 2时 则b 0 即0 t 2时 最优解为 2 t 4 0 0 T 当t 2时 则b1 0 故将x1作为换出变量 用对偶单纯形法迭代一步 得表2 26