最优化方法上机报告

上机报告

一.最速下降法

算法简述：

1.在本例中，先将最速下降方向变量赋一个值，使其二范数满足大于ε的迭代条件，进入循环。

2.将函数的一阶导数化简，存在一个矩阵，将其hesse矩阵存在另一个矩阵。依照公式求出α，进而求出下一任迭代的矩阵初值。循环内设置一个计数功能的变量，统计迭代次数。

3.求其方向导数的二范数，进行判别，若小于ε，则跳出循环，否则将继续迭代。

4.显示最优解，终止条件，最小函数值。

心得体会：

最速下降法的精髓，无疑是求梯度，然后利用梯度和hesse矩阵综合计算，求解下一个当前最优解。但是，要求函数是严格的凸函数，结合严格凸函数的大致图像，这就给初值的选取提供了一点参考。例如在本例中，由于含有两个变量的二次方之和，结合大致图像，想当然的，初值的选取应当在原点附近；又因为变量的二次方之和后面，还减去了变量的一次形式和一次混合积，所以初值的选取应该再向第一象限倾斜。

综合以上考量，第一次选取（1,1）作为初值，判别精度方面，取到千分位，暂定为0.001。运行以后，结果显示迭代了25次，最优解为（3.9995，1.9996），终止条件为5.4592e-04，目标函数为-8.0000。这个结果已经相当接近笔算结果。整体的运

《最优化方法》复习题

一、 简述题

1、怎样判断一个函数是否为凸函数. （例如: 判断函数2122

