线性规划的最钝角CRISS-CROSS算法

摘要

本文对线性规划的最钝角CRISS-CROSS算法进行了研究。文章认为，Zionts求解线性规划问题的criss-cross算法是一个无须初始可行基的主元算法，它交替地进行原始和对偶迭代。随之，Chang，Terlaky和Wang分别独立的提出了有限的criss-cross算法，可以在有限步终止。Criss-cross算法的优点是不需要第一阶段，可以从任何基开始迭代。可惜的是，此类算法一般所需的迭代次数太多，实际表现并不令人满意。潘平奇提出的无比值检验规则降低了每次迭代的复杂性，而最钝角规则尤以其吸引人的几何意义及实践中突出的表现引人注目。本文的目的是基于最钝角规则建立使用LU分解的新criss-cross算法以进一步提高计算效率。在对25个标准NETLIB试验问题所做的实验中，基于新算法编制的一个稠密软件就迭代次数而言胜过了目前最好的单纯形法软件。

目录

文摘

英文文摘

声明

第一章引言

§1.1综述

§1.2 Zionts'criss-cross算法

§1.3基本概念和定理

第二章LU分解原始单纯形及对偶单纯形算法

§2.1 LU分解原始单纯形算法

§2.2 LU分解对偶单纯形算法

第三章最钝角criss-cross算法

§3.1最钝角规则

§3.2最钝角criss-cross算法表格形式描述

§3.3算法的逆矩阵形式描述

§3.4 LU分解形式算法

第四章数值结果及其分析

§4.1数值试验结果

§4.1.1 60个小问题的数值结果

§4.1.2 NETLIB问题数值结果

§4.2本文的创新之处和今后改进的方向

致谢

参考文献