高级运筹学题集及答案.pdf

《高级运筹学题集及答案.pdf》由会员分享，可在线阅读，更多相关《高级运筹学题集及答案.pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、.1.假设有一百万元可以投资到三支股票上，设随机变量Ri表示投资到股票i上的一元E(R1)0.09每年能够带来的收益。通过对历史数据分析，知期望收益，0.200.030.040.030.200.050.040.050.15E(R2)0.07E(R3)0.06。假设使，三支股票的协差矩阵为用股票涨跌稳定性来评测风险，试构建优化模型，在保证期望年收益率不低于0.075 的情况下，风险最小，同时表示为非线性优化的向量形式。解解：设X (x1,x2,x3)T，其中x1,x2,x3分别表示投资组合中R1,R2,R3的所占的比例，有x1 x2 x31保证期望收益率不低于 0.：x1E(R1)x2E(R2)

2、x3E(R3)0.075建立如下优化模型：220.15x30.06x1x20.08x1x30.10 x2x3min f(X)0.20 x120.20 x2s.tx1 x2 x310.09x10.07x20.06x3 0.075x1,x2,x3 00.200.030.040.030.200.05记：A 0.040.050.15表示成向量形式：min f(X)XTAX1 s.tXT111 0.09XT0.07 0.0750.06x1,x2,x3 02.用伪算法语言描述“成功-失败”搜索法。.页脚.解解：s1：初始化：x0,h,0s2：x=x0；f1=f(x)s3：f2=f(x+h)s4：iff2f

3、1go tos5;elsego tos6;ends5:x=x+h;f2=f1;h=2hs6:if|h|go tos7;else go tos8;ends7:x xs8:h h;4go tos3.3.请简述黄金分割法的基本思想，并尝试导出区间收缩比率 0.618.基本思想基本思想：黄金分割法就是用不变的区间缩短率，来代替 Fibonacci 法每次不同的缩短率，因而可以看成是Fibonacci 法的近似。在搜索区间a,b取两点 xy，然后在 x,y 中选取一个作为端点，将搜索区间缩小，直至搜索区间足够小，然后在其取一点作为最优解的近似。一维搜索时，在区间取两对称点1，1作为搜多点，并满足：1=a

4、+(1-)(b-a)1=a+(b-a)取近似值 0.618证明证明：设在第 k 次迭代时的搜索区间为ak,bk，.页脚.则在区间取两对称点k1，k1作为探索点，并满足：k1 ak(1)(bkak)k1 ak(bkak)由于对称性，即：k1ak bkk1在第 k+1 次迭代中，不妨取收缩区间为a,kk1这样，收缩率 表示为：k1akbkak(bkak)bkak5 1 0.61824.请简述牛顿（Newton）法的基本原理，并指出可能会出现的“坏现象”。基本思想基本思想：牛顿法是二阶近似仿照切线法思想，推导出下降向Xk1 Xk H(Xk)1f(Xk)|Dk下的最速下降每次计算Dk H(Xk)1f(

5、Xk)，可看成是椭球数|g法。对于正定二次函数，一次可达最优解。一定条件下，具有二阶收敛速度。坏现象坏现象：对初始点的依赖性很大，要求初始点接近极小点。若初始点远离极小点，不能保证收敛，甚至连 Newton 向2f(x(k)1f(x(k)都不一定是下降向，导致算法达不到极小点。5.叙述 Powell 算法思想.（向加速法）算法思想算法思想：又称向加速法。是在研究正定二次函数的极小化问题时形成的，由于迭代过程中构造一组共个向，其本质属于共轭向法。每一轮迭代过程中由 n+1 个相继的一维搜索组成，先依次沿着n 个已知的线性无关向搜索，然后沿本轮迭代的初始点和第 n 次搜索所得点的连线向搜索，得到这

6、一轮迭代的最好点并作为下一阶段的起点，再用第 n+1 个向（最后的搜索向）代替前 n 个向的一个，开始下一轮的迭代。6.简述有约束优化时既约梯度法的基本思想。基本思想基本思想：将线性规划的单纯形法推广到带线性约束的非线性问题上。把线性约束优化问题min f(X).页脚.AX=bs.tX 0简化为仅在非负限制下的极小化问题min F(XN)11XB=B b B NXN 0s.tX 0NXB其中，A (B,N)，X，B 为 mm 的可逆矩阵，XB为 m 维的基向量，XN为XNn-m 维的非基向量。求出目标函数F(XN)的梯度，此时的梯度是 n-m 维函数的梯度，称为f(X)的既约梯XN沿负既约梯度

7、r(XN)F(XN)XNfXB(XN),XN(B1N)TXBfXB(XN),XN。度向r(XN)移动，可使目标函数值降低。7.利用罚函数法求解非线性规划的收敛点min f(X)x1 x2g1(X)x12 x2 0s.tg2(X)x1 0分别假设初始可行点满足1)g1(X)0,g2(X)0；2)g1(X)0,g2(X)0.解：解：马良书 69 页8.设gj(X)(j 1,2L,l)为凸函数，则R X|gj(X)0,j 1,2L,l为凸集。证明证明：设x,yR，0,1，有gjx 0，gjy 0，j 1,2,L,lgj(X)(j 1,2L,l)为凸函数，则有gjx(1)y gjx(1)gjy，j 1

