图书信息1

内容简介

图书目录

图书信息2

内容简介

前言

目录

部分章节

图书信息1

书 名: 工程优化设计与MATLAB实现

作　者：李万祥 褚衍东

出版社： 清华大学出版社

出版时间： 2010年02月

ISBN: 9787302206170

开本： 16开

定价: 32.00 元

内容简介

《工程优化设计与MATLAB实现》以简洁、完整的基本理论为基础，以实用、多角度的工程实例为对象，以MATLAB语言为工具，介绍了优化设计的理论及应用。主要内容包括：优化设计基本模型；优化设计的数学基础知识；线性规划；一维搜索方法；无约束优化问题、有约束优化问题的经典算法；启发式优化算法，包括蚁群算法、粒子群优化算法、遗传算法、模拟退火算法和人工神经网络算法；MATLAB优化工具箱函数及应用；优化算法工程应用实例。

《工程优化设计与MATLAB实现》可作为高等工科院校有关专业优化设计方面的教材和教学参考书，也可供有关专业师生和工程技术人员参考。

图书目录

第1章 绪论

1.1 最优化问题的提出

1.2 最优化问题的分类

1.3 优化模型的图形表示

1.4 有限元法引例

1.5 多学科设计优化集成软件iSIGHT简介

第2章 优化设计的数学基础

2.1 向量与矩阵的范数

2.1.1 向量的范数

2.1.2 矩阵的范数

2.2 方向导数与梯度

2.2.1 方向导数

2.2.2 梯度

2.3 函数的泰勒级数展开

2.4 无约束优化问题的极值条件

2.5 凸集与凸函数

2.5.1 凸集

2.5.2 凸函数

2.6 有约束优化问题的极值条件

2.6.1 等式约束优化问题的极值条件

2.6.2 不等式约束优化问题的极值条件

习题

第3章 线性规划

3.1 线性规划的标准形式

3.2 单纯形法

3.2.1 基本解与基本可行解

3.2.2 基本可行解的转换

3.2.3 单纯形法的计算步骤

3.2.4 单纯形法列表计算

3.3 单纯形法的MATLAB程序及实例

3.4 改进的单纯形法

3.4.1 改进的单纯形法的基本思想

3.4.2 改进的单纯形法的计算步骤

3.5 改进的单纯形法的MATLAB程序及实例

习题

第4章 一维搜索方法

4.1 确定初始单峰区间的方法——进退法

4.1.1 进退法原理

4.1.2 进退法程序框图及MATLAB程序

4.2 黄金分割法

4.2.1 黄金分割法的基本原理

4.2.2 黄金分割法的计算方法

4.2.3 黄金分割法的计算框图和MATLAB程序

4.3 拉格朗日插值多项式

4.3.1 线性插值

4.3.2 二次函数插值

4.3.3 n次拉格朗日插值多项式

4.4 插值与拟合的其他方法

4.4.1 差商与牛顿插值

4.4.2 列维尔插值法

4.4.3 曲线拟合的最小二乘法

4.4.4 正交多项式及其在曲线拟合中的应用

4.5 一元及多元非线性方程求根

4.5.1 一元非线性方程求根

4.5.2 多元非线性方程组求根

习题

第5章 无约束优化问题的导数解法

5.1 最速下降法

5.1.1 最速下降法的基本原理

5.1.2 最速下降法的MATLAB程序

5.2 牛顿法

5.2.1 牛顿法的基本原理

5.2.2 阻尼牛顿法

5.2.3 阻尼牛顿法的MATLAB程序

5.3 共轭梯度法

5.3.1 共轭方向的概念

5.3.2 共轭方向与函数极值的关系

5.3.3 共轭梯度法的几种形式

5.3.4 共轭梯度法的MATLAB程序

5.4 变尺度法

5.4.1 变量的尺度

5.4.2 变尺度矩阵的建立

5.4.3 变尺度法的MATLAB程序

习题

第6章 无约束优化问题的直接解法

6.1 坐标轮换法

6.1.1 坐标轮换法的基本原理

6.1.2 搜索方向与步长的确定

6.1.3 坐标轮换法的MATLAB程序

6.2 单形替换法

6.2.1 单形替换法（一）

6.2.2 单形替换法（二）

6.2.3 单形替换法的MATLAB程序

6.3 鲍威尔法

6.4 鲍威尔法的MATLAB程序及实例

习题

第7章 约束优化问题的直接解法

7.1 随机方向法

7.1.1 随机方向法的基本原理

7.1.2 随机方向法的步骤

7.1.3 随机方向法的MATLAB程序

7.2 复合形法

7.2.1 复合形法的步骤

7.2.2 复合形法的MATLAB程序

7.3 可行方向法

7.3.1 可行方向法的搜索策略

7.3.2 Zoutendijk可行方向法

7.3.3 Rosen可行方向法

7.3.4 Rosen可行方向法的MATLAB程序

习题

第8章 约束优化问题的间接解法

8.1 罚函数法

8.1.1 内点罚函数法

8.1.2 外点罚函数法

8.1.3 混合罚函数法

8.2 增广乘子法

8.2.1 拉格朗日乘子法

8.2.2 等式约束的增广乘子法

8.2.3 不等式约束的增广乘子法

习题

第9章 多目标函数优化设计

9.1 多目标优化问题

9.1.1 多目标优化问题的数学模型

9.1.2 多目标优化设计解的类型

9.2 多目标优化问题的求解方法

9.2.1 线性组合法

9.2.2 理想点法

9.2.3 乘除法

第10章 最优化问题的启发式算法

10.1 蚁群算法

10.2 粒子群优化算法

10.2.1 粒子群优化算法的基本原理

10.2.2 用粒子群算法求解函数优化问题

