2.对偶理论.ppt_第1页
2.对偶理论.ppt_第2页
2.对偶理论.ppt_第3页
2.对偶理论.ppt_第4页
2.对偶理论.ppt_第5页
已阅读5页，还剩33页未读， 继续免费阅读

下载本文档

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

文档简介

第二章线性规划的对偶理论及其应用 窗含西岭千秋雪 门泊东吴万里船对偶是一种普遍现象 2 第一节问题的提出 假设工厂考虑不进行生产而把全部可利用的资源都让给其他企业 工厂希望给这些资源定出一个合理的价格 即使别的单位愿意购买 又使本工厂能得到生产这些产品所能获得的最大收益 3 二 对偶问题 1 对称LP问题的定义 2 对称LP问题的对偶问题 第一类对称形式 第二类对称形式 4 例1 写出下列LP问题的对偶问题 对偶 5 3 对偶问题的对偶 推导过程 变形 对偶 6 对偶 变形 7 写出下列LP问题的对偶问题 例2 解 上述LP问题的对偶问题为 8 三 非对称LP问题的对偶问题 例3 写出下列LP问题的对偶问题 9 10 11 直接写出LP问题的对偶问题 例3 12 13 第二节LP问题的对偶理论 定理1 弱对偶定理 14 15 推论1 若LP问题有无界解 则其对偶问题无可行解 若LP问题无可行解 则对偶问题一定无解 推论2 极大化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的下界 极小化问题的任何一个可行解所对应的目标函数值都是其对偶问题的目标函数值的上界 推论3 16 例4考虑下面一对LP问题 其对偶问题为 17 定理2 最优性准则 证明 18 例5 19 定理3 强对偶定理 若 L D 均有可行解 则 L D 均有最优解 且 L D 的最优目标函数值相等 证明 20 21 22 推论 在用单纯形法求解LP问题 L 的最优单纯形表中松弛变量的检验数的相反数就是其对偶问题 D 的最优解 证明 23 解 化为标准型 例5求下列问题对偶问题的最优解 24 以 1 为枢轴元素进行运算 x1为换入变量 x3为换出变量 以 4 为枢轴元素进行旋转运算 x2为换入变量 x5为换出变量 25 此时达到最优解 X 4 2 MaxZ 14 26 定理4 互补松驰定理 27 例6考虑下面问题 28 解 则 29 第三节对偶问题的经济学解释 影子价格 标准化 30 1 定义 二 影子价格 2 含义 31 1400 3 2 1 80 32 例8 做目标函数2x1 3x2的等值线 与阴影部分的边界相交于Q 4 2 点 表明最优生产计划为 生产I产品4件 生产II产品2件 Q 4 2 x1 x2 4x1 16 4x2 12 x1 2x2 8 4 4 0 8 3 Z 14 Q 4 25 1 875 Z 14 125 Q 4 2 5 Z 15 5 Q 4 2 Z 14 33 2 告诉管理者花多大代价购买进资源或卖出资源是合适的 3 影子价格的作用 1 告诉管理者增加何种资源对企业更有利 3 为新产品定价提供依据 34 第四节对偶单纯形法 一 步骤 建初始表 结束 选出出基和进基变量进行运算 Y N 35 例9 用对偶单纯形法求解下列LP问题
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

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

最新文档

评论

0/150

提交评论