基于最陡边规则的亏基对偶Ⅰ阶段算法  

A Phase-I Algorithm Based on the Basis Deficiency Perturbation Primal Simplex Method

作　　者：马艳琴[1] 卜春霞[2] 潘平奇[3] 

机构地区：[1]黄河科技学院电子系,河南郑州450063 [2]郑州大学数学系,河南郑州450001 [3]东南大学数学系,江苏南京211102

出　　处：《数学的实践与认识》2013年第10期196-200,共5页Mathematics in Practice and Theory

基　　金：国家自然科学基金(61174085);河南省科技厅基础与前沿技术研究资助项目(102300410058)

摘　　要：将摄动算法和亏基原始单纯形算法相结合,采用最陡边的列主元规则,以充分发挥这两种算法的优势,从而为亏基对偶单纯形算法提供一个新的I阶段算法,以使其进一步克服了退化所带来的困扰.初步的数值试验表明,所提出的算法能有效地减少总迭代次数,其效率不仅远远优于传统的原始两阶段单纯形算法,且优于原有的亏基原始单纯形算法,是一个非常吸引人而充满希望的新尝试.Combine the perturbation primal simples algorithm and deficient-basis algorithm to bring a dual feasible basis, overcome computational difficulties yielding from degeneracy. Preliminary computational experiments show that it requires less iterations overall, and it is superior not only to the conventional simplex algorithm but the deficient-basis algorithm. So this a very attractive new approach being full of promise.

关 键 词：线性规划 单纯形法 亏基 退化 摄动 LU分解 

分 类 号：O221.1[理学—运筹学与控制论]