论文部分内容阅读
本文将最钝角原理与放松约束的思想相结合，提出了求解标准线性规划问题的“最钝角对偶松弛算法”．先基于最钝角原理略去对偶问题中的部分约束条件得到一个规模较小的子问题，它的原问题有较少的变量．用亏基对偶单纯形方法求得其最优解后，添加略去的变量(作为非基变量)得到一个与原来问题等价的问题，检验相应的解是否为其最优解；如果不是，则它必为一个原始基本可行解，于是可用亏基单纯形法求解得到最优解。
本研究的初步数值试验表明，与传统两阶段单纯形算法相比，本文提出的算法能有效地减少迭代次数；由于其中用于较小松弛子问题的迭代占很大比重，从而就大大降低了求解线性规划问题所需要的CPU时间，新算法对于大规模问题的求解具有潜在的优势，值得进一步研究。