线性规划的无比值检验criss-cross算法  

Ratio-test-free criss-cross algorithm for linear programming

作　　者：颜红彦[1] 潘平奇[2] 

机构地区：[1]南京林业大学理学院,江苏南京210037 [2]东南大学数学系,江苏南京210096

出　　处：《合肥工业大学学报（自然科学版）》2009年第12期1949-1952,共4页Journal of Hefei University of Technology：Natural Science

摘　　要：Zionts提出的求解线性规划问题的criss-cross算法实际是一阶段算法,不过与传统一阶段算法不同,它交替进行原始和对偶迭代,而产生的既可以是原始可行解,也可以是对偶可行解。为了提高计算效率,文章提出了一种采用无比值检验规则的新criss-cross算法,基于新算法编制的一个稠密软件在对40个小问题进行的数值试验中,就迭代次数而言,以2.12的比率胜过了传统的两阶段算法。The criss-cross algorithm for solving linear programming problems presented by Zionts is actually a phase-1 algorithm. Different from classical phase-1 algorithm, it performs primal arid dual iterations alternately until a primal or a dual solution is reached. To improve computational efficiency, a new criss-cross algorithm based on the ratiot-test-free rule is proposed. In computational tests with 40 small problems, a code based on a dense implementation of the proposed algorithm outperformed the classical two-phase algorithm with the total iteration ratio 2. 12.

关 键 词：线性规划 criss—cross算法 无比值检验规则 

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