课程编号: 07000203 北京理工大学2007-2008学年第二学期

2005级数学专业最优化方法终考试卷（A卷）

1．(20分)某化工厂有三种资源A、B、C，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为x1,x2,x3,其数学模型为：

maxz?3x1?2x2?5x3?x1?2x2?x3?430(A资源限制)?(B资源限制) ?3x1?2x3?460s.t?(C资源限制)?x1?4x2?420??x1,x2,x3?0请回答如下问题：

（1）给出最优生产方案；

（2）假定市场信息表明甲产品利润已上升了一倍，问生产方案应否调整？ （3）假定增加一种添加剂可显著提高产品质量，该添加剂的资源限制约束为：

x1?2x2?3x3?800问最优解有何变化？

2222．(12分)用Newton法求解minf(x)?4x1?x2?2x1x2，初始点取为x0?(1,1)T，迭代一步。

3．(10分)用FR共轭梯度法求解三个变量的函数f(x)的极小值，第一次迭代的搜索方向为p0?(1,?1,2)T，沿p0做精确

111T线搜索，得x1?(x1,x2,x3)， 设

?f(x1)?f(x1)??2,??2，求从x1出发的搜索方向p1。 11?x1?x2skykTskykTTskskT4．(15分) 给定下面的BFGS拟Newton矩阵修正公式：Hk?1?(I?T)Hk(I?T)?T，

ykskykskyksk其中sk?xk?1?xk,yk?gk?1?gk

22用对应的拟Newton法求解：minf(x)?x1?2x1x2?2x2?4x1，初始点取为x0?(0,0)T，H0?I。

5．(15分)写出问题

2minf(x)??3x1?x2?x3s.t.x1?x2?x3?12?x1?x2?x3?0

取得最优解的Kuhn-Tucker（K－T）必要条件，并通过K－T条件求出问题K－T点及相应Lagrange乘子。 6(12分)．求约束问题

minz??x12s..t?x12?x2??1

?????x1?0,x2?0在x1?(0,0)T及x2?(1,0)T处的下降方向集合、可行方向集合以及可行下降方向集合，并画图表示出来 7（8分）考察优化问题

minf(x)s.t.x?D设D为凸集，f(x)为D上凸函数，证明：f(x)在D上取得极小值的那些点构成的集合是凸集。

1TT8（8分）设minf(x)?xAx?bx?c，其中A为对称正定矩阵，x*为f(x)的极小值点，又设x0(?x*)可表示

21为x0?x*??p，其中??R，p是A对应于特征值?的特征向量，证明：若从x0出发，沿最速下降方向做精确一维

搜索，则一步达到极小值点。

课程编号:07000203 北京理工大学2008-2009学年第一学期

，

2006级数学专业最优化方法终考试卷（A卷）

1．(15分) 用单纯形法求解线性规划问题

minf(x)??3x1?x2?x3s.t.x1?2x2?x1?9

?x3?2?x1?x2?x3?1x1,x2,x3?02．(10分)写出线性规划问题

maxf(x)?2x1?3x2?x3s.t.?5x1?x2?x3?20?x1?2x2x1,x2?0的对偶问题并证明该对偶问题没有可行解。

223．(15分)考虑用最速下降法迭代一步minf(x)?x1， 初始点取为x0?(?1,1)T。（1）采用精确一维搜索；（2）?2x2?50

采用Wolfe条件进行不精确一维搜索，其中??0.1,??0.9。

?1??21?4．(15分)用DFP拟牛顿法求解minf(x)?x?2x 初始点取为x0???，初始矩阵H0???。

?111????5．(15分)证明集合S?{x|x1?2x2?4,2x1?x2?6}是凸集，并计算原点(0,0)到集合S的最短距离。

21226．(15分 ) 考虑问题

22minf(x)?x1?x1x2?x2?2x1?3x2s.t.x1?x2?2,?x1?2x2?3,x1?0,x2?0.（1）用数学表达式写出在点(,)

1533T

处的下降可行方向集。

（2）假设当前点在(0,0)T处，求出用投影梯度法进行迭代时当前的下降可行方向（搜索方向）。 7（7分）证明：在精确一维搜索条件下，共轭梯度法得到的搜索方向是下降方向。

?a11x1?a12x2??a1nxn?b1??a21x1?a22x2??a2nxn?b2?8（8分）已知线性不等式组?.............................................其中b1,b2?,bm?0，给出一种判断该不等式组是否相容（即

