求解线性丢番图方程组及不等式组的ABS算法
|
摘要
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算法程序。
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.
本文的研究工作分为五个部分,首先介绍了ABS算法的研究进展和ABS软件的概况,其次对线性丢番图方程组的解法做了系统的阐述,接着给出了求解线性丢番图不等式组的求解算法,随后给出了求解超定线性丢番图方程组及不等式组的修正ABS算法,最后给出了用MATLAB编写的相关ABS算法程序。所取得的成果如下:
1.第二章,我们系统地分析了当前求解线性丢番图方程组的方法:Rosser算法和Forterbacher算法,求解线性丢番图方程组的方法:EMAS算法和Conteiean算法。
2.第三章,详细分析了求解线性丢番图方程组的整隐式LU算法和整隐式LX算法,并给出一算例说明了隐式LU与隐式LX算法在整数域与实数域内的一个差别。
3.第四章给出了求解线性丢番图不等式组的ABS算法及其在整线性规划中的应用。
4.第五章给出了求解超定线性丢番图方程组和不等式组的修正ABS算法。
5.附录中给出了用MATLAB编写的相关ABS算法程序。
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.
引文
[1] Rosser J.B. A method of computing exact inverses of matrices with integer coefficient. J. Res. Nat. Bur, 1952, 49: 349-358.
[2] Egervary E. Qufloesung eines homogenen linearen diophantischen Gleichungsystems mit Hilf yon Projektormatrizen. Publ. Math. Debrecen, 1955-56, 4: 481-483.
[3] Weinslock R. Greatest common divisor of several integers and an associated integer Diophantine equation. Amer. Math. Monthly, 1960, 67: 664-667.
[4] Blankinship W A. A new version of the Euclidean algorithm. Amer Math. Monthly, 1963, 70: 742-745.
[5] Bradley G. H. Algorithm and bound for the greatest common divisor of n integers. Community ACM, 1970, 13: 433-436.
[6] Clausen M. and Fortenbacher A. Efficient solution of linear Diophantine equations. J. Symbolic Comput, 1989, 8(1&2): 201-216.
[7] Contejean E. and Devie H. An effcient incremental algorithm for solving systems of linear Diophantine equation. Information and Computation, 1994, 113: 143-172.
[8] Ajili F., Contejean E. Avoding slack varialbes in the solving of linear Diophantine equations and inequations. Theoretical Computer Science, 1998, 173:183-208.
[9] Pottier L. Minimal solutions of linear diophantine systems: boundsand algorithms. In proceedings of the Fourth International Conferenceon Rewriting Techniques and Applications, Como, Italy, 1991, 162-173.
[10] Domenjond Eric. Solving systems of linear diophantine equations. An algebraic approach. In Proc. 16th Mathematical Foundations of Computer Science, Warsaw, LNCS 520, 1991, Springer-Verlag.
[11] 薛方,郑辉,范小寅.线性丢番图方程组的一个数值解法。数学通报,1994,10:45-47.
[12] Esmaeili H., Mahdavi-Amiri N. and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90: 101-115.
[13] Egervary E. On rank-diminishing operations and their applications to the solution of linear equations. ZAMP, 1960, 9: 376-386.
[14] Huang H. Y. A direct method for the general solution of a system of linear equations. JOTA, 1975, 16: 429-445.
[15] Zhao J. Huang's method for solution of consistent linear equations and its generalization. Journal Numerical Mathematics of Chinese Universities, 1981, 3: 8-17.
[16] Abaffy J., Broyden C.G. and Spedicato E. A class of direct methods for linear equations. Nume. Math., 1984, 45: 361-376.
[17] Abaffy J., Spedicato E. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. Ellis Horwood, Chichester, 1989.
[18] Spedicato E., Xia Z. and Zhang L. ABS algorithms for linear equations and optimization. Journal of Computational and Applied Mathematics, 2000, 124:155-170.
[19] Xia Z., Zhang L. ABS algorithms for solving linearly constrained optimization problems via the active set strategy. Ricerca Operativa, 2003, 31: 98-100.
[20] Deng N., Chen Z. The truncated nonlinear ABS algorithm and its convergence property. Computing, 1990, 45: 169-173.
[21] 张立卫,冯恩民,夏尊铨.优化中的ABS算法引论.大连理工大学出版社,1999:25-27.
[22] Bertocchi M., Spedicato E. A vectorized FORTRAN code of the implicit Gauss-Cholesky algorithm of the ABS class. Manual 1/34, LAC, Rome, 1990.
[23] Bertocchi M., Spedicato E. and Vespucci M.T. A vectorized FORTRAN code of the implicit QR algorithm of the ABS class. Manual 1/56, LAC, Rome, 1990.
[24] Bodon E. ABS codes of nonlinear Jhuang, modified Huang and implicit LU algorithms for nonlinear systems of equations. QDMSIA, 2000, 24.
[25] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for determined and underdetermined linear systems, QDMSIA, 2000, 21.
[26] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for overdetermined linear systems, QDMSIA, 2000, 19.
[27] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for KKT linear systems, QDMSIA, 2000, 20.
[28] Bodon E. ABS codes for banded linear systems, Preprint, 2001.
[29] 周奇兵.V1.0/2001 ABS软件的研制(硕士论文),2001.
[30] 刘莹.《ABS SOFTWARE研究的新进展ABSDLLOI&WinABS01》(硕士论文),2001.
[31] 李兴.《隐式LU、LX算法误差分析及ABS软件》(硕士论文),2003.
[32] 邹美凤.《求解线性丢番图方程组的ABS算法与WinABS03的研究》(硕士论文),2004.
[33] Spedicato E., Xia Z. and Zhang L. The implicit LX method of the ABS class. OMS, 1997, 8: 99-110, Also as QDMSIA 2/96.
[34] Spedicato E., Xia Z. and Zhang L. Reformation of the simplex method via the ABS algorithm. AMS Subject Classification(1991): 90C05, 65F05.
[35] Esmaeili H., Mahdavi-Amiri N. and Spedicato E. ABS solutions of a class of linear integer inequalities and integer LP problems. OMS, 2001, 16: 179-192.
[36] Zhao J. ABS algorithms for solving linear inequalities, Report 91/21, University of Bergamo, 1995.
[37] 刘玉龙,求解超定线性方程组的修正ABS算法.徐州师范学院学报(自然科学版),1993,Vol.10.No.3:1-4.
[2] Egervary E. Qufloesung eines homogenen linearen diophantischen Gleichungsystems mit Hilf yon Projektormatrizen. Publ. Math. Debrecen, 1955-56, 4: 481-483.
[3] Weinslock R. Greatest common divisor of several integers and an associated integer Diophantine equation. Amer. Math. Monthly, 1960, 67: 664-667.
[4] Blankinship W A. A new version of the Euclidean algorithm. Amer Math. Monthly, 1963, 70: 742-745.
[5] Bradley G. H. Algorithm and bound for the greatest common divisor of n integers. Community ACM, 1970, 13: 433-436.
[6] Clausen M. and Fortenbacher A. Efficient solution of linear Diophantine equations. J. Symbolic Comput, 1989, 8(1&2): 201-216.
[7] Contejean E. and Devie H. An effcient incremental algorithm for solving systems of linear Diophantine equation. Information and Computation, 1994, 113: 143-172.
[8] Ajili F., Contejean E. Avoding slack varialbes in the solving of linear Diophantine equations and inequations. Theoretical Computer Science, 1998, 173:183-208.
[9] Pottier L. Minimal solutions of linear diophantine systems: boundsand algorithms. In proceedings of the Fourth International Conferenceon Rewriting Techniques and Applications, Como, Italy, 1991, 162-173.
[10] Domenjond Eric. Solving systems of linear diophantine equations. An algebraic approach. In Proc. 16th Mathematical Foundations of Computer Science, Warsaw, LNCS 520, 1991, Springer-Verlag.
[11] 薛方,郑辉,范小寅.线性丢番图方程组的一个数值解法。数学通报,1994,10:45-47.
[12] Esmaeili H., Mahdavi-Amiri N. and Spedicato E. A class of algorithm for Diophantine linear systems, Numer. Math., 2001, 90: 101-115.
[13] Egervary E. On rank-diminishing operations and their applications to the solution of linear equations. ZAMP, 1960, 9: 376-386.
[14] Huang H. Y. A direct method for the general solution of a system of linear equations. JOTA, 1975, 16: 429-445.
[15] Zhao J. Huang's method for solution of consistent linear equations and its generalization. Journal Numerical Mathematics of Chinese Universities, 1981, 3: 8-17.
[16] Abaffy J., Broyden C.G. and Spedicato E. A class of direct methods for linear equations. Nume. Math., 1984, 45: 361-376.
[17] Abaffy J., Spedicato E. ABS Projection Algorithms—Mathematical Techniques for Linear and Nonlinear Equations. Ellis Horwood, Chichester, 1989.
[18] Spedicato E., Xia Z. and Zhang L. ABS algorithms for linear equations and optimization. Journal of Computational and Applied Mathematics, 2000, 124:155-170.
[19] Xia Z., Zhang L. ABS algorithms for solving linearly constrained optimization problems via the active set strategy. Ricerca Operativa, 2003, 31: 98-100.
[20] Deng N., Chen Z. The truncated nonlinear ABS algorithm and its convergence property. Computing, 1990, 45: 169-173.
[21] 张立卫,冯恩民,夏尊铨.优化中的ABS算法引论.大连理工大学出版社,1999:25-27.
[22] Bertocchi M., Spedicato E. A vectorized FORTRAN code of the implicit Gauss-Cholesky algorithm of the ABS class. Manual 1/34, LAC, Rome, 1990.
[23] Bertocchi M., Spedicato E. and Vespucci M.T. A vectorized FORTRAN code of the implicit QR algorithm of the ABS class. Manual 1/56, LAC, Rome, 1990.
[24] Bodon E. ABS codes of nonlinear Jhuang, modified Huang and implicit LU algorithms for nonlinear systems of equations. QDMSIA, 2000, 24.
[25] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for determined and underdetermined linear systems, QDMSIA, 2000, 21.
[26] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for overdetermined linear systems, QDMSIA, 2000, 19.
[27] Bodon E., Luksan L. and Spedicato E. Computational experiments with ABS algorithms for KKT linear systems, QDMSIA, 2000, 20.
[28] Bodon E. ABS codes for banded linear systems, Preprint, 2001.
[29] 周奇兵.V1.0/2001 ABS软件的研制(硕士论文),2001.
[30] 刘莹.《ABS SOFTWARE研究的新进展ABSDLLOI&WinABS01》(硕士论文),2001.
[31] 李兴.《隐式LU、LX算法误差分析及ABS软件》(硕士论文),2003.
[32] 邹美凤.《求解线性丢番图方程组的ABS算法与WinABS03的研究》(硕士论文),2004.
[33] Spedicato E., Xia Z. and Zhang L. The implicit LX method of the ABS class. OMS, 1997, 8: 99-110, Also as QDMSIA 2/96.
[34] Spedicato E., Xia Z. and Zhang L. Reformation of the simplex method via the ABS algorithm. AMS Subject Classification(1991): 90C05, 65F05.
[35] Esmaeili H., Mahdavi-Amiri N. and Spedicato E. ABS solutions of a class of linear integer inequalities and integer LP problems. OMS, 2001, 16: 179-192.
[36] Zhao J. ABS algorithms for solving linear inequalities, Report 91/21, University of Bergamo, 1995.
[37] 刘玉龙,求解超定线性方程组的修正ABS算法.徐州师范学院学报(自然科学版),1993,Vol.10.No.3:1-4.