| 法向消元和线性规划强多项式算法 |
| |
| 引用本文： | 彭岳林,彭猛.法向消元和线性规划强多项式算法[J].中南大学学报(自然科学版),2003,34(1):102-107. |
| |
| 作者姓名： | 彭岳林 彭猛 |
| |
| 作者单位： | 中南大学数学科学与计算技术学院,湖南,长沙,410083 |
| |
| 摘 要： | 为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.
|
| 关 键 词： | 线性规划 最优解集 投影 序结构 强多项式算法 |
| 文章编号： | 1005-9792(2003)01-0102-06 |
| 修稿时间： | 2002年4月29日 |
Normal direction elimination and strong polynomial algorithm for linear programming |
| |
| PENG Yue-lin,PENG Meng.Normal direction elimination and strong polynomial algorithm for linear programming[J].Journal of Central South University:Science and Technology,2003,34(1):102-107. |
| |
| Authors: | PENG Yue-lin PENG Meng |
| |
| 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. |
| |
| Keywords: | linear programming set of optimal solutions projects order construction strong polynomial algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