10.3 遗传算法

10.3.1 遗传算法的基本原理

10.3.2 混合遗传算法

10.3.3 十进制编码遗传算法

10.3.4 用遗传算法求解TSP问题

10.4 模拟退火算法

10.5 人工神经网络算法

10.5.1 人工神经网络的特征及分类

10.5.2 BP网络

10.5.3 Hopfield神经网络模型

第11章 MATLAB优化工具箱简介

11.1 MATLAB常用内部数学函数

11.2 MATLAB优化工具箱的主要函数

11.2.1 MATLAB求解优化问题的主要函数

11.2.2 优化函数控制参数

11.3 线性规划问题

11.4 一元和多元函数的优化问题

11.4.1 一元函数的优化问题

11.4.2 多元函数的无约束优化问题

11.4.3 多元函数的有约束优化问题

11.4.4 二次规划问题

11.5 半无限约束多元函数优化问题

11.6 多目标优化问题

11.6.1 理想点法

11.6.2 线性加权和法

11.6.3 最大最小法

11.6.4 目标达到法

11.7 最小二乘法在优化及数据拟合中的应用

11.7.1 有约束线性最小二乘

11.7.2 最小二乘法数据（曲线）拟合之一

11.7.3 最小二乘法数据（曲线）拟合之二

11.7.4 最小二乘法数据（曲线）拟合之三

11.8 非线性方程的求解

11.8.1 一元非线性方程的解

11.8.2 非线性方程组的解

第12章 工程优化设计实例

12.1 平面连杆机构的优化设计

12.1.1 曲柄摇杆机构优化设计数学模型

12.1.2 曲柄摇杆机构优化设计的MATLAB程序及运行结果

12.2 凸轮优化设计

12.2.1 凸轮型线优化设计目标函数

12.2.2 优化函数约束条件

12.2.3 凸轮机构优化设计的MATLAB程序及计算实例

12.3 螺栓连接的优化设计

12.3.1 螺栓连接受力分析

12.3.2 螺栓连接的设计变量、目标函数及约束条件

12.3.3 螺栓连接的优化数学模型

12.3.4 螺栓连接优化设计的MATLAB程序及运行结果

12.4 圆柱齿轮传动的优化设计

12.4.1 模糊综合评判的一般流程

12.4.2 圆柱齿轮传动优化设计的目标函数和设计变量

12.4.3 圆柱齿轮传动优化设计的约束条件

12.4.4 最优截集水平值γ的确定

12.4.5 圆柱齿轮传动优化设计的MATLAB程序及计算结果

12.5 圆柱螺旋弹簧的优化设计

12.5.1 圆柱螺旋弹簧优化设计的数学模型

12.5.2 圆柱螺旋弹簧优化设计实例

12.6 轴的优化设计

12.6.1 扭转轴的优化设计

12.6.2 圆形等截面轴的优化设计

12.6.3 车床主轴的优化设计

12.7 桁架的优化设计

12.7.1 静定桁架的优化设计

12.7.2 三杆桁架的优化设计

12.8 换热器的优化设计

12.8.1 换热器优化设计（一）

12.8.2 换热器优化设计（二）

12.9 基于优化方法的常微分方程边值问题数值解

12.9.1 基于MATLAB函数的求解方法

12.9.2 求解两点边值问题的打靶法

12.9.3 边界层微分方程组及相似解

12.9.4 流函数方程和温度方程的求解

12.10 含间隙机械系统的参数优化设计

12.10.1 力学模型及运动微分方程

12.10.2 系统的分岔和通向混沌的道路

12.10.3 系统优化设计的MATLAB程序

参考文献

图书信息2

书名：工程优化设计与MATLAB实现（修订版）

书号：9787302266082

作者：张永恒等

定价：34元

出版日期：2011-9-5

出版社：清华大学出版社

内容简介

本书以工程实例为背景，以MATLAB语言为工具，较全面地介绍了优化设计的理论及应用。本书主要内容包括：优化设计基本模型；优化设计数学基础知识；一维搜索方法；无约束优化问题、有约束优化问题的经典算法；启发式优化算法，包括蚁群优化、粒子群优化算法、遗传算法、模拟退火算法、禁忌算法和人工神经网络算法；MATLAB优化工具箱函数及应用；优化算法工程应用实例及MATLAB基础知识。书中配有完整的MATLAB程序。本书可作为高等工科院校有关专业优化设计方面课程的教材和教学参考书，也可供有关专业的师生和工程技术人员参考。

前言

优化设计是一门古老而新兴的理论，既有着很强的应用背景，又有着坚实的数学基础。它的数学基础可以追溯到牛顿（Newton,1642-1727) 、莱布尼茨（W.Leibniz,1646-1716）创立的微积分理论。优化设计与运筹学有着密切的联系，前者是后者在非线性规划方向的延伸和发展。优化设计主要研究连续函数在有约束和无约束条件下单目标函数或多目标函数的最优值问题，而运筹学主要研究经济活动和军事活动中能用数量来表达的有关策划、管理方面的问题。随着科学技术和生产的发展，运筹学已渗入到多个领域，其本身也在不断发展，包含了多个数学分支，如数学规划（又包含线性规划、非线性规划、整数规划、组合规划等）、图论、网络流、决策分析、排队论、可靠性数学理论、库存论、对策论、搜索论、模拟等。在运筹学方面，我国著名科学家钱学森、许国志、数学家华罗庚等作出了重要贡献。1956年钱学森和许国志共同创建了中国第一个运筹学研究组织。从20世纪60年代开始，华罗庚持续近20年在全国范围内推广优选法和统筹法，产生了巨大的经济效益。其中优选法采用的黄金分割搜索方法也是优化设计中一维搜索常用的一种方法。各种启发式（heuristic）算法或智能算法，如遗传算法、蚁群算法、粒子群算法、神经网络算法等不但能解决连续函数的优化问题，也能解决离散函数的优化问题，它们将优化设计与运筹学紧密结合起来。