?ax?ax??ax?bm22mnnm?m11??x1,x2?,xn?0是否有解）的方法并说明理由。

课程编号:07000203 北京理工大学2009-2010学年第一学期

2007级数学专业最优化方法终考试卷（A卷）

1．（8分）将优化问题

minf(x)?|x1|?|x2|?|x3|s.t.x1?x2?12x1?x3?3化为标准形式的线性规划问题。

2．(10分) 给出一个判断任一线性不等式组是否相容（即是否有解）的一般条件，并利用其判断以下不等式组是否相容。

3x1?x2?3x3?62x1?x2?x3?2x1?2x2?3x3?5x1,x2,x3?03．(12分)对于下面的线性规划

minf(x)?5x1?9x2s.t.3x1?4x2?2x1?4x2?6x1?0,x2?0（1）利用对偶单纯形法求解；（2）写出其对偶线性规划问题并利用对偶理论求出对偶问题的最优解。

224．(10分)考虑用最速下降法迭代一步minf(x)?x1?2x2?2x1x2，初始点为x0?(?1,1)T。

5．(15分)用FR共轭梯度法求解minf(x)?x1?6．(10分 ) 考虑问题

2minf(x)?(x1?1)2?x22s.t.x1?x2?02T1212x2?x3 初始点取为x0??1,1,1?。 22

写出问题取得最优解的Kuhn-Tucker（K－T）必要条件，并通过K－T条件求出问题K－T点及相应Lagrange乘子。

22minf(x)?x1?x2?2x1?4x27．(15分 ) 用简约梯度法求解问题

s.t.2x1?x2?1,x1?x2?2,x1?0,x2?0.，初始点取为(0,2)T。

8（10分）基于单纯形算法，试给出一个判定线性规划问题具有唯一最优解的条件，并且举例说明之。 9(10分)．考虑优化问题

minf(x)s..tAx?b,A?Rm?n,x?Rn，设xk为问题可行域中任一点，在xk处前q个约束为有效约束，

TT?1记为Aqxk?bq，其中Aq为行满秩矩阵，令P（1）P?I?A(AAq为投影阵。 qqqq)Aq，证明：

（2）若pk??Pq?f(xk)?0，则为问题的下降可行方向。

课程编号:07000203 北京理工大学2010-2011学年第一学期

2008级数学专业最优化方法终考试卷（A卷）

1(15分)求解线性规划

maxf(x)?4x1?5x2?3x3s.t.x1?2x2?3x3?402x1?4x2x1?x2x1,x2,x3?02．(12分)给定一个线性规划问题

?20 ?2x3?15minf(x)?4x1?3x2?x3s.t.x1?x2?x3?1x1?2x2?3x3?2x1,x2,x3?0

?57?（1）写出其对偶规划。（2）假设已知该对偶规划的最优解为?,?，试求出原始问题的最优解。

?33?223．(15分)给定Rosenbrock函数f(x)?100(x2?x1)?(1?x1)2(1) 求出f(x)的驻点，并判断驻点的最优性。

1T(2) 求出f(x)在点x?(?1,2)处的最速下降方向

T?14．(20分)无约束优化问题阻尼Newton法迭代公式为xk?1?xk??kGKgk，拟Newton法的思想可以是构造一个对称正定

阵Bk近似替代Gk，则搜索方向由Bkpk??gk求出。初始B0?I，Bk?1由Bk修正得到，Bk?1要满足拟Newton方程

Bk?1sk?yk，其中sk?xk?1?xk,yk?gk?1?gk。假定正定阵Bk是秩2修正的，即Bk?1?Bk??uuT??vvT，u,v?Rn，试推导出?,?,u,v的一种取法满足拟Newton方程，

3212并用相应拟Newton法计算minf(x)?x1?x2?x1x2?2x1初始点取为x0?(0,0)T。

225．(12分 ) 考虑问题

minf(x)?(x1?1)2?(x2?2)27s.t.x1?x2??04

写出问题取得最优解的Kuhn-Tucker（K－T）必要条件，并通过K－T条件求出问题K－T点及相应Lagrange乘子。 6．(8分 ) 利用投影矩阵求出向量y?(2,5,7)在超平面H?{x|?2x1?x2?x3?10}上的投影向量。 7(10分)利用简约梯度法求解以下问题，初始点取为(1,0)，迭代一步。

TT