工科研究生教材 最优化计算方法PDF电子书下载

第一篇　线性规划 1

第1章　线性规划的数学模型和基本性质 1

1.1　线性规划问题及其数学模型 1

1.1.1 问题的提出 1

1.1.2　线性规划问题的数学模型 3

1.2　线性规划问题的图解法 5

1.2.1 图解法的步骤 5

1.2.2　线性规划问题求解的几种可能结果 6

1.3　线性规划的基本性质 8

1.3.1　线性规划的基本概念 8

1.3.2 凸集与凸集的顶点 10

1.3.3　线性规划的基本定理 11

习题 13

第2章　单纯形法 15

2.1　单纯形法的原理 15

2.1.1　确定初始基本可行解 15

2.1.2　最优性检验和解的判别 16

2.1.3　从一个基本可行解转换到相邻且改善了的基本可行解 19

2.2　单纯形法的计算步骤 20

2.3　人工变量的处理方法 25

2.3.1 大M法 26

2.3.2　两阶段法 28

2.4　单纯形法的有限终止性 30

2.5　改进单纯形法 33

2.5.1 单纯形法的矩阵描述 33

2.5.2　改进单纯形法 35

习题 40

第3章　线性规划的对偶理论 43

3.1　线性规划的对偶问题 43

3.1.1 对偶问题的提出 43

3.1.2　原问题与对偶问题之间的对偶关系 44

3.2　对偶性定理 48

3.3　对偶单纯形法 53

3.3.1 对偶单纯形法的基本思路 53

3.3.2　对偶单纯形法的计算步骤 53

3.3.3　初始对偶基本可行解的求法 56

习题 59

第4章　灵敏度分析和参数线性规划 61

4.1　灵敏度分析 61

4.1.1　参数cj的灵敏度分析 61

4.1.2　参数bi的灵敏度分析 63

4.1.3　约束条件的系数列向量Ak的灵敏度分析 65

4.1.4　增加一个新变量xn+1的分析 65

4.1.5　增加一个新约束条件的分析 67

4.2　参数线性规划 69

习题 73

第5章　线性规划应用实例 76

5.1　套裁下料问题 76

5.2　配料问题 77

5.3　生产工艺优化问题 79

5.4　多周期动态生产计划问题 80

5.5　有配套约束的资源优化问题 81

5.6　投资问题 82

5.6.1　投资项目组合选择 83

5.6.2　连续投资问题 83

5.7　运输问题及其扩展 84

5.7.1 产销平衡的运输问题 85

5.7.2　产销不平衡的运输问题 86

5.7.3　有转运的运输问题 87

习题 88

第二篇　非线性规划 91

第6章　非线性规划基本概念与基本原理 91

6.1 非线性规划的数学模型和基本概念 91

6.1.1　非线性规划问题举例 91

6.1.2　非线性规划问题的一般数学模型 92

6.1.3　基本概念 93

6.2　凸函数和凸规划 96

6.2.1 凸函数定义与性质 96

6.2.2　凸函数的判别 99

6.2.3 凸规划 101

6.3　无约束问题的极值条件 101

6.3.1 用海赛矩阵判断驻点的性质 102

6.3.2　极值点的必要条件和充分条件 102

6.4　下降迭代算法 104

6.4.1 下降迭代算法的概念 104

6.4.2　下降方向与可行下降方向 105

6.4.3　下降迭代算法的一般步骤 105

6.4.4　算法终止条件 106

习题 107

第7章　一维搜索 108

7.1　黄金分割法 108

7.1.1　单谷函数及其性质 108

7.1.2　黄金分割法基本原理与步骤 109

7.2　牛顿法 112

7.2.1　牛顿法的基本原理 112

7.2.2　牛顿法的算术步骤 113

7.2.3　计算举例 113

7.3　抛物线逼近法 114

7.3.1　经过三点（x1,f（x1））、（x2,f（x2））和（x3,f（x3））作抛物线？（x） 114

7.3.2　用抛物线？（x）的极小点作为f（x）的近似极小点 114

7.3.3　迭代 115

7.4　外推内插法 115

7.4.1　基本原理与步骤 115

7.4.2　计算举例 116

习题 117

第8章　无约束问题最优化方法 118

8.1　变量轮换法 118

8.1.1　基本原理 118

8.1.2　算法步骤 118

8.1.3　计算举例 119

8.2　模式搜索方法 120

8.2.1　探测移动 121

8.2.2　模式移动 121

8.2.3　算法的基本思想 121

8.2.4　算法终止准则 121

8.2.5　算法步骤 122

8.2.6　计算举例 122

8.3　可变单纯形法 124

8.3.1　基本原理和步骤 124

8.3.2　计算举例 125

8.4　最速下降法 126

8.4.1　基本原理与步骤 127

8.4.2　计算举例 127

8.4.3　最速下降法性能分析 128

8.5　牛顿法 129

8.5.1　牛顿法基本原理 129

