求解线性方程组及不等式组的ABS方法

论文摘要

1984年，由Aabby，Broyden及Spedicato[23][28]提出了一类用于求解线性方程组与非线性方程组的投影算法—ABS算法。随后的二十多年的发展中，ABS算法用于求解最小二乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。而线性Diophantine方程组及不等式组，尤其是超定线性不等式组的求解是实际应用中经常遇到的一类问题，在物流、运输中起着重要的作用。本文在ABS的框架下，介绍了线性Doiphantine方程组及不等式组的解法，并重点研究了超定线性不等式组的一种ABS解法。本文为三个部分，第一章介绍了ABS算法的研究进展和ABS软件的概况；第二章给出了基本的ABS算法和几个性质，介绍了一类特殊的ABS算法—隐式LU算法，并系统地分析了当前求解线性Diophantine方程组的方法：EMAS算法；第三章给出了求解不定线性不等式组的ABS算法及其在整线性规划中的应用，并详细研究了一种求解超定线性不等式组的ABS算法，附有相应例题与其MATLAB算法程序加以验证。

论文目录

• 摘要
• Abstract
• 1 引言
• 1.1 ABS算法的历史背景与软件的进展
• 1.1.1 ABS算法的历史背景
• 1.1.2 ABS算法软件的进展
• 1.2 线性Diophantine方程的研究发展
• 1.3 本文的研究工作
• 2 预备知识
• 2.1 ABS算法的研究
• 2.1.1 基本ABS算法
• 2.1.2 ABS算法的几个性质
• 2.1.3 隐式LU算法及性质
• 2.2 求解线性Diophantine方程组的两种方法
• 2.2.1 Rosser算法
• 2.2.2 EMAS算法
• 3 求解线性不等式组的ABS方法
• 3.1 求解不定线性Diophantine不等式组的ABS算法
• 3.1.1 利用EMAS算法间接求解不定线性Diophantine不等式组的详细推导
• 3.1.2 利用不定线性Diophantine不等式组间接求解整线性规划
• 3.2 求解超定线性不等式组的ABS算法
• 3.2.1 求解超定线性不等式组的详细推导
• 3.2.2 算法及数值实验
• 3.2.3 例3.1中隐式LU算法的MATLAB程序
• 4 今后工作展望
• 参考文献
• 致谢