基于最钝角列规则的单纯形法研究开题报告

全文总字数：1021字

1. 研究目的与意义

1947年，美国数学家G.B.Dantzig 提出线性规划模型及单纯形法，标志着这个学科的诞生。20世纪40年代电子计算机的问世，使线性规划和单纯形法迅速发展并付诸应用；同时作为一个基础分支，催生和推动了非线性规划，网络流和组合优化，随机优化，整数规划乃至整个运筹学和决策管理科学的形成发展。

主元规则是单纯形法的灵魂和表征。不同规则产生不同的顶点序列，实质决定了求解问题所需的迭代次数。因而主元规则对于单纯形算法的效率有决定性意义，是多年来单纯形法研究的热点。几何上，从可行域一个顶点出发而终止于最优顶点的一系列首尾相连的边构成一条路径，通常有许多路径通向最优顶点。显然，理想的主元规则应让单纯形迭代取最短路径，以使得所需迭代次数最少。目前尚未找到如此理想的规则，也不知道是否存在，因而，去研究行之有效的主元规则是非常有必要的。

2. 国内外研究现状分析

1947年，美国数学家g.b.dantzig提出线性规划的一般数学模型和求解线性规划问题的通用算法单纯形法。这一算法的提出标志着这个学科的诞生。20世纪40年代电子计算机的问世，使线性规划的迅速发展并付诸应用。

1979年，前苏联数学家l.g.khachiyan提出了求解线性规划问题的第一个多项式时间算法（椭球算法），实现了一次重大的理论突破，可惜该算法在实际中表现不佳，远不能与单纯形法媲美。

1984 年，美国贝尔电话实验室的印度数学家 n.karmarkar 提出了一种有效求解线性规划问题的多项式时间内点算法karmarkar 投影尺度算法，karmarkar法的提出在线性规划领域具有极大的理论意义。与椭球法不同，这个新算法不仅在最坏情况下在时间复杂度上优于单纯形法，在大型实际问题中也有潜力与单纯形法竞争。这一方法的提出掀起了一股内点法的研究热潮。如1986年，megiddo提出的原对偶( primaldual)路径跟踪法。同年，gill等人第一次把用于非线性规划的对数障碍函数法用于线性规划, 并证明了对数障碍函数法和karmarkar投影法是等价的。1989年，adler等发表了从原问题的对偶问题出发的对偶仿射比例调节法。1990 年，印度学者 v.ch venkaiah 阐述了一种新的内点算法投影矩阵不变内点算法。但内点法不能达到精确的顶点解，也不能热启动，因而不能直接应用于整数规划问题的求解，因而单纯形法在实际中仍占有不可替代的位置。

3. 研究的基本内容与计划

研究内容：

（1）研究线性规划的计算方法，在传统的主元规则基础上，借鉴部分计价规则、最陡边规则、近似最陡边规则等主元规则计算方法，寻找效率高的主元规则。

（2）研究表格i阶段算法和i阶段算法最钝角列规则，及与人工变量的区别。比较新算法和传统算法的区别。寻找实例，证明所提算法的有效性。

4. 研究创新点

新算法和传统算法相比降低了每次迭代的时间复杂性，减少运行时间和迭代数，具有竞争性，使算法具有更高的效率。算法具有明显的几何意义和良好的实际表现。迄今的数值试验结果十分令人鼓舞, 表明新算法是很有前途的。很有希望能在稀疏数据结构下实现, 以适用于大规模稀疏问题的求解。