河海大学研究生最优化考试试卷2016

1、河海大学研究生最优化方法考试范围授课老师：丁根宏（2016年春）考试范围：线性和非线性约束占比70%,多目标和动态规划占30%,题型为计算和证明共8道题，其中一道证明题。线性规划：两阶段法改进单纯形法对偶单纯形法的计算基变换的定理保证对偶理论的证明无约束非线性规划：一维搜索（0.618法，Fibonaci法，牛顿切线法和二次插值法）牛顿法公式及推导计算题（最速下降法、牛顿法和共腕梯度法）步骤简单，主要是思想的比较变尺度法和牛顿法的对比有约束非线性规划：K-T条件及验证求K-T点SUMT方法（外点法和内点法）投影梯度法理论及投影梯度的定义多目标规划：解的定义求Rpa*,Rwp*变量空间和函数空间

2、评价函数的收敛性动态规划：最优性原理步骤（6个概念）泛函方程应用举例（多阶段决策问题包括资源分配问题）函数空间和策略空间迭代法考试试卷（2016年6月3号）1、 改进单纯形法，从中间某步继续往下迭代至求出最优解例（P66）用改进单纯形法求解问题min卜-3X|-x2-3xa2X1+m+x3+x4=2X+2xz+3x3+x5=52X1+2x2+x3+x6=6x；20,i=l,62、 对偶理论的证明定理1（弱对偶定理）若K和V分别为互为对偶的线性规划问题和的可行解则有证明，因为yAWc,所以yb=y（A尤）=（yA）k这c工定理2（强标搞定理）若x*和V*分别为互为对偶的线性规划问题和的可行解，且

3、cx*-y*bf则、了分别为和的最优解.证明：因对任一可行解x,故炉为的最优解口同理可证/为的最优解44定理3（对偶定理）若对偶问题（1）和Q）中有一个有最优解，则另一个也一定有最优解，并且两个问题的目标函数的最优值相等。证明：设铲是的最优基可行解，对应的基为B,则其检验数为口=cbB-A-cO令，C#T（单纯形乘子）则有*AWc且露b气匕时）b=cB（B-1b）=c3Xjjcx*由定理Z知y*为（2）的最优解。i由对偶问题的对称性，可证定理的另一种情形3、牛顿切线法的公式及推导.*tnhif(x)基本思想：用Rk)在近似点“的二阶丁”lor展开式近似代替食工)I设、F(x)是在忸.b上的&#

4、39;单峰函数,fM(xk)>0,作炳冷=/(.%)+令g'(H)=/'氏)+)任一.)二。得x-x-EG&1,"L*，"*)S3注意；求出的点儿内与MQ的值无关。,设X的是f(X)的近似点，将f(X)在X阳点作二阶Taylor展开，嬉+*(X-Xm)r77(X,t)(X-X)记右端=4>(X)«令6(X)=0得V/IX)+(X(")(X_X)=0A=牙叫0(')此即为Ncwtoii迭代公式口4、 变尺度法和牛顿法的比较 1)基本原理 在上述阻尼牛顿法中，.H(Xg尸V.X的) X(k+l>=X<k

5、J+x川脸K Xk：minf(X®+AS) 由于逆矩阵H(X*)尸的计算量太大，实现困潍口一 为了保持牛顿法的优点，试图构造H(X尸卜的近似阵才”，不需要求逆矩阵 若WX)为二次函数，其He弱gn矩阵H(X)为常数阵，则在XM1)和X处的梯度之差等于 i(X(k+昨Vf(XQ=A(XW1LXS XW】)-X(k=A*1Vf(X<l+1),Vf(X<k)J 记G(X)=f(X),AGgG(X仲丹 上式又变为AX«>=A-iAG的5、 K-T条件及验证如果设为(i不属于1)在X*也可微，则上述条件可改为：Fwa力+£俨”=o*I/=1产区(X*)=0

6、.i=1班I必之。，热称X业为K-T点。2.考察如:下问题；min7tx)=.#；+料.t*：+彳M5上i+=4l4一y0*验证在最优点jt=(1，5,85)处.KT条件成立*并求在x点的Liigrangi乘子.6、 SUMT外点法(书上例题)例2用外点法求miif(X)=x+x2gi(X)=x-x±WOgz(X尸-也W0解：构造罚函数1(X,M)=X,+x3+4/(|max(0,jrJx3J)|2+mai(O,)|2当殖I时0时，令.=1+2jW|(jcJ-)+Jtj=03FT=112M(.V；.Yj)=0dx1一-12(H)”4(1+AJ)Z1M当Aff8时,X*二(凡0),7、

7、简述动态规划的使用条件及步骤，用空间迭代法求最短路径所谓多阶段决策问题，是指一类活动过程，它可以分为互相联系的若干个阶段，在每一阶段都需要作出决策，从而使整个过程达到最优的活动效果.因此，各个阶段决策的选取常依赖于当前面临的状态,又影响下一个阶段的决策，从而影响整个过程的活动路线，这种把一个问题看成一个前后关联具有链状结构的多阶段过程就称为康过程.也称贯决策过程©动态规划的量优性原理工一个(整个过程的)最优策略所具有的性质是，不论过去的状态和决策如何，其余下的诸决策必构成一个最优子策略.1、函数空间迭代法设h(i)表示由i点出发向N走k步所构成的所有路线中的最短距离。函数空间迭代法求

8、解步骤如下；1°Hl,2，.N-1心尸02"九=min。+1)，i=l2，斗1Jfk(N)=OT反复迭代”直到勾=3率)=虫为止，A1,2N例3下图为一街区的单行道交通网络，分别用函数空间迭代法和策略空间迭代法求各点到顶点5的最短路线。I解I先用函数空间迭代法求解.为了便于运算，将距离C”写成下列矩阵的形式，将人写成列向量的形式,利用菌数空间迭代法求解,步骤迭代如下：其中最后一列i为i点的最优决策,于是得到各点到顶点5的最短路线和最短蹈离如下表，8、多目标规划，评价函数的收敛性设X*ER,若不存在XER满足F(X)WF(X比),则称X*为问题(VP)的(1-2”)口有效解的

9、全体记为R/G设X曦ER,若不存在X£R满足F(X)F(X。则称X*为问题(VP)的弱有效虹(Paret®#?)»弱有效解的全体记为匕10.设多目标规划间即为JV-min尸(才)=1 s.t.才>0；r6A其中f(%)=O1)?4-1r-/+4,&3人(工)=<1,3Vh<4、/一3,1>4求；.；R0.R"和/，。评价函数的收敛性过义7若对任意F,PGEA当FWF时，都有U(F)<U(F»)成立，则称U(F)是F的h格单调增函数定义8若对任意F.PEEP,当FP时，都有U(F)<U(F*)成立，则称U(F)是F的单调增函数。定理8若对