8.5.2 阻尼牛顿法及其计算步骤 131

8.5.3　计算举例 131

8.6　共轭梯度法 132

8.6.1　基本概念和基本原理 132

8.6.2　正定二次函数的共轭梯度法 134

8.6.3　正定二次函数共轭梯度法的计算步骤 136

8.6.4　计算举例 136

8.6.5　用于一般函数的共轭梯度法 138

8.7　拟牛顿法 138

8.7.1　拟牛顿条件 139

8.7.2　DFP法 139

8.7.3　DFP变尺度法的计算步骤 140

8.7.4　计算举例 141

习题 142

第9章　约束问题最优化方法 144

9.1 约束优化问题的最优性条件 144

9.1.1　基本概念 144

9.1.2　Kuhn—Tucker条件（一阶必要条件） 146

9.1.3 关于凸规划的全局最优解定理 149

9.1.4　二阶充分条件 149

9.2　近似规划法 150

9.2.1　线性近似规划的构成 150

9.2.2　近似规划法的算法步骤 151

9.2.3　计算举例 151

9.3　可行方向法 153

9.3.1　基本原理与算法步骤 154

9.3.2　计算举例 155

9.4　罚函数法 157

9.4.1 外点法 157

9.4.2 内点法 161

9.4.3 混合法 163

9.5　乘子法 165

9.5.1 只有等式约束的问题 165

9.5.2　只有不等式约束的问题 167

9.5.3 同时含有等式约束与不等式约束的问题 170

9.6　二次规划 170

9.6.1　二次规划的基本概念与基本性质 170

9.6.2　等式约束二次规划问题 172

9.6.3　有效集法 176

9.6.4　对偶问题 180

9.6.5　二次规划的应用——支持向量机简介 180

习题 183

第三篇　现代最优化算法 186

第10章　最优化问题概论 186

10.1　最优化问题 186

10.1.1 函数优化问题 186

10.1.2　组合优化问题 187

10.2　计算复杂性与NP完全问题 188

10.2.1 计算复杂性的概念 188

10.2.2　NP,NP-C和NP-hard概念 191

10.3　邻域概念 195

10.4　启发式算法 195

10.4.1 启发式算法的概念 195

10.4.2　启发式算法的分类 197

10.4.3　启发式算法的性能分析 198

10.5　小结与注记 199

习题 200

第11章　模拟退火算法 201

11.1　物理退火过程与SA算法的马氏链描述 201

11.1.1 物理退火过程与Metropolis准则 201

11.1.2　物理退火过程的统计力学模型 202

11.1.3　SA算法的基本步骤 203

11.1.4　SA算法的马尔科夫（Markov）链描述 205

11.2　马尔科夫链简介 206

11.3　时齐算法的收敛性 210

11.4　非时齐SA算法的收敛性简介 215

11.5　SA算法实现的技术问题 217

11.5.1　初温的选择 217

11.5.2　时齐SA算法的退温过程控制方法 219

11.5.3　时齐SA算法各温度下的迭代长度规则 221

11.5.4　SA算法的停止准则 222

11.5.5　组合优化问题解的形式和邻域结构设计 222

11.6　改进SA算法及注记 223

习题 224

第12章　遗传算法 225

12.1　遗传算法的基本概念与计算流程 225

12.1.1　遗传算法的基本概念 225

12.1.2　遗传算法的计算流程 227

12.2　遗传算法的数学模型 228

12.2.1 生物进化概念的数学描述 228

12.2.2　遗传机制的数学描述 230

12.3　遗传算法的模式理论 238

12.3.1　模式与遗传算子 238

12.3.2　模式定理 242

12.4　遗传算法的收敛性分析 246

12.4.1　矩阵序列的收敛性与马氏链 246

12.4.2　标准遗传算法的收敛性分析 248

12.5　遗传算法的技术实现 251

12.5.1　编码方案的确定 251

12.5.2　遗传算法的性能评估 252

12.5.3　初始参数的选取和停止原则 253

12.5.4　控制参数的选取和进化技术 254

12.6　遗传算法的改进与注记 258

习题 259

第13章　人工神经网络 260

13.1　概述 260

13.2　人工神经网络的基本概念 261

13.2.1　基本人工神经网络模型 261

13.2.2　人工神经网络的学习算法 261

13.2.3　人工神经元及感知器模型 262

13.3　前馈神经网络及其主要算法 266

13.3.1 多层前馈网络 267

13.3.2　反向传播算法（BP算法） 267

13.4　自组织映射神经网络 269

13.4.1　竞争学习 269

13.4.2 自组织特征映射 270

13.5　反馈型神经网络 271

13.5.1 离散Hopfield网络 272

13.5.2　连续Hopfield网络 276

13.6　人工神经网络应用案例 278

13.6.1 自组织网络用于模式识别 279

13.6.2　Hopfield人工神经网络在TSP中的应用 279

习题 282

参考文献 283