- 1、本文档共14页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
关于运筹学对偶单纯形法方法:设原问题maxz=CXAX=bX≥0设B是一个基,令B=(P1,P2,…,Pm),它对应的变量为
XB=(x1,x2,…,xm)当非基变量都为零时,可以得到XB=B-1b。若在B-1b中至少有一个负分量,设(B-1b)i0,并且在单纯形表的检验数行中的检验数都为非正,即对偶问题保持可行解,它的各分量是1、对应基变量x1,x2,…,xm的检验数是σi=ci–zi=ci-CBB-1Pi=0,i=1,2,…,m2、对应非基变量xm+1,…,xn的检验数是σj=cj–zj=cj-CBB-1Pj?0,j=m+1,…,n第2页,共14页,星期六,2024年,5月每次迭代时,将基变量中的负分量xl取出(换出变量),去替换非基变量中的xk,要求在所有检验数仍保持非正(对偶问题可行性)的前提下,进行基变换。从原问题来看,经过每次迭代,原问题由非可行解往可行解更靠近,当原问题得到可行解时,便得到了最优解(原问题、对偶问题)。注意:1.对偶单纯形法不是解对偶问题的单纯形法,而是应用对偶原理求解原问题最优解的一种方法。当然,当求解得到原问题的最优解的同时,也就得到对偶问题的最优解。2.在具体计算中,不另外构造单纯形表格,而是在原始问题的单纯形表格基础上进行对偶处理。第3页,共14页,星期六,2024年,5月对偶单纯形法的计算步骤:(1)根据线性规划问题,列出初始单纯形表,检查b列的数值,若都为非负,并且检验数都为非正,则已得到最优解。停止计算;若b列的数值至少还有一个负分量,检验数保持非正,那么进行计算。(3)确定换入变量:检查xl所在行的各系数alj(j=1,2,…,n)。若所有的alj?0,则无可行解,停止计算。(2)先确定换出变量:若min{(B-1b)i|(B-1b)i0}=(B-1b)l对应的基变量xl为换出变量。(实际上,可取任何一个取负值的基变量作为换出变量。取最小的含义是尽快)第4页,共14页,星期六,2024年,5月若存在alj0,(j=1,2,…,n),计算按θ规则所对应的非基变量xk为换入变量(保持对偶问题解的可行性)。(4)以alk为主元素,进行迭代,即进行矩阵行变换。得新的单纯形表。重复(1)-(4)步,直到求出最优解为止。为什么要用下式来确定换入变量呢?原因如下:第5页,共14页,星期六,2024年,5月第6页,共14页,星期六,2024年,5月第l行变成:行变换将Pk变成单位向量,因为bl0,一定要求bl/alk?0,要选主元素alk0。检验数变成(行变换)要保证可行性,就要有?jnew?0,j=1,…,n),,1,,,0,,0,1,...0,,0,(ln1lklklmlklklaaaaaabLLLL+),,0,,,0,,0,,0,,0(ln11klknklklmmlkkaaaaasssss---++LLLL第7页,共14页,星期六,2024年,5月令T={j|alj0}当j?T时,alj?0,从而?jnew=?j-alj/alk?k0,满足可行性。当j?T时,?jnew=?j-alj/alk?k=alj[?j/alj-?k/alk]由于?j,?k,alk,alj均小于0,从而上述括号内的比值均大于0。又由于alj0,为保证?jnew?0,(j?T)故只要选取就能有方括号内大于等于0,从而?jnew?0。第8页,共14页,星期六,2024年,5月解:先将这问题转化(此时b可以是负的),以便得到对偶问题的初始可行基maxz=-2x1-3x2-4x3-x1-2x2-x
您可能关注的文档
- 运动和能的形式.ppt
- 青少年特征与常见心理问题辅导 (2).ppt
- 钢筋混凝土植筋国家规范.ppt
- 霍乱的预防和控制.ppt
- 金属材料的焊接性和焊接结构的设计.ppt
- 难治性高血压 (2).ppt
- 诗歌鉴赏送别诗优秀.ppt
- 连续性血液净化治疗的应用.ppt
- 问题肌肤的五步分析销售篇.ppt
- 课题化学元素与人体健康课件课件.ppt
- 两个相干源产生波具有3b chmc.pdf
- wifi高性能模块ce fcc rohs认证-xrf report电子档.pdf
- linux pci multiport installation manual多端口安装手册.pdf
- 二章基本概念理论.pdf
- 互联网工程任务组ietfs turnerrfc5940 txt.pdf
- mtz0数学高级证明集合关系群mathematics paper 3 sets relations and groups french.pdf
- 网上书店需求规格说明.pdf
- 系统测试用例pcweb终端.pdf
- apv1 keil环境下接口兼容问题.pdf
- 2023届江西省八所重点中学高三3月联考英语试题(原卷版).docx
文档评论(0)