《*优化方法》介绍*优化的基本概念、常用算法及有关的理论分析和应用,全书包括7部分内容,分别是绪论、线性规划、非线性规划、多目标规划、动态规划、现代优化方法和MATLAB在优化中的应用。书中的部分例题和案例用MATLAB软件做了演示计算,各章给出了典型例题并配有一定数量的习题,书后给出了部分习题答案或提示。便于读者加深对书中内容的理解。
《*优化方法》可作为理工科大学数学类本科少学时和工科硕士研究生的*优化课程教科书,还可作为理工科本科生和工程技术人员的学习参考书。 *优化方法_王开荣 主编_科学出版社_

前言
一、绪论
二、线性规划
第1章 线性规划与单纯形方法
1.1 线性规划问题举例
1.2 线性规划问题的标准形及解的概念
1.3 线性规划问题的图解法
1.4 线性规划的基本定理
1.5 单纯形方法
1.6 单纯形方法的补充与说明
习题1
第2章 对偶问题与灵敏度分析
2.1 对偶问题及其数学模型
2.2 对偶单纯形方法
2.3 灵敏度分析
2.4 参数线性规划
习题2
第3章 整数线性规划
3.1 整数规划及其数学模型
3.2 割平面方法
3.3 分支定界法
3.4 0-1规划的割平面方法
习题3
第4章 运输问题与指派问题
4.1 运输问题及其数学模型
4.2 表上作业法
4.3 指派问题及其数学模型
习题4
三、非线性规划
第5章 无约束非线性规划
5.1 基本概念与性质
5.2 一维搜索方法
5.3 *速下降法
5.4 Newton法
5.5 拟Newton法
5.6 共轭梯度法
5.7 Powell方法
习题5
第6章 约束非线性规划
6.1 约束非线性规划问题的*优性条件
6.2 罚函数法
6.3 乘子法
6.4 可行方向法
6.5 二次规划
习题6
四、多目标规划
第7章 多目标规划简介
7.1 多目标规划问题的数学模型
7.2 多目标规划问题解的概念与性质
7.3 求解多目标规划问题的评价函数法
习题7
五、动态规划
第8章 动态规划简介
8.1 多阶段决策过程
8.2 动态规划的基本概念和基本原理
8.3 动态规划应用举例
习题8
六、现代优化方法
第9章 现代优化方法简介
9.1 模拟退火算法
9.2 遗传算法
9.3 粒子群优化算法
9.4 蚁群优化算法
9.5 神经网络算法
9.6 禁忌搜索算法
七、MATLAB在优化中的应用
第10章 MATLAB初步
10.1 MATLAB界面
10.2 基本运算与函数
10.3 矩阵和数组的运算
10.4 MATLAB作图
10.5 程序设计
第11章 MATLAB优化工具箱
11.1 线性规划
11.2 非线性规划
11.3 多目标规划
11.4 动态规划
11.5 遗传算法
11.6 GUI优化工具
11.7 优化工具箱函数
习题参考答案或提示
参考文献

