求解线性规划的对偶算法.pdf

收稿日期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)摘 要单纯形法一般采用行变换进行计算.本文给出了两种列变换的计算方法,一种与原始单纯形法等价,一种与对偶单纯形法等价,本文称之为对偶方法.这两种方法不引入松弛变量或剩余变量,计算规模小,有明显竞争优势.关键词线性规划;原始单纯形法;对偶单纯形法;对偶方法;对偶理论 中图分类号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,即单纯形方法、椭球算法和内点算法.当前,单纯形法与内点法呈现了伯仲难分的态势,内点法在稀疏大规模线性规划领域具有很强的竞争力,而单纯形法在整数规划求解方面具有得天独厚的竞争优势,其本身固有的“热启动”属性及其大规模问题分解技术,使得单纯形法在实践中仍具有一席之地4-5.作为一种广泛应用的方法,单纯形法可划分为原始单纯形法、对偶单纯形法和原始-对偶单纯形法等三种基本类型6-7.在同类单纯形法间的区别主要体现为入基规则或出基规则的区别.目前采用最陡边规则的对偶单纯形法被认为是最具竞争力的单纯形法8.作为一项重要理论,对偶理论无论在理论方面还是在实践方面都对数学规划的发展作出了卓越的贡献,不仅基于此提出了对偶单纯形法、原始-对偶单纯形法、运输单纯形法、网络单纯形法等多种强有力的算法,而且其本身蕴含的经济理论催生了影子价格理论这一诺贝尔经济学奖的杰作,值得指出的是,博弈论的创立也与对偶理论密切相关9.文献1 0 提出了一种采用检验数替换价值系数的单纯形法,这种方法原理简单,不仅有助于提高单纯形法的计算效率,而且能够使得单纯形法的一些性质和特征变得显而易见,使得一些结论的理论解释和数学证明变得一目了然.本文的研究表明,这种方法有助于提出单纯形法的新变种.在本文中,应用检验数替换价值系数单纯形法的算法思想,提出了两个求解线性规划的新算法.这两个方法计算思路独特,已有的单纯形法都是基于行变换进行计算的,而这两种方法是基于列变换且在对偶问题上进行迭代的.理论证明,这两个新算法分别等价于原始单纯形法和对偶单纯形法,鉴于其均是在它们的对偶模型上进行计算的,故称它们分别是原始单纯形法和对偶单纯形法的对偶方法.众所周知,一个线性模型总伴随着一个对偶模型.本文的工作表明,一个求解方法同时也将伴随着对偶方法,故认为是对数学规划对偶理论的一个新发展.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 对单纯形法的改进主要基于如下定理.定理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.步骤3 根据最大检验数规则或别的规则确定入基变量,再根据规则确定出基变量,进而确定主元.步骤4 基于主元进行矩阵变换,便可得到新的基可行解.步骤5 把模型的价值向量改变为k,置k=k+1,转入步骤2.显然上述方法,在每次迭代中均用检验数替换了价值系数,故称为检验数替换价值系数的单纯形法.该方法确实极大地简化了检验数的计算过程.不仅如此,应用定理1和上述方法的计算思想还可以得到原始单纯形法和对偶单纯形法的对偶方法,其理论基础是:(i)由于原模型的价值系数和对偶模型的资源系数相对应,因而在原模型中以检验数替代价值系数,相当于在对偶模型中以原模型的检验数替代其资源系数;(i i)原始单纯形法和对偶单纯形法每次迭代计算的是原模型,它们的对偶方法每次迭代计算的是对偶模型.为了方便论述,特把原有的原始单纯形法和对偶单纯形法称为原方法(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也具有普适性的应用价值.方便起见,模型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 进行矩阵列变换,得到新模型或新表(约束条件的符号保持为)(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.之所以把上述新方法称为原始单纯形法的对偶方法,理由有如下几点:(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列作为处理列,进行矩阵变换可得新的模型模型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均非负,故为最优解.根据步骤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.501-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为原始单纯形法初始表所对应模型的对偶模型.第二,对偶方法选取基行的原则和原始单纯形法选取入基变量的规则是一致的.第三,对偶方法选取基列的规则和原始单纯形法的规则是一致的.第四,对偶方法进行的矩阵变换也与原始单纯形法是一致的.第五,原始单纯形法最优解判定的规则是所有检验数非正,对偶方法则要求所有资源系数非正.第六,原始单纯形法总是维持资源系数非负,对偶方法则维持所有价值系数非负.总之,两者的区别是,一个采取行形式,一个采取列形式,但相应的数值总相同.因而,两者方法是等价的.故命题成立.对原始单纯形法及其对偶方法进行比较,可得到如下有趣的结论,如下结论1 在原始单纯形法的最优表中,若第h列变量为基变量,则在对偶方法最终得到的模型(最优模型)或表中第h行为基行.结论2 原始单纯形法所求解的模型要么存在最优解要么存在无界解,对偶方法所求解的模型要么存在最优解要么无解.事实上,当使用对偶方法求解时,只要出现下述约束条件,即可判定问题无解,即ai1x1+ai2x2+ai nxnbi,其中所有技术系数非正,而资源系数bi为正数.尽管原始单纯形法与它的对偶方法等价,但对偶方法不仅适用的模型有所差别,而且求解思路也截然不同.求解思想为:如果定义所有变量取零值时为零解,则对偶方法的求解过程就是把一个零解由非可行解转化为可行解的过程.5 原始单纯形法之对偶方法的实施及其优势该方法是基于模型3进行计算的,仅要求所有的价值系数和变量均非负即可.对于这一类模型,新方法无需引入松弛变量或剩余变量就可进行计算,可以直接判定是否有最优解或无解.反之,原始单纯形法一般需要引入松弛变量或剩余变量把模型3标准化后才可求解,当不存在初始基可行解的情形下还需要使用大M法或两阶段方法.故该方法不仅计算直接简便,而且在计算规模和效率都具有优势.模型3也方便使用对偶单纯形法求解,但仍需要引入松弛变量或剩余变量进行计算,将增大计算规模,这样一来新方法同对偶单纯形法相比也具有优势.不仅如此,新方法也能够解决一般性的线性规划问题.实施原始单纯形法的前提条件是,必须基于线性规划的标准形式且同时有初始基可行解.无疑上述标准形式的对偶问题即为模型3,因而新方法可通过求解线性规划的对偶问题进行求解.当不存在初始基可行解时,原始单纯形法需要引入人工变量借助大M法或两阶段方法来求解.对于大M法,人工模型的对偶模型中任一对偶变量y要么满足y-M要么满足y 0,无法满足模型3所有变量为非负的要求.为此,当y-M时,只需作简单变换y=y-M即可,这样一来新方法也可求解一般性的线性规划问题.注意到,此时两种方法具有同样的计算规模,仅仅差别是一个为行变换、一个为列变换,计算效率是同样的.综合上述,新方法相对于原始单纯形法和对偶单纯形法均体现出了明显的竞争优势.6 对偶单纯形法的对偶方法及其特点不仅原始单纯形法存在对偶方法,对偶单纯形法同样也存在对偶方法.仿照原始单纯形法的对偶方法,可直接得到对偶单纯形法的对偶方法.首先给出采用检验数替换价值系数的对偶单纯形法.这个方法基于如下的初始单纯形表5第3期 韩伟一:求解线性规划的对偶算法表4 对偶单纯形法的初始单纯形表价值系数c1c2cnCBXBbx1x2xncB1xB1b1a1 1a1 2a1ncB mxB mbmam1am2am n检验数12n其中xB i为第i行的基变量,xB i为其价值系数,约定所有检验数均非正,而所有资源系数不要求全非负,基变量形成的矩阵为单位阵.根据上表,可给出对偶单纯形法如下步骤1 置k=0,B0=Imm,给出初始基可行解.步骤2 计算检验数向量k,根据最优解判定规则,在获得最优解或发生无解的情形下结束算法,否则转入步骤3.步骤3 由最小资源系数规则或其它规则先确定出基变量,再根据规则确定入基变量,进而确定主元.步骤4 基于主元进行矩阵变换,便可得到新的基可行解.步骤5 把模型的价值向量改变为k,置k=k+1,转入步骤2.对偶单纯形法的对偶方法基于如下模型模型1 0m i n=C X.s.t.A Xb,X0.其中所有资源系数均非正,而所有价值系数不一定全非正.为了方便阐述,对偶单纯形法的对偶方法如下:步骤1 如果所有的价值系数都大于等于0,则已经获得最优解,转到步骤5.否则选取最小价值系数所在行,作为处理列,假设为第t行.步骤2 设处理列的向量为pt,则按照如下规则确定所处理的行ar t=m i nkbkak tak t0 则第r行作为处理行.步骤3 进行矩阵列变换,得到新模型或新表(约束条件的符号保持为)(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.比较对偶单纯形法及其对偶方法,也可得到如下有趣的结论,如下结论3 在对偶单纯形法的最优表中,若第h列变量为基变量,则在对偶方法最终得到的模型(最优模型)或表中第h行为基行.结论4 对偶单纯形法所求解的模型要么存在最优解要么无解,而对偶方法所求解的模型要么存在最优解要么存在无界解.事实上,当使用对偶方法求解时,只要某列的价值系数为负,但所在列的各技术系数非负,即可判定6大 学 数 学 第3 9卷存在无界解.仿照定理2的证明,也可证明对偶单纯形法与其对偶方法是等价的,但对偶方法体现了截然不同的求解思路:在对偶方法中,零解始终是可行解,它采取了把一个零解由非最优解转化为最优解的求解过程.对偶单纯形法的对偶方法非常适合求解模型1 0这样的线性规划问题,避免引入松弛变量、剩余变量和人工变量,既不扩大计算规模,而且计算直接简便.不仅如此,如果一个线性规划问题适合采用对偶单纯形法求解,则此对偶方法也可通过求解问题的对偶模型进行求解.两种方法具有同样的计算规模,主要区别是一个为行变换、一个为列变换,故计算效率是相同的.上述两点说明,相对于对偶单纯形法,它的对偶方法更具有竞争优势.7 列变换的一般结论在前文提出的两种对偶方法中均涉及了列变换.下面讨论列变换的理论性质引理1 在线性规划的等式约束间开展行变换形成的新模型与原模型具有同样的可行解.证 行变换表现为两种基本形式:(i)某行乘以一个非零数,形成新的等式约束;(i i)某行通过加上另一行的倍形成新的等式约束.这意味着任意可行解代入新约束等式仍然成立,因而命题成立.定理3 基于模型5采用列变换形成的新模型与原模型不具有同样的可行解,但新模型的对偶模型与原模型的对偶模型却具有同样的可行解.证 模型5如下m i n=C X.s.t.A Xb.对于任意变量xi,可增加xi为任意实数的约束条件.增加了约束条件后的模型无疑与模型5等价,其相应的对偶问题为模型1 1m a x=Y b.s.t.Y A=C,Y0.其中Y为对偶变量向量.这意味着在模型5中进行的列变换等价于在模型1 1的等式约束间进行的行变换.根据引理1,命题得证.如上的定理3进一步说明了两种对偶方法求解的正确性.可得到如下的推论推论1 两种对偶方法形成的新模型与原始模型均不具有同样的可行解,但它们的对偶模型总是与原模型的对偶模型具有同样的可行解.两种方法得到的最优解均为零解,显然不是原模型的最优解.8 结 论本文对检验数替换价值系数来实施单纯形法的思想进行了探讨.与其说给出了原始单纯形法与对偶单纯形法的对偶方法,不如说给出了两类新的线性规划求解方法.这两个新方法主要通过列变换求解对偶模型进行计算,对于一般性的线性规划问题,可取得和原始单纯形法、对偶单纯形同样的计算效率.不仅如此,在一些特殊形式的问题(模型3和模型1 0)上,两个对偶方法因为不需要引入松弛变量或剩余变量,既直接方便,又可减小计算规模、提高计算效率.因而,两个对偶方法相比于原始单纯形法与对偶单纯形法更具竞争优势.作为重要的理论创新,本文第一次提出了如下观点:不仅线性规划模型存在对偶模型,而且求解线性规划的方法也可存在对偶方法,这无疑将进一步丰富和拓展线性规划的理论研究.致谢 作者非常感谢相关文献对本文的启发以及审稿专家提出的宝贵意见.7第3期 韩伟一:求解线性规划的对偶算法 参 考 文 献1 李炜.线性优化及其扩展M.北京:国防工业出版社,2 0 1 1:1 7 2-1 8 5.2 KHA CH I ANLG.Ap o l y n o m i a l a l g o r i t h mi n l i n e a rp r o g r a mm i n gJ.S o v i e tM a t h e m a t i c sD o k l ady,1 9 7 9,2 0(1):1 9 1-1 9 4.3 KMAMA R KA RN.An e wp o l y n o m i a l t i m ea l g o r i t h mf o rl i n e a rp r o g r a mm i n gJ.C o m b i n a t o r i c a,1 9 8 4,4(4):3 7 3-3 9 5.4 K ON S T AN T I N O SP,N I KO L AO SS,G e o r g eS.An e we f f i c i e n tp r i m a l d u a l s i m p l e xa l g o r i t h mJ.C o m p u t e r s&O p e r a t i o n sR e s e a r c h,2 0 0 3,3 0:1 3 8 3-1 3 9 9.5 潘平奇.线性规划计算M.北京:科学出版社,2 0 1 2:1 0 0-1 0 9.6 杨静蕾,张建勇,杨君泺.线性规划单纯形法的三种实现形式探析J.大学数学,2 0 2 0,3 6(4):6 8-7 3.7 张建中,许绍吉.线性规划M.北京:科学出版社,2 0 0 2:9 3-1 0 7.8 T AN O M,M I YA S H I R O R,K I TAHA R A T.S t e e p e s t-e d g er u l ea n di t sn u m b e ro fs i m p l e xi t e r a t i o n sf o ran o n d e g e n e r a t eL PJ.O p e r a t i o n sR e s e a r c hL e t t e r s,2 0 1 9,4 7(3):1 5 1-1 5 6.9 D ONA L DC A,D AV I DIS.T h eC o m p u t a t i o no fS h a d o w P r i c e si nL i n e a rP r o g r a mm i n gJ.J o u r n a lo ft h eO p e r a t i o n a lR e s e a r c hS o c i e t y,1 9 8 2,3 3(6):5 5 7-5 6 5.1 0 韩伟一.单纯形法检验数的新计算方法J.大学数学,2 0 2 1,3 7(1):1 0 2-1 0 7.T h eD u a lM e t h o dt oS o l v eL i n e a rP r o g r a mm i n gHAN W e i y i(S c h o o l o fE c o n o m i ca n dM a n a g e m e n t,H a r b i nI n s t i t u t eo fT e c h n o l o g y,H a r b i n1 5 0 0 0 1,C h i n a)A b s t r a c t:S i m p l e xm e t h o d sa r eg e n e r a l l yb a s e do nr o wt r a n s f o r m a t i o n.T w on e ws i m p l e xm e t h o d sb a s e do nc o l u m nt r a n s f o r m a t i o na r ep r o p o s e d.I t i sp r o v e dt h e o r e t i c a l l yt h a to n em e t h o di se q u i v a l e n tt op r i m a ls i m p l e xm e t h o da n dt h eo t h e r i se q u i v a l e n t t od u a l s i m p l e xm e t h o d.S o t h e ya r e c a l l e da sd u a lm e t h o d.T w om e t h o d sd o nt n e e d t o i n t r o d u c e s l a c kv a r i a b l e sa n ds u r p l u sv a r i a b l e s,h a v eas m a l l c o m p u t a t i o n a l s c a l ea n do b v i o u sc o m p e t i t i v ea d v a n t a g e.K e yw o r d s:l i n e a rp r o g r a mm i n g;p r i m a l s i m p l e xm e t h o d;d u a l s i m p l e xm e t h o d;d u a lm e t h o d;d u a l t h e o r y8大 学 数 学 第3 9卷