LU分解与亏基摄动对偶结合的线性规划新算法

"基于LU分解的亏基摄动对偶阶段算法_马艳琴.pdf" 文章主要探讨了一种结合了LU分解的亏基摄动对偶阶段算法，该算法旨在优化线性规划问题中的对偶单纯形算法，特别是针对退化问题。退化是指在单纯形迭代过程中，某些基变量变得极度接近于零，导致算法效率降低，甚至可能陷入无穷循环。为了解决这一问题，作者提出了新的第一阶段算法。 在传统单纯形法中，如果初始基不满足可行性条件，通常需要引入人工变量使问题变得可行，但这会增加迭代次数，降低算法效率。退化现象进一步恶化了这一情况。为克服退化，学者们提出了多种策略，例如字典序规则和Bland规则，但它们在实际应用中并不总是表现出理想的性能。 文章特别提到了潘平奇教授在1999年提出的对偶摄动单纯形算法，该算法无需人工变量，可以从任意基开始迭代，尤其适用于处理高度退化的线性规划问题。这种算法提高了算法的效率，并且在数值实验中表现出色。 在此基础上，马艳琴、张利利和卜春霞三人将对偶摄动思想与亏基单纯形算法相结合，创建了一种新的第一阶段算法，利用LU分解来加速计算过程。LU分解是一种常用的矩阵分解方法，它可以将矩阵分解为一个下三角矩阵和一个上三角矩阵的乘积，从而简化线性系统的求解。 新算法的核心在于，通过LU分解，可以快速地计算出摄动后的对偶问题解，有效地处理退化基，避免或减少因退化导致的迭代次数增加和运算时间延长。实验结果证明，这种基于LU分解的亏基摄动对偶阶段算法不仅优于传统的单纯形算法，而且比原有的亏基单纯形算法更为高效，对于解决退化问题具有显著优势，是线性规划领域的一个有吸引力和希望的新方法。 这项工作为解决线性规划中的退化问题提供了新的思路，即通过结合摄动策略和LU分解优化算法，提高了对偶单纯形算法的效率和稳定性，为未来相关领域的研究和发展奠定了基础。