第1 章 线性规划与单纯形方法
1.1 线性规划问题举例
例1.1(生产计划问题) 设生产A ,B ,C 三种产品,每吨利润分别2 万元、3 万
元、1 万元,生产单位产品所需的工时和原材料如表1.1 所示.
若所能利用的劳动力总工时是固定的4 个单位,供应的原材料每天不超过9t ,
试制订生产计划,使三种产品的总利润*大.
解 设x1 ,x2 ,x3 分别为产品A ,B ,C 的产量,由题意,劳动力约束条件为x1 +
2 x2 + 2 x3 ≤ 4 ,原材料约束条件为x1 + 4 x2 + 7 x3 ≤ 9 ,故生产计划问题的数学模
型为
max z = 2 x1 + 3 x2 + x3
s.t.
x1 + 2 x2 + 2 x3 ≤ 4
x1 + 4 x2 + 7 x3 ≤ 9
x1 ,x2 ,x3 ≥ 0
例1.2(用料*省问题) 有一批长为7.4m 的钢管,需要切断成2.9m 的100 根,
2.1m 的200 根,1.5m 的300 根,问应如何下料,才能使用料*省?
解 7.4m 钢管的可能分割方式如表1.2 所示.
设用于各种切割方式的钢管分别为x1 ,x2 ,… ,x8 根,则用料问题的数学模
型为
min 0 x1 + 0.1 x2 + 0.2 x3 + 0.3 x4 + 0.8 x5 + 0.9 x6 + 1.1 x7 + 1.4 x8
s.t.
x1 + 2 x2 + x4 + x6 ≥ 100
2 x3 + 2 x4 + x5 + x6 + 3 x7 ≥ 200
3 x1 + x2 + 2 x3 + 3 x5 + x6 + 4 x8 ≥ 300
x1 ,x2 ,… ,x8 ≥ 0 且为整数.
从以上两个例题可知,线性规划问题具有以下特征:
(1) 用一组决策变量( x1 ,x2 ,… ,xn )T 表示某一方案,在一般情形下,决策变量
有非负限制;
(2) 目标函数和约束条件函数都是线性函数;
(3) 目标函数实现*大化或*小化;
(4) 约束条件是线性等式或线性不等式.
1.2 线性规划问题的标准形及解的概念
1.2.1 线性规划问题的标准形
线性规划问题的目标函数有*大、*小的形式,约束条件有“ ≤ ” 、“ ≥ ” 、“ = ”的
形式,这给讨论问题带来了不便.因此,本书规定线性规划问题的标准形(standard
form)为
max z = c1 x1 + c2 x2 + … + cn xn
s.t.
a11 x1 + a12 x2 + … + a1 n xn = b1
a21 x1 + a22 x2 + … + a2 n xn = b2
… …
am1 x1 + am2 x2 + … + amn xn = bm
x1 ,x2 ,… ,xn ≥ 0
(1.1)
称c1 ,c2 ,… ,cn 为价值系数,b1 ,b2 ,… ,bm 为资源限制量,aij ( i = 1 ,2 ,… ,m ;j = 1 ,
2 ,… ,n)为第i 个产品对第j 种资源的单位消耗量.线性规划问题的标准形也可以
有以下的表述形式:
(1) 缩写形式:
max z = Σ
n
j = 1
cj x j
s.t. Σ
n
j = 1
aij x j = bi , i = 1 ,2 ,… ,m
xj ≥ 0 , j = 1 ,2 ,… ,n
(2) 向量形式:
max z = cT x
s.t. Σ
n
j = 1
pj x j = b
xj ≥ 0 , j = 1 ,2 ,… ,n
其中c = ( c1 ,c2 , … ,cn )T ,x = ( x1 ,x2 , … ,xn )T ,pj = ( a1 j ,a2 j , … ,amj )T ,b = ( b1 ,
b2 ,… ,bm )T.
(3) 矩阵形式:
max z = cT x
s.t.
Ax = b
x ≥ 0
其中
A = ( p1 ,p2 ,… ,pn ) =
a1 1 a12 … a1 n
a2 1 a22 … a2 n
? ? ?
am1 am2 … amn
称为约束方程组的系数矩阵.
以后介绍线性规划问题的一些基本概念和求解方法都是针对线性规划标准形
而得的.对非标准形的线性规划问题,可施展适当的变换将其转化为标准形.
(1) 若目标函数为min z = c1 x1 + c2 x2 + … + cn x n ,则令z′ = - z 便有max z′ =
- c1 x1 - c2 x2 - … - cn xn ;
(2) 不等式约束ai1 x1 + ai2 x2 + … + ain xn ≤ bi ,增加松弛变量xn + i ≥ 0 便有
ai1 x1 + ai2 x2 + … + ain xn + xn + i = bi
不等式约束ai1 x1 + ai2 x2 + … + ain xn ≥ bi ,增加剩余变量(也称为松弛变量) xn + i ≥ 0
便有
ai1 x1 + ai2 x2 + … + ain xn - xn + i = bi
(3) 对无非负要求的自由变量xi ,令xi = x′i - x″i ,其中x′i ≥ 0 ,x″i ≥ 0 ,由x′i ,x″i
的大小来确定x i 的正负.
例1.3 将下列线性规划问题化为标准形:
min z = x1 - 2 x2 + 3 x3
s.t.
x1 - x2 + x3 ≤ 3
2 x1 - x2 + 3 x3 ≥ 5
x1 + x2 + x3 = 4
x1 ,x3 ≥ 0 ,x2 为自由变量
解 原问题化为标准形式为
max z′ = - x1 + 2 x′2 - 2 x″2 - 3 x3
s.t.
x1 - x′2 + x″2 + x3 + x4 = 3
2 x1 - x′2 + x″2 + 3 x3 - x5 = 5
x1 + x′2 - x″2 + x3 = 4
x1 ,x′2 ,x″2 ,x3 ,x4 ,x5 ≥ 0
1.2.2 线性规划问题解的概念
(1) 可行解(feasible solution).若x 满足Ax = b 且x ≥ 0 ,则称x 为线性规划
问题(1.1)的可行解.称D = { x| Ax = b ,x ≥ 0}为线性规划问题(1.1)的可行域.可
行解是可行域内的点,有时也称为可行点.
(2) *优解(optimal solution).满足(1.1)的解称为*优解.
(3) *优值(optimal value).若x 是(1.1)的*优解,则称z = cT x 为(1.1)的*
优值.
(4) 基(basis).设(1.1)约束方程组的系数矩阵是m × n 矩阵,其秩为r( A) =
m ,若B 是A 中的m 阶非奇异子矩阵,则称B 为(1.1)的一个基矩阵,简称为基.
(5) 基变量(basic variable).基矩阵B 的列向量p j 称为基向量,所对应的决策
变量称为基变量.
不妨设A 的前m 个列向量线性无关(其他情形类似) ,即矩阵A 可表示为A =
( B ,N) ,称N 为非基矩阵,约束等式Ax = b 可表示为
( B ,N)
xB
xN
= b
故有xB = B- 1 b - B- 1 NxN.若取非基变量xN = 0 ,则有xB = B- 1 b.
(6) 基解( basic solution).称x =
xB
xN
=
B- 1 b
0 为线性规划问题(1.1) 的
基解.
(7) 基可行解(basic feasible solution).若x 是线性规划问题(1.1)的基解且
xB = B- 1 b ≥ 0 ,则称x 为(1 ,1)的基可行解.
线性规划的基可行解的个数是有限的,其个数不超过Cm
n.
(8) 退化(degenerate).若基可行解x 中存在值为0 的基变量,则称此基可行
解x 为退化的基可行解;若基变量都是严格大于0 的,则称x 为非退化的基可
行解.
(9) 非退化(non唱degenerate).若(1.1)的所有基可行解都是非退化的,则称
(1.1)为非退化的线性规划问题.
1.3 线性规划问题的图解法
图解法只适合于求解两个变量的线性规划问题,其优点是简单、直观,有助于
理解线性规划问题的几何特征,更能直观地了解线性规划的算法思想和求解步骤,
将有助于加深线性规划的通用算法―― 单纯形方法的理解.
例1.4 求解如下线性规划问题:
max z = x1 + x2
s.t.
2 x1 + x2 ≤ 3
x1 + 2 x2 ≤ 3
x1 ≥ 0 ,x2 ≥ 0
解 如图1.1 所示,可行域是由x1 ,x2 坐标轴与直线2 x1 + x2 = 3 ,x1 + 2 x2 = 3
所围成的区域在**象限中的部分.
对目标函数z = x1 + x2 ,将z 作为参数取一组不同的值,从而得到一组相应的
平行线,称之为目标函数的等值线.对极大化问题沿目标函数值增加的方向移动目
标函数的等值线,直到可行域边界的极限位置为止.如图1.1 所示,在x1 + x2 = 2
处,可行域边界的极限点就是*优解.对本例而言,*优解是直线2 x1 + x2 = 3 ,
x1 + 2 x2 = 3 的交点(1 ,1) ,*优值为z = 2.
若是极小化问题,就让目标函数的等值线沿目标函数值减小的方向平行移动.
从图1.1 可知,线性规划问题的几何特征如下:
(1) 若线性规划问题的可行域非空,则其可行域为一凸多边形;
(2) 若线性规划问题有*优解,则必有可行域的一个顶点为其*优解;
(3) 线性规划问题的*优解可能不**,但其目标函数的*优值是**的;
(4) 线性规划问题的可行域和*优解有以下几种可能情况:
(i) 可行域为一有界闭区域,线性规划问题有***优解或有一个以上的*
优解,如图1.2 所示;
(ii) 可行域为无界区域,有一个***优解或有多个*优解,或无*优解(目
标函数无界) ,如图1.3 所示;
(iii) 可行域为空,无可行解,即约束条件出现了矛盾约束.
1.4 线性规划的基本定理
1.4.1 凸集和极点
(1) 凸集(convex set).设集合D 炒Rn ,若橙x(1) ,x(2) ∈ D 均有αx(1) + (1 - α) x(2)
∈ D( 橙α ∈ [0 ,1]) ,则称D 为凸集,如图1.4 所示.
从图1.4 中可以看出,连接凸集内任意两点的连线段均在凸集内.
(2) 凸组合(convex combination).设m 个点x(1) ,x(2) ,… ,x( m) ∈ Rn ,若存在m
个数k1 ,k2 ,… ,km ,满足ki ≥ 0( i = 1 ,2 ,… ,m) ,Σ
m
i = 1
ki = 1 ,使得x = k1 x(1) + k2 x(2)

王开荣主编的《*优化方法》编写时特别注重课程体系的完整性、应用性和内容的可读性。为此,在系统介绍基本概念与基础理论时,省略了一些烦琐艰深的证明和推导过程,侧重于算法的叙述和算例分析。行文时注重通俗易懂,对专业术语尽量作通俗的解释,以增强本书的可读性。