求解线性丢番图方程组的ABS方法与WinABS03的研究

【作者】 邹美凤；

【导师】 夏尊铨；

【作者基本信息】 大连理工大学 ， 运筹学与控制论， 2004， 硕士

【摘要】 1984年，Abaffy、Broyden及Spedicato共同研究开发了一类用于求解线性方程组与非线性方程组的投影算法—ABS算法。随后二十多年的发展ABS算法扩展到可以求解最小二乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。线性丢番图方程组的求解是实际应用中经常遇到的一类问题，在物流、运输中起着重要的作用，从而对线性丢番图方程解的探讨变得尤为必要。本文在ABS的框架下系统的研究线性丢番图方程组的解法。 本文的研究工作分三个部分，首先介绍了ABS算法的研究进展和ABS软件的概况，其次对线性丢番图方程组的解法作了系统的阐述，最后给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法并介绍了在ABS软件方面的部分工作。所取得的成果如下： 1．第二章，我们系统的分析了当前求解单个线性丢番图方程的方法：Rosser算法和Forterbacher算法，求解线性丢番图方程组的的方法：EMAS算法和Contejean算法。 2．第三章在ABS算法的基础上给出了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法，讨论了相应的ABS性质，并讨论了复杂性分析及其应用。 3．第四章改进了WinABS01的输入界面，网页介绍和安装技术研制的结果，给出了新的ABS软件—WinABS03和ABSDLL03的使用解释更多还原

【Abstract】 In 1984, Abaffy, Broyden and Spedicato developed a kind of projection algorithms for linear and nonlinear equations - ABS algorithms. Throughout the following twenty years, ABS algorithms have been extended to solve the least squares, the inequality systems, linear programming and nonlinear programming with linear constraints etc. Linear Diophantine equations appear often in modeling and practical application, which play an important part in transportation. So it is particularly necessary to find out the solution of linear diophantine equation. This paper is devoted to studying the linear diophantine equation systematically under the ABS environment.In this thesis, three parts are considered. Firstly we outline the development of ABS algorithms and the ABS software; Secondly, the approaches for linear Diophantine equations are illuminated in detail; Finally we present the LLIU algorithm and the IILX for linear Diophantine equations, at the same time my work in ABS software is given. The main results obtained in this thesis can be summarized as follows:1. In chapter two, we analyzed the methods for single linear Diophantine equations: Rosser algorithm and Fortenbacher algorithm; the methods for linear Diophantine equations: EMAS algorithm and Contejean algorithm.2. In chapter three, the DLU and IILX algorithms for linear Diophantine equations are given based on the ABS algorithms. Corresponding properties, complexity and their application are discussed.3. Chapter four improves the input interface, net page introduction and installation, the usage of WinABS03 and ABSDLL03 is presented.更多还原