![运筹学对偶单纯形法_第1页](http://file4.renrendoc.com/view5/M00/2D/14/wKhkGGYbQ7-AWoy-AAGqCZmlN0U420.jpg)
![运筹学对偶单纯形法_第2页](http://file4.renrendoc.com/view5/M00/2D/14/wKhkGGYbQ7-AWoy-AAGqCZmlN0U4202.jpg)
![运筹学对偶单纯形法_第3页](http://file4.renrendoc.com/view5/M00/2D/14/wKhkGGYbQ7-AWoy-AAGqCZmlN0U4203.jpg)
![运筹学对偶单纯形法_第4页](http://file4.renrendoc.com/view5/M00/2D/14/wKhkGGYbQ7-AWoy-AAGqCZmlN0U4204.jpg)
![运筹学对偶单纯形法_第5页](http://file4.renrendoc.com/view5/M00/2D/14/wKhkGGYbQ7-AWoy-AAGqCZmlN0U4205.jpg)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
第六节对偶单纯形法1可编辑ppt本节内容安排对偶单纯形法的求解思路对偶单纯形法的求解步骤2可编辑ppt对偶单纯形法是根据对偶原理和单纯形法的原理而设计出来求解原LP的一种方法。采用的技术是在原问题的单纯形表格上进行对偶处理。注意:对偶单纯形法不是求解对偶问题的单纯形法。一对偶单纯形法的求解思路(一)什么是对偶单纯形法3可编辑ppt1单纯形法中原问题(max)的最优解满足的条件:(1)是基本解(2)可行解(XB=B-1b≥0);(3)检验数C-CBB-1A0,-CBB-1≤0即YAC,Y0即对偶解可行
(二)普通单纯形法4可编辑ppt2普通单纯形法的求解思路:
从满足(1),(2)的一个初始基本可行解出发(此时原LP问题中,b列保持≥0,对偶的解一般为非可行基解),通过逐步迭代,增大原目标函数值,每一步迭代,都得到一个基本可行解,并且逐步迭代实现检验数行≤0(对偶解可行)。0迭代到(3)得到满足,即所有检验数≤0,此时,原问题的基可行解达到最优时,对偶的基解由不可行达到可行,得到的这个基可行解也是对偶问题的最优解。5可编辑ppt3普通单纯型法的求解过程:对原问题的一个基可行解,判别是否所有检验数非正cj-zj0(j=1,…,n);若是,又基变量中无非零人工变量,即找到问题最优解,基变量中含有非零人工变量,则无最优解;若否,再迭代,找出相邻的目标函数值更大的基可行解,并继续判别,只要最优解存在,就一直迭代下去,直到找出最优解为止.6可编辑ppt
1对偶单纯形法求解思路:换个角度考虑LP求解过程从满足(1)(3)的一个非可行基解(检验数行保持≤0)出发,(此时对偶问题的解一般为可行解),通过逐步迭代直至(2)得到满足,即直到实现到b列所有的值≥0,原问题的解在迭代过程中从非可行解变成可行解,最终达到最优解,此时,对偶问题也达到最优解。单纯形法中原问题的最优解满足的条件:(1)是基本解;(2)可行解(XB=B-1b≥0);(3)检验数C-CBB-1A0,-CBB-1≤0即YAC,Y0即对偶解可行(三)对偶单纯形法7可编辑ppt普通单纯形法对偶单纯形法前提是原问题可行
优化条件两种方法都从原问题的基解出发前提是对偶可行
优化条件2两种方法的联系:YAC,Y08可编辑ppt原问题基可行解最优解判断对偶问题的可行解对偶问题最优解判断对偶单纯形法基本思路普通单纯形法基本思路9可编辑ppt3对偶单纯形法的使用条件:①原问题的初始基解的检验数全部≤0;②b列至少一个元素<0;
4实施对偶单纯形法的基本原则:
在保持对偶可行的前提下进行基变换——每一次迭代过程中取出基变量中的一个负分量作为换出变量去替换某个非基变量(作为换入变量),使原始问题的非可行解向可行解靠近。10可编辑ppt第一步:构造初始单位阵,确定原问题(max)的初始基B,使所有检验数Cj-Zj=σj=Cj-CBB-1Pj≤0,即Y=CBB-1(b列的值)是对偶可行解,建立初始单纯形表。第二步:可行性检验。检验b列和σj行(即检查基变量的取值)若bi≥0(XB=B-1b≥0),σj≤0,
则原问题得到最优解,计算停;若bi<0,σj≤0,则用对偶单纯形法进行换基迭代.
二对偶单纯形法的步骤:11可编辑ppt第三步
先确定换出变量解答列(b列)中的负元素对应的基变量出基,相应的行为主元行。一般选最小的负元素出基,即若min{(B-1b)i|(B-1b)I<0}=(B–1b)l则选取xl为换出变量.
检验第l行中非基变量xj的系数αlj,若所有的αlj≥0,则LP问题无可行解,(下面进行说明),此时计算结束。否则转下步12可编辑ppt当bl<0,而对所有j=1,…,n,有alj
0,则原问题无可行解。证明:xl+al,m+1xm+1+…+al,nxn=bl因alj
0(j=m+1,…,n),又bl<0,故有xl<0,即不可能存在xj
0(j=1,…,n)的解,故原问题无可行解,此时对偶问题的目标函数值无界。13可编辑ppt若有:Min{cj–zj/αlj|αlj<0,xj为非基变量}=ck–zk/αlk则确定xk为换入变量,相应的列为主元列,标出主元素αlk
,应用矩阵的初等行变换得到新的单纯形表。第四步:若对于bl<0,且有alj<0,
则确定换入变量应用最小比值原则目的:是在保持下一个对偶问题的基解可行的前提下,减少原始问题的不可行性。下面进行说明根据最小比值原则:14可编辑pptalk为主元素xk为进基变量[]设下一个表中的检验数为(cj-zj),则15可编辑ppt(1)对alj
0,因cj-zj
0,故,又因主元素alk<0,故有,所以(cj-zj)
0;(2)对alj<0,因,故有(cj-zj)
0;所以,(cj-zj)0(j=1,…,n)则有:16可编辑ppt
第五步:用换入变量替换换出变量,得到一个新的基,对新的基再检查是否所有
如果是,得原问题的最优解;如果否,回到第一步再重复计算,直到检验数行非正,基列非负,得到最终表.17可编辑ppt例6
应用对偶单纯型法求解下面的线性规划问题18可编辑pptCBXBbx1x2x3x4x5cj-2-3-400-1-2-110-21-301x4x500-2-3-400cj-zj-3-4min{σj/αlj|αlj<0}x5换出变量x1换入变量0-5/21/21-1/21-1/23/20-1/2x4x10-20-4-10-1-12bx5x4x3x2x1XBCBcj00-4-3-2cj-zjmin{σj/αlj|αlj<0}x2换入变量8/52x4换出变量19可编辑pptbx5x4x3x2x1XBCBcj00-4-3-2-2/5-1/57/5011/5-2/5-1/510x1x2-2-3-1/5-8/5-3/500cj-zj11/52/5bi≥0,σj≤0得到最优解为:X*=(11/5,2/5,0,0,0)T对偶问题最优解为:20可编辑ppt例:
用对偶单纯形法求解下面线性规划
解:构造对偶单纯形表进行迭代,21可编辑ppt从最后的表可以看到,B-1b列元素中有-2<0,并且,-2所在行各元素皆非负,因此,原问题没有可行解。22可编辑ppt原问题可以从非可行解开始(即初始解可以是非可行解),在构造初始单位阵时,不需要加人工变量,简化计算.对偶单纯形法的特点:灵敏度分析和整数规划常借助于对偶单纯形法分析.使问题处理简单.变量多,约束条件少的问题,在迭代过程中计算工作量小,
因此,可以把变量少,约束条件多的LP问题转化成变量多,约束条件少的对偶问题,再用对偶单纯形法求解.23可编辑ppt
对偶单纯形法的局限性:很难找到初始可行基,很少单独使用.初始单纯形表的检验数行很难满足小于或等于零的要求,即满足检验数行对应的对偶问题的解是可行解.24可编辑ppt对于原问题为最小化时,选取换出变量的原则不变,选取换入变量时作相应改变:
σj≥0
min{σj/αlj|αlj>0,xj为非基变量}=σk/αlk注意:若xl为换出变量,所有αlj≤0,则原问题无可行解。25可编辑ppt初始可行基例:用对偶单纯形法求解线性规划问题:对偶问题的初始可行基26可编辑ppt换出换出min{σj/αlj|αlj<0}45y2换入变量27可编辑ppt28可编辑ppt最优解29可编辑ppt对偶单纯形法与原始单纯形法内在的对应关系原始单纯形法对偶单纯形法前提条件所有bi≥0所有bi≥0?最优性检验所有所有换入、出基变量的确定先确定换入基变量后确定换出基变量先确定换出基变量后确定换入基变量原始基本解的进化可行最优非可行可行(最优)30可编辑ppt单纯形法和对偶单纯形法步骤是是是是否否否否所有所有得到最优解计算计算典式对应原规划的基本解是可行的典式对应原规划的基本解的检验数≤0所有所有计算计算以aek为中心元素进行迭代以alk为中心元素进行迭代停没有最优解没有最优解普通单纯形法对偶单纯形法31可编辑ppt例用对偶单纯形法求解minz=2x1+4x2+6x3
s.t.
2x1-x2+x3≥10
x1+2x2+2x3≤122x2-x3≥4x1,x2,x3≥0解:将问题化为:maxz′=-2x1-4x2-6x3
s.t.-2x1+x2-x3+x4=-10
x1+2x2+2x3+x5=12-2x2+x3+x6=-4xj≥0(j=1,2,…,6)
检验数ccBxB-2-4-6000
x1x2x3x4x5x6
000x4x5x6-21-11001220100-21001-2-4
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 推动销售团队建设和绩效管理三篇
- 2023年电力工程项目评价分析报告
- 2023年双丙酮丙烯酰胺项目评估分析报告
- 2024年竞聘竞岗个人演讲稿
- 2024年服务员竞聘领班演讲稿
- 【正版授权】 IEC 62435-5:2017 EN-FR Electronic components - Long-term storage of electronic semiconductor devices - Part 5: Die and wafer devices
- 09、初中数学.一元一次方程的应用题(二).第09讲.教师版
- 2024年印尼涂料(油漆)添加剂市场竞争态势与及未来趋势预测报告
- 【正版授权】 IEC 62396-2:2012 EN Process management for avionics - Atmospheric radiation effects - Part 2: Guidelines for single event effects testing for avionics systems
- 2024年印度锂电池负极材料行业状况及未来发展趋势报告
- 中层管理人员竞聘试题大全
- 2022-2023学年高一语文期末测试卷(统编版必修下册)(一)原卷
- MOOC 系统解剖学-河北医科大学 中国大学慕课答案
- 2024年河南省焦作市中考数学一模试卷
- MOOC 概率统计和随机过程-南京邮电大学 中国大学慕课答案
- 2024年安徽省合肥市庐阳中学八年级下册数学期末检测试题含解析
- 2024年天津市金钰国有资本管理有限公司招聘笔试参考题库附带答案详解
- 防人身伤害重点要求专项理论考试试题及答案
- 电大专科《行政组织学》期末考试试题及答案
- 大学英语(二)智慧树知到期末考试答案2024年
- 脊髓损伤的康复治疗研究进展
评论
0/150
提交评论