线性规划的对偶理论经典运筹学ppt课件.ppt_第1页
线性规划的对偶理论经典运筹学ppt课件.ppt_第2页
线性规划的对偶理论经典运筹学ppt课件.ppt_第3页
线性规划的对偶理论经典运筹学ppt课件.ppt_第4页
线性规划的对偶理论经典运筹学ppt课件.ppt_第5页
已阅读5页,还剩31页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

第2章线性规划的对偶理论及其应用 线性规划最重要的理论之一进行经济分析的重要工具 上堂课的主要内容 1 对称型对偶问题 2 标准型的对偶问题 则对偶问题 D 为 目标函数max 目标函数min 目标函数系数 约束方程常数列 约束方程常数列 目标函数系数 变量个数n 约束方程个数n 约束方程个数m 变量个数m 约束方程 变量 0 0 无符号约束 变量 0 约束方程 0 无符号约束 系数矩阵A 3 混合型对偶问题 2 2对偶线性规划解的理论 最优单纯形表 最优单纯形表 常数项 010 1 43 23 2 1001 4 1 27 2 0015 4 15 215 2 000 1 4 1 2Z 17 2 最优值Z 17 2 最优值W 17 2 最优解 7 2 3 2 最优解 0 1 4 1 2 定理2 1对偶问题的对偶就是原问题 即互为对偶规划 一 对称定理 设原问题 P 对偶问题 D 二 弱对偶性定理 推论2 若原问题 P 和其对偶问题 D 都存在可行解 则 P 和 D 都存在最优解 推论1 若 P 有可行解 但无上界 则 D 无可行解 若 D 有可行解 但无下界 则 P 无可行解 定理2 3原线性规划 P 与其对偶规划 D 存在以下对应关系 1 P 有最优解的充要条件是 D 有最优解 2 若X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是 CX Y b 三 对偶性定理 由定理2 2的推论2知 D 有最优解 充分性 由定理2 1知 P 与 D 互为对偶 充分性同理证明 1 P 有最优解的充要条件是 D 有最优解 B为最优基 2 若X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是CX Y b 证明 必要性 设X 和Y 分别是 P 和 D 的最优解 由定理2 2 必有CX Y b 设 P 的最优解X 对应的最优基为B 所以CX Y b 充分性 设X 和Y 分别是 P 和 D 的可行解 且CX Y b 证 设X是 P 的任一可行解 由定理2 2 必有CX Y b CX 所以X 是 P 的最优解 同理可证Y D 的最优解 要证X 和Y 分别是 P 和 D 的最优解 定理2 3原问题 P 与其对偶问题 D 存在以下对应关系 1 P 有最优解的充要条件是 D 有最优解 2 若X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是CX Y b 推论 1 若 P 有可行解而 D 无可行解 则 P 无界 若 D 有可行解而 P 无可行解 则 D 无界 3 若 P 存在最优解X 则 D 一定存在最优解Y 且 2 原问题 P 与其对偶问题 D 最优值相同 只需求出 P 或 D 中一个的最优解和最优值 即可得另一个的最优解和最优值 0 1 21 1 41 41 4 1201 2 3 21 2 0 1 20 11 4 9 4Z 31 4 的最优单纯形表为 求其对偶问题的最优解和最优值 解 对偶问题的最优值 W 31 4 最优解 推论3 若 P D 为对称型对偶问题 且 P 存在最优解X 则 D 一定存在最优解Y 且 1 Y 是 P 的标准型的最优单纯形表检验行中松弛变量的系数 设最优基为B 最优值Z 19 松弛变量X3X4X5的检验数为0 1 2 D 的最优解Y0 0 1 2 最优值S0 19 推论2 若原问题 P 和其对偶问题 D 都存在可行解 则 P 和 D 都存在最优解 推论1 若 P 有可行解 但无上界 则 D 无可行解 若 D 有可行解 但无下界 则 P 无可行解 定理2 3原问题 P 与其对偶问题 D 存在以下对应关系 1 P 有最优解的充要条件是 D 有最优解 2 若X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是CX Y b 推论 1 若 P 有可行解而 D 无可行解 则 P 无界 若 D 有可行解而 P 无可行解 则 D 无界 3 若 P 存在最优解X 则 D 一定存在最优解Y 且 2 原问题 P 与其对偶问题 D 最优值相同 原问题与对偶问题解的关系 一定 不可能 不可能 不可能 不可能 可能 不可能 可能 可能 P 无可行解 D 无可行解 无界 P 无可行解 D 有可行解 四 互补松弛定理 定理2 4设X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是方程组 证明 充分性 已知X 和Y 分别是 P 和 D 的可行解 且 所以X 和Y 分别是 P 和 D 的最优解 必要性 已知X 和Y 分别是 P 和 D 的最优解 因为X 和Y 分别是 P 和 D 的最优解 定理2 4设X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是方程组成立 互补松弛定理 互补松弛定理 设X 和Y 分别是 P 和 D 的可行解 则X 和Y 分别是 P 和 D 的最优解的充要条件是方程组成立 把X 代入 P 的第i个方程时为等式 松约束 紧约束 定理2 4设X 和Y

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论