广义来说优化设计采用的方法是搜索的方法，传统的优化设计方法主要采用线搜索方法，而启发式优化方法采用多方位的随机搜索方法。对非线性函数来说，在极值点附近可以用二次函数来逼近，若存在极小值，则极值点附近的函数值均大于极值点处的函数值。求连续函数极值的问题，一部分人可能会想到用求导数的方法来解决，另一部分人可能不采用求导数的方法，而直接用比较的方法来确定搜索区间和极小值。与求导数的方法相比，直接搜索法是优化设计中更基础的方法。从优化设计的数学模型来分，优化设计问题可分为有约束的优化问题和无约束的优化设计问题；而从求解方法来分，优化设计方法可分为基于导数的方法和直接搜索方法。随机方向法、复合型法、鲍威尔法、可行方向法均属于直接搜索法，值得注意的是遗传算法、蚁群算法、粒子群算法等启发式算法均含有随机方向法的基本内涵。

优化设计广泛应用于航空、汽车、化工、电力、建筑、机械制造等众多领域，由于优化问题的多样性，相应出现了多种优化设计方法，每一种方法都有其自身的特点和适用范围，在实际应用中，特别对于大型优化设计问题，不应以一次计算结果或一种方法得出的结果作为最终的最优结果。

优化设计是以工程设计问题为背景，将最优化原理与计算技术相结合的产物。不论是从学习的角度还是从应用的角度，实践都是非常重要的，实践既是学习的终点又是学习的起点。本书特别强调理论与实践的结合。实践包括多个方面，最基本的是通过简单的例子用手工演算来验证算法，然后是通过编程利用计算机实现和验证优化算法，最后是针对工程设计问题建立优化设计模型，选择合适的优化算法解决设计问题。MATLAB不但是实现数值计算的计算机高级语言，同时也是解决多种工程和数学问题的仿真软件。本书以MATLAB语言作为程序设计语言和实践环境，针对每一种算法编写了学习程序，方便读者学习。这些程序主要为验证优化算法而设计，读者可以以此为基础编写自己的程序。MATLAB本身包含有命令格式和GUI格式的优化工具箱，并随着版本的升级不断加入新的优化算法。本书第11章简要介绍了MATLAB优化工具箱命令格式的各种优化函数，优化工具箱函数为实现优化设计提供了极大的方便，但从学习的角度来说，应尽可能自己编程以便深刻领会和掌握所学的优化算法。

本书修订版保持了原书的内容，对部分内容作了修订，完善了各章习题。本书配有电子教案，需要者可与清华大学出版社联系。

本书由张永恒主编并统稿，蔡慧林、褚衍东审阅，何玮、马斌、朱凌云（兰州交通大学）、严军（西北师范大学）参加编写。第1章、第12.1~12.3节由张永恒编写；第9章和第12.10节由何玮编写；第5、6、7章由马斌编写；第2、4、8章由朱凌云编写；第3、10、11章和第12.4~12.9节由严军编写；习题由张永恒、马斌、朱凌云编写。在编写过程中，张鹏、刘金平、程明、周志勇、宁珍、刘军强、唐强完成了部分程序的调试工作，在此表示感谢。在编写过程中参考了网络中有关作者的资料在此一并表示感谢。

由于作者水平有限，书中一定有不少错误和缺点，敬请广大读者提出宝贵意见。

目录

目 录

第1章 绪论1

1.1 最优化问题的提出1

1.2 最优化问题的分类4

1.3 优化模型的图形表示5

1.4 有限元法引例10

1.5 多学科设计优化集成软件iSIGHT简介12

习题16第2章 优化设计的数学基础18

2.1 向量与矩阵的范数18

2.1.1 向量的范数18

2.1.2 矩阵的范数18

2.2 方向导数与梯度19

2.2.1 方向导数19

2.2.2 梯度20

2.3 函数的泰勒级数展开21

2.4 无约束优化问题的极值条件22

2.5 凸集与凸函数25

2.5.1 凸集25

2.5.2 凸函数25

2.6 有约束优化问题的极值条件27

2.6.1 等式约束优化问题的极值条件27

2.6.2 不等式约束优化问题的极值条件29

习题36第3章 线性规划37

3.1 线性规划的标准形式37

3.2 单纯形法38

3.2.1 基本解与基本可行解38

3.2.2 基本可行解的转换42

3.2.3 单纯形法的计算步骤44

3.2.4 单纯形法列表计算47

3.3 单纯形法的MATLAB程序及实例49

3.4 改进的单纯形法51

3.4.1 改进的单纯形法的基本思想52

3.4.2 改进的单纯形法的计算步骤52

3.5 改进的单纯形法的MATLAB程序及实例55

习题57第4章 一维搜索方法60

4.1 确定初始单峰区间的方法--进退法60

4.1.1 进退法原理60

4.1.2 进退法程序框图及MATLAB程序61

4.2 黄金分割法63

4.2.1 黄金分割法的基本原理63

4.2.2 黄金分割法的计算方法63

4.2.3 黄金分割法的计算框图和MATLAB程序64

4.3 拉格朗日插值多项式66

4.3.1 线性插值66

4.3.2 二次函数插值66

4.3.3 ?n?次拉格朗日插值多项式70

4.4 插值与拟合的其他方法71

4.4.1 差商与牛顿插值71

4.4.2 列维尔插值法72

4.4.3 曲线拟合的最小二乘法75

4.4.4 正交多项式及其在曲线拟合中的应用76

