2-4对偶理论.ppt

对偶理论 目录 对偶问题的提出对偶问题的基本性质对偶问题最优解的经济解释 影子价格对偶单纯形法 1 对偶问题的提出 1 1对称对偶关系1 2一般对偶关系1 3一般对偶关系的实例 1 1对称对偶关系 回顾例1 生产计划问题 例1的核心问题是 在有限资源的限制下 使利润最大 这称为生产计划问题 生产计划问题 例1的核心问题是 在有限资源的限制下 使利润最大 资源定价问题如果这些资源不用于生产 而是出售 则称之为资源定价问题 生产计划问题 资源定价问题它们是一对 对偶问题 是一个硬币的两面 资源定价问题设每个单位的资源价格分别为y1 y2 y3 在无损失的条件下可接受的最低单价是多少 提示 资源的用途改变了 但利润不应受损 资源定价问题从产品A来看 投入相应资源获得相应的利润 若这些资源不用于生产 为保证利润不受损应足什么条件 1 y1 4 y2 0 y3 2 资源定价问题1 y1 4 y2 0 y3 2请给出产品B的类似条件2 y1 0 y2 4 y3 3资源定价欲求解的是 利润不受损时 资源的最低定价 MINW 8y1 16y2 12y3请给出目标函数 下面将原问题和对偶问题改写成矩阵形式 并给出原问题和对偶问题的一般对应关系 对W已知b为列向量 因此Y必须是行向量 对约束条件由于Y是行向量 因此Y只能写在A的左侧 下面给出原问题和对偶问题的一般对应关系 互为对偶 给出两个模型的符号形式 互为对偶 对称对偶关系的特点 目标函数一个求MAX 一个求MIN 约束条件一个 一个 约束条件中决策变量一个在A的左侧 一个在右侧 b和C位置互换称以上关系为对称对偶关系 习惯上 MAX称为原问题MIN称为对偶问题 1 2一般对偶关系 非对称模型的规划又如何找到其对偶问题呢 转化为对称关系中的原问题 MAX形式 再给出对偶模型 下面简要讨论转化的问题 1 2一般对偶关系 将一般线规转化为原问题 MAXZ AX b 形如MinZ CX MAXZ CX形如 L1 b1的约束条件 L1 b1的约束条件形如 L1 b1的约束条件 L1 b1和 L1 b1总之有办法将一般线规转化为对称线规 1 2一般对偶关系 如果每个一般线规都如是转化 再给出对偶问题 则太繁琐 实际上我们只需要记住一句口诀 变号大横和小竖 等号对应无约束下面以实例说明口诀的意义 1 3一般对偶关系的实例 给出每个约束对应的对偶变量 将目标函数下置 给出每个约束对应的对偶变量 将目标函数下置 给出决策变量取值范围根据 变号大横和小竖 等号对应无约束 求最小值的问题竖着变号 横着不变号 亦即各yi的不等号方向和决策变量的一致 给出每个约束对应的对偶变量 将目标函数下置 给出决策变量取值范围根据 变号大横和小竖 等号对应无约束 求最小值的问题竖着变号 横着不变号 亦即各yi的不等号方向和约束条件的一致 给出对偶约束条件 注意竖着要变号 1y1 2y2 0y3 2请给出另外的3个约束条件 等号对应无约束 方向一致 给出每个约束对应的对偶变量 将目标函数下置 给出决策变量取值范围给出对偶约束条件 注意竖着要变号 1y1 2y2 0y3 2给出对偶约束条件 注意竖着要变号 1y1 2y2 0y3 2请给出另外的3个约束条件 给出每个约束对应的对偶变量 将目标函数下置 给出决策变量取值范围给出对偶约束条件 注意竖着要变号 1y1 2y2 0y3 21y1 0y2 1y3 3 3y1 2y2 1y3 51y1 1y2 1y3 1给出目标函数 给出每个约束对应的对偶变量 将目标函数下置 给出决策变量取值范围给出对偶约束条件 注意竖着要变号 1y1 2y2 0y3 21y1 0y2 1y3 3 3y1 2y2 1y3 51y1 1y2 1y3 1给出目标函数 MAXZ 5y1 4y2 6y3 练习 根据对偶问题 给出原问题 2 对偶问题的基本性质 以下所讨论的基本性质都是针对对称对偶问题来说的 原问题MAXZ CX AX b X 0对偶问题MINW Yb YA C Y 0 2 对偶问题的基本性质 2 1对称性2 2弱对偶性2 3无界性2 4等值必同优2 5同优必等值 对偶定理 2 6检验数和对偶问题基解2 7互补松弛定理 2 1对称性 对偶的对偶是原问题 2 2弱对偶性 大的不大 大的不大 MAXZ MINW证明 原问题MAXZ CX AX b X 0对偶问题MINW Yb YA C Y 0设X Y分别为原问题和对偶问题的任意可行解AX b YAX YbYA C YAX CX Yb YAX CX 2 3无界性 一个具有无界解 另一个一定没有可行解没有可行解具有无界解 一个没有可行解 另一个 一个无界解 另1个无可行解 可行域为空 原问题和对偶问题都不存在可行解 域 2 3无界性 无界性的证明 假设原问题具有无界解 证明对偶问题无可行解 用反证法 假设对偶问题有可行解Y 根据弱对偶性有CX Yb 这说明CX有上界 这和原问题具有无界解矛盾 因此只能是对偶问题无可行解 2 4可行解等值必同优 若X 和Y 是原问题和对偶问题的可行解 且有CX Y b 则X 和Y 分别为原问题和对偶问题的最优解 证明 由题设CX Y b 由弱对偶性Y b CX X为原问题任一可行解 CX CX 可知X 为原问题最优解 请你用类似的方法证明 Y b Yb 2 5同优必等值 对偶定理 若原问题有最优解 那么对偶问题也有最优解 且目标函数值相等 反之亦然 下面我们从回顾例1开始理解这个定理的证明过程 对偶问题的矩阵形式为 矩阵形式 向量形式 向量形式 对 原 对 原 松弛变量检验数CBB 1 3 2 1 8 0 判优条件C CBB 1A 0或CBB 1 A C 代入具体值 CBB 1 对 原 松弛变量检验数CBB 1 3 2 1 8 0 判优条件C CBB 1A 0或CBB 1 A C 你发现了什么 CBB 1是对偶问题的可行解 记住这个结论 下面开始证明 CBB 1 同优同值 对偶定理 若原问题MAXZ CX AX b X 0有最优解则对偶MINW Yb YA C Y 0也有最优解 且CX Y b 原问题有最优解X B 1b Z CBB 1b则C CBB 1A 0 或CBB 1 A C最优表中CBB 1 0 令CBB 1 Y可知Y CBB 1可作对偶可行解 代入W Yb得MINW CBB 1b MAXZ由等值必同优可知 Y CBB 1是对偶最优解得证 YA C 2 6检验数和对偶问题基解 我们不加证明的给出一个结论 任一步迭代中 检验数行总是给出对偶问题的基解 且目标函数值相等 对应关系下面举例说明 在初始表中松弛变量XS的检验数 S原变量的检验数 得对偶基解 0 0 0 2 3 目标函数等值z w 0 Y YS S 对偶变量Y 对偶松弛YS 在表1中观察检验数行 类似可得对偶问题基解 取负 0 0 3 4 2 0 同时目标函数等值z w 9 1 2 3 4 2 6检验数和对偶问题基解 练习 请根据教材P表中的检验数行给出对偶问题基解 2 6检验数和对偶问题基解 既然原问题基解X和相应对偶问题基解Y 总有目标函数值相等 那等值必同优 又如何理解呢 请注意条件 对于原问题和对偶问题的才有等值必同优 可行解 2 7互补松弛定理 设原问题MAXZ CX AX b X 0对偶问题MINW Yb YA C Y 0互补松弛定理若X是原问题可行解 XS是松弛变量Y是对偶问题可行解 YS是对偶松弛变量则下列条件等价Y XS 0和YS X 0X和Y是最优解下面给出该定理的理论证明 若YSX YXS 0 则一定有Z W YAX X和Y同优 标准化 标准化 将b C代入得 2 7互补松弛定理 下面结合教材例5 具体说明该定理如何应用 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 42X1 X2 3X3 X4 X5 3首先给出对偶问题 MAXZ 4Y1 3Y2Y1 2Y2 2Y1 Y2 32Y1 3Y2 5Y1 Y2 23Y1 Y2 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 42X1 X2 3X3 X4 X5 3首先给出对偶问题 再对两个规划标准化 MAXZ 4Y1 3Y2Y1 2Y2 2Y1 Y2 32Y1 3Y2 5Y1 Y2 23Y1 Y2 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 42X1 X2 3X3 X4 X5 X7 3首先给出对偶问题 再对两个规划标准化 MAXZ 4Y1 3Y2Y1 2Y2 2Y1 Y2 32Y1 3Y2 5Y1 Y2 23Y1 Y2 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 42X1 X2 3X3 X4 X5 X7 3首先给出对偶问题 再对两个规划标准化 MAXZ 4Y1 3Y2Y1 2Y2 Y3 2Y1 Y2 Y4 32Y1 3Y2 Y5 5Y1 Y2 Y6 23Y1 Y2 Y7 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 42X1 X2 3X3 X4 X5 X7 3再给出各约束条件对应的对偶问题决策变量MAXZ 4Y1 3Y2Y1 2Y2 Y3 2Y1 Y2 Y4 32Y1 3Y2 Y5 5Y1 Y2 Y6 23Y1 Y2 Y7 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y12X1 X2 3X3 X4 X5 X7 3 Y2再给出各约束条件对应的对偶问题决策变量MAXZ 4Y1 3Y2Y1 2Y2 Y3 2Y1 Y2 Y4 32Y1 3Y2 Y5 5Y1 Y2 Y6 23Y1 Y2 Y7 3 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y12X1 X2 3X3 X4 X5 X7 3 Y2再给出各约束条件对应的对偶问题决策变量MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1Y1 Y2 Y4 3 X22Y1 3Y2 Y5 5 X3Y1 Y2 Y6 2 X43Y1 Y2 Y7 3 X5 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y12X1 X2 3X3 X4 X5 X7 3 Y2最后给出最优解的对偶松弛条件 MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1Y1 Y2 Y4 3 X22Y1 3Y2 Y5 5 X3Y1 Y2 Y6 2 X43Y1 Y2 Y7 3 X5 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 X7 3 Y2 X7 Y2 0最后给出最优解的对偶松弛条件 MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1Y1 Y2 Y4 3 X22Y1 3Y2 Y5 5 X3Y1 Y2 Y6 2 X43Y1 Y2 Y7 3 X5 Y XS 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 X7 3 Y2 X7 Y2 0最后给出最优解的对偶松弛条件 MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1 Y3 X1 0Y1 Y2 Y4 3 X2 Y4 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 X7 3 Y2 X7 Y2 0由红线条件可知 X6 X7 0MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1 Y3 X1 0Y1 Y2 Y4 3 X2 Y4 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 X6 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 X7 3 Y2 X7 Y2 0于是约束条件转变为MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1 Y3 X1 0Y1 Y2 Y4 3 X2 Y4 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 3 Y2 X7 Y2 0于是约束条件转变为MAXZ 4Y1 3Y2Y1 2Y2 Y3 2 X1 Y3 X1 0Y1 Y2 Y4 3 X2 Y4 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 3 Y2 X7 Y2 0MAXZ 4Y1 3Y2 将Y1 4 5 Y2 3 5代入下面约束得Y1 2Y2 Y3 2 X1 Y3 X1 0Y1 Y2 Y4 3 X2 Y4 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 3 Y2 X7 Y2 0MAXZ 4Y1 3Y2 将Y1 4 5 Y2 3 5代入下面约束得可知Y1 2Y2 Y3 2 X1 Y3 X1 0 Y3 0 Y1 Y2 Y4 3 X2 Y4 X2 0 Y4 14 52Y1 3Y2 Y5 5 X3 Y5 X3 0 Y5 8 5Y1 Y2 Y6 2 X4 Y6 X4 0 Y6 3 53Y1 Y2 Y7 3 X5 Y7 X5 0 Y7 0 Y XS 0 YS X 0 MINW 2X1 3X2 5X3 2X4 3X5 Xj 0Y1 4 5 Y2 3 5X1 X2 2X3 X4 3X5 4 Y1 X6 Y1 02X1 X2 3X3 X4 X5 3 Y2 X7 Y2 0求解上面方程得 X1 X5 1MAXZ 4Y1 3Y2 将Y1 4 5 Y2 3 5代入下面约束得可知Y1 2Y2 Y3 2 X1 Y3 X1 0 Y3 0 Y1 Y2 Y4 3 X2 Y4 X2 0 Y4 14 5 X2 02Y1 3Y2 Y5 5 X3 Y5 X3 0 Y5 8 5 X3 0Y1 Y2 Y6 2 X4 Y6 X4 0 Y6 3 5 X4 03Y1 Y2 Y7 3 X5 Y7 X5 0 Y7 0 Y XS 0 YS X 0 3 对偶问题最优解的经济解释 影子价格 设原问题MAXZ CX AX b X 0对偶问题MINW Yb YA C Y 0当两个问题同时存在最优解时有 Z Ci Xi Yi bi W CBB 1 b观察Z 的表达式bi代表第i种资源的总量 Yi 代表最优配置下 第i种资源的价格 称为影子价格 这不是市价而是根据资源在生产中的贡献作的一种估价 3 对偶问题最优解的经济解释 影子价格 设原问题MAXZ CX AX b X 0对偶问题MINW Yb YA C Y 0当两个问题同时存在最优解时有 Z Ci Xi Yi bi W CBB 1 b影子价格是一种边际价格令Z 对b求偏导数得它表示增加某种资源1个单位 Z 的变化值 3 对偶问题最优解的经济解释 影子价格 影子价格的作用影子价格有助于企业做出买卖某种资源的决策 当资源影子价格高于市价 则应大量买进 以增加收益 当资源影子价格低于市价 则应卖出 3 对偶问题最优解的经济解释 影子价格 影子价格的作用影子价格有助于企业判断最优方案中某种资源是否有剩余 根据对偶松弛定理 在最优解中有Y Xs 0其中Y 是对偶最优解 是资源影子价格 Y 0时 必有Xs 0 该种资源无剩余 Y 0时 必有Xs 0 该种资源有剩余 延伸阅读 运筹学教程 胡运权主编 郭耀煌副主编 P49 3 对偶问题最优解的经济解释 影子价格 原问题某型 由检验数和对偶基解的关系 可得Y 各分量如表 3 对偶问题最优解的经济解释 影子价格 原问题某型 由检验数和对偶基解的关系 可得Y 各分量如表 其中Y1 Y2 Y3也是三种资源的影子价格 CBB 1 Y1Y2Y3 影子价格 3 对偶问题最优解的经济解释 影子价格 原问题某型 资源1的影子价格为Y1 3 2 这表明该种资源无剩余当市价低于3 2时可买入 当市价高于3 2时可卖出 Y1Y2Y3 影子价格 3 对偶问题最优解的经济解释 影子价格 原问题某型 资源2的影子价格为Y2 1 8 这表明该种资源也无剩余对于资源2的买入与卖出 和资源1有类似的结论 Y1Y2Y3 影子价格 3 对偶问题最优解的经济解释 影子价格 原问题某型 资源3的影子价格为Y3 0 这表明该种资源一定有剩余 以上结论读者可验证 影子价格非零的资源一定没有剩余 而影子价格为零的资源一定有剩余 Y1Y2Y3 影子价格 3 对偶问题最优解的经济解释 影子价格 原问题某型 另外如果目标函数系数2 3不是价格 而是利润 那么Y1 Y2 Y3就不再是影子价格而是影子利润 Y1Y2Y3 影子价格 3 对偶问题最优解的经济解释 影子价格 原问题某型 单纯形乘子 CBB 1对偶变量取值影子价格 Y1Y2Y3 影子价格 松弛变量检验数 4 对偶单纯形法 单纯形法迭代过程 变C不变b条件 保持XB 0 结果 检验数 0 Y 0 可见当X 0 且Y 0时 即得到最优解 原始单纯形法是 从X 0出发 到Y 0结束 对偶单纯形法是 从Y 0出发 到X 0结束 结果 单纯形法迭代过程 变C不变b条件 保持XB 0 结果 检验数 0 Y 0 对偶单纯形法迭代过程 变b不变C条件 保持检验数 0 Y 0 结果 XB 0 结果 试对比 原始 对偶 单纯形法迭代过程 变C不变b条件 保持XB 0 结果 检验数 0 Y 0 对偶单纯形法迭代过程 变b不变C条件 保持检验数 0 Y 0 结果 XB 0 4 对偶单纯形法 下面结合例6 具体说明对偶单纯形法 MinW 2X1 3X2 4X3X1 2X2 X3 32X1 X2 3X3 4 常规处理方式MAXW 2X1 3X2 4X3 MX6 MX7X1 2X2 X3 X4 X6 32X1 X2 3X3 X5 X7 4需引入人工变量才有初始单位阵I要7个变量 MinW 2X1 3X2 4X3X1 2X2 X3 32X1 X2 3X3 4 MAXW 2X1 3X2 4X3X12X2X3X4 32X1X23X3X5 4对约束条件变号 常规处理方式MAXW 2X1 3X2 4X3 MX6 MX7X1 2X2 X3 X4 X6 32X1 X2 3X3 X5 X7 4需引入人工变量才有初始单位阵I要7个变量 下面用对偶单纯形法 首先引入松