2.线性规划的对偶理论(第2部分)

4 影子价格 对偶最优解的经济含义 说明 yi的值相当于在给定的生产条件下 bi每增加一个单位时目标函数的增量 影子价格 第i个约束条件的影子价格的经济含义是 其它条件不变的情况下 该资源单位的变化所引起的目标函数最优值的变化量在现有的技术和管理条件下 某种资源的影子价格越大 说明该资源对目标增益的影响越大 同时该资源越紧缺和贵重 应该给与高度关注 通过降低消耗或设法补充 提高收益 某种资源的影子价格为零 说明该资源相对富裕 一方面可以转让该资源 另一方面 通过挖潜和增加对影子价格大于零资源的投入 使原有的剩余资源充分利用 甚至于成为新的紧缺资源影子价格不是市场价格 而是在现有技术和管理条件下 新增单位资源所能够创造的价值 是特定企业的一种边际价格 不同企业或同一企业不同时期 同种资源的影子价格可能不同 当市场价格高于影子价格 可以卖出 相反 则应买进 以获取更大收益 例 第一章例2 当第一个约束右端项增加1 变为最优解为若第二个约束右端项加1 变为最优解不变 即设备B的边际价格为零 若第三个约束的右端项加1 变为最优解为 综上 影子价格是灵敏度分析的一种形式 它通过获取一个单位的追加的产品因素 去测量放宽一个约束条件的价值 比较追加资源的价值和资源的实际成本 就能比较有把握地作出各种可行的决策 5 对偶单纯形法一 什么是对偶单纯形法 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法 在原始问题的单纯形表格上进行对偶处理 注意 不是解对偶问题的单纯形法 二 单纯形法的求解过程就是 在保持原始可行的前提下 b列保持 0 通过逐步迭代实现对偶可行 检验数行 0 对偶单纯形法思想 换个角度考虑LP求解过程 保持对偶可行的前提下 检验数行保持 0 通过逐步迭代实现原始可行 b列 0 从非可行解变成可行解 三 对偶单纯形法的实施1 使用条件 检验数全部 0 资源列至少一个元素 0 2 实施对偶单纯形法的基本原则 在保持对偶可行的前提下进行基变换 每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量 作为换入变量 使原始问题的非可行解向可行解靠近 3 对偶单纯形法算法步骤 建立初始单纯形表 计算检验数行 基变换 先确定换出变量 解答列中的负元素 选最小的负元素 对应的基变量出基 即 相应的行为主元行 然后确定换入变量 原则是 在保持对偶可行的前提下 减少原始问题的不可行性 如果 最小比值原则 则选为换入变量 相应的列为主元列 主元行和主元列交叉处的元素为主元素 按主元素进行换基迭代 旋转运算 枢运算 将主元素变成1 主元列变成单位向量 得到新的单纯形表 继续以上步骤 直至求出最优解 例5 用对偶单纯形法求解LP 6 灵敏度分析一 灵敏度分析的含义和内容1 什么是灵敏度分析 研究线性规划模型某些参数或限制量的变化对最优解的影响及其程度的分析过程称为灵敏度分析或优化后分析 2 灵敏度分析的内容 目标函数的系数变化对最优解的影响 约束方程右端系数变化对最优解的影响约束方程增加一个变量变化对最优解的影响约束方程增加一个约束条件对最优解的影响 回答两个问题 这些参数在什麽范围内发生变化时 最优基不变 即最优解或最优解结构不变 参数变化超出上述范围时 如何用最简便的方法求出新的最优解 二 手工进行灵敏度分析的基本原则1 在最优表格的基础上进行 2 尽量减少附加计算工作量 三 灵敏度分析举例 例 引入非负的松弛变量X3 x4 x5 将该LP化为标准型 用表格单纯形法求解最终单纯表如下 1 分析Ci的变化范围 试分析 1和 2分别在什么范围变化 问题的最优解不变 表中解为最优的条件是 1 1 2 0 1 5 1 5 0 由此推导得当 2 1 1时满足上述要求 当 1 0时 再将 2反映到表下表中得 为使表中解仍为最优解 应有 1 5 2 5 0 推导得 1 2 2 分析bi的变化范围 试分析 1 2和 3分别在什么范围变化 问题的最优基不变 先分析 1的变化 由公式 由此推得 6 1 2 使问题最优基不变的条件是 同理有 推得 4 2 推得 5 3 15 3 增加一个变量的分析 若在第一章例2中 若增加一个变量X6 有c6 4 P6 2 4 5 T 试分析问题最优解的变化 分析步骤 将其代入下表得 3 判断 6由于 6 0 继续用单纯形法迭代得下表 故新的解为 x1 3 x2 2 x6 1 z 16 6 增加一个约束条件的分析 若在第一章例2中 若增加一个约束条件3x1 2x2 14 试分析问题最优解的变化 分析 增加一个约束条件 在实际问题中相当于增添一道工序 在计算过程中相当于系数阵A增加1行 首先将原最优解代入新增约束检查是否满足 是 则说明新增约束不影响最优解 否则再作下面的讨论 将新增约束标准化 添加到原最优表格中 相当于约束矩阵新增1行 进行规格化处理 用矩阵的行变换将当前基变成单位阵 用适当方法 通常是对偶单纯形法 进行迭代求出新的最优解 如在上例中增加约束 3x1 2x2 14 当前最优解x1 3 x2 3 有3X3 2X3 15 14 不满足该约束 将约束条件标准化 加上松弛变量 后加入原最优表格 进行规格化处理 然后用对偶单纯形法迭代求出新的最优解 为使由P1 P4 P2 P6 列组成单位矩阵 对表2 13中由各变量列组成的系数矩阵进行行的初等变换 将上表各行数字按以下对应关系进行变换 1 1 2 2 3 3 4 4 3 1 2 3 得下表 因此增加约束条件后 问题的新的解为x1 8 3 x2 3 z 43 3 练习1 现有线性规划问题 先用单纯形法求出最优解 然后分析在下列各种条件下 最优解分别有什么变化 1 约束条件 的右端常数由20变为30 2 约束条件 的右端常数由90变为70 3 目标函数中X3的系数由13变为8 4 X1的系数列向量由变为 5 增加一个约束条件