线性规划解法注记：半单纯形法的改进

"高培旺在《南通大学学报(自然科学版)》2011年第10卷第2期中发表的文章《关于解线性规划问题的一种半单纯形法的注记》，指出了某文献中解线性规划问题的半单纯形法存在错误，并通过理论分析和实例进行了证明。文章进一步探讨了这种所谓的‘半单纯形法’与经典两阶段法之间的本质联系，认为它们实际上是一致的，只是人工变量没有明确表示，且枢轴列的选择标准有所差异。为了优化这种方法，作者对半单纯形法（或两阶段法的第一阶段）的枢轴行和枢轴列选择进行了改进，并通过数值试验显示，改进后的单纯形算法在计算效率上显著优于原半单纯形法。该研究属于自然科学领域，涉及线性规划、基本可行解、单纯形法、半单纯形法和两阶段法等概念。" 这篇文章详细讨论了线性规划问题的求解方法，特别是针对一种被称为“半单纯形法”的算法。线性规划是运筹学中的基础问题，用于优化线性目标函数在一系列线性约束条件下的表现。单纯形法是求解线性规划问题的经典方法，由George Dantzig于1947年提出，它通过迭代过程将非基变量替换为基础变量，直到找到最优解。 文章指出文献中的定理2关于半单纯形法是错误的，作者提供了理论分析和实例来证明这一点。这表明，对于算法的验证和批评是确保数学模型和计算方法正确性的重要环节。此外，作者还揭示了“半单纯形法”与两阶段法之间的关系，两阶段法通常用于处理有不等式和等式约束的线性规划问题，第一阶段是为了构建一个可行解，第二阶段则是寻找最优解。半单纯形法可能只是在形式上隐藏了人工变量，但其核心逻辑与两阶段法相同。 为了提高算法的效率，作者对半单纯形法的枢轴规则进行了改进。枢轴规则是单纯形法中决定下一个进入基和退出基变量的关键步骤，不同的选择策略可以影响算法的性能。通过数值试验，作者证明了改进后的算法在计算速度上优于原半单纯形法，这凸显了算法优化对于实际应用的重要性。 线性规划问题广泛应用于资源分配、生产计划、投资决策等领域，因此优化求解方法具有很高的实用价值。这篇论文不仅揭示了现有方法的不足，还提出了解决方案，对于理解和改进线性规划的算法有着积极的贡献。