课程编号: 07000203北京理工大学2007-2008学年第二学期2005级数学专业最优化方法终考试卷（A 卷）1．(20分)某化工厂有三种资源A 、B 、C ，生产三种产品甲、乙、丙，设甲、乙、丙的产量分别为x 1,x 2,x 3,其数学模型为：⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤++++=0,,)(4204)(46023)(4302.523max 3212131321321x x x C x x B x x A x x x t s x x x z 资源限制资源限制资源限制 请回答如下问题：（1）给出最优生产方案；（2）假定市场信息表明甲产品利润已上升了一倍，问生产方案应否调整？ （3）假定增加一种添加剂可显着提高产品质量，该添加剂的资源限制约束为：12328003xx x ++≤问最优解有何变化？2．(12分)用Newton 法求解2221212min ()42f x x x x x =+-，初始点取为0(1,1)Tx =，迭代一步。
3．(10分)用FR 共轭梯度法求解三个变量的函数()f x 的极小值，第一次迭代的搜索方向为0(1,1,2)Tp =-，沿0p 做精确线搜索，得1111123(,,)Tx x x x =， 设111112()()2,2f x f x x x ∂∂=-=-∂∂，求从1x 出发的搜索方向1p 。
4．(15分) 给定下面的BFGS 拟Newton 矩阵修正公式：1()()T T TT k k k k k k k k T T T k k k k k ks y s y s s H I H I y s y s y s +=--+，其中11,k k k k k k s x x y g g ++=-=-用对应的拟Newton 法求解：1222121422)(min x x x x x x f -+-=，初始点取为0(0,0)Tx =，0H I =。
5．(15分)写出问题取得最优解的Kuhn-Tucker （K －T ）必要条件，并通过K －T 条件求出问题K －T 点及相应Lagrange 乘子。
6(12分)．求约束问题在1(0,0)Tx =及2(1,0)Tx =处的下降方向集合、可行方向集合以及可行下降方向集合，并画图表示出来 7（8分）考察优化问题min ()..f x s t x D∈，设D 为凸集，()f x 为D 上凸函数，证明：()f x 在D 上取得极小值的那些点构成的集合是凸集。
8（8分）设1min ()2T Tf x x Ax b x c =++，其中A 为对称正定矩阵，*x 为()f x 的极小值点，又设0(*)x x ≠可表示为0*x x p μ=+，其中1R μ∈，p 是A 对应于特征值λ的特征向量，证明：若从0x 出发，沿最速下降方向做精确一维搜索，则一步达到极小值点。
课程编号:07000203 北京理工大学2008-2009学年第一学期2006级数学专业最优化方法终考试卷（A 卷）1．(15分) 用单纯形法求解线性规划问题 2．(10分)写出线性规划问题的对偶问题并证明该对偶问题没有可行解。
3．(15分)考虑用最速下降法迭代一步2212min ()2f x x x =+， 初始点取为0(1,1)Tx =-。
（1）采用精确一维搜索；（2）采用Wolfe 条件进行不精确一维搜索，其中0.1,0.9μσ==。
4．(15分)用DFP 拟牛顿法求解2212min ()2f x x x =+ 初始点取为011x ⎛⎫= ⎪-⎝⎭，初始矩阵02111H ⎛⎫= ⎪⎝⎭。
5．(15分)证明集合1212{|24,26}S x x x x x =+≥+≥是凸集，并计算原点(0,0)到集合S 的最短距离。
6．(15分?) 考虑问题（1）用数学表达式写出在点15(,)33T处的下降可行方向集。
（2）假设当前点在(0,0)T处，求出用投影梯度法进行迭代时当前的下降可行方向（搜索方向）。
7（7分）证明：在精确一维搜索条件下，共轭梯度法得到的搜索方向是下降方向。
8（8分）已知线性不等式组1111221121122222112212.............................................,,0n n n n m m mn n mn a x a x a x b a x a x a x b a x a x a x bx x x ++≥⎧⎪++≥⎪⎪⎨⎪++≥⎪⎪≥⎩L L L L 其中12,,0m b b b ≥L ，给出一种判断该不等式组是否相容（即是否有解）的方法并说明理由。
课程编号:07000203 北京理工大学2009-2010学年第一学期2007级数学专业最优化方法终考试卷（A 卷）1．（8分）将优化问题化为标准形式的线性规划问题。
2．(10分) 给出一个判断任一线性不等式组是否相容（即是否有解）的一般条件，并利用其判断以下不等式组是否相容。
3．(12分)对于下面的线性规划（1）利用对偶单纯形法求解；（2）写出其对偶线性规划问题并利用对偶理论求出对偶问题的最优解。
4．(10分)考虑用最速下降法迭代一步221212min ()22f x x x x x =+-，初始点为0(1,1)Tx =-。
5．(15分)用FR 共轭梯度法求解22212311min ()22f x x x x =++ 初始点取为()01,1,1T x =。
6．(10分?) 考虑问题2212212min ()(1)..0f x x x s t x x =-+-≤写出问题取得最优解的Kuhn-Tucker （K －T ）必要条件，并通过K －T 条件求出问题K －T 点及相应Lagrange 乘子。
7．(15分?) 用简约梯度法求解问题221212121212min ()24..21,2,0,0.f x x x x x s t x x x x x x =+---≤+≤≥≥，初始点取为(0,2)T。
8（10分）基于单纯形算法，试给出一个判定线性规划问题具有唯一最优解的条件，并且举例说明之。
9(10分)．考虑优化问题min ()..,,m nnf x s t Ax b A Rx R⨯≥∈∈，设k x 为问题可行域中任一点，在k x 处前q 个约束为有效约束，记为q k q A x b =，其中q A 为行满秩矩阵，令1()T T q q q q q P I A A A A -=-，证明：（1）q P 为投影阵。
（2）若()0k q k p P f x =-∇≠，则为问题的下降可行方向。
课程编号:07000203 北京理工大学2010-2011学年第一学期2008级数学专业最优化方法终考试卷（A 卷）1(15分)求解线性规划2．(12分)给定一个线性规划问题（1）写出其对偶规划。
（2）假设已知该对偶规划的最优解为57,33T⎛⎫⎪⎝⎭，试求出原始问题的最优解。
3．(15分)给定Rosenbrock 函数222211()100()(1)f x x x x =-+-(1) 求出()f x 的驻点，并判断驻点的最优性。
(2) 求出()f x 在点1(1,2)Tx =-处的最速下降方向4．(20分)无约束优化问题阻尼Newton 法迭代公式为k K k k k g G x x 11-+-=α，拟Newton 法的思想可以是构造一个对称正定阵k B 近似替代k G ，则搜索方向由k k k B p g =-求出。
初始0B I =，1k B +由k B 修正得到，1k B +要满足拟Newton 方程1k k k B s y +=，其中k k k x x s -=+1,k k k g g y -=+1。
假定正定阵k B 是秩2修正的，即1TT k k B B uu vv αβ+=++，n R v u ∈,，试推导出v u ,,,βα的一种取法满足拟Newton 方程，并用相应拟Newton 法计算221212131min ()222f x x x x x x =+--初始点取为0(0,0)T x =。
5．(12分?) 考虑问题写出问题取得最优解的Kuhn-Tucker （K －T ）必要条件，并通过K －T 条件求出问题K －T 点及相应Lagrange 乘子。
6．(8分?) 利用投影矩阵求出向量(2,5,7)Ty =在超平面123{|210}H x x x x =-++=上的投影向量。
7(10分)利用简约梯度法求解以下问题，初始点取为(1,0)T，迭代一步。
8（8分）证明：在拟牛顿法中，若矩阵k H 正定，则拟牛顿法得到的搜索方向（非零向量）是下降方向。
课程编号: MTH17085 北京理工大学2010-2011学年第二学期2009级数学专业最优化方法终考试卷（A 卷）1(15分)．求解线性规划,,426..2)(max 32121321321≥≤+-≤+++-=x x x x x x x x t s x x x x f不用重新计算，给出发生下列变化后新的最优解。
（1）32132)(max x x x x f ++=。
（2）增加一个新约束2231≥+-x x 。
2．(18分)给定极小化问题2211222min ()44221f x x x x x x =++++初始点取为0(0,0)Tx = 。
(1)针对初始点处的负梯度方向求出满足不精确一维搜索Wolfe 条件的步长区间，其中0.1,0.9μσ==。
(2) 用PRP 共轭梯度法求解上述问题。
3．(15分) 试推导无约束优化问题拟Newton 法对称秩1公式，即1T k k H H uu α+=+，n u R ∈，给出,u α的取法满足拟Newton 方程k k k s y H =+1，其中k k k x x s -=+1,k k k g g y -=+1。
并用相应拟Newton 法计算2211222min ()44221f x x x x x x =++++初始点取为0(0,0)T x =。
4．(10分?) 用外罚函数法求解12212min ()..0f x x x s t x x =+-=5(12分)利用广义简约梯度法求解问题12221212min ()..400,0.f x x x s t x x x x =--+-=≥≥。
初始点取为(2,0)T，迭代一步。
6（8分）设12(,,,)n f x x x L 为凸集n D R ⊂上的凸函数，α为实数，证明水平集121212(;){(,,,)|(,,,),(,,,)}n n n L f x x x x x x D f x x x αα=∈≤L L L 为凸集。
7．(10分)若原始线性规划为min ()..0T f x c xs t Ax b x =≥≥其对偶问题为max ()..0T Tf x b y s t A y c y =≤≥证明：（1）x 为原始问题的可行解，y 为对偶问题的可行解，则T Tc x b y ≥（2）若原始问题与对偶问题其中之一有无下界的目标函数，则另一个无可行解。