课程编号: 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