第六章单纯形法的灵敏度分析.ppt

第六章单纯形法的灵敏度分析 一 问题的提出二 目标函数系数的变化三 右端项的变化四 技术系数的变化五 增加约束条件 一 问题的提出 假设范例目标函数 Maxz 50 x1 100 x2约束条件 1 x1 1 x2 3002 x1 1 x2 4000 x1 1 x2 250 x1 0 x2 0中x2的目标函数系数由100变为75 求新问题的解 一 问题的提出 解 经过单纯形迭代得到最优表 一 问题的提出 比较范例的最优表 一 问题的提出 事实上 系数的改变并未改变LP问题的解 思考 1 如果C2变为45 最优解会变吗 为保证最优解不变 C2的取值范围 2 参数变化时 可否利用原问题的最优表求解 而不必从头进行单纯形迭代 以简化计算 一 问题的提出 要解决以上问题 需要探讨初始单纯形表与最优单纯形表的关系 观察范例的单纯形求解过程 一 问题的提出 事实上 在单纯形表的迭代过程中 最核心的变化是系数矩阵的行变换 其它值如cj在每次迭代中不变 zj和检验数则是根据其它元素计算得出 一 问题的提出 初始矩阵 最优矩阵 行变换 初始基 初始矩阵变最优矩阵的过程可以表示为 如 b2变为100 则最优矩阵可计算出 单纯形法的灵敏度分析基本思路 1 将某个参数的变化反映在最终表中 2 看最终表是否还满足最优表的要求 基是否为单位排列阵 检验数是否都非正 b列是否都为非负的数 3 若满足上述要求则最优基没有改变 若不满足则在新的最终表上继续进行迭代 直到找到新的最优基为止 二 目标函数系数ck的变化 1 在最终单纯形表中 xk是非基变量除了xk的检验数外 ck的变化不会影响到最终单纯形表中其它任何数值 只要xk的检验数仍然非正 最优解和最优值都会保持不变 如范例 使最优解不变的cj值变化范围 要使最优解不变 须c3 50 0求得c3 50 二 目标函数系数ck的变化 二 目标函数系数ck的变化 2 在最终单纯形表中 xk是基变量此时各非基变量的检验数均有可能受到影响 同时还会影响到最优值 要最优解不变 必须保证所有的检验数非正 要使最优解不变 须 c1 0且c1 100 0求得0 c1 100 二 目标函数系数ck的变化 要使最优解不变 须50 c2 0求得c2 50 二 目标函数系数ck的变化 要使最优解不变 须2c4 50 0且 c4 50 0求得 50 c4 25 二 目标函数系数ck的变化 课堂练习 有下列线性规划问题 Maxz 2x1 3x2 4x3S t x1 2x2 x3 x4 3 2x1 x2 3x3 x5 4x1 x2 x3 x4 x5 0分别分析目标函数中x1和x3的系数在什么范围内变动时 最优解不变 课堂练习 解 最优表为 课堂练习 所有 j 0时 原最优解不变从表中可得到 23 7 c1 3 2 课堂练习 从表中看到 3 c3 11 5 0可得到c3 11 5时 原最优解不变 三 右端项的变化 右端项发生变化时 最优解中变量的取值总会随之变化 讨论右端项的取值范围时 考虑的是使最优基和对偶价格不变 三 右端项的变化 例 范例中b1为300 使最优基不变的b1取值范围 解 最优表中的b列可表示为B b0 三 右端项的变化 最优表可表示为 三 右端项的变化 最优值z 50b1 12500可见b1的对偶价格50 由b1 250 0推出b1 250由 2b1 650 0推出325 b1只要最优基不变 对偶价格也不会变 即325 b1 250时对偶价格不变 三 右端项的变化 练习 分析范例b2的变化范围 对偶价格在单纯形表中的表示 根据对偶价格定义 如果最优目标函数值Z 可以表示为右端项bi的函数 则对于目标函数最大化的LP问题 bi的对偶价格可以表示为数学表达式 关键是 如何将目标函数表示为bi的函数 B CB 对偶价格在单纯形表中的表示 观察范例最优表 对偶价格在单纯形表中的表示 由于故 最终表中第i个初始基变量的z值 对偶价格在单纯形表中的表示 结论 各右端项的对偶价格就是其所在方程中初始基变量在最优表中的zj值 相关概念 影子价格 右端项增加一单位 使最优目标函数值增加的数量 四 技术矩阵的变化 1 最终单纯形表中非基变量对应的系数列向量由pk pk 时 最优表中发生变化的有 最优矩阵中的第k列 变为B0pk 最终表中检验数 k ck CB T B0pk 若仍有 k 0 则最优解不变 否则继续迭代 直到找到新的最优解 四 技术系数的变化 2 对于增加一个变量 从而使得系数矩阵增加一列pn 1的情况 技术矩阵由m n阶变为m n 1 阶在最终表中加入一列pn 1 B0pn 1然后计算检验数 若 n 1 0 则进行迭代 直到找到新的最优解 四 技术系数的变化 如范例 新增产品3 价值系数为150 相应增加一个技术列向量p6 2 0 5 1 5 T则最优矩阵中p6 B 检验数 6 150 50 0 100 25 四 技术系数的变化 所有检验数仍然小于0 故最优基和最优解不变 说明增加了产品3并不改变原生产计划 四 技术系数的变化 假如产品3的工艺改进 价值系数变为160 技术列向量变为 1 5 2 1 T则最优矩阵中p6 B 检验数 6 160 50 0 100 35 四 技术系数的变化 检验数 6 35 还需迭代 四 技术系数的变化 3 最终单纯形表中基变量对应的系数列向量由pk pk 时 原最优解的可行性和最优解都可能遭到破坏 情况比较复杂 一般重新求解 五 增加约束条件 在原线性规划中增加一个约束条件时 先将原问题的最优解的变量值代入新增的约束条件 如果满足 则说明新增的条件没有起到限制作用 故最优解不变 如果不满足 则将新增的约束添入原最终单纯形表中进一步求解 五 增加约束条件 如范例 新增约束条件 电量限制5000度 生产一个产品1需要用电10度 生产一个产品2需要用电30度 即 10 x1 30 x2 5000原最优解 50 250 0 50 0 代入 10 x1 30 x2 8000 5000 不满足 须迭代 五 增加约束条件 引入松弛变量x6 10 x1 30 x2 x6 5000 五 增加约束条件 用行变换将基变量对应的系数列向量化为单位列向量 课堂练习 对于LP问题 Maxz 2x1 3x2s t x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 课堂练习 分析 1 使最优解不变的系数c2的取值范围 2 使最优基不变的b1的取值范围 3 若增加x6 p6 2 6 3 T c6 5 最优解如何 4 若增加3x1 2x2 15 最优解如何 课堂练习 解 原问题最优表为 课堂练习 1 由 c2 2 0 c2 8 1 2 0 得c2的取值范围 0 4 课堂练习 2 用b1表示最优表中的右端项 初始基在最优表中的形式 课堂练习 由于最优表右端项有非负要求 即解得b1的取值范围 4 10 0 课堂练习 3 增加p6 2 6 3 T 最优表中增加列 初始基在最优表中的形式 课堂练习 最优表变为 课堂练习 用单纯形法进一步求解 可得 X