ABS Algorithms For Solving Linear Diophantine Equations And Inequations

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.