A non-monotone Phase-1 method in linear programming  

线性规划非单调一阶段算法(英文)

作　　者：潘平奇[1] 李炜[1] 

机构地区：[1]东南大学数学系,南京210096

出　　处：《Journal of Southeast University(English Edition)》2003年第3期293-296,共4页东南大学学报（英文版）

基　　金：TheNationalNaturalScienceFoundationofChina(199710 14 )

摘　　要：To gain superior computational efficiency, it might be necessary to change the underlying philosophy of the simplex method. In this paper, we propose a Phase-1 method along this line. We relax not only the conventional condition that some function value increases monotonically, but also the condition that all feasible variables remain feasible after basis change in Phase-1. That is, taking a purely combinatorial approach to achieving feasibility. This enables us to get rid of ratio test in pivoting, reducing computational cost per iteration to a large extent. Numerical results on a group of problems are encouraging.为了获取计算的高效率 ,有必要修正单纯形算法的原则 .本文提出了一个新的单纯形一阶段算法 .与传统单纯形算法不同的是 ,新算法不仅不要求目标函数值单调变化 ,且在一阶段的迭代过程中也不必保持变量的可行性 ,而是采用纯组合的方法去达到可行 .这样摆脱了迭代时的比值检验 ,减少了每次迭代的计算工组量 .理论分析及数值计算结果表明新算法的前景令人鼓舞 .

关 键 词：linear programming Phase-1 ratio-test-free pivoting rule 

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