线性规划模型预处理的研究与实现

实际应用中的大规模线性规划模型,一般都存在大量的冗余约束,例如:常变量、零变量、非极点变量、多余的非零元素等,在利用已知算法求解之前,如果对这些冗余约束进行化约,就能够缩小问题的规模,并能节省大量的计算机存储空间和运算时间。在预处理时,对这些约束采用不同的处理方法,用鞍点算法和鞍点共轭梯度算法检验这些预处理方法的有效性,并对处理结果进行理论分析,得出了和试验结果相符的正确结论。     

LP鞍点共轭梯度法的研究与实现

在线性规划问题中,为了提高算法的求解速度,快速得到最优解。对鞍点算法,共轭梯度法进行了深入研究与分析。针对鞍点算法在逼近鞍点时收敛速度变慢的缺陷,将计算比较简单且有限步迭代即可收敛的共轭梯度法成功的应用于鞍点算法中形成了一种新的算法—鞍点共轭梯度算法。以c 为开发工具,在计算机上实现了该算法,并编成一个解题系统能够快速求解线性规划问题。实验结果表明相对于鞍点算法,用鞍点共轭梯度算法计算,解题时间效率明显提高。