[数学]最优化方法刘第四章

第四章 无约束最优化直接方法 无约束最优化直接方法只要求目标函数是连续的，求解过程中不需要

计算目标函数的导数。

1.单纯形替换法

1)单纯形

(1)定义: 中的单纯形就是指具有个顶点的多面体。若各棱长相

等，称为正规单纯形。

(2)正规单纯形的构建：

已知正规单纯形任一顶点和棱长。

根据棱长构建数组，其中，

正规单纯形的顶点坐标为：，，

在二维情形下，该方法构建的单纯形为一等边三角形。

(3)一般单纯形的构建

已知单纯形任一顶点和正数。

令

则单纯形的顶点坐标为：，，

在二维情形下，该方法构建的单纯形为一直角三角形。

2)基本想法

选定一个初始点，根据上述方法形成初始单纯形，从这一单纯形出

发，通过迭代设法构造新的单纯形以替换原有的单纯形，使新单纯形不

断向目标函数的极小点靠近，直到搜寻到极小点为止。

3)算法

已知目标函数，单纯形各顶点的位置，终止限。

(1)

计算，

令，，于是和分别是单纯形的最好和最坏的顶点。

把顶点去掉，则剩下的顶点构成维空间中的单纯形，其中心。(2)反射

按如下公式通过反射，，其中，称为反射系数，通常取,称为的反

射点。

当时，转(3)，否则转(4)

(3)延伸

计算延伸点,,称为延伸系数。

①如果，那么就用替换，构成新的单纯形,否则，那么就用替换，

构成新的单纯形。②转(6)

(4)收缩

①存在一个标号，,。

也就是说，除最坏点外，反射点至少比其余一个顶点好。此时以替

换构成新的单纯形,转(6)。

②

在这种情况下，反射点比原单纯形所有的顶点还坏。说明反射方向

错误，则舍弃不管，沿方向进行收缩。

，其中是的收缩点，而是收缩系数。

如果，则舍弃收缩点，转(5),减少原单纯形棱长，否则以替换构

成新的单纯形,转(6)。

③，且，但

在这种情况下，反射点只比好，则沿方向进行收缩。

如果，则舍弃收缩点，转(5),减少原单纯形棱长，否则以替换构

成新的单纯形,转(6)。

(5)减少棱长

原单纯形的最好点保持不动，各棱长减半。此时可按下式计算各顶

点坐标。

，

(6)终止准则

计算，

最优化方法-习题解答

张彦斌

计算机学院2014年10月20日

Contents

1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、412第二章线搜索算法-P27习题2、4、643第三章最速下降法和牛顿法P41习题1，2，374第四章共轭梯度法P51习题1，3，6(1)105第五章拟牛顿法P73-2126第六章信赖域方法P86-8147第七章非线性最小二乘问题P98-1，2，6188第八章最优性条件P112-1，2,5,6239第九章罚函数法P132，1-(1)、2-(1)、3-(3),62610第十一章二次规划习题11P178-1（1），529

1第一章最优化理论基础-P13习题1(1)、2(3)(4)、3、4

1.验证下列各集合是凸集:

(1)S={(x1,x2)|2x1+x2≥1,x1−2x2≥1};需要验证：根据凸集的定义，对任意的x(x1,x2),y(y1,y2)∈S及任意的实数λ∈[0,1],都有λx+(1−λ)y∈S.即,(λx1+(1−λ)y1,λx2+(1−λ)y2)∈S证：由x(x1,x2),y(y1,y2)∈S得到，{2x1+x2≥1,x1−2x2≥12y1+y2≥1,y1−2y2≥1(1)

1把(1)中的两个式子对应的左右两部分分别乘以λ和1−λ,然后再相加，即得λ(2x1+x2)+(1−λ)(2y1+y2)≥1,λ(x1−2x2)+(1−λ)(y1−2y2)≥1(2)

合并同类项，

2(λx1+(1−λ)y1)+(λx2+(1−λ)y2)≥1,(λx1+(1−λ)y1)−2(λx2+(1−λ)y2)≥1(3)

证毕.

2.判断下列函数为凸（凹）函数或严格凸（凹）函数：

(3)f(x)=x21−2x1x2+x22+2x1+3x2首先二阶导数连续可微，根据定理1.5，f在凸集上是（I）凸函数的充分必要条件是∇2f(x)对一切x为半正定；（II）严格凸函数的充分条件是∇2f(x)对一切x为正定。

第二章 最优化方法

运筹学简述

运筹学（Operations Research）

系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：

“依照给定条件和目标，从众多方案中选择最佳方案”。

故有人称之为最优化技术。

最优化

最优化：

指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。

最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。

运筹学的主要内容

• 数学规划（线性规划、整数规划、目标规划、动态规划等）

• 图论

• 存储论

• 排队论

• 对策论

• 排序与统筹方法

• 决策分析

运筹学在工商管理中的应用

运筹学在工商管理中的应用涉及几个方面：

• 生产计划

• 运输问题

• 人事管理

• 库存管理

• 市场营销 • 财务和会计

另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。

第一节 线性规划

(Linear Programming)

线性规划问题的数学模型

1. 规划问题

线性规划问题的数学模型

例1.1 如图所示，如何截取x使铁皮所围成的容积最大？

线性规划问题的数学模型

线性规划问题的数学模型

解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：

线性规划问题的数学模型

线性规划问题的数学模型

线性规划问题的求解方法

线性规划问题的求解方法

图解法

max Z = 2X1 + X2

X1 + 1.9X2 ≥ 3.8

X1 - 1.9X2 ≤ 3.8

s.t. X1 + 1.9X2 ≤10.2

第二章 最优化方法

运筹学简述

运筹学（Operations Research）

系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话：

“依照给定条件和目标，从众多方案中选择最佳方案”。

故有人称之为最优化技术。

最优化

最优化：

指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。

最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。

运筹学的主要内容

• 数学规划（线性规划、整数规划、目标规划、动态规划等）

• 图论

• 存储论

• 排队论

• 对策论

• 排序与统筹方法

• 决策分析

运筹学在工商管理中的应用

运筹学在工商管理中的应用涉及几个方面：

• 生产计划

• 运输问题

• 人事管理

• 库存管理

• 市场营销 • 财务和会计

另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。

第一节 线性规划

(Linear Programming)

线性规划问题的数学模型

1. 规划问题

线性规划问题的数学模型

例1.1 如图所示，如何截取x使铁皮所围成的容积最大？

线性规划问题的数学模型

线性规划问题的数学模型

解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：

线性规划问题的数学模型

线性规划问题的数学模型

线性规划问题的求解方法

线性规划问题的求解方法

图解法

max Z = 2X1 + X2

X1 + 1.9X2 ≥ 3.8

X1 - 1.9X2 ≤ 3.8

s.t. X1 + 1.9X2 ≤10.2