"目标超平面上的一种原始-对偶单纯形算法.pdf"
本文主要探讨了一种针对目标最优值已知情况下的线性规划问题的优化算法——目标超平面上的原始-对偶单纯形算法。该算法由高培旺教授提出,旨在提高计算效率并减少迭代次数,特别适用于中大规模的线性规划问题。
线性规划是运筹学中的基础问题,其目标是找到满足一组线性约束条件的变量组合,使目标函数达到最大或最小值。在传统单纯形法中,算法通常沿着单一路径(原始或对偶)进行迭代,但结合原始问题和对偶问题的原始-对偶单纯形算法能提供更灵活的策略,以加速收敛过程。
高培旺教授的算法首先在目标超平面上寻找一个对偶可行基,然后利用Samaras等人提出的原始-对偶算法在此平面上进行迭代。这一方法的一个关键创新在于,在选择枢轴列时采用了无比较值检验方法,减少了计算负担。同时,为了避免Samaras算法在原始可行点退化时可能出现的循环现象,该方法引入了MBU(可能是Modified Bland's Update,即修改后的Bland更新规则)对偶单纯形算法,以确保对偶间隙的严格缩小,从而加速迭代进程。
文中提到的数值试验结果显示,与传统的单纯形算法相比,该新算法在大多数测试案例中表现出更少的迭代次数和执行时间,具有更高的计算效率。这表明,该算法在处理线性规划问题时具有显著优势,尤其对于那些需要高效求解的中大规模问题。
原始-对偶单纯形算法的研究不仅限于单目标线性规划,也扩展到了多目标线性规划和模糊线性规划等领域。这类算法的枢轴准则设计多样性,包括减少原始不可行约束、原始与对偶相互定价以及利用对偶原理进行部分定价等策略,都为算法的优化提供了可能。
Samaras等人的原始-对偶外点算法则引入了变动的原始可行点定价,以避免在极点间的不必要移动,提高了收敛速度。然而,这种算法需要初始时有一个原始可行点和一个对偶可行基,而高培旺教授的改进算法可能解决了这一限制,使其更适应实际应用中的各种初始条件。
"目标超平面上的一种原始-对偶单纯形算法"是一种高效且灵活的求解线性规划问题的方法,通过整合原始和对偶路径,优化枢轴准则,并引入MBU对偶单纯形算法,有效地减少了迭代次数和计算时间,提升了计算效率。这种算法对于解决实际问题,尤其是那些对计算效率有严格要求的中大规模线性规划问题,具有重要的实用价值。