对偶线性规划的性质及其算法研究_信息与计算科学.zip

摘要:在经济生活中，随着现代科学技术的迅猛发展，线性规划有着广泛的运用。本文首先介绍了简单的一般线性规划以及一般线性规划的标准形式和线性规划模型的建立。其次，粗略的介绍了对偶线性规划问题的提出以及对偶线性规划的两种形式“对称型”和“非对称型”。最后，详细的介绍对偶线性规划的基本性质及其算法并给于证明和实例，而且在算法中提出了此算法的优缺点。

关键词: 对偶；线性规划；性质；算法

目录

摘要

Abstract

1 绪论-1

1.1 研究背景-1

1.2 研究的意义-1

1.3 本文的主要工作-1

2 简单的线性规划问题-2

2.1简单的线性规划问题及数学模型的形式-2

2.1.1线性规划模型的一般形式-2

2.1.2线性规划模型的标准形式-2

2.2线性规划的模型建立-3

3 对偶线性规划-5

3.1 对偶线性规划问题的提出-5

3.2 对偶线性规划问题的形式及其构造-6

3.2.1对称型对偶问题的构造-6

3.2.2 非对称型式对偶问题的构造-7

4 对偶线性规划的基本性质-10

4.1 弱对偶定理及其推论-10

4.2 强对偶定理及其推论-11

4.3 互补松弛定理-12

4.4 变量对应关系-13

5 对偶线性规划问题的算法-17

5.1 对偶单纯形法-17

5.1.1 对偶单纯形法的基本思路-17

5.1.2 对偶单纯形法的计算步骤-17

5.2 对偶单纯形法的优点和缺点-19

5.2.1对偶单纯形法的优点-19

5.2.2对偶单纯形法的缺点-19

5.3 对偶单纯形法与单纯形法的区别-20

结论-21

致谢-22

参考文献-23