4.5 一元及多元非线性方程求根81

4.5.1 一元非线性方程求根81

4.5.2 多元非线性方程组求根84

习题85第5章 无约束优化问题的导数解法87

5.1 最速下降法87

5.1.1 最速下降法的基本原理87

5.1.2 最速下降法的MATLAB程序89

5.2 牛顿法90

5.2.1 牛顿法的基本原理90

5.2.2 阻尼牛顿法92

5.2.3 阻尼牛顿法的MATLAB程序93

5.3 共轭梯度法94

5.3.1 共轭方向的概念94

5.3.2 共轭方向与函数极值的关系94

5.3.3 共轭梯度法的几种形式95

5.3.4 共轭梯度法的MATLAB程序99

5.4 变尺度法100

5.4.1 变量的尺度100

5.4.2 变尺度矩阵的建立103

5.4.3 变尺度法的MATLAB程序106

习题108第6章 无约束优化问题的直接解法109

6.1 坐标轮换法109

6.1.1 坐标轮换法的基本原理109

6.1.2 搜索方向与步长的确定109

6.1.3 坐标轮换法的MATLAB程序110

6.2 单形替换法112

6.2.1 单形替换法（一）113

6.2.2 单形替换法（二）114

6.2.3 单形替换法的MATLAB程序115

6.3 鲍威尔法119

6.3.1 鲍威尔法的原理120

6.3.2 鲍威尔基本算法的步骤120

6.3.3 改进的鲍威尔方法121

6.4 鲍威尔法的MATLAB程序及实例125

习题127第7章 约束优化问题的直接解法129

7.1 随机方向法129

7.1.1 随机方向法的基本原理129

7.1.2 随机方向法的步骤129

7.1.3 随机方向法的MATLAB程序130

7.2 复合形法133

7.2.1 复合形法的步骤133

7.2.2 复合形法的MATLAB程序135

7.3 可行方向法140

7.3.1 可行方向法的搜索策略140

7.3.2 Zoutendijk可行方向法141

7.3.3 Rosen可行方向法144

7.3.4 Rosen可行方向法的MATLAB程序146

习题150第8章 约束优化问题的间接解法152

8.1 罚函数法152

8.1.1 内点罚函数法152

8.1.2 外点罚函数法156

8.1.3 混合罚函数法158

8.2 增广乘子法160

8.2.1 拉格朗日乘子法160

8.2.2 等式约束的增广乘子法162

8.2.3 不等式约束的增广乘子法165

习题169第9章 多目标函数优化设计171

9.1 多目标优化问题172

9.1.1 多目标优化问题的数学模型172

9.1.2 多目标优化设计解的类型172

9.2 多目标优化问题的求解方法173

9.2.1 线性组合法173

9.2.2 理想点法174

9.2.3 乘除法175

习题175第10章 最优化问题的启发式算法177

10.1 蚁群算法177

10.1.1 蚁群算法求解TSP的基本原理177

10.1.2 用蚁群算法求解函数优化问题181

10.2 粒子群优化算法185

10.2.1 粒子群优化算法的基本原理185

10.2.2 用粒子群算法求解函数优化问题185

10.3 遗传算法189

10.3.1 遗传算法的基本原理189

10.3.2 混合遗传算法196

10.3.3 十进制编码遗传算法199

10.3.4 用遗传算法求解TSP问题203

10.4 模拟退火算法204

10.5 人工神经网络算法208

10.5.1 人工神经网络的特征及分类208

10.5.2 BP网络209

10.5.3 Hopfield神经网络模型212

习题222第11章 MATLAB优化工具箱简介223

11.1 MATLAB常用内部数学函数223

11.2 MATLAB优化工具箱的主要函数224

11.2.1 MATLAB求解优化问题的主要函数224

11.2.2 优化函数控制参数225

11.3 线性规划问题226

11.4 一元和多元函数的优化问题228

11.4.1 一元函数的优化问题228

11.4.2 多元函数的无约束优化问题228

11.4.3 多元函数的有约束优化问题230

11.4.4 二次规划问题231

11.5 半无限约束多元函数优化问题233

11.6 多目标优化问题234

11.6.1 理想点法234

11.6.2 线性加权和法237

11.6.3 最大最小法239

11.6.4 目标达到法240

11.7 最小二乘法在优化及数据拟合中的应用242

11.7.1 有约束线性最小二乘243

11.7.2 最小二乘法数据（曲线）拟合之一244

11.7.3 最小二乘法数据（曲线）拟合之二245

11.7.4 最小二乘法数据（曲线）拟合之三246

11.8 非线性方程的求解247

11.8.1 一元非线性方程的解247

11.8.2 非线性方程组的解247

习题251第12章 工程优化设计实例254

12.1 平面连杆机构的优化设计254

12.1.1 曲柄摇杆机构优化设计数学模型255

12.1.2 曲柄摇杆机构优化设计的MATLAB程序及运行结果256

12.2 凸轮优化设计257

12.2.1 凸轮型线优化设计目标函数258

12.2.2 优化函数约束条件259

12.2.3 凸轮机构优化设计的MATLAB程序及计算实例259

12.3 螺栓连接的优化设计261

12.3.1 螺栓连接受力分析261

12.3.2 螺栓连接的设计变量、目标函数及约束条件262

12.3.3 螺栓连接的优化数学模型263

12.3.4 螺栓连接优化设计的MATLAB程序及运行结果263

12.4 圆柱齿轮传动的优化设计264

12.4.1 模糊综合评判的一般流程264

12.4.2 圆柱齿轮传动优化设计的目标函数和设计变量266

12.4.3 圆柱齿轮传动优化设计的约束条件267

12.4.4 最优截集水平值?λ???的确定269

