线性规划新算法的改进

《线性规划新算法的改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、高校应用数学学报A辑Appl.Math.J.ChineseUniv.Ser.A2000,15(1):101～106线性规划新算法的改进张敏洪(华罗庚应用数学与信息科学研究中心)(中国科学技术大学研究生院数学部,北京100039)摘　要本文基于算法要简单实用的思想,对一种线性规划新算法中的核心算法进行改进,使其计算方法更简单计算量更少,使整个算法更为可行有效.关键词　基准线(段),切割面,好方向.分类号　(中图)O221;(1991MR)90C05.[1～3]线性规划算法的发展经历了三个主要阶段.最近在《中国科学》上也提出了一种求[4]解线性规划的新算法,此算法的基本思想是

2、在规划问题的可行域中由所建的一个切割面到另一个切割面的不断推进来求取最优解.这种算法的关键在于切割面上的求优,称之为核[5]心算法.由于原核心算法为通用算法主要用的计算方法为二分法和黄金分割法(01618[5]法),使整个算法的计算量很大,计算复杂性无法估计.本文探讨的是如何针对线性规划的特性用一种简单的计算方法来替代二分法和黄金分割法,减少计算量,使算法更加可行有效,且保持原算法的特性.§1　原算法的描述考虑LP的一般型:Tmincxs.t.Ax≥b,x≥0.n　　记可行解集为P={x∈RûAx≥b,x≥0}.首先引入一些概念:knTTkkk(i)基准面:若x∈P,则称

3、超平面{x∈Rûcx=cx}为过x点的基准面,记为Z(x),简记为Zk.kknkkTk(ii)基准线(段):在基准面上,过x的直线L(x)={x∈Rûx=x+tB,cB=0,-∞kkknkkTk

4、x),其中B为n维非零列向量,x(1)=x+t1B,x(2)kk=x+t2B为基准线的端点.k(iii)切割面:超平面0k=L(x)称为切割面.kkTkk(iv)好方向:起点在l(x)上,终点在0k上的向量A,cA<0,则称A为0k上的好方向.原算法的基本思想与计算步骤:k步骤1　从初始可行解x出发.knTTk步骤2　形成基准面:Z(x)={x∈Rûcx=cx}.kkknkk步骤3　确定基准线:在Z(x)上确定一条过x的直线L(x)={x∈Rûx=x+tB,k3Tk3TkkTkkkk3dxk3cx-cxk31icB=0,-∞

5、对确定úcúúcúki=1kkknkkTk的B用二分法求t1,t2,使得l(x)=P∩L(x)={x∈Rûx=x+tB,cB=0,t1≤t≤t2}.kkk步骤4　形成切割面,求出一好方向A,由A与L(x)确定一个超平面0k,使得0k=kL(x).步骤5　切割面0k上求优:Tmincxs.t.x∈P∩0k.k+1得到P∩0k上的最优解x.TkkTk步骤6　决定重复或停止:若满足停机条件,如ûc(tB+qA)û≤F,则停止,其中c(tB+kqA)<0,F为允许误差,F>0;否则k÷=k+1返回步骤1,继续迭代.§2　算法的改进1　切割面上求优——核心算法的改进kkkk假定已从

6、一可行解x建立了一条基准线L(x),给定或求出一好方向A,这里令A为kkk最速下降方向A=-c,则由基准线L(x)上的点沿A方向发射可形成一切割面0k,射线可kkkT表示为x(t,q)=x+tB+qA,q≥0,t1≤t≤t2.在切割面P∩0k上求出使目标函数cx有改k+1进的一个新的最优解x,由此得到一个使目标函数值改进的新可行解.考虑切割面上求优的规划的模型:Tmincxs.t.P∩0k.上述规划模型可视为一个在切割面P∩0k上求优的双层规划问题(BLPk):Tmincx(t,q)t∈[t1,t2],maxqkkks.t.x+tB+qA∈P.0　　不失一般性,假定P是闭

7、集(否则以P的闭包代之),并记P是P的内点集.vTTk0P=P∩0k∩{cx≤cx}-P.vTk引理　定义在点集P上的函数cx,对于在超平面0k上以L(x)为横坐标轴,t为参变©1995-2004TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.张敏洪:线性规划新算法的改进103量的坐标系而言,是单峰凸函数.T这是因为P是凸集与cx是线性函数所决定的.在原算法中,当t固定时,求解下层规划问题:maxqkkks.t.x+tB+qA∈P.kkkTk实际上,就是沿射线x(t,q