论文部分内容阅读
本文对线性规划的最钝角松弛算法进行了研究。文章首先基于最钝角原理略去部分约束条件,用原始单纯形算法求解由此得到的一个规模较小的松弛子问题;然后再添加原先所略去的约束条件恢复原问题;此时若全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解得到基本最优解。数值试验表明,与传统两阶段单纯形算法相比,本文提出的算法可很有效地减少迭代次数;由于其中用于较小松弛子问题的迭代占很大比重,从而就大大降低了求解线性规划问题所需要的CPU时间,新算法对于大规模问题的求解有明显的潜在优势,是一种非常有前途的新算法。