对偶单纯形法详解.ppt_第1页
对偶单纯形法详解.ppt_第2页
对偶单纯形法详解.ppt_第3页
对偶单纯形法详解.ppt_第4页
对偶单纯形法详解.ppt_第5页
已阅读5页,还剩17页未读 继续免费阅读

下载本文档

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

文档简介

,2.3 对偶单纯形法 一、什么是对偶单纯形法? 对偶单纯形法是应用对偶原理求解原始线性规划的一种方法在原始问题的单纯形表格上进行对偶处理。 注意:不是解对偶问题的单纯形法!,二、对偶单纯形法的基本思想 1、对“单纯形法”求解过程认识的提升 从更高的层次理解单纯形法 初始可行基(对应一个初始基本可行解) 迭代另一个可行基(对应另一个基本可行解),直至所有检验数0为止。,所有检验数0意味着 ,,说明原始问题的最优基也是对偶问题的可行基。换言之,当原始问题的基B既是原始可行基又是对偶可行基时,B成为最优基。 定理2-5 B是线性规划的最优基的充要条件是,B是可行基,同时也是对偶可行基。,LP原问题:,若B是A中的一个基,证明:,单纯形法的求解过程就是: 在保持原始可行的前提下(b列保持0), 通过逐步迭代实现对偶可行(检验数行0)。,2、 对偶单纯形法思想: 换个角度考虑LP求解过程:保持对偶可行的前提下(检验数行保持0) ,通过逐步迭代实现原始可行(b列0,从非可行解变成可行解)。,对偶单纯形法的思想(图示),原问题,初始基本可行解,保持为基本可行解,初始对偶可行解,保持对偶可行性,最优解,基本可行性,对偶可行性,始终满足解的可行性,始终满足对偶可行性,三、对偶单纯形法的实施 1、使用条件: 检验数全部0; 解答列至少一个元素 0; 2、实施对偶单纯形法的基本原则: 在保持对偶可行的前提下进行基变换每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。,3、计算步骤: 建立初始单纯形表,计算检验数行。, 基变换: 先确定换出变量解答列中的负元素(一般选最小的负元素)对应的基变量出基; 即,相应的行为主元行。,然后确定换入变量原则是:在保持对偶可行的前提下,减少原始问题的不可行性。 如果,(最小比值原则),则选 为换入变量 , 相应的列为主元列 , 主元行和主元列交叉处的元素 为主元素。,若 ,要计算最小比值吗?为什么?,按主元素进行换基迭代(旋转运算、枢运算),将主元素变成1,主元列变成单位向量,得到新的单纯形表。 循环以上步骤,直至求出最优解。,3、举例用对偶单纯形法求解LP:,化为标准型 ,将两个等式约束两边分别乘以-1,得,以此形式进行列表求解,满足对偶单纯形法的基本条件,具体如下:,0 0 -3/5 -8/5 -1/5,0,cj-zj,0 1 -1/5 -2/5 1/5 1 0 7/5 -1/5 -2/5,2/5 11/5,x2 x1,-3 -2,-2 -3 -4 0 0 x1 x2 x3 x4 x5,cj xj b,XB,CB,最优解: X*=(11/5,2/5, 0, 0, 0)T, 最优值: minW= -maxZ* = -11/5(-2)+2/5(-3)= 28/5,4、举例用对偶单纯形法求解LP:,化为 标准型 ,将三个等式约束两边分别乘以-1,然后 列表求解如下:,最优解是Y*=(5/3,1/3,0,0,1)T, 目标函数最优值为

温馨提示

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

评论

0/150

提交评论