最优化-刘志斌-课后习题3-5参考答案要点

练习题三1、用0.618法求解问题12)(min30tttt的近似最优解，已知)(t的单谷区间为]3,0[，要求最后区间精度0.5。答：t=0.8115；最小值-0.0886.（调用golds.m函数）（见例题讲解5）2、求无约束非线性规划问题min),,(321xxxf=123222124xxxx的最优解解一：由极值存在的必要条件求出稳定点：1122fxx，228fxx，332fxx，则由0fx得11x，20x，30x再用充分条件进行检验：2212fx，2228fx，2232fx，2120fxx，2130fxx，2230fxx即2200080002f为正定矩阵得极小点为T*(1,0,0)x，最优值为-1。解二：目标函数改写成min),,(321xxxf=222123(1)41xxx易知最优解为（1,0,0），最优值为-1。3、用最速下降法求解无约束非线性规划问题。2221212122)(minxxxxxxXf其中TxxX),(21，给定初始点TX)0,0(0。解一：目标函数()fx的梯度112122()()142()122()()fxxxxfxxxfxx(0)1()1fX令搜索方向(1)(0)1()1dfX再从(0)X出发，沿(1)d方向作一维寻优，令步长变量为，最优步长为1，则有(0)(1)0101Xd故(0)(1)2221()()()2()2()2()fxfXd令'1()220可得11(1)(0)(1)1011011XXd求出(1)X点之后，与上类似地，进行第二次迭代：(1)1()1fX令(2)(1)1()1dfX令步长变量为，最优步长为2，则有(1)(2)111111Xd故(1)(2)2222()()(1)(1)2(1)2(1)(1)(1)521()fxfXd令'2()1020可得215(2)(1)(2)2110.81111.25XXd(2)0.2()0.2fX此时所达到的精度(2)()0.2828fX本题最优解11.5X，()1,25fX解二：利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=[1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2)];调用grad.m文件x0=[0,0];[x,val,k]=grad('fun','gfun',x0)结果x=[-1.0000,1.5000]val=-1.2500k=33即迭代33次的到最优解x=[-1.0000,1.5000]；最优值val=-1.2500。4、试用Newton法求解第3题。解一：计算目标函数的梯度和Hesse阵目标函数()fx的梯度112122()()142()122()()fxxxxfxxxfxx242()22fXG，其逆矩阵为10.50.50.51G(1)(0)1(0)0.50.5()0,01,11,1.50.51TTTXXGfX计算(1)()0fX。本题最优解11.5X，()1,25fX解二：除了第3题建立两个M文件外，还需建立Hesse矩阵的M文件利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(1)-x(2)+2*x(1)*x(1)+2*x(1)*x(2)+x(2)*x(2);functiong=gfun(x)g=[1+4*x(1)+2*x(2),-1+2*x(1)+2*x(2)];functionh=hess(x)g=[42;22];调用newton.m文件x0=[0,0];[x,val,k]=newton('fun','gfun','hess',x0)结果x=[-1.0000,1.5000]val=-1.2500k=15、用Fletcher—Reeves法求解问题222125)(minxxXf其中TxxX),(21，要求选取初始点6010,)2,2(TX。解一：1122201()(,),0502xfxxxx20050G，12()(2,50).Trfxxx第一次迭代：令00(4,100)Tpr，000004(4,100)100120450(4,100)050100TTrrpGp即，(1)(0)00(1.92,0)TXXp第二次迭代：1(3.84,0)Tr，21020||||3||||2000rr，T1100(3.846,0.15)prp111113.84(3.84,0)00.4802203.846(3.846,0.15)0500.15TTrrpGp(2)(1)11(0.0732,0.072)TXXp第三次迭代：2(0.1464,3.6)Tr……（建议同学们自己做下去，注意判别kr）解二：利用matlab程序求解首先建立目标函数及其梯度函数的M文件functionf=fun(x)f=x(1)^2+25*x(2)*x(2);functiong=gfun(x)g=[2*x(1),50*x(2)];调用frcg.m文件x0=[2,2]’;epsilon=1e-6;[x,val,k]=frcg('fun','gfun',x0,epsilon)结果x=1.0e-006*[0.2651,0.0088]val=7.2182e-014k=616、试用外点法（二次罚函数方法）求解非线性规划问题01)(..)2()(min22221xXgtsxxXf其中221),(RxxX解：设计罚函数(,)()*[()]^2PxMfXMgX采用Matlab编程计算，结果x=[10]；最优结果为1。（调用waidianfa.m）7、用内点法（内点障碍罚函数法）求解非线性规划问题：31212min(1)..100xxstxx解：容易看出此问题最优解为x=[10]；最优值为8.给出罚函数为31212(,)(1)(1/(1)1/)Pxrxxrxx令21211(,)3(1)0(1)Pxrrxxx；222(,)10Pxrrxx从而当0r时，1/2(1/3)1()0rxrxr（建议同学自己编程序计算）82212112min()()20fXxxhXxx解：建立乘子法的增广目标函数：22121212(,,)(2)(2)^22xxxxxxx令：1121(,,)2(2)0xxxxx2121(,,)2(2)0xxxxx解上述关于x的二元一次方程组得到稳定点222222x当乘子取2时，或发参数趋于无穷时，得到1*1xx即最优解。（建议同学自己编程序计算）练习题四1、石油输送管道铺设最优方案的选择问题：考察网络图4-6，设A为出发地，F为目的地，B，C，D，E分别为四个必须建立油泵加压站的地区。图中的线段表示管道可铺设的位置，线段旁的数字表示铺设这些管线所需的费用。问如何铺设管道才能使总费用最小？图4-1解：第五阶段：E1—F4；E2—F3；第四阶段：D1—E1—F7；D2—E2—F5；D3—E1—F5；第三阶段：C1—D1—E1—F12；C2—D2—E2—F10；C3—D2—E2—F8；C4—D3—E1—F9；第二阶段：B1—C2—D2—E2—F13；B2—C3—D2—E2—F15；第一阶段：A—B1—C2—D2—E2—F17；最优解：A—B1—C2—D2—E2—F最优值：172、用动态规划方法求解非线性规划123123123max()27,,0fxxxxxxxxxx解：1239,9,9xxx，最优值为9。3、用动态规划方法求解非线性规划22112121212max765..21039,0zxxxstxxxxxx解：用顺序算法阶段：分成两个阶段，且阶段1、2分别对应12,xx。决策变量：12,xx状态变量：,iivw分别为第j阶段第一、第二约束条件可供分配的右段数值。1111*22211111111100(,)max{76}min{76,76}xvxwfvwxxvvww*111min{,}xvw22*2*2222122220522222222222205(,)max{5(2,3)}max{5min{7(2)6(2),7(3)6(3)}}xxfvwxfvxwxxvxvxwxwx由于2210,9vw，2**222222222205(,)(10,9)max{min{33292760,68396621}xfvwfxxxx可解的129.6,0.2xx，最优值为702.92。4、设四个城市之间的公路网如图4-7。两点连线旁的数字表示两地间的距离。使用迭代法求各地到城市4的最短路线及相应的最短距离。214358674214358674图4-2城市公路网解：城市1到城市4路线——1-3-4距离10；城市2到城市4路线——2-4距离8；城市3到城市4路线——3-4距离4。5、某公司打算在3个不同的地区设置4个销售点，根据市场部门估计，在不同地区设置不同数量的销售点每月可得到的利润如表4-19所示。试问在各地区如何设置销售点可使每月总利润最大。表4-1地区销售点01234123000161210251714302116322217地区地区销售点销售点0011223344123123000000161210161210251714251714302116302116322217322217解：将问题分为3个阶段，k=1，2，3；决策变量xk表示分配给第k个地区的销售点数；状态变量为sk表示分配给第k个至第3个地区的销售点总数；状态转移方程：sk+1=sk－xk，其中s1=4；允许决策集合：Dk（sk）=｛xk|0≤xk≤sk｝阶段指标函数：gk（xk）表示xk个销售点分配给第k个地区所获得的利润；最优指标函数fk（sk）表示将数量为sk的销售点分配给第k个至第3个地区所得到的最大利润，动态规划基本方程为：1044()max[()()]3,2,1()0kkkkkkkkkxsfsgxfsxkfsk=3时，333333()max[()]xsfsgx417174316163214142110101000043210x3*f3(s3)g3（x3）417174316163214142110101000043210x3*f3(s3)g3（x3）k=2时，2222223220()max[(