优化第一阶段线性规划的对偶单纯形算法

本文主要探讨了一种针对目标超平面的对偶单纯形算法，用于解决线性规划问题的第一阶段。作者高培旺针对具有最优值的辅助目标函数，提出了一种创新的求解策略。首先，他将这个辅助目标函数作为新的约束引入原始的第一阶段线性规划问题中，形成了扩展的线性规划模型。在这个过程中，关键步骤是通过枢轴行的旋转操作，在辅助超平面上寻找一个极顶点。如果找到的极点是可行解，算法则结束；否则，算法会固定在这个辅助超平面上继续迭代。 接下来，算法的核心是对右手项取负值的所有约束进行处理，将它们的和设定为目标约束，通过对偶迭代的方式，使得目标函数的右侧值逐渐增加，同时保持非负约束的可行性。当原本取负值的约束变为可行时，将其从目标约束中移除。这个过程重复进行，直到找到一个可行解或者得出原问题无可行解的结论。 实验部分，作者选择了NerI’LIB和MIPuB测试数据库中的标准中大规模算例，在MATLAB平台上进行了数值试验。结果显示，与传统的单纯形算法相比，这种对偶单纯形算法在大多数情况下能够使用较少的迭代次数和执行时间，从而显示出更高的计算效率。这表明，对于线性规划问题的第一阶段，特别是那些规模较大的问题，这种算法具有显著的优势，值得进一步研究和应用。 关键词包括线性规划、第一阶段辅助问题、单纯形算法、对偶单纯形算法以及目标超平面。通过这篇论文，作者不仅提供了理论上的改进，还展示了其在实际问题求解中的实用价值。