法向消元和线性规划强多项式算法

• 作者: 彭岳林 彭猛
• 来源期刊: 中南工业大学学报(自然科学版)
• 学科: 工学
• 关键词: 线性规划 最优解集 投影 序结构 强多项式算法
• 年，卷（期）: 2003,（1）
• 所属期刊栏目: 数学
• 页码范围: 102-107
• 页数: 6页
• 分类号: O221.1|O184|TP301.6
• 字数: 7699字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-7207.2003.01.026

摘要

为了求最优集(不只是求零维的最优点),提出了行满秩线性代数方程组的法向消元解法,指出它与点和法向量组的逐次投影等价,并进一步将其发展成最小投影法,用来判定原始等式约束平面和若干坐标超平面的交的可行性;通过逐次投影在等式约束平面上建立序结构,逐维选优和判定可行性,使线性规划单纯形迭代解法所进行的Rn空间中平面组合穷举的计算变成逐次降维的等式约束平面上低维平面的形和位判定的代数计算,得到线性规划问题的低于O(mn3)的强多项式直接算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	彭岳林	中南大学数学科学与计算技术学院	3	11	2.0	3.0
2	彭猛	中南大学数学科学与计算技术学院	1	7	1.0	1.0