优化人工变量单纯形算法提高计算效率

本文主要探讨了一种改进的无人工变量单纯形算法，该算法由高培旺针对Arsham算法进行了优化设计，旨在提高线性规划问题的求解效率。首先，算法的关键改进在于非基变量的选择策略。它不再像传统的单纯形方法那样随机选取一个非基变量作为候选，而是根据简约价值系数（Reduced Cost）的绝对值大小，从大到小逐列搜索，优先选择那些能显著降低目标函数值的非基变量加入基变量集。这个步骤一直持续到找到非正简约价值系数的变量，从而确保每一步的优化都是朝着目标函数减小的方向进行。 其次，算法引入了一个关键的临界值概念，即目标函数的当前值与最优值的平均值。在每次单纯形迭代过程中，如果目标函数的值超过了这个临界值，算法会重新进行非基变量的选择和加入基变量集的过程。这种动态调整的方式有助于避免陷入局部最优解，提高了算法的全局搜索能力。 作者通过在计算机上对24个标准测试问题进行了详尽的数值试验，结果显示，与经典的单纯形算法相比，改进后的算法所需总迭代次数显著减少，特别是在22个问题上，计算时间明显节省。这意味着该算法具有更高的计算效率和稳定性，尤其是在处理大规模或复杂线性规划问题时，表现出了优于Gao的另一种改进算法的性能。 本文提出的新算法在优化策略和性能上做出了实质性改进，对于提高线性规划问题的求解速度和精度具有实际价值。关键词包括线性规划、单纯形法、第一阶段问题、人工变量和基变量集，这些都反映了研究的核心内容和方法论。通过这种方法，研究人员能够在实际应用中更好地利用资源，解决复杂的问题，并且提升整个行业的计算效率。