运筹学对偶单纯形法.ppt

上传人:石*** 文档编号:87136257 上传时间:2023-04-16 格式:PPT 页数:14 大小:637.50KB
返回 下载 相关 举报
运筹学对偶单纯形法.ppt_第1页
第1页 / 共14页
运筹学对偶单纯形法.ppt_第2页
第2页 / 共14页
点击查看更多>>
资源描述

《运筹学对偶单纯形法.ppt》由会员分享,可在线阅读,更多相关《运筹学对偶单纯形法.ppt(14页珍藏版)》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、关于运筹学对偶单纯形法现在学习的是第1页,共14页方法:设原问题 max z=CX AX=b X 0 设B是一个基,令B=(P1,P2,Pm),它对应的变量为 XB=(x1,x2,xm)当非基变量都为零时,可以得到XB=B-1b。若在B-1b中至少有一个负分量,设(B-1b)i 0,并且在单纯形表的检验数行中的检验数都为非正,即对偶问题保持可行解,它的各分量是 1、对应基变量x1,x2,xm的检验数是 i=ci zi=ci-CB B-1Pi =0,i=1,2,m 2、对应非基变量xm+1,xn的检验数是 j=cj zj=cj-CB B-1Pj 0,j=m+1,n现在学习的是第2页,共14页每次

2、迭代时,将基变量中的负分量每次迭代时,将基变量中的负分量xl取出(换出变量)取出(换出变量),去替换非基变去替换非基变量中的量中的xk,要求在所有检验数仍保持非正(对偶问题可行性)的前提,要求在所有检验数仍保持非正(对偶问题可行性)的前提下,进行基变换。下,进行基变换。从原问题来看,经过每次迭代,原问题由非可行解往可行解更靠近,当原问题得到可行解时,便得到了最优解(原问题、对偶问题)。注意注意:1.对偶单纯形法不是解对偶问题的单纯形法,而是应用对偶原理求解原问题最优解的一种方法。当然,当求解得到原问题的最优解的同时,也就得到对偶问题的最优解。2.在具体计算中,不另外构造单纯形表格,而是在原始问

3、题的单纯形表格基础上进行对偶处理。现在学习的是第3页,共14页对偶单纯形法的计算步骤:(1)根据线性规划问题,列出初始单纯形表,检查b列的数值,若都为非负,并且检验数都为非正,则已得到最优解。停止计算;若b 列的数值至少还有一个负分量,检验数保持非正,那么进行计算。(3)(3)确定换入变量:检查xl所在行的各系数alj(j=1,2,n)。若所有的 alj0,则无可行解,停止计算。(2)先确定换出变量:若 min(B-1b)i|(B-1b)i 0=(B-1b)l对应的基变量xl为换出变量。(实际上,可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快)现在学习的是第4页,共14页若存在al

4、j 0,(j=1,2,n),计算按规则所对应的非基变量xk为换入变量(保持对偶问题解的可行性)。(4)以alk为主元素,进行迭代,即进行矩阵行变换。得新的单纯形表。重复(1)-(4)步,直到求出最优解为止。为什么要用下式来确定换入变量呢?原因如下:现在学习的是第5页,共14页现在学习的是第6页,共14页第l行变成:行变换将Pk变成单位向量,因为bl0,一定要求bl/alk0,要选主元素alk0。检验数变成(行变换)要保证可行性,就要有jnew 0,j=1,n),1,0,0,1,.0,0,(ln1lklklmlklklaaaaaabLLLL+),0,0,0,0,0(ln11klknklklmml

5、kkaaaaasssss-+LLLL现在学习的是第7页,共14页令T=j|alj0 当jT时,alj 0,从而jnew=j-al j/a al kk 0,满足可行性。当jT时,jnew=j-al j/a al kk=a al jj/a al j-k/a al k 由于j,k,a al k,a al j均小于0,从而上述括号内的比值均大于0。又由于alj0,为保证jnew 0,(jT)故只要选取就能有方括号内大于等于0,从而jnew 0。现在学习的是第8页,共14页 解:先将这问题转化(此时b可以是负的),以便得到对偶问题的初始可行基 max z=-2x1-3x2-4x3 -x1-2x2-x3+

6、x4=-3 -2x1+x2-3x3+x5=-4 xj 0,j=1,2,3,4,5 建立这个问题的初始单纯形表例:用对偶单纯形法求解:min=2x1+3x2+4x3 x1+2x2+x3 3 2x1-x2+3x3 4 x1,x2,x3 0 现在学习的是第9页,共14页现在学习的是第10页,共14页现在学习的是第11页,共14页则 X*=(11/5,2/5,0,0,0)T为原问题的最优解。同时 Y*=(y1*,y2*)=(8/5,1/5)现在学习的是第12页,共14页对偶单纯形法特点:(1)简化计算:不引入人工变量将线性规划化成标准型,构造初始单纯形表(初始解是非可行解),只要检验数非负(最优检验数),就可以进行基的转换;(2)适于变量多于约束条件:当变量少于约束方程的个数时,可考虑变成对偶问题后,再用对偶单纯形法;(3)局限性:多数问题很难找到检验数为负(最优检验数)的初始可行解。但可用于灵敏度分析中简化计算。?现在学习的是第13页,共14页感感谢谢大大家家观观看看现在学习的是第14页,共14页

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 生活休闲 > 资格考试

本站为文档C TO C交易模式,本站只提供存储空间、用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。本站仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知淘文阁网,我们立即给予删除!客服QQ:136780468 微信:18945177775 电话:18904686070

工信部备案号:黑ICP备15003705号© 2020-2023 www.taowenge.com 淘文阁