运筹学基础-对偶线性规划(3).ppt

灵敏度分析 是指对系统或事物因周围条件变化所表现出的敏感性程度的分析 在前面讲的线性规划问题中 通常都是假定问题中的aij bi cj系数是已知的常数 但实际上这些参数都是一些估计或预测的数字 在现实中 如果市场条件变化 cj值就会发生变化 如果工艺技术条件改变 则aij就会变化 如果资源的可用量发生变化 则bi也会发生变化 2 5灵敏度分析 问题 1 参数发生变化时 问题的最优解会有什么变化 2 参数多大的范围内变化时 原最优解保持不变 解决方法 1 当参数变化时 用单纯形法从头计算 看最优解有无变化 但这样做既麻烦又没有必要 2 把个别参数的变化直接在获得最优解的最终单纯形表上反映出来 这样就不需要从头计算 而只需对获得最优解的单纯形表进行审查 看一些数字变化后是否仍满足最优解的条件 如果不满足的话 再从这个表开始进行迭代计算 求得最优解即可 这也就是灵敏度分析 灵敏度分析的步骤如下 1 将参数的改变计算反映到最终单纯形表上来 b B 1 b 具体计算方法是 按下列公式计算出由参数aij bi cj的变化而引起的最终单纯形表上有关数字的变化 Pi B 1 Pi cj zi cj zi aijyi 2 检验原问题是否仍为可行解 即右端常数是否大于0 3 检验对偶问题是否仍为可行解 即检验数是否小于0 4 按下表所列情况得出结论和决定继续计算的步骤 常数项的改变量 系数的改变量 目标函数系数的改变量 解的情况判定表 一 分析cj变化的影响 目标函数中的系数cj的变化仅仅影响到检验数 cj zi 的变化 所以将cj的变化直接反映到最终单纯形表中 只可能出现表中的前两种情况 例 已知线性规划问题 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 用单纯形法求得最终单纯形表如下 最终单纯形表 试确定 a 当目标函数变为maxZ 5x1 1 5x2时 最优解会出现什么变化 b 目标函数变为maxZ 2 l x1 x2时 l在什么范围变化 最优解不变 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 maxZ 5x1 1 5x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 解 a 将目标函数系数的变化直接反映到最终单纯形表中 变量x5的检验数为正 继续迭代 maxZ 5x1 1 5x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 继续迭代得下表 即得新解x1 4 x2 0 x3 15 x4 0 x5 1 此时MaxZ 20 解 b 将目标函数系数的变化直接反映到最终单纯形表中 为使表中解为最优 应有 1 4 1 4l 0 1 2 1 2l 0 即得 1 l 1 二 分析bi变化的影响 bi的变化在实际问题中表明可用资源的数量发生变化 其变化 b反映到最终单纯形表上只引起基变量列数字变化 b 因此灵敏度分析的步骤为 1 由 b B 1 b算出 b 将其加到最终表基变量列的数字上 2 由于其对偶问题仍为可行解 检验行没变 故只需检查原问题是否仍为可行解 再按相应步骤进行 注 此公式是单纯形法利用公式求解的推导结果 问题 B与B 1分别是什么 以此题为例 初始单纯形表 最终单纯形表 B B 1 原理是 B I 经过初等变换可化为 I B 1 其中I是单位阵 参见36页 又例 初始单纯形表 B B 1 例 上例中 最终单纯形表 a 若第2个约束条件右端项增大到32 分析最优解变化 b 若第2个约束条件变为6x1 2x2 24 l 分析l在什么范围内变化 表中基为最优解 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 maxZ 2x1 x25x2 15 6x1 2x2 32 x1 x2 5x1 x2 0 解 a 第2个约束条件右端项增大到32 因 因表中原问题为非可行解 故用对偶单纯形法继续计算 将其加到最终单纯形表的基变量b这一列上得下表 注 B 1扩充了检验行 目标值的变化 b B 1 b 15 2 107 2 23 2 2 17 2 2 35 211 2 1 2 21 2 继续迭代得下表 最优值maxz 10 即得新解x1 5 x2 0 x3 15 x4 2 x5 0 解 b 若第2个约束条件变为6x1 2x2 24 l 因 将其加到最终单纯形表的基变量b这一数列上得下表 15 2 5l 47 2 l 43 2 l 4 17 2 l 4 15 2 5 4l 0 l 6 7 2 1 4l 0 l 14 3 2 1 4l 0 l 6 得 6 l 6 三 增加一个变量的分析 增加一个变量在实际问题中反映为增加一种新的产品 分析步骤是 1 计算新变量最终表检验数sj cj zi cj y Pj 2 计算新变量最终表约束函数系数向量Pj B 1Pj 3 判定 若sj 0 只需将Pj 和sj的值直接反映到最终单纯形表中 原最优解不变 若sj 0 则按单纯形法继续迭代计算 其中cj是新变量目标函数系数 Pi是新变量约束函数系数 y 是对偶问题的解 最终单纯形表 例 上例中 若增加一个变量x6 有c6 3 P6 3 4 2 T 试分析最优解的变化 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 maxZ 2x1 x2 3x65x2 3x6 156x1 2x2 4x6 24x1 x2 2x6 5x1 x2 x6 0 解 将其反映到最终单纯形表中得下表 因s6 1 0 故用单纯形法继续计算 增加变量x6 有c6 3 P6 3 4 2 T 试分析最优解的变化 检验数sj cj zi cj y Pj Pj B 1Pj 继续迭代得下表 由此得新的解为 x1 7 2 x2 0 x3 51 4 x4 0 x5 0 x6 3 4 Maxz 2 7 2 3 3 4 37 4 四 分析aij变化的影响 假如xj在最终表中为基变量 则aij的变化将使最终表中的B 1变化 因此有可能出现原问题与对偶问题均为非可行解的情况 例 上例中 c2 3 x2的系数向量变为P2 8 4 1 T 试分析最优解的变化 解 同上例 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 maxZ 2x1 3x28x2 156x1 4x2 24x1 x2 5x1 x2 0 11 21 21 23 2 继续迭代得下表 因原问题与其对偶问题均为非可行解 通过引入人工变量将原问题转化为可行解 再用单纯形法继续计算 将第一行x3 4x4 24x5 9化为标准型 x3 4x4 24x5 9 再加上人工变量 x3 4x4 24x5 x6 9 因s5 0 故用单纯形法迭代计算 x3 4x4 24x5 x6 9 继续迭代得下表 新的最优解为maxz 89 8 x1 11 4 x2 15 8 x3 0 x4 0 x5 3 8 x6 0 五 增加一个约束条件的分析 增加一个约束条件 在实际问题中相当于增添一道工序 分析的方法是先将原来的问题的最优解变量取值代入这个新增的约束条件中 如满足 说明新增约束未起到限制作用 原最优解不变 否则 将新增约束直接反映到最终表中 再进行分析 例 上例中 新增添一个约束条件3x1 2x2 12 试分析最优解的变化 解 先将原问题最优解x1 7 2 x2 3 2代入新约束条件 因有 故将约束条件写成3x1 2x2 x6 12 并取x6为基变量 直接反映到最终表中 3 7 2 2 3 2 27 2 12 maxZ 2x1 x25x2 15 6x1 2x2 24 x1 x2 53x1 2x2 12x1 x2 0 得下表 x1与x2的向量不是单位向量 要继续变换 得下表 用对偶单纯形法迭代继续变换 得下表 新的最优解为maxz 8 x1 4 x2 0 x3 15 x4 0 x5 1 x6 0 2 7参数线性规划 参数aij bi cj在什么范围内变化时最优解不变是实际问题中常常要研究的问题 当这些参数超出这个范围时 最优解会发生怎样的变化 即为参数线性规划要研究的问题 例 线性规划问题 maxZ l 2x1 x25x2 15 6x1 2x2 24 x1 x2 5 lx1 x2 0 第三个约束右端不断增大 分析最优解会发生怎样的变化 此时l 0 参数线性规划求解步骤 1 令l 0求解得最终单纯形表 2 将参数的变化反映到最终单纯形表中 因 反映到最终单纯形表中 3 让l逐步增大 观察原问题与对偶问题解的变化 看哪一个首先出现非可行解 15 2 15 2 l 0 x1 7 2 1 2 l x2 3 2 3 2 l Z 17 2 1 2 l 7 2 1 2 l 0 3 2 3 2 l 0 当0 l 1表中解为最优解 此时 当l 1时 用对偶单纯形法迭代 注 不用讨论7 2 1 2 l 0的情况 因为此时 15 2 15 2 l也是负的 且绝对值更大 因此出基项仍然是x3 第一行 当l继续增大 原问题与对偶问题都保持可行解 故计算至此结束 结论 01 x1 3 x2 3 maxZ 9 图示 目标函数Z l 与l的变化关系图 9 l 1 Z 17 2 1 2 l l 1 Z 9 注 问题中多个参数变化时 应使目标函数z l 是l的线性函数 例 求解下述参数线性规划问题 maxZ 2 l x1 1 2l x25x2 15 6x1 2x2 24 x1 x2 5x1 x2 0 解 按参数线性规划求解问题的第一 二步 令l 0求得最优解 并将cj的变化值反映到最终单纯形表中 反映到最终单纯形表中 当 1 5 l 1时 表中解为最优解 此时 当l 1 变量x4的检验数为正值 用单纯形法继续迭代得 z 7 2 2 l 3 2 1 2l 17 2 13l 2 1 4 l 4 0 1 2 5l 2 0 1 5 l 1 当l 1 5 变量x5的检验数为正值 用单纯形法继续迭代得 当l 1 原问题与对偶问题都保持可行解 故计算至此结束 工厂的最优计划为x1 2 x2 3 z 2 2 l 3 1 2l 7 8l 当l 1 变量x4的检验数为正值 用单纯形法继续迭代得 当l 1 5 当l 1 5时 变量x5的检验数为正值 用单纯形法