课程编号: 07000203 北京理工大学2007-2008学年第二学期
2005级数学专业最优化方法终考试卷(A卷)
1.(20分)某化工厂有三种资源A、B、C,生产三种产品甲、乙、丙,设甲、乙、丙的产量分别为x1,x2,x3,其数学模型
maxz?3x1?2x2?5x3?x1?2x2?x3?430?为:?3x1?2x3?460s.t??x1?4x2?420??x1,x2,x3?0(A资源限制)(B资源限制) (C资源限制)请回答如下问题:
(1)给出最优生产方案;
(2)假定市场信息表明甲产品利润已上升了一倍,问生产方案应否调整? (3)假定增加一种添加剂可显著提高产品质量,该添加剂的资源限制约束为:
x1?2x2?3x3?800问最优解有何变化?
222T2.(12分)用Newton法求解minf(x)?4x1?x2?2x1x2,初始点取为x0?(1,1),迭代一步。
T3.(10分)用FR共轭梯度法求解三个变量的函数f(x)的极小值,第一次迭代的搜索方向为p0?(1,?1,2),沿p0做精确线搜
?f(x1)??2,索,得x1?(x,x,x), 设1?x111121T3?f(x1)??2,求从x1出发的搜索方向p1。 1?x2skykTskykTTskskT4.(15分) 给定下面的BFGS拟Newton矩阵修正公式:Hk?1?(I?T)Hk(I?T)?T,
ykskykskyksk其中sk?xk?1?xk,yk?gk?1?gk
T22用对应的拟Newton法求解:minf(x)?x1?2x1x2?2x2?4x1,初始点取为x0?(0,0),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?0TT在x1?(0,0)及x2?(1,0)处的下降方向集合、可行方向集合以及可行下降方向集合,并画图表示出来
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*)可表示为
2x0?x*??p,其中??R1,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的对偶问题并证明该对偶问题没有可行解。
22T3.(15分)考虑用最速下降法迭代一步minf(x)?x1?2x2, 初始点取为x0?(?1,1)。(1)采用精确一维搜索;(2)采用
?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的最短距离。
2122
6.(15分 ) 考虑问题
22minf(x)?x1?x1x2?x2?2x1?3x2s.t.x1?x2?2,?x1?2x2?3,x1?0,x2?0.(1)用数学表达式写出在点(,)T
1533T
处的下降可行方向集。
(2)假设当前点在(0,0)处,求出用投影梯度法进行迭代时当前的下降可行方向(搜索方向)。 7(7分)证明:在精确一维搜索条件下,共轭梯度法得到的搜索方向就是下降方向。
?a11x1?a12x2?a1nxn?b1??a21x1?a22x2?a2nxn?b2?8(8分)已知线性不等式组?.............................................其中b1,b2?ax?ax?ax?bm22mnnm?m11??x1,x2,xn?0,bm?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)写出其对偶线性规划问题并利用对偶理论求出对偶问题的最优解。
22T4.(10分)考虑用最速下降法迭代一步minf(x)?x1?2x2?2x1x2,初始点为x0?(?1,1)。
5.(15分)用FR共轭梯度法求解minf(x)?x1?6.(10分 ) 考虑问题
2minf(x)?(x1?1)2?x22T1212x2?x3 初始点取为x0??1,1,1?。 22s.t.x1?x?022
写出问题取得最优解的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)。
T8(10分)基于单纯形算法,试给出一个判定线性规划问题具有唯一最优解的条件,并且举例说明之。 9(10分).考虑优化问题
minf(x)s..tAx?b,A?Rm?n,x?Rn,设xk为问题可行域中任一点,在xk处前q个约束为有效约束,记为
TT?1Aqxk?bq,其中Aq为行满秩矩阵,令PP?I?A(AAqqqq)Aq,证明:(1)q为投影阵。
(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?2223.(15分)给定Rosenbrock函数f(x)?100(x2?x1)?(1?x1)(1) 求出f(x)的驻点,并判断驻点的最优性。
(2) 求出f(x)在点x?(?1,2)处的最速下降方向
?14.(20分)无约束优化问题阻尼Newton法迭代公式为xk?1?xk??kGKgk,拟Newton法的思想可以就是构造一个对称正定
1T
T阵Bk近似替代Gk,则搜索方向由Bkpk??gk求出。初始B0?I,Bk?1由Bk修正得到,Bk?1要满足拟Newton方程
Bk?1sk?yk,其中sk?xk?1?xk,yk?gk?1?gk。假定正定阵Bk就是秩Bk?1?Bk??uuT??vvT,u,v?Rn,试推导出?,?,u,v的一种取法满足拟Newton方程,
并用相应拟Newton法计算minf(x)?5.(12分 ) 考虑问题
2修正的,即
3212x1?x2?x1x2?2x1初始点取为x0?(0,0)T。 22minf(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