|
|||||
|
|
| 法向消元和线性规划强多项式算法 | |
| 作者姓名： | 彭岳林 彭猛 |
| 作者单位： | 中南大学数学科学与计算技术学院,湖南,长沙,410083 |
| 摘 要： | 为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法. |
| 关 键 词： | 线性规划 最优解集 投影 序结构 强多项式算法 |
| 文章编号： | 1005-9792(2003)01-0102-06 |
| 修稿时间： | 2002-04-29 |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |