基于亏基的摄动原始单纯形Ⅰ阶段算法  

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

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

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

出　　处：《数学的实践与认识》2013年第13期161-167,共7页Mathematics in Practice and Theory

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

摘　　要：通过摄动技术来使问题强制获得对偶可行性,执行亏基对偶单纯形算法得到一个原始可行基,并采用修正的主元规则,以充分发挥这两种算法的优势,从而为亏基原始单纯形算法提供一个新的I阶段算法,以使其进一步克服退化所带来的困扰.初步的数值试验表明,亏基和摄动两种算法优势的结合,能有效地克服退化的影响,能有效地减少总迭代次数和运行时间,其效率远远优于传统两阶段单纯形算法.This article Makes problems compulsory for dual feasibility through the per- turbation technique, carries out deficiency dual simplex algorithm to get a original feasible, and adopts the modified primary rules, in order to give full play to the advantages of these two kinds of algorithms, so as to provide a new Phase-1 algorithm for deficient-basis algo- rithm and make the further overcome the degradation caused by problems. Our numerical results show that the deficient-basis and perturbation algorithm is the combination of the advantages, can effectively overcome the influence of the degradation, and reduce the total iterations and operation time effectively, its efficiency is far superior to the traditional two stage simplex algorithm.So this is a very attractive new approach being full of promise.

关 键 词：线性规划 单纯形法 亏基 退化 摄动 主元规则 

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