课 程 编 号 : 0 7 0 0 0 2 0 3
北 京 理 工 大 学 2 0 0 7 - 2 0 0 8 学 年 第 二 学 期
2005 级数学专业最优化方法终考试卷（ A 卷）
A 、 B 、 C，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为
1． (20 分 )某化工厂有三种资源 x1,x 2,x 3 ,其数学模型为：
max z 3 x1 2 x2 5 x3
2 2 3 430 ( A资源限制 ) 1
x x x 3 x1 2 x3 460 ( B资源限制 ) s.t 4 2 420 (C资源限制 )
x x x1 , x2 , x3 0
请回答如下问题： （1）给出最优生产方案； （ 2）假定市场信息表明甲产品利润已上升了一倍，问生产方案应否调整？ （3）假定增加一种添加剂可显着提高产品质量，该添加剂的资源限制约束为：
xx
1
2
2
3x 3 800 问最优解有何变化？
2． (12 分 )用 Newton 法求解 min f ( x ) 4 x12 x22 2 x12 x 2 ，初始点取为 x0 (1, 1)T ，迭代一步。 3．(10 分 )用 FR 共轭梯度法求解三个变量的函数 索，得 x1
f ( x ) 的极小值，第一次迭代的搜索方向为 2,
p0 (1, 1,2)T ，沿 p0 做精确线搜
( x11 , x21 , x 31 )T ， 设 f ( x1 )
x11
f ( x1 )
x21
2 ，求从 x1 出发的搜索方向 p1 。
4． (15 分 ) 给定下面的
BFGS 拟 Newton 矩阵修正公式：
H
k 1
其中 sk
x
k 1
xk , yk
g
( I sk ykT )H k ( I sk yk T )T ykT sk yk T sk
sk skT ，
yk T sk
k 1
gk
2 4 x1 ，初始点取为 x0 (0,0) T ， H 0 I 。 2x1 x 2 2 x 22 用对应的拟 Newton 法求解： min f ( x ) x15． (15 分 )写出问题 取得最优解的 Kuhn-Tucker （ K － T ）必要条件，并通过 K － T 条件求出问题 K － T 点及相应 Lagrange 乘子。
6(12 分 )．求约束问题
(0,0) T 及 x 在 x
1
2
(1,0) T 处的下降方向集合、可行方向集合以及可行下降方向集合，并画图表示出来
7（ 8 分）考察优化问题
min f ( x ) s.t. x
D
，
设 D 为凸集， f ( x ) 为 D 上凸函数，证明： 8（ 8 分）设 min
f ( x) 在 D 上取得极小值的那些点构成的集合是凸集。
x0 x *
f ( x ) 1 xT Ax bT x c ，其中 A 为对称正定矩阵， x * 为 f ( x ) 的极小值点，又设 x 0 ( x*) 可表示为
2
R 1， p 是 A 对应于特征值 的特征向量，证明：若从 x0 出发，沿最速下降方向做精确一维搜索， p ，其中
则一步达到极小值点。 课程编号 :07000203
北京理工大学 2008-2009 学年第一学期
2006 级数学专业最优化方法终考试卷（ A 卷）
1． (15 分 ) 用单纯形法求解线性规划问题
2． (10 分 )写出线性规划问题
的对偶问题并证明该对偶问题没有可行解。
min f ( x) x12 2x22 ， 初始点取为 x0
0.1, 0.9 。 采用 Wolfe 条件进行不精确一维搜索，其中
3． (15 分 )考虑用最速下降法迭代一步 4． (15 分 )用 DFP 拟牛顿法求解
( 1, 1)T 。（ 1）采用精确一维搜索；（ 2）
min f ( x)
x12 2x22 初始点取为 x 0
1
1
，初始矩阵 H 0
2 1 。 1 1
5． (15 分 )证明集合 S { x | x1 6． (15 分 ?) 考虑问题 （1）用数学表达式写出在点
2x2 4, 2x1
x2 6} 是凸集，并计算原点
(0,0) 到集合 S 的最短距离。
（ 2）假设当前点在 (0,0) T 处，求出用投影梯度法进行迭代时当前的下降可行方向（搜索方向）。 7（ 7 分）证明：在精确一维搜索条件下，共轭梯度法得到的搜索方向是下降方向。
( , ) 处的下降可行方向集。
3 3
15T
ax
11
1
a21 x1
8（ 8 分）已知线性不等式组............................................. L a1 n x n b1
a22 x 2 L a2n xn b2
12 2 ax
其中
b1 , b2 L , bm
0 ，给出一种判断该不等式组是否相容（即 am 1 x1 am 2 x 2 L amn xn
bm
x1 , x2 L , xn 0
是否有解）的方法并说明理由。
课程编号 :07000203
北京理工大学 2009-2010 学年第一学期
2007 级数学专业最优化方法终考试卷（ A 卷）
1．（ 8 分）将优化问题
化为标准形式的线性规划问题。
2． (10 分 ) 给出一个判断任一线性不等式组是否相容（即是否有解）的一般条件，并利用其判断以下不等式组是否相容。 3． (12 分 )对于下面的线性规划
（1）利用对偶单纯形法求解；（
2）写出其对偶线性规划问题并利用对偶理论求出对偶问题的最优解。
4． (10 分 )考虑用最速下降法迭代一步 5． (15 分 )用 FR 共轭梯度法求解
min
f ( x) x12 2 x22 x12
min f ( x )
1 x 22 2
12x1 x2 ，初始点为 x 0 ( 1, 1)T 。
2
x32
初始点取为 x0
1,1,1
T
。
6． (10 分 ?) 考虑问题
min f ( x ) ( x1 1)2 s.t . x1
x 22
x2
2 0
写出问题取得最优解的
Kuhn-Tucker （ K － T ）必要条件，并通过
K － T 条件求出问题 K － T 点及相应 Lagrange 乘子。
min f ( x ) x2
x 2 2 x 2
1
4 x 2
1
7． (15 分 ?) 用简约梯度法求解问题
s.t . 2 x1 x2 1,
x1 x2 2, x1 0, x2 0.
，初始点取为 (0, 2)T 。
8 （ 10 分）基于单纯形算法，试给出一个判定线性规划问题具有唯一最优解的条件，并且举例说明之。 9(10 分 )．考虑优化问题
min f ( x)
，设 x k 为问题可行域中任一点，在 xk 处前 q 个约束为有效约束，记为
s..t Ax b, A Rm n , x Rn
Aq xk bq ，其中 Aq 为行满秩矩阵，令 P I A T ( A A T ) 1 A ，证明：（ 1） Pq 为投影阵。
q q q q q
（2）若 pkPq f (xk ) 课程编号 :07000203
0 ，则为问题的下降可行方向。
北京理工大学 2010-2011 学年第一学期
T
2008 级数学专业最优化方法终考试卷（ A 卷）
1(15 分 )求解线性规划
2． (12 分 )给定一个线性规划问题
（1）写出其对偶规划。（
2）假设已知该对偶规划的最优解为
5 , 7
，试求出原始问题的最优解。
3 3
100( x2 x12 )2
3． (15 分 )给定 Rosenbrock 函数 f ( x ) (2) 求出 f ( x ) 在点 x 1
(1 x1 )2 (1) 求出 f ( x ) 的驻点，并判断驻点的最优性。
k
( 1, 2)T 处的最速下降方向
4．(20 分 )无约束优化问题阻尼 Newton 法迭代公式为 xk 1
近似替代 Gk ，则搜索方向由 B p g 求出。初始 B
其中 sk xk 1 xk , yk g
k k
k
0
xk
I ，B
G
K 1
k 1
gk ，拟 Newton 法的思想可以是构造一个对称正定阵 由 B 修正得到， B 要满足拟 Newton 方程 B s
k
k 1
Bk y ，
k 1 k k
k 1
gk 。假定正定阵 Bk 是秩 2 修正的，即 Bk 1 Bk
uu T
vvT ， u, v R n ，试推导出
, , u, v 的一种取法满足拟
并用相应拟
Newton 方程，
Newton 法计算 min f ( x )
3
x12
2
1
x22 x1 x2 2 x1 初始点取为 x0 2
(0, 0)T 。
5． (12 分 ?) 考虑问题
写出问题取得最优解的
Kuhn-Tucker （ K － T ）必要条件，并通过 K － T 条件求出问题 K － T 点及相应 Lagrange 乘子。
6． (8 分 ?) 利用投影矩阵求出向量
y
(2, 5, 7)T 在超平面 H
{ x | 2x1 x2 x3
10} 上的投影向量。
7(10 分 )利用简约梯度法求解以下问题，初始点取为 8（ 8 分）证明：在拟牛顿法中，若矩阵 课程编号 : MTH17085
(1,0) T ，迭代一步。
H k 正定，则拟牛顿法得到的搜索方向（非零向量）是下降方向。
北京理工大学 2010-2011 学年第二学期
2009 级数学专业最优化方法终考试卷（ A 卷）
max f ( x ) s. t . x1
x1
2 x1 x 2 2 x 2 x 2 x 3 x 3 0
6 4
1(15 分 )．求解线性规划
x1 , x 2 , x 3
min f ( x)
4 x12 不用重新计算， 给出发生下列变化后新的最优解。 2．(18 分 )给定极小化问题 向求出满足不精确一维搜索
（ 1） max f ( x )
2x 1 3 x2 x 3 。（ 2）增加一个新约束x1 2 x 3 2 。 4x1 x2 2 x22 Wolfe 条件的步长区间，其中
(0, 0)T 。(1) 针对初始点处的负梯度方 1初始点取为 x0
0.9 。 (2) 用 PRP 共轭梯度法求解上述问题。 0.1, 2 x2 3．(15 分 ) 试推导无约束优化问题拟 Newton 法对称秩 1 公式，即 H k 1 H k uuT ，u R ，给出 , u 的取法满足拟 Newton
n方程 H k 1 yk sk ，其中 sk xk 1 xk , yk
g k 1 gk 。并用相应拟 Newton 法计算
min f ( x)
4 x12 4 x1 x 2 2x22
2x2
1 初始点取为 x0
(0, 0)T 。
4． (10 分 ?) 用外罚函数法求解
min f ( x) x1 x2
x s.t . x1 22 0
min f ( x ) x1 x2
5(12 分 )利用广义简约梯度法求解问题
s.t . x12 x22 4 0 。初始点取为 (2, 0)T ，迭代一步。
x1 0, x2 0.
6（ 8 分）设
f ( x1 , x2 ,L , x n ) 为凸集 D
Rn 上的凸函数，
为实数，证明水平集
L( ; f ) {( x1 , x2 ,L , xn ) | ( x1 , x2 ,L , xn ) D , f ( x1 , x2 , L , x n )
} 为凸集。
min f ( x )
cT x
max f ( x ) bT y
7． (10 分 )若原始线性规划为 s. t.
Ax
b
其对偶问题为
s. t . AT y c 证明：（ 1） x为原始问题的可行解，
x 0
y
0
问题的可行解，则
cT x bT y （ 2）若原始问题与对偶问题其中之一有 无下界 的目标函数，则另一个无可行解。
f ( x ) n ci
min
i 1
x
i
n
8． (12 分 ?) 给定非线性规划问题
s.t . ai xi
b
i 1
x
0
n
1 2
(ai ci ) 2
, cb i 1
其中 aii ,
都是正常数，设
x* 是该问题的最优解，证明该问题的最优值为
f ( x*)
。
b
y 为对偶
北京理工大学级数学专业最优化方法期末试卷试题A卷MT.doc
