线性规划的两阶段基点迭代转移算法研究

"一种求解LP问题的两阶段基点迭代转移方法* (2014年)，作者：刘道建、黄天民、陈勇，发表于《湖南大学学报(自然科学版)》第41卷第1期，2014年1月，文章编号1674-2974(2014)01-0117-08，关键词包括线性规划、基点转移矩阵、退化、局部正则化、算法，中图分类号0221.1，文献标识码A。" 本文研究的是线性规划（LP）问题的高效求解方法，主要关注的是如何通过基点迭代转移来优化求解过程。线性规划是一种优化技术，用于在满足一系列线性约束的情况下最大化或最小化一个线性目标函数。其几何特性可以在二维平面上直观地表示，即线性规划问题的可行域是一个多边形区域。 作者们提出了一个两阶段基点定向转移搜索方法，该方法基于线性规划的线性和几何平面的双重特性。首先，他们定义了一种特殊基点转移矩阵，这个矩阵用于描述在不同基点之间的转换。转移矩阵的运算使得基点的迭代转移更加有序和定向，从而改进了传统的单纯形法。单纯形法是求解线性规划问题的一种常用方法，通过在单纯形的不同顶点之间迭代，寻找最优解。 第二阶段的定向迭代转移模型建立在第一阶段的基础上，旨在更有效地搜索最优解。模型通过对基点进行定向迭代，避免了无效的或者不必要的转移，提高了算法的效率。 此外，针对线性规划中可能出现的基点退化问题，作者们引入了可行域局部ε-正则化方法。退化基点是指在某些情况下，单纯形中的一个基变量可以为零，导致迭代过程变得复杂甚至停滞不前。通过局部ε-正则化，可以将退化基点转化为非退化基点，确保迭代过程始终是有效的。这种方法有助于消除基点退化对极点转移搜索过程的负面影响，提高算法的稳定性和收敛速度。 这项工作提供了一种新的线性规划求解策略，通过基点的定向转移和退化基点的正则化处理，提高了求解效率和算法的鲁棒性。对于大规模线性规划问题，这样的优化方法尤其具有实际应用价值。