法向消元和线性规划强多项式算法
来源期刊：中南大学学报(自然科学版)2003年第1期
论文作者：彭岳林 彭猛
文章页码：102 - 107
关键词：线性规划；最优解集；投影；序结构；强多项式算法
Key words：linear programming; set of optimal solutions; projects; order construction; strong polynomial algorithm
摘 要：为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.
Abstract: In order to solve linear programming problem, the authors find the optimal solution set, turn the method from point iteration into the normal direction elimination, turn the process from finding one optimal solution point by point into finding the optimal solution set dimension by dimension. The results show that the polynomial algorithm has less time complexity than O(mn3) for linear programming.
