实验报告
题目：序列二次规划法求极值
班级： 数学系09级5班
组成员：
程序设计者：
算法设计者:
实验报告设计者：
优化问题实验报告：
1题目 运用序列二次规划法求优化问题
2问题叙述
用序列二次规划法来求解优化问题
Min f(x)=x2
s.t –x2≤0;
x-1≤0;
3方法介绍
序列二次规划法的步骤：
一、搜索方向d的确定
二、步长的确定
4
程
序
代 运行环境为VC++6.0
/*/
#include
#include
double alpha(double*x)
{ 码
VC++
环
境
return((x[0]+x[1]-1)*(x[0]+x[1]-1));
}
double func( double *x ,int mr)
{
return
0.5*x[0]*x[0]+0.166667*x[1]*x[1]+mr*alpha(x);
}
void vgrand( double*p ,double *x, int mr)
{
p[0]=-1*x[0]-2*mr*(x[0]+x[1]-1);
p[1]=-0.3333333*x[1]-2*mr*(x[0]+x[1]-1);
}
double norm ( double *x )
{
return
sqrt ( 0.5*x[0]*x[0]+0.166667*x[1]*x[1] );
}
double goldf (double t, double*p, double *x,int mr)
{
double xtmp[2];
for (int i=0; i!=2; ++i)
xtmp[i]=x[i]+p[i]*t;
return func(xtmp,mr);
}
double gold (double begin ,double end, double t2, double *p, double
第4讲 最优化问题
一、知识要点
在日常生活和生产中，我们经常会遇到下面的问题：完成一件事情，怎样合理安排才能做到用的时间最少，效果最佳。这类问题在数学中称为统筹问题。我们还会遇到“费用最省”、“面积最大”、“损耗最小”等等问题，这些问题往往可以从极端情况去探讨它的最大（小）值，这类问题在数学中称为极值问题。以上的问题实际上都是“最优化问题”。
二、精讲精练
【例题1】 用一只平底锅煎饼，每次只能放两个，剪一个饼需要2分钟（规定正反面各需要1分钟）。问煎3个饼至少需要多少分钟？
练习1：
1.烤面包时，第一面需要2分钟，第二面只要烤1分钟，即烤一片面包需要3分钟。小丽用来烤面包的架子，一次只能放两片面包，她每天早上吃3片面包，至少要烤多少分钟？
2.用一只平底锅烙大饼，锅里只能同时放两个。烙熟大饼的一面需要3分钟，现在要烙3个大饼，最少要用几分钟？
3.小华用平底锅烙饼，这只锅同时能放4个大饼，烙一个要用4分钟（每面各需要2分钟）。可小华烙6个大饼只用了6分钟，他是怎样烙的？
【例题2】妈妈让小明给客人烧水沏茶。洗水壶需要1分钟，烧开水需要15分钟，洗茶壶需要1分钟，洗茶杯需要1分钟。要让客人喝上茶，最少需要多少分钟？
练习2：
1.小虎早晨要完成这样几件事：烧一壶开水需要10分钟，把开水灌进热水瓶需要2分钟，取奶需要5分钟，整理书包需要4分钟。他完成这几件事最少需要多少分钟？
2.小强给客人沏茶，烧开水需要12分钟，洗茶杯要2分钟，买茶叶要8分钟，放茶叶泡茶要1分钟。为了让客人早点喝上茶，你认为最合理的安排，多少分钟就可以了？
3.在早晨起床后的1小时内，小欣要完成以下事情：叠被3分钟，洗脸刷牙8分钟，读外语30分钟，吃早餐10分钟，收碗擦桌5分钟，收听广播30分钟。最少需要多少分钟？
【例题3】五（1）班赵明、孙勇、李佳三位同学同时到达学校卫生室，等候校医治病。赵明打针需要5分钟，孙勇包纱布需要3分钟，李佳点眼药水需要1分钟。卫生室只有一位校医，校医如何安排三位同学的治病次序，才能使三位同学留在卫生室的时间总和最短？
第5章 Newton型方法
(Newton-type Method)
§5.1 Newton法
对于正定二次函数
121
2()(,)TTfXfxxXAXbXc==++（A正定矩阵）要
具有二次终结性，即在处沿
0X)(
00Xfp−∇=到))((
0001XfXX−∇+=λ，再沿某
方向直达最优点
1p
111*pXXλ+=，则方向具有性质：在处沿方向进行
精确一维搜索有，说明与正交，可令1p
1X
1p
0
10=AppT
0p
1Ap
1()
1fXAp−∇=，得
，或。 1
11()pAfX−=−∇21
11[()](pfXf−=−∇∇
1)X
事实上，方向可以理解为从出发沿经一次精确一维搜索便得最优
点。 1p
1X
1p6656556
对于一般函数()fX，记，
，有 2(),()gfXGfX=∇=∇
2(),(
kkkgfXGfX=∇=∇)k
)()()(
21
)()()(2
kkkkkT
kkXXoXXGXXXXgXfXf−+−−+−+=
)()(
21
)()()(
kkT
kkT
kkXXGXXXXgXfX−−+−+=ψ
)()(XXfψ≈
一、Newton法
定理5-1-1：正定⇒
kG)(Xψ有唯一极小值点
证明：正定kG⇒)(Xψ严格凸)(Xψ⇒有唯一极小值点
定理5-1-2：正定⇒
kG)(Xψ的极小值点1
1kkkkXXGg−
+=−
X极小值点
kkkkkkgGXXgXXGX10)(0)(−−=⇒=+−⇒=∇⇒ψ
注：对于正定二次型，用方向一次到达最优点。 1()()
kkk1
kkGg−=−pGXfX−=−∇
定义：牛顿方向(Newton direction)1
kkkpGg−Δ−
注：①一般情况下不一定正定，甚至也不一定可逆；②不正定时不
一定下降方向；③步长kG
kG
kG
kp
1≠
kλ，可以是不断变化的；④只在的附近有效。 kX
定理5-1-3：设()fX是二阶连续可微函数，且
（1） 存在*X使； *()0fX∇=
（2） 存在使0L>()(),,GXGYLXYXY−<−∀；
1第一章绪论
2最优化：就是从所有可能的方案中，选出最合理
的，达到事先规定的最优目标的学科。
这样的问题称为最优化问题，
达到最优目标的方案称为最优方案，
寻找最优方案的方法称为最优化方法。§1.1引言
广义上：运筹学(Operation Research)
狭义上：数学规划（programming)
3发展:
(1)最优化问题是一个古老的问题。早在17世纪，
Newton和Leibniz已经提出了函数的极值问题，
但没有系统的理论.因为算法不完善及计算工具
不先进，以后二、三百年发展缓慢。
（2）第二次世界大战中由于军事上(战略、战术）
的需要，如
资源调配问题
运输问题
提出了许多不能用古典方法解决的问题，从而
产生了线性规划，非线性规划、动态规划、组
合优化等新方法，产生运筹学，
4（3）
但直到20世纪40年代，最优化的理论和算法才得
以迅速发展，并不断完善，逐步成为一门系统的学
科。在实际中最优化方法发挥的作用越来越大，其
应用越来越广泛，尤其是在工程设计中的应用。
重要性：因为应用广泛
所需数学知识：高等数学、线性代数
5§1.2 优化问题的模型举例
6例1 产品调运问题
设某产品有个产地，各产地产品的产量分别为m
12,,,
maaa
有n
个销售地，每个销地的销量分别为
12,,,
nbbb
设由第i个产地到第j个销地的运费单价为
ijc
问如何安排运输计划，使总运费最小（假设产销平衡）。
ijx
解设由第i个产地到第j个销地的运输量为
1n
j
1m
imin
1(1,2,,)n
iji
jxaim
1(1,2,,)m
ijj
ixbjn
0(1,2,,1,2,,)
ijximjn，..s
tijijcx
1a
ia
ma
1b
jb
n
bijc
ijx
7例2将非线性方程组
的求解转化为一优化问题。112
212
12(,,,)0
(,,,)0
(,,,)0n
n
nnfxxx
fxxx
fxxx
2
1212
1min(,,,)(,,,)n
