求解线性规划的对偶算法.pdf
《求解线性规划的对偶算法.pdf》由会员分享,可在线阅读,更多相关《求解线性规划的对偶算法.pdf(8页珍藏版)》请在咨信网上搜索。
1、 收稿日期2 0 2 1-1 0-0 4;修改日期2 0 2 1-1 2-1 7 基金项目国家自然科学基金资助项目(1 2 1 7 1 1 2 1);哈尔滨工业大学研究生教育改革项目(2 2 HX 0 9 0 1)作者简介韩伟一(1 9 7 4-),男,博士,副教授,从事运筹学研究.E-m a i l:w y h a n h i t.e d u.c n第3 9卷第3期大 学 数 学V o l.3 9,.32 0 2 3年6月C O L L E G E MATHEMAT I C SJ u n.2 0 2 3求解线性规划的对偶算法韩伟一(哈尔滨工业大学 经济与管理学院,哈尔滨1 5 0 0 0 1
2、)摘 要单纯形法一般采用行变换进行计算.本文给出了两种列变换的计算方法,一种与原始单纯形法等价,一种与对偶单纯形法等价,本文称之为对偶方法.这两种方法不引入松弛变量或剩余变量,计算规模小,有明显竞争优势.关键词线性规划;原始单纯形法;对偶单纯形法;对偶方法;对偶理论 中图分类号O 2 2 1 文献标识码A 文章编号1 6 7 2-1 4 5 4(2 0 2 3)0 3-0 0 0 1-0 81 引 言线性规划是运筹学的重点研究领域.当前求解线性规划的方法大致可归为三大类型1-3,即单纯形方法、椭球算法和内点算法.当前,单纯形法与内点法呈现了伯仲难分的态势,内点法在稀疏大规模线性规划领域具有很强
3、的竞争力,而单纯形法在整数规划求解方面具有得天独厚的竞争优势,其本身固有的“热启动”属性及其大规模问题分解技术,使得单纯形法在实践中仍具有一席之地4-5.作为一种广泛应用的方法,单纯形法可划分为原始单纯形法、对偶单纯形法和原始-对偶单纯形法等三种基本类型6-7.在同类单纯形法间的区别主要体现为入基规则或出基规则的区别.目前采用最陡边规则的对偶单纯形法被认为是最具竞争力的单纯形法8.作为一项重要理论,对偶理论无论在理论方面还是在实践方面都对数学规划的发展作出了卓越的贡献,不仅基于此提出了对偶单纯形法、原始-对偶单纯形法、运输单纯形法、网络单纯形法等多种强有力的算法,而且其本身蕴含的经济理论催生了
4、影子价格理论这一诺贝尔经济学奖的杰作,值得指出的是,博弈论的创立也与对偶理论密切相关9.文献1 0 提出了一种采用检验数替换价值系数的单纯形法,这种方法原理简单,不仅有助于提高单纯形法的计算效率,而且能够使得单纯形法的一些性质和特征变得显而易见,使得一些结论的理论解释和数学证明变得一目了然.本文的研究表明,这种方法有助于提出单纯形法的新变种.在本文中,应用检验数替换价值系数单纯形法的算法思想,提出了两个求解线性规划的新算法.这两个方法计算思路独特,已有的单纯形法都是基于行变换进行计算的,而这两种方法是基于列变换且在对偶问题上进行迭代的.理论证明,这两个新算法分别等价于原始单纯形法和对偶单纯形法
5、,鉴于其均是在它们的对偶模型上进行计算的,故称它们分别是原始单纯形法和对偶单纯形法的对偶方法.众所周知,一个线性模型总伴随着一个对偶模型.本文的工作表明,一个求解方法同时也将伴随着对偶方法,故认为是对数学规划对偶理论的一个新发展.2 检验数替换价值系数的原始单纯形法线性规划的标准形式如下:模型1m a xz=C X.s.t.A X=b,X0.其中,C=(c1,c2,cn)为价值系数向量,b=(b1,b2,bn)T为资源系数向量,X=(x1,x2,xn)T为决策变量向量,技术矩阵为A,由n个列向量和m个行向量组成,定义如下A=ai jmn=(p1,p2,pn)=(q1,q2,qm)T.文献1 0
6、 对单纯形法的改进主要基于如下定理.定理1 在模型1中,记X(B)为基B对应的基可行解,(B)=C-CBB-1A为基可行解X(B)的检验数向量,令E=(B),则下列的模型2与模型1等价模型2m a xz=E X.s.t.A X=b,X0.设单纯形法共需要p次迭代,第k(0kp-1)次迭代过程中相应的基为Bk,则总有B0=Imm.为了方便,记k(Bk)=(k1,k2,k n)为第k次迭代过程中相应的检验数向量,简写为k.则改进后的单纯形法如下步骤1 置k=0,B0=Imm,给出初始基可行解.步骤2 计算检验数向量k,根据最优解判定规则,在获得最优解或发生无界的情形下结束算法,否则转入步骤3.步骤
7、3 根据最大检验数规则或别的规则确定入基变量,再根据规则确定出基变量,进而确定主元.步骤4 基于主元进行矩阵变换,便可得到新的基可行解.步骤5 把模型的价值向量改变为k,置k=k+1,转入步骤2.显然上述方法,在每次迭代中均用检验数替换了价值系数,故称为检验数替换价值系数的单纯形法.该方法确实极大地简化了检验数的计算过程.不仅如此,应用定理1和上述方法的计算思想还可以得到原始单纯形法和对偶单纯形法的对偶方法,其理论基础是:(i)由于原模型的价值系数和对偶模型的资源系数相对应,因而在原模型中以检验数替代价值系数,相当于在对偶模型中以原模型的检验数替代其资源系数;(i i)原始单纯形法和对偶单纯形
8、法每次迭代计算的是原模型,它们的对偶方法每次迭代计算的是对偶模型.为了方便论述,特把原有的原始单纯形法和对偶单纯形法称为原方法(P r i m a lm e t h o d).原方法和对偶方法的一个显著区别为,原方法均对技术矩阵采用行变换,而对偶方法则采用列变换.3 原始单纯形法的对偶方法主要针对如下模型:模型3m i n=C X.s.t.A Xb,X0.其中价值向量C为非负向量.事实上,上述模型就是下述模型的对偶模型模型4m a xz=C X.s.t.A Xb,X0.其中资源向量b为非负向量.2大 学 数 学 第3 9卷既然模型4引入松弛变量后即可使用原始单纯形法进行求解,因而模型3也具有普
9、适性的应用价值.方便起见,模型3可写为如下形式模型5m i n=C X.s.t.A Xb.其中,A=ai jm(m+n)=(p1,p2,pn)=(q1,q2,qm+n)T,pt(1tn)为列向量,qr(1rm+n)为行向量.为了方便阐述新算法,特给出如下定义定义1 定义约束条件xi0所在的行为变量i的基行.基于模型3,原始单纯形法的对偶方法如下步骤1 如果所有的资源系数都小于等于0,则已经获得最优解,转到步骤5.否则选取最大资源系数所在行,作为处理行,假设为第r行.步骤2设处理行的向量为qr,则按照如下规则确定所处理的列ar t=m i nkckar kar k0 .则第t列作为处理列.步骤3
10、 进行矩阵列变换,得到新模型或新表(约束条件的符号保持为)(i)把技术矩阵A和价值向量C的第t列的元素均除以ar t;(i i)把技术矩阵A的第s(st)列减去第t列乘以ar s/ar t;(i i i)把资源系数所在列减去第t列乘以br/ar t.步骤4 转到步骤1.步骤5 在最终的模型或表中,由m+n个约束条件的后n个约束条件来确定各变量的值,规则为:xi(1in)的最优解为-bm+i.在最终的模型或表中,由m+n个约束条件的前m个约束条件来确定对偶变量的值,规则为:若第k(1km)个约束条件为基行,且相应的约束条件为xh0,则对偶变量yk=ch,否则对偶变量yk=0.之所以把上述新方法称
11、为原始单纯形法的对偶方法,理由有如下几点:(i)新方法求解的模型是原始单纯形法所求解模型的对偶模型;(i i)原始单纯形法采用行变换,新方法采用列变换;(i i i)原始单纯形法保持资源系数总非负,而新方法保持价值系数总非负;(i v)原始单纯形法最终使得检验数均非正,而新方法最终使得资源系数均非正.下面通过例子演示新单纯形法的计算过程例1求解如下线性规划问题模型6m i nz=2x1+3x2.s.t.x1+x23,x1+2x24,x10,x20.解 由于m a x3,4,0,0=4,所以没有取得最优解,则第2行作为处理行,再根据算法的步骤2,计算m i n2/1,3/2=3/2,可知第2列作
12、为处理列,进行矩阵变换可得新的模型模型7m i nz=0.5x1+1.5x2.s.t.0.5x1+0.5x21,x20,x10,-0.5x1+0.5x2-2.由于m a x1,0,0,-2=1,故没有取得最优解,则第1行作为处理行,再根据算法的步骤2,计算m i n0.5/0.5,1.5/0.5=1,可知第1列作为处理列,进行列变换可得新的模型3第3期 韩伟一:求解线性规划的对偶算法模型8m i nz=x1+x2.s.t.x10,x20,2x1-x2-2,-x1+x2-1.在上述模型中所有资源系数均非正,已经获得最优解.此时,可发现x1=0,x2=0为模型8的可行解,由于x1和x2均非负,故为
13、最优解.根据步骤5,原问题的最优解为x1=2,x2=1,对偶问题的最优解为y1=1,y2=1.4 原始单纯形法之对偶方法的正确性证明为了说明上述新方法的正确性,使用文献1 0 提出的检验数替换价值系数单纯法对例1的对偶问题进行求解.相应的对偶问题如下:模型9m a x=3y1+4y2.s.t.y1+y22,y1+2y33,y10,y20.对上述问题引入松弛变量y3,y4形成标准形式,并使用单纯表进行求解,如下表1 第一个单纯形表价值系数3400CBXBby1y2y3y40y3211100y441201检验数3400表2 第二个单纯形表价值系数3400CBXBby1y2y3y40y30.50.5
14、01-0.54y21.50.5100.5检验数100-2表3 第三个单纯形表价值系数100-2CBXBby1y2y3y41y11102-10y2101-11检验数00-2-1比较两个算法的计算结果,可知模型6,7,8分别是表1,2,3中模型的对偶模型.这说明新方法是正确的,也进一步说明了它被称为原始单纯形法之对偶方法的原因.4大 学 数 学 第3 9卷下面给出原始单纯形法之对偶方法的正确性证明.定理2 原始单纯形法的对偶方法可对模型3正确求解.证 首先,模型3为原始单纯形法初始表所对应模型的对偶模型.第二,对偶方法选取基行的原则和原始单纯形法选取入基变量的规则是一致的.第三,对偶方法选取基列的
15、规则和原始单纯形法的规则是一致的.第四,对偶方法进行的矩阵变换也与原始单纯形法是一致的.第五,原始单纯形法最优解判定的规则是所有检验数非正,对偶方法则要求所有资源系数非正.第六,原始单纯形法总是维持资源系数非负,对偶方法则维持所有价值系数非负.总之,两者的区别是,一个采取行形式,一个采取列形式,但相应的数值总相同.因而,两者方法是等价的.故命题成立.对原始单纯形法及其对偶方法进行比较,可得到如下有趣的结论,如下结论1 在原始单纯形法的最优表中,若第h列变量为基变量,则在对偶方法最终得到的模型(最优模型)或表中第h行为基行.结论2 原始单纯形法所求解的模型要么存在最优解要么存在无界解,对偶方法所
16、求解的模型要么存在最优解要么无解.事实上,当使用对偶方法求解时,只要出现下述约束条件,即可判定问题无解,即ai1x1+ai2x2+ai nxnbi,其中所有技术系数非正,而资源系数bi为正数.尽管原始单纯形法与它的对偶方法等价,但对偶方法不仅适用的模型有所差别,而且求解思路也截然不同.求解思想为:如果定义所有变量取零值时为零解,则对偶方法的求解过程就是把一个零解由非可行解转化为可行解的过程.5 原始单纯形法之对偶方法的实施及其优势该方法是基于模型3进行计算的,仅要求所有的价值系数和变量均非负即可.对于这一类模型,新方法无需引入松弛变量或剩余变量就可进行计算,可以直接判定是否有最优解或无解.反之
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 求解 线性规划 对偶 算法
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【自信****多点】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【自信****多点】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。