8、,2,L,l两边变号gjx(1)ygjx(1)gjy 0,j 1,2,L,l即x(1)yR。R 为凸集.页脚.9.设xk 2k,k 1,2,L，则xk收敛阶数为 1，且线性收敛。证明证明：显然，X0。由于|X(k1)X|2(k1)1lim limkk0|X(k)X|k022所以由收敛定义和 阶收敛知，xk收敛阶数为=1，且=1/2 知为线性收敛。10.设f(X)1TX AX bTX c，A 是对称矩阵。给定初始点X0，试证明由最速下降2法产生的迭代点列Xk有如下公式：Xk1(gk)Tgkk X kTg，k 0,1,2,3,L(g)Agkk其中gk AXkb。证明证明：由数学分析知，在Xk的领域

9、中，使f(X)下降最快的向是负梯度向，取P(K)f(Xk)下面确定步长k：由于f(X)为二次函数，故二阶连续可导，作二阶 Taylor 展开：1f(XkP(k)f(Xk)f(Xk)T(P(k)(P(k)TA(P(k)2令df f(Xk)TP(k)(P(k)TAP(k)0d可得最优步长为f(Xk)TP(k)k(k)T(k)(P)AP记gk f(Xk)AXkb则Xk1(gk)Tgkk X kf(X)X kTg，k 0,1,2,3,Lk(g)Agkkk11.试证在最速下降法中，相邻两次搜索向必正交，即f(Xk1 T)f(Xk)0证明证明：设第 k 步的步长为k，梯度为Pk，则有第 k+1 步的梯度为

10、P(k1)b AX(k1)b A(X(k)kP(k).页脚.b AX(k)kAP(k)P(k)kAP(k)|P(k)|2(P(k),P(k)Qk(k)T(k)(P)AP(AP(k),P(k)(P(k1),P(k)(P(k),P(k)k(AP(k),P(k)0即f(Xk1 T)f(Xk)0，两次搜索向必正交。12.f(x)在凸集R是凸函数的充要条件是对于任意的x,yR，g()fx(1)y在0,1是凸函数。证明：必要性：设，0,1，由于R是凸集，所以对于任意的x,yR，有x(1)yR，x(1)yRg(1)f(1)x1(1)y)fx(1)x yyyy fx(1)y(1)x(1)(1)y f(x(1)

11、y(1)x(1)y)由f(x)为R上凸函数可知g(1)fx(1)y(1)fx(1)yg()(1)g()所以，g()fx(1)y在0,1是凸函数。充分性：若对于任意的x,yR，g()fx(1)y在0,1是凸函数，则有fx(1)y g()gg 1(1)g0gg(1)(1)g(0)f(x)(1)f(y)所以f(x)是凸函数。13.考虑二次函数 f(x)=x1 2x1x23x2x1x21)写出它的矩阵向量形式:f(x)=1TTQxxxb222f(x)1T22XX(1,1)X262.页脚.2)矩阵 Q 是不是奇异的?|Q|80，非奇异3)证明:f(x)是正定的显然 Q 正定，故 f(x)正定4)f(x)

12、是凸的吗?由于 f(x)正定，所以 f(x)是凸的5)写出 f(x)在点x=(2,1)T处的支撑超平面(即切平面)程f(X)10，f(X)2226X-15 111切平面程：f(X)f(X)f(X)T(X X)即x221 2x1x23x26x110 x211 014.设f(x)12xTGxrTx是正定二次函数，证明一维问题min(a)f(xkadk)的最优步长为af(xk)Tdkk dkTGdk.证明证明：同（10）题15.考虑约束优化问题min fx x24x212s.t3x14x213初始点(2,2)，用两种惩罚函数法求解.解解：标准化min fx x2214x2.页脚.s.tg1(x)3x

13、14x213 0（1）外罚函数法构造罚函数2P(X,M)x12 4x2 Mmin(0,3x1 4x213)2当g1(x)0时，2P(X,M)x12 4x2 M(3x14x213)2PP 2x16M(3x14x213)0，8x28M(3x14x213)0 x1x1解得：XM(3,1)。（2）障碍罚函数法构造障碍罚函数2P(X,r)x124x2r3x14x213求解P3rP4r 2x1 08x 0，2x1(3x14x213)2x1(3x14x213)2两式抵消，得：x1 3x2，代入上式2x2(13x213)2 r当r 0时，有x2 0或x21，所以取x2的值为 0 或者 1，对应的x1取值为 0

14、 或者3。由于点(0,0)不在可行域，所以取(3,1)为最优点。1 17 1 17T(,)T(0,3)2216.验证点与是否是规划问题min fx x12 x22s.tx12 x2 9 x1 x21 0.页脚.的 K-T 点。对 K-T 点写出相应的 Lagrange 乘子。解：规划问题标准化min f(x)x12 x22 0s.tg1(X)9 x12 x2g2(X)x1 x21 02x12x11f(X)，g2(X)，g1(X)2x1121 170 2，X(2)。1 1732记X(1)下面验证正则点：1 171g1(X)，g2(X(1)1 171(1)1 17 1 17T(,)(1)(1)22

15、显然g1(X)与g2(X)线性无关，于是为正则点。0 1g1(X(2)，g2(X(2)61同样g1(X(2)与g2(X(2)T(0,3)线性无关，于是也是正则点。下面验证是否满足 Kuhn-Tucker 条件：1 171 1710f(X)jgj(X)12 1j1011 17(1)2(1)1 17 1 17T(,)1 17122 0，故得1 0，2 不满足 Kuhn-Tucker 条件。22f(X(2)00 10)jgj(X(2)12 j11-6102T1(0,3)得1-0，2 0，故不满足 Kuhn-Tucker 条件。617.设集合S R是凸集，nf1(x),L fk(x)是S上的凸函数，令

16、f(x)maxf1(x),L fk(x)xS.页脚.证明f(x)也是S上的凸函数。证明证明：设X,Y S，由f1(x),L,fk(x)是 S 上的凸函数，则存在(0,1)，使得fiX(1)Yfi(X)(1)fi(Y),i 1,2,L,k令fs(X)f(X)maxf1(X),L,fk(X)ft(Y)f(Y)maxf1(Y),L,fk(Y)其中s,t 1,2,L,k。fX(1)Y maxf1X(1)Y,L,fkX(1)Y maxf1(X)(1)f1(Y),L,fk(X)(1)fk(Y)maxf1(X),L,fk(X)(1)maxf1(Y),L,fk(Y)fs(X)(1)ft(Y)f(X)(1)f(

17、Y)其中式等号成立的充要条件是：s t。即：fX(1)Yf(X)(1)f(Y)故 f(x)为凸函数。18.用最速下降法求解无约束问题minfx 3x1 2 4x2 3，取初始点22x14,3。T解解：显见，X()(2,3)T。取X(1)(4,3)T，代入6x 12 f(X)18x224得12f(X(1)0由.页脚.|f(X(1)|2144 得60H(X)08因 f(X)是二次函数，故得最优步长|f(X(1)|21f(X(1)TH(X)f(X(1)6从而，得2X(2)X(1)f(X(1)3显见，|f(X(2)|2 0，所以X(2)X()。f(x)1Tx AxbTxc2（A 为对称正定矩阵）的极小值只需19.证明：用牛顿法求函数一次迭代。证明：令f(X)AX b 0，得极小值点为X()A1b f(X(0)AX(0)b，2f(X(0)A，向为：D(0)2f(X(0)1f(X(0)X(1)X(0)D(0)X(0)2f(X(0)1f(X(0)X(0)A1(AX(0)b)X(0)A1AX(0)A1b A1b对比可知，X(1)X()。结论得证。.页脚.