【作者】 高成志；

【导师】 夏尊铨；

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

【摘要】 1984年,Aabby、Broyden及Spedicato共同研究开发了一类用于求解线性方程组与非线性方程组的投影算法——ABS算法。随后二十多年的发展,ABS算法扩展到可以求解最小二乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。而线性丢番图方程组及不等式组的求解是实际应用中经常遇到的一类问题,在物流、运输中起着重要的作用,于是对线性丢番图方程组及不等式组的求解就显得尤为必要。本文在ABS的框架下,系统地研究了线性丢番图方程组及不等式组的解法。 本文的研究工作分为五个部分,首先介绍了ABS算法的研究进展和ABS软件的概况,其次对线性丢番图方程组的解法做了系统的阐述,接着给出了求解线性丢番图不等式组的求解算法,随后给出了求解超定线性丢番图方程组及不等式组的修正ABS算法,最后给出了用MATLAB编写的相关ABS算法程序。所取得的成果如下: 1.第二章,我们系统地分析了当前求解线性丢番图方程组的方法:Rosser算法和Forterbacher算法,求解线性丢番图方程组的方法:EMAS算法和Conteiean算法。 2.第三章,详细分析了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法,并给出一算例说明了隐式LU与隐式LX算法在整数域与实数域内的一个差别。 3.第四章给出了求解线性丢番图不等式组的ABS算法及其在整线性规划中的应用。 4.第五章给出了求解超定线性丢番图方程组和不等式组的修正ABS算法。 5.附录中给出了用MATLAB编写的相关ABS算法程序。更多还原

【Abstract】 In 1984, Abaffy, Broyedn 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 and inequations appear often in modeling and practical application, which play an important role in the transportation. So it is particularly necessary to find out the solution of linear Diophantine equations and inequations. This paper is devoted to studying the linear Diophantine equations and inequations under the ABS environment.In this thesis, five parts are considered. Firstly, the development of ABS algorithms and the ABS software are outlined;secondly, the approaches for linear Diophantine equations are illuminated in detail;thirdly, ABS algorithms for solving linear Diophantine inequations and their application in integer linear programming are given;fourthly, the modified ABS algorithms for solving overdetermined linear Diophantine equations and inequations are presented;finally, the programs coded by MATLAB for some corresponding ABS algorithms are given. The main results obtained in this thesis can be summarized as follows:1. In chapter two, the methods for single Diophantine equation are analyzed, such as Rosser algorithm and Fortenbacher algorithm;so are the methods for linear Diophantine equations, such as EMAS algorithm and Contejean algorithm.2. In chapter three, the integer implicit LU algorithm and the interger implicit LX algorithm are analyzed in detial;furthermore, an example is given to illustrate the difference of the implicit LU algorithm and the implicit LX algorithm between real number field and integer field.3. Chapter four gives ABS algorithms for solving linear Diophantine inequations and their application in integer linear programming.4. Chapter five presents the modified ABS algorithms for solving linear overdetermined linear Diophantine equations and inequations.5. The programs code by MATLAB for some corresponding ABS algorithms are given in appendix.更多还原