线性规划的一种新算法——直接搜索迭代法

A NEW ALGORITHM BY DIRECT SEARCH ITERATION FOR LINEAR PROGRAMMING

本文提出一种新的线性规划迭代算法．它把一般线性规划问题化为一个只含不等式约束的标准形．然后从标准形的任一可行点开始直接进行迭代（不添加松弛变量），即可求出最优解．粗估本算法计算性能在高维时至少不亚于Ｋａｒｍａｒｋａｒ法等内点法，低维时也可与单纯形法相比，且迭代过程无误差积累．

In this paper, we present a new algorithm for linear programming. According to this algorithm, a general problem of linear programming is turned into a normalized form in which the constraint conditions are only inequality constraints. Then the optimal solution can be found by iterative computing from any feasible point, and no relaxation variable is needed. By a roughly estimating, the computation performance of the algorithm should not be inferior to the Karmarkar algorithm, or other inner point methods algorithm in the higher dimensional conditions, and should be equal to the simplex method algorithm in the lower dimensional conditions. No acccumulated error occurs in the iterative process, and a good performance has been shown in the preliminary computing tests on a small scale.