含自由变量LP问题的改进单纯形法

《含自由变量LP问题的改进单纯形法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、第21卷第1期2012年2月运筹与管理OPERATIONSRESEARCHANDMANAGEMENTSCIENCEV01．21，No．1Feb．2012含自由变量LP问题的改进单纯形法张劲松，李红(九江学院理学院，江西九江332005)摘要：对于含自由变量的LP问题，为了得到比单纯形法⋯更有效的算法，通过研究在单纯形法迭代过程中，将自由变量化为非负变量再实施运算的规律，提出一种能节省存贮空间和提高运算速度的改进单纯形法。数值实验表明新算法是有效的。关键词：运筹学；LP问题；单纯形法；自由变量中图分类号：0221．1文章标识码：A文章编号：1007—3221(20i2)01．0053．04I

2、mprovedSimplexMethodaboutLinearPrOgramminawithFreeVariableZHANGJin'song，LIHong(CollegeofScience，JiujiangUniversity，Jiujiang332005，China)Abstract：ForLinearProgrammingwithfreevariables，toobtainmoreeffectivealgorithmsthansimplexmethod，throughtheresearchintotheoperationruleoffreevariablesaftertheyaret

3、urnedintonon—negativevariablesintheprocessofiterationonsimplexmethod，weofferanimprovedsimplexmethodthatcansavestoragespaceandincreaseoperationspeed．Anumericalexperimentindicatesthenewalgorithmiseffective．Keywords：operationalresearch；linearprogramming；simplexmethod；freevariable0引言考虑含自由变量的LP问题：严孑：c‰

4、{s．t．o■=bfi=1，⋯，m(1)l茗f芝O．『=1，⋯，q(1sqsn)其中戈=(菇l，．··，戈。)7，c=(c1'．一，c。)’，口：为mXn实矩阵A的第i个行向量，不妨设秩A=m，D={菇I口；T戈=b；，i=1，⋯，m；Xj≥O，．『=1，⋯，q}≠妒，同时A中已含有二个单位矩阵，，b；≥0(i=1，···，m)。对问题(1)，由[2]对自由变量‰(k=q+1，⋯，n)作变换菇。=x／一茗”。(茹：≥o，算f≥0)，即可将其化为非负变量，从而启动单纯形法。但这样做显然增加了问题的规模。特别是许多生产实践和实际生活中的问题，自由变量的个数很多，这样将使得本来规模就很大的问题再

5、度增大规模。因此，研究扎=x／一髫?(x／≥o，算，≥o)在单纯形法迭代过程中的规律，从而省略这一工作而直接由菇。参与迭代运算，具有重要的现实意义。收稿日期：2010—06．08基金项目：江西省自然科学基A金-(2010GQS0129)；江西省教育厅科技项目(2010GJJl0620)作者简介：张劲松(1970-)，男，江西九江人，讲师，硕士。研究方向：运筹学；李缸(1979．)，女，，社西九江人，副教授，博士，研究方向：运筹学、管理学。54运筹与管理2012年第21卷1算法思想引理1．1若原始LP问题(1)中的自由变量个数大于或等于方程个数，则其对偶问题的自由变量个数小于或等于方程个数。

6、证明若在问题(1)中有n—q芝m，则ms／1．一q，由对偶理论，即对偶问题的自由变量个数m小于或等于方程个数17,一q。证毕。由引理1．1，只需考虑问题(1)所含自由变量个数小于或等于m的情形。定理1．2若含自由变量z；(尼=q+1，⋯，凡)的凹问题(1)有最优解，则必定有茁。(或一龙。)入基，或髫。对应的检验数为零。证明对问题(1)列出初始单纯形表。考察任意一个自由变量钆，若是非基变量，检验数为以，对应的A中列向量为A。。作变换算。=茗’。一菇”。(茗’；-->0，z”。≥0)，则戈’¨茹”。的检验数分别为“、一f。，对应的A中列向量分别为A¨一4。。按最小比值规则确定茗。(s≠k)为人

7、基变量，z，为出基变量，作旋转运算得算’”算”。的检验数分别为铲》，、吨+》。若它们均为零，得证；否则，它们均不为零且互为相反数，必有一个大于零，由最优性准则[31，此时的解不是最优解。依此迭代下去，要消除正的检验数，只有算7¨茗”；人基。而由单纯形表显然有茗’。和一算”。(或一石7。和茗”。)对应的列(包括检验数)完全一致，因此在表中可共用一列。而这两列合并后对应的变量为并’。一戈”。(或一戈’。+算”。)，即为石。(