212151022)(x x x x x x x f +-++=是否为凸函数） 2、写出几种迭代的收敛条件.

3、熟练掌握利用单纯形表求解线性规划问题的方法（包括大M 法及二阶段法）.

见书本61页(利用单纯形表求解);

69页例题 (利用大M 法求解、二阶段法求解);

4、简述牛顿法和拟牛顿法的优缺点.

简述共轭梯度法的基本思想.

;

写出Goldstein 、Wolfe 非精确一维线性搜索的公式。

5、叙述常用优化算法的迭代公式．

（1）法的迭代公式：(1)(),().

k k k k k k k k a b a a b a λτμτ=+--??=+-?

（2）Fibonacci 法的迭代公式：111(),(1,2,,1)()n k k k k k n k n k k k k k n k F a b a F k n F a b a F λμ---+--+?=+-??=-??=+-??

．

（3）Newton 一维搜索法的迭代公式： 11k k k k x x G g -+=-． （4）推导最速下降法用于问题1min ()2

T T f x x Gx b x c =++的迭代

最优化方法习题1答案

《最优化方法》（研究生）期末考试练习题答案

二.简答题

min -5y1 9y2, s.t. 4y1 3y2 3, -2y1 y2 2, 1．

3y1 4y2 8, y1,y2 0;

x3 x4 0, （以x1为源行生成的割平面方程） 2．

注意：在x1为整数的情况下，因为x3,x4 0，该方程自然满足，这是割平面的退化情形

1

656

111

x3 x4 , （以x2为源行生成的割平面方程）

442

3．

a1 0,b1 3

1 a1 0.382(b1 a1) 0 0.382*3 1.146

1 a1 0.618(b1 a1) 0 0.618*3 1.854 ( 1) (1.146)3 2*1.146 1 0.2131 ( 1) (1.854)3 2*1.854 1 3.6648

事实上,不经计算也可以看出

( 1) ( 1)，所以a2 0,b2 1.854。

即：初始的保留区间为[0，1.854]。近似的最优解：x*

0 1.854

0.927.2

f1(x) x1e x2*( 1) 2.7 x1ex2 2.7

4．令

f2(x) x1

《最优化方法及其应用》 课 程 实 验 报 告

项目名称： 学生姓名： 学生学号： 指导教师： 完成日期：

一、 实验内容

项目一 一维搜索算法（一）

最优化方法课程实验 许庆平 3111008162 杨理平 2013年12月30 [实验目的]

编写加步探索法、对分法、Newton法的程序。 [实验学时] 2学时 [实验准备]

1．掌握一维收搜索中搜索区间的加步探索法的思想及迭代步骤； 2．掌握对分法的思想及迭代步骤；

3．掌握Newton法的思想及迭代步骤。 [实验内容及步骤]

编程解决以下问题：

1．用加步探索法确定一维最优化问题

min?(t)?t3?2t?1t?0

的搜索区间，要求选取t0?0,h0?1,??2．

2．用对分法求解

min?(t)?t(t?2)，

已知初始单谷区间[a,b]?[?3,5]，要求按精度??0.3，??0.001分别计算．

3．用Newton法求解

min?(t)?t3?2t?1，

已知初始单谷区间[a,b]?[0,1]，要求精度??0.01．

项目二 一维搜索算法（二）

[实验目的]

编写黄金分割法、抛物线插值法的程序。 [实验学时]

2学时 [实验准备]

1．掌握黄金分割法的思想及迭

实用标准文案

精彩文档

华南农业大学期末考试试卷（A 卷）

2010--2011学年第 1 学期 考试科目： 运筹学与最优化方法 考试类型：（闭卷）考试 考试时间： 120 分钟 学号 姓名 年级专业

一、 用单纯形法求解下列线性规划问题（共 15 分）

12121212max 105349

..528,0z x x x x s t x x x x =++≤??

+≤??≥?

2

二、灵活运用单纯形法和对偶单纯形法解下列问题（共 15 分） 12

121212

max 62..33

,0z x x x x s t x x x x =++≥??+≤??≥?

实用标准文案

精彩文档

三、解下列0-1型整数规划问题（共 10 分）

12345

123451345124512345max 3252324

73438..116333

,,,,01

z x x x x x x x x x x x x x x s t x x x x x x x x x =+--+++++≤??+-+≤??-+-≥??=?或

四、利用库恩-塔克（K-T ）条件求解以下问题（共 15 分）

22

121122

121212max ()1

第6章 约束最优化方法

6.1

可行方向法 罚函数法 乘子法

主 要 内 容

6.2 6.3

6.4 6.5

二次规划问题 网格法

求解约束最优化问题比求解无约束最优化问题要困 难的多，因为每次迭代不仅要使目标函数值下降 (对最小化问题),同时还要考虑解的可行性问题。

求解约束非线性优化问题的方法很多。 有些是将约束非线性优化问题转化为无约束非线 性优化问题(SUMT),如罚函数法(外点法)、 障碍函数法(内点法)等， 有些是通过构造下降可行方向进行迭代，如 Zoutengijk可行方向法、Rosen梯度投影法、简约 梯度法等， 有些是将非线性优化问题转化为线性规划问题， 如线性逼近法等；还有网格法等等。

6.1 可行方向法

可行方向法是求解约束最优化问题的一类常用方法，

是无约束最优化问题下降迭代算法的自然推广。

可行方向法的典型策略是从某可行点出发，沿该点

的下降可行方向进行搜索，求出使目标函数值下降的新的可行点,

算法的主要步骤是选择搜索方向和确定沿此方向搜索的步长。

搜索方向的选择方式不同就形成不同的可行方向法。

6.1.1 可行方向法概述

6.1.2 Zoutendijk可行方向法

第二章最优化方法 运筹学简述

运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案”。 故有人称之为最优化技术。 最优化 最优化： 指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。 最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。

运筹学的主要内容

数学规划（线性规划、整数规划、目标规划、动态规划等） 图论 存储论 排队论 对策论

排序与统筹方法 决策分析

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

运筹学在工商管理中的应用涉及几个方面： 生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计

另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。 第一节线性规划 (Linear Programming)

线性规划问题的数学模型 1. 规划问题

线性规划问题的数学模型

例1.1 如图所示，如何截取

第二章最优化方法 运筹学简述

运筹学（Operations Research） 系统工程的最重要的理论基础之一，在美国有人把运筹学称之为管理科学(Management Science)。运筹学所研究的问题，可简单地归结为一句话： “依照给定条件和目标，从众多方案中选择最佳方案”。 故有人称之为最优化技术。 最优化 最优化： 指针对决策问题，按照决策的目标，从多个可能的方案中选择出最好的方案的过程。 最优化方法的主要研究对象是各种人类组织的管理问题和生产经营活动，其目的在于求得一个合理运用人力、物力和财力的方案，使资源的使用效益得到充分的发挥，最终达到最优目标。

运筹学的主要内容

数学规划（线性规划、整数规划、目标规划、动态规划等） 图论 存储论 排队论 对策论

排序与统筹方法 决策分析

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

运筹学在工商管理中的应用涉及几个方面： 生产计划 运输问题 人事管理 库存管理 市场营销 财务和会计

另外，还应用于设备维修、更新和可靠性分析，项目的选择与评价，工程优化设计等。 第一节线性规划 (Linear Programming)

线性规划问题的数学模型 1. 规划问题

线性规划问题的数学模型

例1.1 如图所示，如何截取

《最优化原理与方法》复习题

一．美佳公司计划制造 I、II 两种家电产品。已知各制造一件时分别占用设备 A、B 的台时、调试时间、调试工序每天可用于这种家电的能力、各售出一件时的获利情况，如下表所示。

（1）试写出上述问题的数学规划模型； （2）给出求解该模型的lingo代码。

二．将下列线性规划化为标准型，并列出初始单纯形表。

miny??3x1?4x2?2x3?5x4, s.t. 4 x1?x2?2x3?x4??2, x1?x2?3x3?x4?14, ?2x1?3x2?x3?2x4?2, x1,x2,x3?0,x4无约束;

三．已知线性规划问题

max x1?2x2?3x3?4x4, s.t. ?x1? x2?x3?3x4 ?5, 6x1?7x2?3x3?5x4?8, 12x1?9x2?9x3 ?9x4?20, x1,x2?0,x3?0,x4无约束;写出其对偶规划。

四．试选用一种方法求解下述线性规划问题

minz

第七章 最优化方法简介

7.1 最优化问题—— Optimization

Minf(x)?Minf(x1,x2,?,xn)s.t.gi(x)?gi(x1,x2,?,xn)?0i?1,2,?,m

可行域： D?x?Rngi(x)?0可行点： ?x?D

问题的解：x??D——最优解； 线性规划——f(x),gi(x)?i?1,2,?,m

?i?1,2,?,m——均为线性函数，

其他一般称为：非线性规划；

其中，若f(x)为二次函数，gi(x)i?1,2,?,m为线性函数——二次规划， 其他如：几何规划、动态规划 etc.

7.2 一维优化方法

对象：Minf(x),x?[a,b]?R， 简化： f(x),x?[a,b] 为

单峰函数——

x??[a,b],f(x)?:?x?[a,x?),?f(x)?:?x?(x,b]

当f(x)在[a,b]上可导，则问题转化为求解方程f?(x)?0的问题，这是第5章所讨论的内容。

以下讨论其他方法。

7.2.1 四等分法

等分方法，或分段检验的目的主要是希望能确定解在哪部分内从而可以保留，或者说哪部分可以删去。据此，使保留部分越来越小，获得所需要的结果。

比较：二