对偶工管重点_第1页
对偶工管重点_第2页
对偶工管重点_第3页
对偶工管重点_第4页
对偶工管重点_第5页
已阅读5页，还剩4页未读， 继续免费阅读

下载本文档

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

文档简介

6 互补松弛定理 设X 和Y 分别是问题P和D的可行解 则它们分别是最优解的充要条件是 同时成立 一般而言 我们把某一可行点 如X 和Y 处的不等式约束 包括对变量的非负约束 称为松约束 而把等式约束称为紧约束 互补松弛定理也称松紧定理 它描述了线性规划达到最优时 原问题 或对偶问题 的变量取值和对偶问题 或原问题 约束松紧之间的对应关系 例4 已知 试通过求对偶问题的最优解来求解原问题的最优解 解 对偶问题为 用图解法求出 Y 1 3 W 11 将y 1 1 y 2 3代入对偶约束条件 1 2 5 式为紧约束 3 4 为松约束 令原问题的最优解为X x1 x2 x3 x4 x5 则根据互补松弛条件 必有x3 x4 0 1 3 1 2 3 4 5 又由于y 1 0 y 2 0 原问题的约束必为等式 即 化简为 此方程组为无穷多解 令x5 0 得到x1 1 x2 2即X 1 1 2 0 0 0 为原问题的一个最优解 Z 11 再令x5 2 3 得到x1 5 3 x2 0即X 2 5 3 0 0 0 2 3 也是原问题的一个最优解 Z 11 步骤 1写出对偶问题 注意符号 2由问题的最优解 实质是变量 的松紧 是否 0 判断另一个问题的松紧约束3最优解代入判断约束条件符号 找出松紧约束 从而得出另一个问题的紧变量 0 变量 约束 松紧对应 例5 已知原问题的最优解为X 0 0 4 Z 12试求对偶问题的最优解 解 1 2 3 将X 0 0 4 代入原问题中 有下式 由x3 0 得对偶问题的第三个约束条件为紧约束 所以 根据互补松弛条件 必有y 1 y 2 0 代入对偶问题 3 式 y3 3 因此 对偶问题的最优解为Y 0 0 3 W 12 练习已知线性规划问题Min Z 2x1 3x2 5x3 2x4 3x5S t x1 x2 2x3 x4 3x5 42x1 x2 3x3 x4 x5 3xi 0 i 1 2
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

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

最新文档

评论

0/150

提交评论