已阅读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. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 自无证建房出售合同(2篇)
- 粘土冰淇淋课件
- 语文单据 课件
- 专题01 字音字形词语(考点串讲)-七年级语文上学期期末考点大串讲(统编版2024·五四学制)
- 第一讲 成长趣事(看图写话教学)-二年级语文上册(统编版)
- 第七讲 做手工(看图写话教学)-二年级语文上册(统编版)
- 西京学院《应用统计学》2021-2022学年第一学期期末试卷
- 西京学院《数字电子技术》2021-2022学年期末试卷
- 西京学院《机械工程测试技术》2021-2022学年第一学期期末试卷
- 冲突 作文 课件
- 工程造价咨询服务质量承诺及保证措施
- 最新种植新病历
- 水联动试车方案(共33页)
- 高效电池片(TOPCon)生产项目可行性研究报告模板-提供甲乙丙资质资信
- INPLAN操作培训PPT课件
- VB和Oracle的链接
- 代理报关委托书
- 小学美术四年级质量检测试卷(共3页)
- 青少年科学调查体验活动分析报告
- 大班科学四季的变化ppt课件
- 建设部211文件
评论
0/150
提交评论