11-16对偶问题与灵敏度分析.ppt

用单纯形法求解下述问题 并指出问题的解属于哪一类 分别用大M法和两阶段法求解下列线性规划问题 并指出解属于哪一类 复习 已知线性规划问题用单纯形法计算时得到的初始单纯形表及最终单纯形表如下表 所示 请将表中空白处数字填上 本讲内容 什么是对偶问题单纯形法的矩阵描述对偶问题的性质线性规划的灵敏度分析 什么是对偶问题 例1 生产计划问题 某工厂在计划期内要安排A B两种产品的生产 已知生产单位产品的利润与所需的劳力 设备台时及原材料消耗 如下 问 如何安排生产使该厂获利最大 maxz 70 x1 120 x2s t 9x1 4x2 3604x1 5x2 2003x1 10 x2 300 x1 x2 0 影子价格 对偶问题的提出 考虑上一讲的生产计划问题 若设备和原料都用于对外加工 工厂收取加工费 试问 该厂设备工时 劳动力和原料该如何定价 一个合理的定价是 收取的加工费不能低于自己生产所得收益 在此前提下使总加工费尽量小 设该厂劳动力工时 设备和原料的定价分别为y1 y2 y3 全用于对外加工所获得总利润设为w 即 用于原生产计划生产A产品消耗的工时 设备和原料分别为9工时 4台时和3公斤 所产生的单件利润为70 则现这些资源用于服务 所获得利润应不低于原单件产品的利润 则 同理 相对B产品有 显然 工厂给这些生产要素定价 既要保证自己的利益 又要使自己的价格具有竞争力 价格越高越好 价格越低越好 Minw 360y1 200y2 300y3s t 9y1 4y2 3y3 704y1 5y2 10y3 120y1 y2 y3 0 对偶定义 y1 y2 y3称为对偶变量 构成的向量记为Y y1 y2 y3 T 其维数等于原本模型的阶数m 对偶模型的一般形式 P Maxz CX D Minw bTYs t AX bs t ATY CX 0Y 0 这是最常见的对偶模型形式 称为对称性对偶模型 两者间具有非常对称的关系 1 P为max型 D为min型 2 P的变量个数等于D的约束个数 3 P的约束个数等于D的变量个数 4 P的目标函数系数 D约束右端向量 5 P的约束右端向量 D的目标函数系数 6 P的技术系数 D的技术系数的转置 其他形式 若P的某约束为等式 那么D相应变量无非负限制 若P的某变量无非负限制 那么D的相应约束为等式 D 如何写出LP模型的对偶模型 若LP为max型 则划为 P 形式 等式 自由变量除外 若为min型 则划为 D 形式 等式 自由变量除外 然后按照 D 或 P 的形式写出其对偶形 P Maxz CX D Minw bTYs t AX bs t ATY CX 0Y 0 例1 写出下列规划问题的对偶问题 Maxz 2x1 2x2 4x3s t X1 3x2 3x3 304x1 2x2 4x3 80X1 x2 x3 0 解 设对偶变量为y1 y2 目标函数为wminw 30y1 80y2s t y1 4y2 23y1 2y2 23y1 4y2 4y1 y2 0 P Maxz CX D Minw bTYs t AX bs t ATY CX 0Y 0 例2 写出下列规划问题的对偶问题 minz 2x1 8x2 4x3s t X1 3x2 3x3 30 x1 5x2 4x3 804x1 2x2 4x3 50X1 0 x2 0 x3无限制 解 设对偶变量为y1 y2 y3目标函数为wmaxw 30y1 80y2 50y3s t y1 y2 4y3 23y1 5y2 2y3 8 3y1 4y2 4y3 4y1 0 y2无限制 y3 0 建立对偶问题的规则 对于上表 特别把握以下要点 求max的对偶问题时 变量反号求min的对偶问题时 约束反号 课堂习题 写出下列线性规划问题的对偶问题 单纯形法的矩阵描述 单纯形法的矩阵描述 设有线性规划问题 Maxz CXAX bX 0 加上松弛变量XS xn 1 xn 2 xn m 化为标准型 Maxz CX 0XsAX IXS bX 0 XS 0 单纯形法的矩阵描述 设A中存在一可行基B 相应的变量可分为基变量XB和非基变量XN 价值系数也分为CB CN 即 A B N X XB XN TC CB CN Maxz CX 0XsAX IXS bX 0 XS 0 因而 于是 Maxz CX 0XsAX IXS bX 0 XS 0 代入XB 目标值 矩阵形式描述的单纯形表 关于对偶问题的基本定理 定理1 对称性symmetryproperty 一个线性规划 P 的对偶问题 D 的对偶问题恰是原问题 P 定理2 弱对偶weakdualityproperty 若X 0 Y 0 分别为 LP 和 DP 的可行解 那么CX 0 Y 0 b 证明 该定理说明 如果原问题是最大化问题 则它的任意可行解对应的目标函数值都会小于等于其对偶问题 极小化 的任一可行解对应的目标函数值 例题 证明 由X 0 Y 0 分别为原问题和对偶问题的可行解 则 AX 0 b X 0 0Y 0 A C Y 0 0 于是 CX 0 Y 0 b 定理2 Maxz 2x1 2x2 4x3s t X1 3x2 3x3 304x1 2x2 4x3 80X1 x2 x3 0 minw 30y1 80y2s t y1 4y2 23y1 2y2 23y1 4y2 4y1 y2 0 例3 任意取一些可行解试试看 定理3 无界性 若一个问题无界 则另一个问题不可行 逆命题不成立 maxz x1 x2s t 2x1 x2 40 x1 x2 20 x1 x2 0 可行域 例4 P59 例4 定理4 最优性定理 若X 0 Y 0 分别为 LP 和 DP 的可行解 且CX 0 Y 0 b 那么X 0 Y 0 分别为 LP 和 DP 的最优解 证明 由弱对偶性可知 CX Y 0 b CX 0 则X 0 X 同理 Y 0 Y 定理5 强对偶性strongdualityproperty 若 P 问题有最优解 则 D 问题也有最优解 且两者的最优值相等 证明 添加松弛变量Xs 可将 P 问题描述为 设X 是LP问题的最优解 相应的最优基为B 如终表如下表所示 则检验数必定满足 令 问题 1 由以上定理可知 对偶问题的最优解Y 的表达式为 2 求Y 有必要重新求解 D 吗 没必要 可从原问题的最终单纯形表中获得 P D 定理6 互补松弛complementaryslacknessproperty 原问题及其对偶问题的可行解X 0 和Y 0 是最优解的充要条件是 Y 0 XS 0 YSX 0 0 XS YS分别为原问题松弛向量和对偶问题剩余向量 该定理说明 一对对偶问题达到最优 当且仅当松弛约束对应的对偶变量必定是紧的 利用互补松驰定理 可以在知道一个问题的最优解时 求解其对偶问题的最优解 例5 P59 MinZ 2x1 3x2 5x3 2x4 3x5s t X1 x2 2x3 x4 3x5 42x1 2x2 3x3 x4 x5 3xj 0 j 1 5 4 5 2 3 5 2 5 3 约束条件是松的 也即ys 0 由互补松弛定理知X 0 ys 0所以x2 0 同理 x3 0 x4 0 又y1 0 而Y 0 xs 0 知xs 0 即原问题第一个约束取等式 同理 第2个约束也取等式 对偶最优解的经济含义 由对偶定理 求z 对bi的偏导数 对偶的最优解 资源的影子价格 shadowprize 如例1 终表中松弛变量下检验数乘子CBB 1 0 1 36 0 52 分别称为系统中资源劳动力 设备和原料的影子价格 表示三者各增加一个单位时 对总利润的增加值分别为0 1 36 0 52 当最优基B确定后 目标函数的最优值 以原料为例 原料由300增加到301时 目标函数值 利润增加0 52个单位 同理 劳动力的影子价格为0 设备的影子价格为1 36 例6 某工厂经理对该厂生产的两种产品用线性规划确定最优的产量 根据产品的单位产值和生产这些产品的三种资源供应限量 建立了如下的线性规划模型 资源1的影子价格y1 3 0 资源2的影子价格y2 4 1 资源1的影子价格y3 5 3 如果将资源1增加为91 则说明资源1的增加不改变产品方案也不增加总的产值 如果将资源2增加为81 则说明资源2的增加 改变了产品方案 总的产值也由原来215增加到216 增加量等于资源2的影子价格 在管理决策中的作用 增加哪一种资源对增加经济效益最有利 按影子价格大小选择用多大的代价增加资源才合算如果增加资源的代价超过其影子价格 则不划算 影子价格和市场价格的区别 应如何考虑新产品的价格 新产品定价要高于消耗资源的影子价格利润例 新产品单件消耗资源数量为1 2 3单位 则新产品定价要大于 产品价格变动时哪些资源最为可贵 哪些无关紧要 例 上例中的产品售价不是 5 4 而是 5 5 则从单纯形表中可算出影子价格将从 0 1 3 变化为 可以帮助分析工艺改变后对资源节约的收益 例 如果改进工艺后 第三种资源能节约2 则带来的经济收益将是 对偶单纯形法是求解线性规划的另一的基本方法 它是根据对偶原理和单纯形法的原理而设计出来的 因此称为对偶单纯形法 不要简单理解为是求解对偶问题的单纯形法 由对偶理论可以知道 对于一个线性规划问题 能够通过求解它的对偶问题来找到它的最优解 什么是对偶单纯形法 也就是说 求解原问题 LP 时 可以从 LP 的一个基本解 并不一定是基可行解 开始 逐步迭代 使目标函数值 Z Yb CBB 1b CX 减少 当迭代到XB B 1b 0时 即找到了 LP 的最优解 这就是对偶单纯形法 同原始单纯形求法一样 求解对偶问题 DP 也可以从 DP 的一个基本可行解开始 从一个基本可行解 迭代 到另一个基本可行解 使目标函数值减少 例一 用对偶单纯形法求解 解 将模型转化为 所以 X 2 2 2 0 0 0 Z 72 原问题Z 72其对偶问题的最优解为 Y 1 3 3 7 3 W 72 练习 灵敏度分析SensitivityAnalysis 为什么要进行灵敏度分析 前面对线性规划的讨论 价值系数c 资源系数b和技术系数矩阵A都是已知常数 但现实中 这些系数可能只是估计量 存在误差或随着时间的推移可能有些许变化 糟糕 这个月产品市场价格与原计划时发生变化了 年初安排的生产计划还是最优的么 价值系数C变化的灵敏度分析 设只有一个价值系数cj发生变化 其它系数不变 那么cj在什么范围内变化而最优解不变呢 例 生产计划问题 价值系数变化的灵敏度分析 设只有一个价值系数cj发生变化 其它系数不变 那么cj在什么范围内变化而最优解不变呢 例 生产计划问题 最优单纯形表 考虑C2发生变化 价值系数变化的灵敏度分析 设只有一个价值系数cj发生变化 其它系数不变 那么cj在什么范围内变化而最优解不变呢 例 生产计划问题 最优单纯形表 显然只要 28 0 12c2 014 0 16c2 0成立 则最优解不变 即87 5 c2 233 33 右端项b变化的灵敏度分析 考察单纯形表 0 z I b 0 C 因此 只要B 1b 0 则最优基不变从而对偶最优解不变 也即影子价格不变 例如生产计划问题 考虑b3变化的灵敏度分析 最优单纯形表 由此可见 p3 p1 p2 是最优基 即 计算机灵敏度分析的例子 生产计划问题Excel 生产计划问题DM 多个参数变化的灵敏度分析 百分之百法则 1 对于所有变化的目标函数系数 当其所有允许增加百分比和允许减少百分比之和不超过100 时 则最优解不变 2 对于所有变化的右端项系数 当其所有允许增加百分比和允许减少百分比之和不超过100 时 则对偶最优解不变 例 上述生产计划问题 若市场条件变化 产品A的单位利润下降为53元 产品B单位利润上升至160元 最优生产计划是否会发生变化 若A产品利润升为95元 而B产品降到90元呢 1 解 产品A利润降为53元 则 C1 17产品b利润升为160元 则 C2 40 根据前面的计算结果 计算变化率 因此 最优生产计划不会改变 V1 17 36 70 0 5 50 V2 40 233 333 120 0 353 35 3 V v1 v2 83 5 2 解 产品A利润升为95元 则 C1 25产品B利润降为90元 则 C2 30 根据前面的计算结果 计算变化率 因此 最优生产计划会改变 V1 25