12.4.5 圆柱齿轮传动优化设计的MATLAB程序及计算结果270

12.5 圆柱螺旋弹簧的优化设计272

12.5.1 圆柱螺旋弹簧优化设计的数学模型272

12.5.2 圆柱螺旋弹簧优化设计实例274

12.6 轴的优化设计275

12.6.1 扭转轴的优化设计275

12.6.2 圆形等截面轴的优化设计276

12.6.3 车床主轴的优化设计278

12.7 桁架的优化设计281

12.7.1 静定桁架的优化设计281

12.7.2 三杆桁架的优化设计284

12.8 换热器的优化设计286

12.8.1 换热器优化设计（一）286

12.8.2 换热器优化设计（二）289

12.9 基于优化方法的常微分方程边值问题数值解291

12.9.1 基于MATLAB函数的求解方法291

12.9.2 求解两点边值问题的打靶法292

12.9.3 边界层微分方程组及相似解293

12.9.4 流函数方程和温度方程的求解295

12.10 含间隙机械系统的参数优化设计306

12.10.1 力学模型及运动微分方程307

12.10.2 系统的分岔和通向混沌的道路308

12.10.3 系统优化设计的MATLAB程序309

习题312参考文献316

部分章节

第3章 线性规划线性规划问题是最优化理论的重要分支，也是最基本的内容，许多实际问题抽象成数学模型后，都可以归结为线性规划问题。自从1947年G.B.Dantzig 提出求解线性规划的单纯形法以来，线性规划在理论上趋向成熟，在实用中日益广泛与深入。特别是随着计算机技术及数值计算方法的发展，线性规划的应用领域更为广泛。3.1 线性规划的标准形式例1-1和例1-2所述问题的数学模型的共同特点是目标函数和约束条件均为线性，设计变量非负。例1-1中的约束条件既含有不等式约束也含有等式约束，而例1-2中的约束条件仅含“≤”的约束。归纳起来，线性规划问题的一般形式为目标函数：???max? (?min?)f(x)=c?1x?1+c?2x?2+…+c?nx?n?? 约束条件：a?11x?1+a?12x?2+…+a?1nx?n≤(=,≥)b?1a?21x?1+a?22x?2+…+a?2nx?n≤(=,≥)b?2?a?m1x?1+a?m2x?2+…+a?mnx?n≤(=,≥)b?mx?j≥0, j=1,2,…,n, m<n线性规划问题的常规求解方法是利用矩阵的初等变换，求解时引进非负的松弛变量(对“≥”的约束称为剩余变量)将不等式约束转化为等式约束，也就是将线性规划问题的一般形式变为标准形式。因此，线性规划问题数学模型的标准形式为线性目标函数加上等式及变量非负的约束条件。用数学表达式表述为???min(max)? c?1x?1+c?2x?2+…+c?nx?n?s.t.? a?11x?1+a?12x?2+…+a?1nx?n=b?1 a?21x?1+a?22x?2+…+a?2nx?n=b?2 ? a?m1x?1+a?m2x?2+…+a?mnx?n=b?m x?j≥0, j=1,2,…,n, m<n??用矩阵表示为???min? (?max?) c??T?x?s.t.? Ax=b x?j≥0, j=1,2,…,n (3-1) ??因此，例1-1的模型化成标准形式为???min? f(x)=x?1+x?2+x?3+x?4+x?5+0x?6+0x?7+0x?8+0x?9 +0x?10+0x?11+0x?12+0x?13+0x?14?s.t. ?x?1+x?2+x?3+x?4+x?5+x?6=18 -3x?1-4x?2+5x?3-4x?4-6x?5+x?7=-80 -3x?1+x?8=-5 -4x?2+x?9=-15 4x?1+x?10=35 4x?2+x?11=40 5x?2+x?12=30 4x?4+x?13=40 6x?5+x?14=35 x?j≥0, j=1,2,…, 14?? 例1-2的模型化成标准形式为???max? f(x)=220x?1+250x?2+0x?3+0x?4+0x?5+0x?6?s.t.? x?1+x?2+x?3=1200 2x?1+x?2+x?4=1800 x?1+x?5=800 x?2+x?6=1000 x?j≥0, j=1,2,…, 6??3.2 单 纯 形 法在学习单纯形法之前需要了解以下两个基本概念。极点： 若凸集S中的点x，不能成为S中任何线段的内点，则称x为S的极点。单纯形： 若一个凸集仅包含有限个极点，则称此凸集为单纯形。单纯形法是求解线性规划问题的有效方法。线性规划问题的可行域是n维向量空间?R??n 中的多面凸集，如果存在最优解，则最优解必在该凸集的某极点处达到。极点所对应的可行解称为基本可行解。单纯形法的基本思想是：先找出一个基本可行解，对它进行鉴别，看是否为最优解。若不是，则按照一定法则转换到另一改进的基本可行解,再鉴别。若仍不是，则再转换,按此重复进行。因基本可行解的个数有限，故经有限次转换必能得出问题的最优解。如果问题无最优解，也可用此法判别。3.2.1 基本解与基本可行解在绪论中提到过，如果目标函数是一元线性函数f(x),x∈[a,b]，则f(x)的最大值（或最小值）必在x的端点上取得。而对多元线性规划问题来说，这一结论也是成立的，即f(x)的最大值或最小值在由约束条件构成的求解域的顶点上取得。线性规划问题属于有约束优化（规划）问题，约束条件由等式线性约束和变量非负条件构成。基本解是只满足线性约束条件的解，而基本可行解是既满足等式线性约束又满足变量非负要求的解。因此线性规划问题的解可通过求解线性等式约束方程来获得。下面先通过一个例子来说明单纯形法的基本原理及求解过程。【例3-1】 用单纯形法求解下面的线性规划问题：???max? f(x)=2x?1+x?2-2x?3?s.t.? x?1+x?2+2x?3≤5 x?1+3x?2-x?3≤3 x?1,x?2,x?3≥0?? 解： (1) 先用MATLAB线性规划函数求解，其计算程序如下： %ch31_li1clc;close all;f=-\\2\\];A=\\1\\];b=\\;xl=\\;\\=linprog(f,A,b,\\,\\,xl)计算结果为 x= 3.4696 0.0000 0.4696fval= -6.0000 (2) 手算求解引入松弛变量，将所给问题化成线性规划标准形式:???max? f(x)=2x?1+x?2-2x?3+0x?4+0x?5?s.t.? x?1+x?2+2x?3+x?4+0x?5=5 x?1+3x?2-x?3+0x?4+x?5=3 x?1,x?2,x?3,x?4,x?5≥0??将上式约束方程用矩阵表示：??11 21013-101x?1x?2x?3x?4x?5=53 (3-2) ?? 由于方程个数少于变量个数，因此有无穷多个解。但若取其中3个变量的解为零，则可得到确定的解，并且按这种取法得到的解是有限的，对本问题来说可有10个不同的解。应用MATLAB编程检索这10个解的部分结果如下： ----------l=1-----j=1, k=2------------ x(1,2)=6.000000,-1.000000A=1 1 1 3y=11----------l=2-----j=1, k=3------------x(1,3)=3.666667,0.666667AA=1 2 1 -1y=6.0000----------l=3-----j=1, k=4------------ x(1,4)=3.000000,2.000000AA=1 1 1 0y=6----------l=4-----j=1, k=5------------ x(1,5)=5.000000,-2.000000AA=1 0 1 1y=10从中可以看出，虽然这些解都是基本解，但并不都是基本可行解。并且?x??1=3.6667,?x??3=0.6667 和?x??1=3.0,?x??4=2.0都是最优基本可行解。挑选基本解的程序如下： %ch1_li1_1clc;clear all;b=\\';A1=\\1 1 2 1 0 1 3 -1 0 1\\];f=\\2 0 0\\];l=0;for j=1:5 for k=1:5if(j~=k&&j<k)AA=\\A1(1,j), A1(1,k) A1(2,j), A1(2,k)\\];if det(AA)~=0 l=l+1; x=inv(AA)?b;fprintf('---------l= %d-----j= %d, k= %d-----------\ x(%d,%d)= %f,%f',l,j,k,j,k,x(1),x(2)) AA y=f(j)?x(1)+f(k)?x(2)endendendend下面通过初等变换或消元法求解例3-1。如果约束条件中变量的系数组成的矩阵是满秩的，则对应的变量为基本变量，其系数矩阵称为基矩阵。求解时应选择基本变量和基矩阵进行初等变换。由式（3-2）可知，选择松弛变量x?4,x?5为基本变量，对应的系数组成的矩阵为基矩阵将会带来很大方便。令非基本变量x?1,x?2,x?3均为零，则得到x?4=5, x?5=3。将该结果代入目标函数中，得??f(x)=2×0+1×0-2×0+0×5+0×3=0??这一结果似乎没有带来什么益处，因为对目标函数没有丝毫影响。但是通过观察可以发现，如果将变量x?1由0变成正值，用其替换其中一个基本变量，则目标函数增加最多，因为变量x?1的系数最大。这是将非基本变量选进基本变量的一个原则。接下来的问题是将原来的基本变量x?4,x?5中的哪一个移出，使其成为非基本变量。解决这一问题要借助约束条件，如果仍旧保持x?2,x?3为零，并去掉方程中非基本变量x?2,x?3及其系数，则约束方程为??110101x?1x?4x?5=53 (3-3) ??分别选x?1, x?4和x?1, x?5为基本变量考察解的情况。以x?1, x?4为基本变量，同时令x?5=0，结果为x?1=3, x?4=2, f=6; 再以x?1, x?5为基本变量，同时令x?4=0，结果为x?1=5, x?5=-2, f=10. 第二种方案是不可取的，因为解x?1=5, x?5=-2不是基本可行解，只是基本解。也就是说应该选择变量x?5移出基本变量表。为了说明进基变量的系数列向量元素与右端项元素的关系，将x?1分别替换x?4和x?5的情况用下面的模型进行分析。用x?1替换x?4的约束方程为??a?110a?211x?1x?5=b?1b?2??选a?11为消元主元，结果为??1001x?1x?5=b?1/a?11b?2-a?21b?1a?11??从而得??x?1=b?1/a?11, x?5=b?2-a?21b?1a?11 (3-4) ??用x?1替换x?5的约束方程为??1a?110a?21x?4x?1=b?1b?2 (3-5) ??选a?21为消元主元，结果为??1001x?4x?1=b?1-a?11b?2a?21b?2a?21 (3-6) ??从而得??x?4=b?1-a?11b?2a?21, x?1=b?2/a?21 (3-7) ??观察式（3-4）和式（3-7) ，注意到当??x?1=?min?b?ia?i1=?min?51,31=b?2a?21=31=3 (3-8) ??时，可得到基本可行解，否则x?1的取值不能使所有基本变量的取值成为基本可行解，如式（3-4) . 出基变量与式（3-8）有着必然的联系。式（3-8）中最小比值对应的右端项元素或系数行下标对应的基本变量就是出基变量，且比值分母系数下标就是进基变量对应的主消元元素。验证式（3-3）可知，变量x?5为被替换出的变量，与计算结果一致。由此可见，目标函数与约束条件配合，约束方程求解完成后，将基本变量结果代入目标函数中，通过比较非基本变量系数大小决定进基变量（此时认为非基本变量取值不为零）。对求最大值问题，系数较大的非基本变量为进基变量；对于最小值问题，系数较小的非基本变量为进基变量。确定了进基变量后，则计算右端项与进基变量在约束方程中列系数向量对应元素的比值，比值小者的行下标对应的基本变量为出基变量。下面对单纯形法进行更一般的说明。将式(3-1)中的约束矩阵A按列表示:??A=[p?1 p?2 … p?n]??p?i(i=1,2,…,n)是m×1的向量，p?i的分量是各约束方程中与设计变量x?i对应的系数。设矩阵A的秩为m，将设计变量x分解为基本变量和非基本变量，即x=[x?E x?N]??T?,相应地，系数矩阵A也分解为两部分，一部分为基矩阵，用E表示；另一部分为非基矩阵，用N表示。于是A=[E N],E=[p?1 p?2 … p?m], N=[p?m+1 p?m+2 … p?n]。式(3-1)中的约束条件重新表示为??[E N]x?Ex?N=b(3-9)??即??Ex?E+Nx?N=b??上式两端左乘E?-1并移项，得??x?E=E?-1b-E?-1Nx?N (3-10) ??x?N的分量为自由变量，它们取不同的值，就会得到方程组的不同解。特别地，如果令x?N=0，则得到??x=x?Ex?N=E?-1b0 (3-11) ??称解x为方程组Ax=b的一个基本解。如果E?-1b≥0，则称??x=x?Ex?N=E?-1b0??为满足约束条件的基本可行解（非负的基本解）. 3.2.2 基本可行解的转换基本可行解的转换就是在得到了某组基本可行解后，如何进一步改进获得更好的解，最终达到最优基本可行解。从3.2.1节的分析可知，获得改进的解是在满足约束条件的前提下使目标函数值增加（对于最大值问题）或使目标函数值减小（对于最小值问题）的解。设已经获得一组基本可行解：??x? (0) =E?-1b0??其对应的目标函数值记为f?0。设x=x?Ex?N是另一组基本可行解，将其代入目标函数中，得??f=c??T?x=c??T??E c??T??Nx?Ex?N=c??T??Ex?E+c??T??Nx?N=c??T??E(E?-1b-E?-1Nx?N)+c??T??Nx?N=c??T??EE?-1b+(c??T??N-c??T??EE?-1N)x?N=f?0+∑nj=m+1(c?j-c??T??EE?-1p?j )x?j=f?0+∑nj=m+1(c?j-z?j)x?j (3-12) ?? 如果每次将一个非基本变量转换为基本变量，并假定求目标函数的最大值，那么由式（3-12) 可知，选择求和项中系数c?j-z?j>0最大者对应的非基本变量进入基本变量，当该变量取正值时，可使目标函数增加最多。如果所有非基本变量的系数c?j-z?j不再有正值，则说明非基本变量的进基运算不会再使目标函数值增加，此时就终止计算，输出最优结果。非基本变量转换为基本变量后，则要将上一轮迭代中的一个基本变量转换为非基本变量，判断出基本变量表的条件由约束方程的消元计算格式给出。设x?k为进基变量，不失一般性，认为x?k替换x?r，在约束方程中相应地用p?k替换p?r, p?k=[a′?1k a′?2k … a′?mk]??T?, p?r=[a′?1r a′?2r … a′?mr]??T?，新的基矩阵为E?(1)。为表示清楚起见，将p?k标记为p?(k)?r，其元素相应地表示为p?(k)?r=[a′?(k)?1r a′?(k)?2r … a′?(k)?mr]??T?。因此基矩阵E?(1)表示为??E?(1)=[p?1 p?2 … p?(k)?r … p?m]=10…a′?(k)?1r…001…a′?(k)?2r…0??????…a′?(k)?rr…0????00…a′?(k)?mr…1?? 变量x?k由零变为正值后，新的方程组的解为??x′?E=E?-1?(1)b′ (3-13) ??其中，基矩阵E?(1)的逆阵为??E?-1?(1)=10…-a′?(k)?1ra′?(k)?rr…001…-a′?(k)?2ra′?(k)?rr…0??????…1a′?(k)?rr…0????00…-a′?(k)?mra′?(k)?rr…1 (3-14) ?? 这里认为初始基矩阵为单位阵。在基矩阵中用p?k替换p?r，就是将p?k放在第r列的位置上。对于式（3-14）所示的矩阵，其逆矩阵只有第r列的元素发生变化，对角线上的元素为相应元素的倒数，该列上其他元素等于原来的元素取反再除以对角线上的元素。式（3-13）的解为??x?(k)?r=b′?ra′?(k)?rr (3-15) x?(k)?i=b′?i-a′?(k)?irb′?ra′?(k)?rr=b′?i-a′?(k)?irx?(k)?r, i=1,2,…, m,i≠r (3-16) ?? 由于设计变量非负，并假设设计变量在约束方程中的系数和右端项元素均大于零，因此x? (k)?r≥0自然满足；而式（3-16）中的变量非负意味着??b′?i-a′?(k)?irb′?ra′?(k)?rr≥0??即??b′?ia′?(k)?ir-b′?ra′?(k)?rr≥0 (3-17) ??当??θ=x?k=b′?ra′?(k)?rr=?min? b′?ia′?(k)?ir,a′?(k)?ir>0 (3-18) ??时，则能保证用x?k替换x?r使所有基本变量非负。在线性规划中，通常称??σ?j=c?j-z?j (3-19) ??为判别数或检验数。对极小化问题，进基变量x?k的下标与σ?k=c?k-z?k=?min?j(c?j-z?j)项的下标“k”对应，非基本变量x?k的引入使目标函数?f=f?0+∑nj=m+1σ?jx?j?增加最多（最大值问题），或减少最多（最小值问题）。出基变量x?E?r的下标与θ=b′?ra′?rk=?min?b′?ia′?ik,a′?ik>0项的下标“r”对应。式（3-18）和式（3-19）是单纯形法求解线性规划问题的重要判别式和检验规则。3.2.3 单纯形法的计算步骤应用单纯形法求解时，首先要了解怎样求得初始基本可行解，又怎样从一个基本可行解转到邻近的另一个基本可行解，又怎样检验得到的基本可行解是不是最优解。下面通过例题3-2说明这些问题。【例3-2】 用单纯形法求下述问题的最优解：???min? z=-6x?1+3x?2-2x?3?s.t.? 2x?1+x?2+x?3≤6 x?1+x?3≤2 x?1,x?2,x?3≥0?? 解： 首先引入松弛变量x?4,x?5，把数学模型化为标准形式：???min? z=-6x?1+3x?2-2x?3+0x?4+0x?5?s.t.? 2x?1+x?2+x?3+x?4+0x?5=6 x?1+0x?2+x?3+0x?4+x?5=2 x?1,x?2,x?3,x?4,x?5≥0?? 引入松弛变量后，变量总数n=5，约束方程数m=2（不含变量大于等于零的约束），因此有n-m=3个非基本变量，并令其为零进行求解。一个简单的做法就是选松弛变量x?4,x?5为基本变量，因为其系数列向量为单位基向量E=p?4 p?5=1001。将基本变量用右端列向量和非基本变量表示，得??x?4=6-2x?1-x?2-x?3x?5=2-x?1-x?3??令非基本变量x?1=x?2=x?3=0，则基本解为??x?4=6, x?5=2??记初始基本解为??x?(0)=\\??T??? 此解又满足式x?j≥0,j=1,2,…,5，因此，x?(0)是基本可行解，它对应着凸可行域的一个顶点。一般来说，对于约束条件全为“≤b?i”形式(i=1,2,…,m)的线性规划问题，通过引入松弛变量，可较容易地找到一个初始基本可行解。下一步，将初始基本可行解x?(0)=\\??T?代入目标函数表达式中，得??z=-6×0+3×0-2×0+0×6+0×2=0?? 非基本变量x?1=x?2=x?3=0对应的目标函数值z=0，为找出进基变量，将x?4,x?5代入原式得??z=-6x?1+3x?2-2x?3+c?4(6-2x?1-x?2-x?3)+c?5(2-x?1-x?3)=6c?4+2c?5+(-6-2×c?4-c?5)x?1+(3-c?4)x?2+(-2-c?4-c?5)x?3=\\1001]62]+\\-\\1001]211101]x?1x?2x?3]=c??T?EE?-1b+(c??T??N-c??T??EE?-1N)x?N=-6x?1+3x?2-2x?3?? 由上式看出，x?1增加1个单位，目标函数值z下降6个单位；x?2增加1个单位，z增加3个单位；x?3增加1个单位，z值下降2个单位。如果使x?1和x?3成为正值，都能使目标函数向极小方向改善，那么当前解不是最优解。选择的进基变量应是使目标函数改善最大的非基本变量进基。由前面的分析看到，在目标函数中，应选择有负系数，且负系数绝对值最大的非基本变量进基。例3-2中，目标函数中x?1的系数为-6，所以x?1应选为进基变量。这是因为当x?1由当前的零变为正值时，使目标函数下降最大。出基变量的选择也不是任意的，原则是要保证变量满足非负条件。为此，要考察约束条件。这两个方程均有变量x?1要从0上升为正值，要从x?4和x?5这两个变量中选择一个出基（即从当前值下降到0) ，而另两个非基本变量x?2和x?3还要保持为零。由式??x?4=6-2x?1-x?2-x?3x?5=2-x?1-x?3??得??x?4=6-2x?1x?5=2-x?1?? x?1从0变为正值时，x?4和x?5可从当前值下降为0，但不能成为负值（因为变量要满足非负条件）。由上式可以看出，x?1取x?1=θ??min? =?min? b?ia?i1=21=2时，x?4和x?5均为非负 (x?4=2>0, x?5=0) ，且θ??min? 使x?5=0，因此选x?5为出基变量。已经确定了进基变量x?1和出基变量x?5，就可进行新的消元求解。继续求解下面的方程：??0x?5+x?2+x?3+x?4+2x?1=6x?5+0x?2+x?3+ 0x?4+x?1=2?? 此时，令非基本变量x?2=x?3=x?5=0，求x?1和x?4的解。为了下面便于说明建立单纯形表的过程，用初等变换（消元）求解上面的方程，结果为??-2x?5+x?2-x?3+x?4+0x?1=2x?5+0x?2+x?3+0x?4+x?1=2??解得??x?1=2, x?4=2?? 再将x?1和x?4用约束方程的非基本变量表示，得??x?4=2-x?2+x?3+2x?5x?1=2-x?3-x?5??将其代入目标函数，得??z=-6(2-x?3-x?5)+3x?2-2x?3+c?4(2-x?2+x?3+2x?5)+c?5x?5??整理得??z=-6×2+c?4×2+(3-c?4)x?2+(-2+6+c?4)x?3+(c?5+6+2c?4)x?5??由于所有非基本变量的系数均为非负，没有进一步可使目标函数减少的非基本变量，因此迭代结束，最优解为x?1=2,x?2=0,x?3=0,f=-12. 根据3.2.2节的介绍及上面的计算，单纯形法的一般步骤可归纳如下。 (1) 把线性规划问题的约束方程组表达成标准形方程组，然后找出一个基本可行解作为初始基本可行解。对等式约束或“≥b?i”形式的约束，如果不易得出初始基本可行解，则需