资源描述：
《求标准线性规划问题的一种截解法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第11卷第2期运筹与管理Vol.11,No.22002年4月OPERATIONSRESEARCHANDMANAGEMENTSCIENCEApr.,2002求标准线性规划问题的一种截解法高培旺(中南大学铁道校区数理力学系,湖南长沙410075)摘要:本文提出了求解线性规划问题的一种新思路,就是通过平行移动目标函数等值面,即改变目标函数作为参数的取值来截取基本可行解,甚至最优解。值得注意的是,本算法可能会克服由退化引起的迭代循环。关键词:标准线性规划;基本可行解;目标函数等值面中图分类号:O22111文章标识码:A文章编号:1007-3221(2002)02-0025-06A
2、Solution-InterceptingMethodforStandardLinearProgrammingGAOPe-iwang(DeptofMathematicsandMechanics,SouthCentralUniversity,Changsha410075,China)Abstract:Thispaperpresentsanewthoughtofinterceptinginitialbasicfeasibleorevenoptimalsolutionsofstandardlinearprogramming(SLP)byparallellymovingtheob
3、jectiveequivalenceplane,i.e.,changingthevaluesoftheobjectivefunctionasaparameter.Itshouldbenotedthatthealgorithmcanovercometheiterativerecurrencecausedbydegeneracy.Keywards:standardlinearprogramming;basicfeasiblesolution;objectiveequivalenceplane.0引言考虑下述标准线性规划问题:T(SLP)maxf=cx(1)s.t.Ax=b(2
4、)x (3)m@n这里,AIR,向量b,c和x有相应的维数且假设rank(A)=m,b .如果一个初始可行基不能从上述(SLP)问题的约束条件(2)中直接观察到,则一般需要通过两阶段法构造一个新[1,2]的线性规划问题来获取。虽然文献[3]引入了一种半单纯形法直接获取初始可行基,但选收稿日期:2001-10-31作者简介:高培旺(1964-),男,湖南永州人,中南大学铁道校区数理系工程师,博士,1999年毕业于北京理工大学,主要从事可靠性工程和运筹学方面的研究。26运筹与管理2002年第11卷取入基变量的准则不同于单纯形法,因而在求最优解时,需要在原来的迭代表上另外加
5、上一行判别数的计算。本文提出了求解标准线规划问题的一种新的思路,就是把目标函数f当作参变量,通过fT取值的变化而使目标函数等值面cx=f平行移动,从而截取初始基本可行解,直至最优解。本算法只需在一张适当的迭代表上执行一个阶段的单纯形迭代过程即可。1算法原理T注意到如果我们把目标函数f当作一个参变量,则目标函数等值面cx=f就会随着f取值的变化而平行移动。为此,我们把目标函数(1)和m个约束等式(2)联立起来,有Tf=cx(4)0=b-Ax由(4),我们可以构造一张初始迭代表(见表1)来启动本算法的迭代过程。表2表1初始迭代表Table2Table1Initialitera
6、tivetableaux,,xbx1,,xq-1fq+1nbxxqb0a01,,a0,q-1a0qa0,q+1,,a0n0b1a11,,a1,q-1a1qa1,q+1,,a1nf0cT,,,,,,,,,,,,,,,,,,,,,0b-A0bmam1,,am,q-1amqam,q+1,,amn接下来,为了移动目标函数等值面截取(SLP)的初始基本可行解,直至最优解。选择f和某一变量xq作一旋转变换得到一张新表,如表2所示。最后,继续一系列的旋转变换来从x中选择m-1个变量进入基变量中。如果存在的话,随着取参变量f的相应值,算法将以截得(SLP)的基本可行解,直至最优解而终止。
7、2算法步骤根据本算法原理,给出算法步聚如下:步骤1:选择cq=max{cj
8、cjX0,a1j>0}作为旋转主元,则在第1行与第q列间执行旋转1[j[nnb1变换获得表2。于是,取,f=cq将使目标函数等值面移动到过约束面Ea1jxj=b1和xja1qj=1b1=0(j=1,2,,,n,jXq)的交点p(0,,0,xq=,0,,0)处。如果所有a1j[0(j=1,2,,,a1qn),很明显,(SLP)无可行解,算法终止。步骤2假设在进行了k-1(1
