论文部分内容阅读
本文尝试给出一种单纯形法的改型算法，它在概率意义下是多项式时间算法。经过分析，运用所给出的算法来求解线性规划问题，在约束方程个数m≥27时，以及决策变量个数n≥2m的情况下，至多迭代m+8次，即可使得到线性规划问题最优解的概率超过0.9864。这对于求解线性规划最优解问题，是很理想的结果。全文共分四章：
第一章，概述线性规划的基本理论，发展历史以及经济意义；
第二章，介绍求解线性规划问题的有效算法——单纯形法的基本思想和计算步骤，并指出其存在的问题；
第三章，给出求解线性规划最优解问题的一种概率意义下的多项式时间算法，详细阐述该算法的基本思想、算法步骤，以及相应的理论说明和迭代次数的概率分析，并举例说明其计算效果；
第四章，对本文主题思想以及提出的算法进行总结。