目标超平面算法：一种原始-对偶单纯形方法

"该文介绍了一种针对目标超平面上的原始-对偶单纯形算法，旨在提高线性规划问题的求解效率。作者高培旺提出，在已知目标最优值的情况下，首先通过一次迭代到达目标超平面找到对偶可行基，随后运用Samaras等人提出的原始-对偶算法在此平面上进行对偶迭代。为了减少计算工作量，文章采用了无比较检验方法选择枢轴列，并为防止算法在原始可行点退化时可能出现的循环现象，引入了MBU对偶单纯形算法进行迭代，确保对偶间隙的严格缩小。通过中大规模数值实验，证明了该算法相对于传统单纯形算法在大多数情况下具有更少的迭代次数和执行时间，计算效率更高。该研究适用于线性规划、多目标线性规划以及模糊线性规划等领域，对原始-对偶单纯形算法的优化有着重要意义。" 本文探讨的是线性规划中的优化算法，特别是原始-对偶单纯形算法的改进。作者关注的焦点是当目标最优值已知时如何更有效地解决问题。传统的单纯形算法通常沿着原始或对偶路径进行迭代，但原始-对偶单纯形算法结合了两者的优势，提供了更大的灵活性。文中提到的算法创新在于，它首先通过一次迭代直接将问题映射到目标超平面上，找到对应的对偶可行基，然后在此基础上应用Samaras等人的算法进行对偶迭代。 为了提升效率，该算法在选择枢轴列时避免了代价高昂的比较检验。此外，考虑到Samaras算法在原始可行点退化时可能陷入循环，作者引入了MBU对偶单纯形算法，以加速迭代并减少对偶间隙，确保算法的收敛性。实验结果显示，该改进后的算法在处理各种规模的问题时，相比于经典单纯形算法，其迭代次数和执行时间均有所减少，计算效率显著提高。 此研究对于那些拥有目标最优值信息的线性规划问题尤其有价值，如第一阶段单纯形算法中的辅助目标函数问题。它不仅扩展了线性规划算法的应用范围，还为解决多目标和模糊线性规划问题提供了新的思路。这项工作对于优化理论和实践领域都有着积极的贡献。