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

全文总字数：1837字

1. 研究目的与意义

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

主元标算法都是针对单纯形算法存在退化现象就如何选择最优入基、离基做出的一系列研究及改进。退化现象是单纯形法一直以来需解决的难题，为了克服退化问题许多学者提出了有限主元规则：扰动法、字典序规则、bland规则等，其中bland规则由于其简单而备受关注，但是这些有限主元规则的实际应用方面并不令人满意，甚至都不能和dantzig规则相比。

1990 年，潘平奇推广了bland有限规则，引人反映目标梯度与约束梯度夹角大小的主元标作为确定变量进基优先性的依据，潘教授的数值试验表明此规则明显优于 bland规则。然而潘平奇的方法仅适用于只含不等式约束的线性规划问题。为便于求解标准线性规划问题，许多学者在其基础上又提出了对偶主元标法。由于对偶主元标法是利用严格互补松弛来推导过度的，针对这一问题，又有学者提出了投影主元标法。1998年,潘平奇提出了亏基的概念,给出了亏基单纯形算法和对偶单纯形算法。由于基的概念是主元算法的基础，这就为进一步改进提供了可能。数值实验表明，亏基的应用效果甚佳,发展前景十分看好。

2. 国内外研究现状分析

线性规划作为最优化的一个分支，是运筹学、决策科学和管理科学最重要的基础，也是最著名的应用最广泛的数学工具之一，催生和推动了非线性规划，网络流和组合优化，随机优化，整数规划乃至整个运筹学和决策管理科学的形成发展。

线性规划的萌芽可以追溯到19世纪20年代。法国数学家j. b. j. fourier于1823年、比利时数学家v. poussin于1911年分别写过一篇涉及线性规划的论文，然而这些孤立的工作没有产生任何影响。1939年，前苏联数学家l. kantorovich在其《生产组织与计划的数学方法》一书中提出解乘数法，已涉及线性规划模型及其求解。f .l .hitchcock于1941年发表了一篇很好的有关运输问题的论文，但一直未受关注，直到40年代末50年代初被重新发现，已是单纯形法问世之后。

人类的实践活动是一切科学理论和方法的原动力第二次世界大战战事的需求极大地推动了科学技术的发展。而怎样运用现有条件取得最大战场利益的现实需求催生了最化和运筹学。1947年，美国数学家 george b. dantzig提出了线性规划模型及单纯形法，一般被认为标志着这个学科的的诞生。单纯形法的计算机实现发端于美国标准局，w .orchard-hays编制了基于单纯形法第一个商业软件，在早期的计算机上求解线性规划问题。

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

研究内容：

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

（2）研究基于最钝角行规则的对偶i阶段算法和表格对偶i阶段算法，比较新算法和传统算法的区别。寻找实例，证明所提算法的有效性。

4. 研究创新点

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