优化线性规划：无比值检验的新criss-cross算法

"线性规划的无比值检验criss-cross算法是Zionts提出的一种解决线性规划问题的策略，该算法结合了原始问题和对偶问题的迭代，可以生成原始可行解或对偶可行解。不同于传统的两阶段算法，criss-cross算法交替进行原始和对偶迭代。为了提升计算效率，文章提出了一个新的改进版本，即采用无比值检验规则的criss-cross算法。在针对40个小型问题的数值实验中，基于新算法的稠密软件在迭代次数上以2.12的比率优于传统的两阶段方法。该算法的关键在于摒弃了比率测试，从而提高了算法的执行效率。" 线性规划是一种优化技术，用于寻找在一组线性约束条件下的最佳线性目标函数。在解决线性规划问题时，通常有两种主要的方法：单纯形法和内点法。Zionts的criss-cross算法则提供了一种不同的途径，它实际上是一个一阶段算法，通过同时处理原始问题和对偶问题来寻找解。这种交替迭代的方式使得算法在某些情况下能够更快地找到解决方案。 传统的两阶段算法首先确保找到一个可行解（第一阶段），然后在此基础上优化目标函数（第二阶段）。然而，criss-cross算法可以跳过第一阶段，直接寻找可行解或最优解，这显著减少了计算步骤，特别是在问题规模较小或者初始近似解较优的情况下。 无比值检验规则是新criss-cross算法的核心改进。在原算法中，比率测试是判断迭代是否应该继续的一个关键步骤，它比较两个方向上的改善速率来决定下一步的迭代方向。但无比值检验规则可能避免了这个可能导致额外计算的比较过程，从而简化了算法并提升了速度。实验结果显示，新算法在迭代次数上平均节省了约78%（1/2.12），这对于计算密集型问题来说是一个显著的改进。 线性规划问题广泛应用于各种领域，包括工程、经济、管理科学等。更高效的求解方法对于处理大型或复杂问题至关重要。Zionts的criss-cross算法及其无比值检验规则的引入，为线性规划的计算效率提升开辟了新的道路，对于优化领域的研究和发展具有积极的影响。