学位论文 > 优秀研究生学位论文题录展示

线性规划一种概率意义下的多项式算法

作　者: 王凤霞
导　师: 夏少刚
学　校: 东北财经大学
专　业: 数量经济学
关键词: 线性规划单纯形法改型算法多项式算法
分类号: O221.1
类　型: 硕士论文
年　份: 2005年
下　载: 174次
引　用: 0次
阅　读: 论文下载

内容摘要

线性规划问题在社会实践中的应用非常广泛。对于求解该问题,自单纯形法被提出以来,它一直是实际应用中极其有效的计算方法。但在理论上,单纯形法被证明是指数复杂性的。寻找线性规划问题的多项式时间算法,是多年来人们追求的目标。Khanchian的椭球法和Karmarkar的投影尺度法,证明了线性规划问题确实存在多项式算法。但实践表明,这两种方法理论上的优越性并不能在实际应用中得以实现。考虑到单纯形法的实际运算效果与理论分析两方面的矛盾,人们提出,能否有一种单纯形法的改型是多项式算法?这成为近年来不少学者研究的热点。本文尝试给出一种单纯形法的改型算法,它在概率意义下是多项式时间算法。经过分析,运用本文所给出的算法来求解线性规划问题,在约束方程个数m≥27时,以及决策变量个数,n≥2m的情况下,至多迭代m+8次,即可使得到线性规划问题最优解的概率超过0.9864。这对于求解线性规划最优解问题,是很理想的结果。全文共分四部分: 第一章,概述线性规划的基本理论,发展历史以及经济意义; 第二章,介绍求解线性规划问题的有效算法——单纯形法的基本思想和计算步骤,并指出其存在的问题; 第三章,给出求解线性规划最优解问题的一种概率意义下的多项式时间算法,详细阐述该算法的基本思想、算法步骤,以及相应的理论说明和迭代次数的概率分析,并举例说明其计算效果; 第四章,对本文主题思想以及提出的算法进行总结。

全文目录

引言  7
第一章线性规划概述  7-13
  1.1 线性规划简史  7-8
  1.2 线性规划问题及其数学模型  8-9
  1.3 线性规划问题解的一般理论  9-10
  1.4 对偶理论及经济意义  10-13
第二章单纯形法概述  13-19
  2.1 基本思想  13-15
  2.2 计算步骤  15-16
  2.3 单纯形法补遗  16-18
    2.3.1 单纯形法的开始  16
    2.3.2 进出基变量的相持及突破  16-17
    2.3.3 多重最优解  17-18
  2.4 计算复杂性向题  18-19
第三章一种改型算法  19-31
  3.1 基本思想  19-21
  3.2 算法步骤  21-25
  3.3 几点理论说明  25-26
  3.4 迭代次数分析及算例说明  26-31
第四章结论  31-32
参考文献  32-34
后记  34-35

线性规划一种概率意义下的多项式算法

内容摘要

全文目录

相似论文