| 【中文题名】 | 求解线性丢番图方程组及不等式组的ABS算法 |
| 【英文题名】 | ABS Algorithms for Solving Linear Diophantine Equations and Inequations |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-7-7 |
| 【中关键词】 | ABS算法,线性丢番图方程组,隐式LU算法,线性整不等式组,超定线性丢番图方程组,超定线性不等式组 |
| 【英关键词】 | ABS algorithms,linear Diophantine equations,the implicit LU algorithm,linear integer inequalities,overdetermined linear Diophantine equations,overdetermined linear inequalities,MATLAB programs, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>数论>丢番图分析（丢番图数论）> |
| 【论文摘要】 | 1984年,Aabby、Broyden及Spedicato共同研究开发了一类用于求解线性方程组与非线性方程组的投影算法——ABS算法。随后二十多年的发展,ABS算法扩展到可以求解最小二乘问题、不等式组、线性规划和具有线性约束的非线性规划等问题。而线性丢番图方程组及不等式组的求解是实际应用中经常遇到的一类问题,在物流、运输中起着重要的作用,于是对线性丢番图方程组及不等式组的求解就显得尤为必要。本文在ABS的框架下,系统地研究了线性丢番图方程组及不等式组的解法。
本文的研究工作分为五个部分,首先介绍了ABS算法的研究进展和ABS软件的概况,其次对线性丢番图方程组的解法做了系统的阐述,接着给出了求解线性丢番图不等式组的求解算法,随后给出了求解超定线性丢番图方程组及不等式组的修正ABS算法,最后给出了用MATLAB编写的相关ABS算法程序。所取得的成果如下:
1.第二章,我们系统地分析了当前求解线性丢番图方程组的方法:Rosser算法和Forterbacher算法,求解线性丢番图方程组的方法:EMAS算法和Conteiean算法。
2.第三章,详细分析了求解线性丢番图方程组的整隐式... |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
Abstract |
5-8 |
|
1 绪论 |
8-14 |
|
1.1 线性丢番图方程的研究发展 |
8 |
|
1.2 ABS算法与软件的进展 |
8-12 |
|
1.2.1 ABS算法的研究 |
8-12 |
|
1.2.2 ABS软件的发展 |
12 |
|
1.3 本文工做概要几论文结构 |
12-14 |
|
2 求解线性丢番图方程的几种方法 |
14-22 |
|
2.1 非齐次线性丢番图方程组的求解 |
14-17 |
|
2.1.1 Rosser算法 |
14-15 |
|
2.1.2 EMAS算法 |
15-17 |
|
2.2 齐次线性丢番图方程组的解法 |
17-19 |
|
2.2.1 Fortenbacher算法的思想和几何意义 |
17-18 |
|
2.2.2 Contejean算法(Fortenbacher算法的推广) |
18-19 |
|
2.3 求非负整数解的一个数值解法 |
19-22 |
|
2.3.1 问题的实用意义 |
19-20 |
|
2.3.2 直接分解法 |
20 |
|
2.3.3 终端因子列表发(LFL方法) |
20-22 |
|
3 求解一类线性整方程的整隐式LU和LX算法 |
22-32 |
|
3.1 IILU算法及其应用 |
22-25 |
|
3.1.1 整隐式LU(IILU)算法 |
22 |
|
3.1.2 基本概念和基本理论 |
22-23 |
|
3.1.3 IILU算法的性质 |
23 |
|
3.1.4 算法在求初始可行解中的应用 |
23-24 |
|
3.1.5 IILU算法在整线性规划中的应用 |
24-25 |
|
3.2 IILX算法及整线性规划的一些结果 |
25-30 |
|
3.2.1 IILX算法 |
25-26 |
|
3.2.2 IILX算法应用于整规划的一些结果 |
26-28 |
|
3.2.3 IILU算法与IILX算法的补充说明 |
28-30 |
|
3.3 IILU算法与其他算法的比较 |
30-32 |
|
4 求解一类线性丢番图不等式组的ABS算法 |
32-38 |
|
4.1 利用EMAS算法来间接求解线性丢番图不等式组 |
32-35 |
|
4.1.1 利用EMAS算法间接求解线性Diophantine的详细推导 |
32-34 |
|
4.1.2 利用线性Diophantine不等式组间接求解整线性规划 |
34-35 |
|
4.2 利用ABS算法求解整线性不等式组 |
35-38 |
|
4.2.1 实数域用于直接求解线性Diophantine不等式组的ABS算法 |
35-36 |
|
4.2.2 整数域用于求解线性Diophantine不等式组的修正ABS算法 |
36-38 |
|
5 求解超定整线性方程组及不等式组的修正ABS算法 |
38-43 |
|
5.1 求解超定线性丢番图方程组的修正ABS算法的推导 |
38-40 |
|
5.2 求解超定整不等式组的修正ABS算法 |
40-43 |
|
结论 |
43-44 |
|
参考文献 |
44-46 |
|
附录 MATLAB程序 |
46-50 |
|
攻读硕士学位期间发表学术论文情况 |
50-51 |
|
致谢 |
51-52 |
|
大连理工大学学位论文版权使用授权书 |
52 |
|
| 【DOI】 | LunWen.ID:2.2008.11256 |
