最优化方法及其应用课后答案.pdf

《最优化方法及其应用课后答案.pdf》由会员分享，可在线阅读，更多相关《最优化方法及其应用课后答案.pdf（25页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、最优化方法部分课后习题解答习题一习题一1.1.一直优化问题的数学模型为：一直优化问题的数学模型为：2min f(x)=(x1 3)2+(x2 4)5g(x)=x x 01212gs.t.(x)=x x+50122g(x)=x 013g4(x)=x20试用图解法求出：试用图解法求出：（1 1）无约束最优点，并求出最优值。无约束最优点，并求出最优值。（2 2）约束最优点，并求出其最优值。约束最优点，并求出其最优值。（3 3）如果加一个等式约束如果加一个等式约束h(x)=x1x2=0，其约束最优解是什么？，其约束最优解是什么？解：（1）在无约束条件下，f(x)的可行域在整个1x 0 x2平面上，不难

2、看出，当x=（3，4）时，f(x)取最小值，即，最优点为x=（3，4）：且最优值为：f(x)=0（2）在约束条件下，f(x)的可行域为图中阴影部分所示，此时，求该问题的最优点就是*在约束集合即可行域中找一点(x1,x2)，使其落在半径最小的同心圆上，显然，从图示中可15 5以看出，当x=(,)时，f(x)所在的圆的半径最小。4 4*15x1=04其中：点为g1(x)和g2(x)的交点，令求解得到：25x=g2(x)=x1x2+5=02415 565*即最优点为x=(,)：最优值为：f(x)=4 48g1(x)=x1x25（3）.若增加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。

3、2.2.一个矩形无盖油箱的外部总面积限定为一个矩形无盖油箱的外部总面积限定为S S，怎样设计可使油箱的容量最大？试列出这个优，怎样设计可使油箱的容量最大？试列出这个优化问题的数学模型，并回答这属于几维的优化问题化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为：max f(x)=x1x2x3x1x2+2x2x3+2x1x3Sx 0s.t.1x 02x30该优化问题属于三维的优化问题。x=s/3,y=s/3,z=s/12v=3s 3s1s2=18 习题二习题二3.3.计计算一般二次函数算一般二次函数f(x)=解：设：A=(a)ij nn1TX AX+bTX+c的梯度。

4、的梯度。2,b=(b,b,.b)T,X=(x,x,.x)T则：12n12nnf(x)=12i=1 j=1a xx+bx+cij i jnni ii=1，将它对变量ix(i=1,2,.n)球偏导数得：n1nnf(x)aa1jxji 1xia1jxj+ai 1xi+b122xj=1i=1j=1i=1n11nn1nx+b1 a x1f(x)a2jxj+aa x2i2 i2=2 j j+i2 i+bf(x)=2j=1i=1i=12j=122xf(x)nnnn11 xaa3i nxinjxja xni=1ji=12+j=1bj=1ja+in21T=(AX+A X)+b21nb12b35.5.求下列函数的

5、梯度和求下列函数的梯度和 HesseHesse矩阵矩阵（1）f(x)=x2+2x2+3x2 4xx1231 3（2）f(x)=3xx+e2xx121 2 x2ex1x26x+ex1x2+xxex1x2解：f(x)=221 26x+ex1x2+xxex1x26x+x2ex1x22121122 0-4解：f(x)=0 4 04 0 626.6.判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：22（1）f(x,x)=x+2x1212+3xx1 2解：2f(x)不是半正定，即f(x)非凸，然后判断-f(x)，经验证：2(f(x)不是半正定，由此可

6、知：f(x)非凸非凹。2（2）f(x,x)=4xx+3x25x61122x 11 22解：2f(x)半正定，故f(x)为凸函数。（3）f(x,x3)=x1+2x2 3x3 4xx1x21 2解：2f(x)不是半正定，即f(x)非凸，然后判断-f(x)，经验证：2(f(x)不是半正定，由此可知：f(x)非凸非凹。2227.7.设约束优化问题的数学模型为：设约束优化问题的数学模型为：2min f(x)=x2+4x+4x+11x2210)=xx+2 0s.t.g1(x1222g(x)=x x 2x+2x 021212试用试用 K-TK-T 条件判别点条件判别点x=1,1是否为最优点。是否为最优点。T

7、解：对于点x=1,1，g(x)=0，g(x)0，点满足约束条件，故点X是可行解。12T21且g1(x)是起作用约束，I=1,f(x)=,g(x)=，由gi(x)0条件下的211K-T 条件得：f(x)g(x)=0,0，得到=2，点x=1,1满足 K-T 条Tiii1iI件。又因2f(x)正定，故f(x)为严格凸函数，该最优化问题是凸规划问题，由x*=1,1是 K-T 点，所以x*=1,1也是该问题的全局最优点。TT8.8.设约束优化问题：设约束优化问题：2min f(x)=(x1 2)2+x2st.g2(x)=x20g(x)=1+x2+x 0312它的当前迭代点为它的当前迭代点为xk=1,0，

8、试用，试用 K-T 条件判定它是不是约束最优解。条件判定它是不是约束最优解。TTTk1k2k3kkg1(x)=x10解：对于点x=1,0g(x)=10,g(x)=0,g(x)=0，点x=1,0是可行点，20 且起作用的约束条件是，g2(x),g3(x)，I=2,3,f(xk)=，g2(xk)=012 g(x)=，由约束条件为g(x)0时的 K-T 条件得，应有：3k i1f(x)+g(x)=0,0解得：T2=1，所以xk1,0为 K-T 点。=1=iiiiI3现判断该问题是否为凸规划问题，因 f(x)正定，故f(x)为凸函数，g(1x),g(x2)为线性函数，亦为凸函数，2g(x)半正定，所以

9、g(x)为凸函数，所以该优化问题为凸规33划问题，即点x=k1,0是该问题的约束最优解。T2习题三习题三1.1.对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。max f(x)=3x1+x2+2x312x1+3x2+6x3+x4=9（1 1）8x+x4x+2x=10s.t.12353x x=016xj0,(j=1,2.6)12 3 6 3 0 0解：令A=81-4 0 2 0=(P,P,P,P,P,P)12345630 0 0 0 -1167（1）基解x=(0,0,0,0)不是基可行解，136（2）基解

10、x2=(0,10,0,7,0,0)不是基可行解，（3）基解x3=(0,3,0,0,3.5,0)是基可行解，且f(x)=3，721(,4,0,0,0,)不是基可行解，（4）基解x4=445（5）基解x=(0,0,8,0,0)不是基可行解，532（6）基解x=是基可行解，且f(x)=3，(0,0,0,16,0)621（7）基解x=(1,0,0,0,3)不是基可行解，72（8）基解x8=(0,0,0,3,5,0)是基可行解，且f(x)=0，1552,0,)不是基可行解。(,0,0,（9）基解x9=44939是基可行解，且f(x)=。（10）基解x10=(,0,0,0,4,)444167（11）基解x

11、=(0,0,0,0)不是基可行解。1136（12）基解x12=(0,10,0,7,0,0)不是基可行解。7（13）基解x13=(0,3,0,0,0)是基可行解，且f(x)=3。251432（15）基解x=是基可行解，且f(x)=3。(0,0,0,8,0)152（14）基解x=(0,0,8,0,0)不是基可行解。（16）基解x16=(0,0,0,3,5,0)是基可行解，且f(x)=3。2.2.用单纯形法求解下列线性规划问题：用单纯形法求解下列线性规划问题：max f(x)=10 x1+5x23x1+4x2 9（1 1）s.t.5x1+2x28x,x 012解：将现行规划问题化为标准形式如下：mi

12、n(f(x)=10 x15x2+0 x3+0 x43x1+4x2+x3=9s.t.5x1+2x2+x4=8x,x,x,x 01234作初始单纯形表，并按单纯形表步骤进行迭代，如下：CBXBb-10 x1-5x20 x30 x4i00 x3x49804.21.6161.5117.535-1001001042-52.80.4-110010010051417514010-0.60.2231427251431.60-10 x3x11.54-5-10 x2x13(1,0,0)此时，j均为正，目标函数已不能再减小，于是得到最优解为：x=2目标函数值为：f(x*)=17.5*3.3.分别用单纯形法中的大分别

13、用单纯形法中的大 MM 法和两阶段法求解下列线性规划问题：法和两阶段法求解下列线性规划问题：min f(x)=5x12x2+3x36x4（1）x1+2x2+3x3+4x4=7s.t.2x1+x2+x+2x=3x,x,x3,x 401234解：（1 1）大大 M M 法法：把原问题化为标准形式，并加入人工变量如下：min f(x)=5xxx12x2+3x36x4+M5+M6x1+2x2+3x3+4x4+x5=7s.t.2x+2x+x6=31+x2+xx,x,x,x,x3,x 40123456作初始单纯形表，并按单纯形表步骤进行迭代，如下：CBXBb5x1-2x23x3-6x4-6x4-6x4iM

14、Mx5x673122131421001001-0.5010-20.53M+3-21.51.751.5-10M5-3M-2-3M 3-4M-6-6Mx5x4M-611.5-3100.5100.5110.56-M100010010139-M11+3Mx3x43-6113-32.529M-6 M+15因为M 是一个很大的正数，此时j均为正，所以，得到最优解：x*=(0,0,1,1,)T，最优值为f(x*)=3（2 2）两阶段法）两阶段法首先，构造一个仅含人工变量的新的线性规划如下：ming(x)=0 x1+0 x2+0 x3+0 x4+x5+x6x1+2x2+3x3+4x4+x5=7s.t.2x+x

15、2+x+2x4+x6=3x,1x,x,x3,x,x 0123456按单纯形法迭代如下：CBXBx5x6x5x4x3x4*b0 x10 x20 x30 x41x41x4i11100073-1011.5-11112-3-314-32.521-300.5000.531-410.5-11042-6010011001001-0.501.7511.50-210.533-21.5最优解为：x=(0,0,1,1,0,0)，最优值：g(x)=0因人工变量x5=x6=0，则原问题的基可行解为:x*=(0,0,1,1,)T,进入第二阶段计算如下表所示：CBXBx3x4b5x1-2x23x3-6x43-6113-32

16、.52900.51*100T010由上表可知，检验数均大于等于 0，所以得到最优解：x=(0,0,1,1,)最优值为f(x)=3。*4.4.某某糖果厂用原料糖果厂用原料 A A，B B，C C 加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖加工成三中不同牌号的糖果，甲，乙，丙，已知各种牌号糖果中果中 A,B,CA,B,C 含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建立价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该

17、厂获利最大？试建立这个问题的线性规划数学模型。这个问题的线性规划数学模型。甲ABC乙丙原料成本（元/千克）每月限用量（千克）20002500120060%15%2.001.502060%0.402.8550%0.302.25%加工费0.50售价3.401.00解：设x表示甲、乙、丙中分别含A、B、C 的含量，构造此问题的i,yi,zi0,i=1,2,3数学规划模型如下：max f(x)=0.9x1.4x2+1.9x3+0.45y1.45y30.5z1+1+0.95y2+1+0.45z2+0.95z3x1+y1+z12000 x+y+z 2500222x3+y3+z312000.4x 0.6x

18、0.6x 0231s.t.0.85y10.15y20.15y300.2x+0.2x 0.8x 02310.6y10.6y2+0.4y300.5z+0.5z 0.5z 0231zi0,i=1,2,3xi,yi,5.5.求解下列线性规划问题的对偶问题求解下列线性规划问题的对偶问题min f(x)=2x1+2x2+4x32x1+3x2+5x 2（1）3x+x+7x3 3123s.t.x+4x+6x 5231x2,xx1,30max f(x)=5x1+6x2+3x3 x1+2x2+2x3=5x+5xx3（2）123s.t.4x+7x+3x 8231x1无约束,x20,x30解：（1）由表 3.7 可得

19、该问题的对偶问题为：maxg(y)=2y1+3y2+5y32y1+3y2+y323y+y+4y 23s.t.12y+7y2+6y345y1 0,y,y 0123（2）该问题的对偶问题为：ming(y)=5y1+3y2+8y3y13y2+4y3=52y+5y+7y 6123s.t.2y y+3y 3123y无约束,y 0,y 01236.6.用对偶单纯形法求解下列线性规划问题：min f(x)=4x1+12x2+18x3x1+3x3 3（1）s.t.2x2+2x 5x,x,3x 0123解：（1）首先，将“”约束条件两边反号，再加入松弛变量，得：min f(x)=4x1+12x2+18x3+0

20、x4+x5 x13x3+x4=3s.t.2x 2x+x=5235x,x,x,x,x 012345建立初始单纯形表如下图所示，所有j 0。则对应对偶问题解是可行的，则继续迭代：CBXBx4x5b4x112x218x30 x40 x500-3-5-1040-212-3-218100010计算min3,5=5，所以x5为换出变量，=min6,9=6，确定x2为换入变量。继续迭代，得到如下单纯形表：CBXBx4x2b4x112x218x30 x40 x500-3-2.5-104010-3161000-0.50min3=3,x出，min4，2=2，x4换3换入。CBXBx3x2jb4x111*12x21

21、8x30 x411*0 x50011.5此时，所有 0，故原问题的最优解为x=20103T0,12,最优值为：f(x)=3610020-0.56其对偶问题得到最优解为：x*=2,6T，最优值为：f(x*)=36。7.7.已知线性规划问题已知线性规划问题min f(x)=2x1x2+x3x1+x2+x3 6s.t.x+2x 412x,x,x 0123先用单纯形法求出最优解，再分别就下列情况进行分析：先用单纯形法求出最优解，再分别就下列情况进行分析：（1 1）目标函数中变量目标函数中变量x1,x2,x3的系数分别在什么范围内变化，问题的最优解不变；的系数分别在什么范围内变化，问题的最优解不变；（2

22、 2）两个约束条件的右端分别在什么范围内变化，问题的最优解不变。两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量x4,x5min f(x)=2x1x2+x3+0 x4+0 x5,+x2+x3+x4=6x1s.t.x+2x+x=4125x,x,x,x,x 012345用单纯形法求解，如下表：CBXBx4x5b2x1-1x21x30 x40 x5i0011.5420-1x4x21-121.5-0.51.512-1010101101100100010-0.50.50.562*T由上表可知，所有的检验数均大于等于零，得最优解:x=(0,2,0,4,0)

23、,所以原问题的最优解为：x*=(0,2,0,)T，最优值f(x*)=2（1）变量x1，x2，x3中，x1，x3为非基变量，x2为基变量。3311由=，当c=c+c，所以，当c+),此时最优解不变。111,时，c2111222由3=1，当c时，c313=c3+c30，所以，当c30,+),此时最优解不变。c2(3,1)，最优解不变。综上，当c1,+)，c，c24,030,+),此时最优解不变。（2）b1的变化范围1210.5 b41b401B1b+B10=2+00.5 1=+b 10020 得到：4+b的变化范围是b10 b1 4，则b112，最优解保持不变。0410.5040.50B1b+B1

24、=+=+b 00.5 b20.520b22 2 得到：4 b2 8，则b2的变化范围是0,12，最优解保持不变。习题四习题四3.3.用用 Newton 法求解法求解(t)=t32t+1用第用第 1 题求得的区间，按精度题求得的区间，按精度=0.01计算。计算。解：(t0)=(0)=1,t(t(t(t0)，则h1=t0+h0=1,1)=0,1=0,因为1)1=h0=2t2=t1，(t2)=22,2=22,(t(t2)，反向，因为K=2 0,所以=0，b=31+h1=1)则搜索区间为t0,3(t)=3t 2,(t)=6,(0)=20取：215 55t=1,(t)=1,(t)=6,所以t=1=10.

25、01，继续迭代t=t=，000066 66(t0)491149t=t=,则tt=0.01,令t=，则t 0.8165，0006060(t0)60t t0=0.0005 0.01,所以t*=0.817,*=(t*)0.088。4.4.用黄金分割法求解用黄金分割法求解min(t)=t(t+2)已知初始单谷区间已知初始单谷区间aa，b=-3b=-3，55，按精度，按精度=0.001计计算。算。解：t1=3+0.3828=0.056,t2=3+50.056=1.944，(t(t2)=7.667136，因为(t(t2)，则新的搜索区间为-3，1.944：1)=0.115136,1),继续迭代，因为1)t

26、1=1.832608,(t(t2)=0.987592，1)=0.306764,t2=1.111392,tt2,继续迭代，因为(t(t2)，所以新的搜索区间为-1.832608，0.056：11)t1=1.111292,(t(t2)=0.888075，1)=0.987592,t2=0.665448,t(t(t2)，所以新的搜索区间为-1.832608，-0.665448：1t2,继续，1)t1=1.386753,(t(t2)=0.987592，1)=0.854402,t2=1.111392,t(t(t2)，所以新的搜索区间为-1.386753，-0.6654481t2,继续，因为1)t2=0.9

27、40987,(t2)=0.996518,t(t，1=1.111392,1)=0.987592，t(t(t2)，所以新的搜索区间为-1.111392，-0.665448：1t2,继续，因为1)t1=0.940987,(t(t2)=0.973038，1)=0.996518,t2=0.835799,t(t(t2)，所以新的搜索区间为-1.111392，-0.835799：1t2,继续，因为1)t2=0.940987,(t2)=0.996518,t(t，1=1.006115,1)=0.999962，t(t(t2)，所以新的搜索区间为-1.111392，-0.940987：1t2,继续，因为1)t1=1

28、.046295,(t(t2)=0.999962，1)=0.997857,t2=1.006115,t(t(t2)，所以新的搜索区间为-1.046295，-0.940987：1t2,继续，因为1)t2=0.981215,(t2)=0.999647,t(t，1=1.006115,1)=0.999962，t(t(t2)，所以新的搜索区间为-1.046295，-0.981215：1t2,继续，因为1)t1=1.021434,(t(t2)=0.999962，1)=0.999540,t2=1.006115,t(t(t2)，所以新的搜索区间为-1.021434，-0.981215：1t2,继续，因为1)t2=

29、0.996579,(t2)=0.999987,t(t1=1.006115,1)=0.999962，t(t(t2)，所以新的搜索区间为-1.006115，-0.981215：1t2,继续，因为1)t1=0.996579,(t(t2)=0.999914，1)=0.999987,t2=0.990727,t(t(t2)，所以新的搜索区间为-1.006115，-0.990727：1t2,继续，因为1),继续，因为1),继续，因为1)t2=0.998830,(t2)=0.999998505,t(t1=1.000237,1)=1.00000016，t(t(t2)，新的搜索区间为-1.002472，-0.99

30、88301t2,继续，因为1)t1=1.001081,(t(t2)=1.00000016，1)=0.999999075,t2=1.000237,，停止迭代。所以：因为t1t2,t t0,(t)=0.063,t t0,(t)=0.1588 ,t t0,(t)=0.2004,t t0,(t)=0.2029 ,t t0,(t)=0.2032 ,t t0,(t)=0.2034 (t0)=0.2032新的搜索区间为0.6260，1，t1=0.6260,t2=1,t0 0.6284，t 0.6276,，t是(t)在区间上的近似最优解，t*=t=0.6276，t0 t 11.919883.89760.073

31、48x2=xg11=0.48089=Tg1A g10.0030.150.06913f(x2)=0.124872g2T00同理继续迭代，最后至x=，此时最优解x=，f(x)=000 g gT2.2.用用 NewtonNewton 法求解法求解Tmin f(x)=60 10 x14x2+x21+x22-xx，初始点x=001 2，0，=0.01.解：Tg(x)=f(x)=10+2xx1x1x2,4+2221 21331G(x)=G(x)=12123310032131x=xG(x)g(x)=8,6T0124100 33Tf(x)1=0,0,f(x1)=0 0.01 最优解为x*=8,6T,f(x*)

32、=83.3.用修正用修正 NewtonNewton 法求解法求解22Tmin f(x)=（4 x+）+（2 x 21）+x+1x+10=0.01.112，初始点x=00，0，T解：g(x)=f(x)=8x+9,4x 3129 0 x1=x0+t0p0=t3 8t40T0，g(x)=9，G(x)=，G(x)=30401048018119 00t981T,，令x1=x0+t0p0=8则p0=G(x)g(x)=13=9 3038 40t4409999f(x)=t2t+16 t=1时，f(x)最小11689 3Tx=，f(x)=0,0T,118 49 3T x*=157*=,f(x)8 416f(x)

33、=0 0.0114.4.用共轭梯度法求解用共轭梯度法求解min（x1+4x2），取初始点x=，1，=0.01.0122T解：令f(x)=x2+4x2,f(x)=2x,8x，p=f(x)=2,8111200TTx=x+t p=1012T+t=12t,18t000108 022令min(1 2tt0)+4(1 80)=min(t)，则(t)=520t 68=0 t=0.130969ddt00Tx=0.738062,0.047752T，f(x1)1=1.476124,0.3820162f(x)2.3248781则=0.0341890268f(x)0 新搜索方向为p1=f(x1)+0p021111.4

34、76124 21.544502=+0.034189=0.382016因此有x=x+tp=0.7380621.544502t,0.047752+0.108504t11Td由f(x+tp)=0 t 0.47712711 11dt 0.738062 1.544502因而得下一迭代点x=x+tp=+0.477127=0.00,0.007T211 10.0477520.108504f(x2)=0 0.01停止迭代，x*=0,0T,f(x*)=05.5.用共轭梯度法求解用共轭梯度法求解min f(x)=2xT21+x22-xx，自定初始点，=0.01.1 2T000解：f(x)=4x x,2x x，取初始

35、点x=0,1，p=f(x)=1,2T1221T01x=x+t p=+t=t,12t100001020 令min2t0+(1 2t(1 2t0)t00)=min(t)则(t)=16t5=0 t=0.12522d00dtTTx=10.3125,0.375，f(x)1=0.875,0.43752f(x)0.957031251=0.191406025f(x)0 新搜索方向为p1=f(x1)+0p0 0.8751 0.683594=+0.191406=0.820120.43752因而得下一迭代点x=x+tp=0.31250.683594t,0.3750.820312tT211111d由f(x+tp)=0

36、 t=0.456927，11 11dt则x=0.000,0.000T，f(x)=0,0T,22f(x)=0 0.01停止迭代2T*T*则x*=x=0,0，综上所述，原问题的最优解x=0,0，最优值为f(x)=026 6.120用用80TA=,g(x)=8x 40,2x 126、解：取H0=I,0212D DF FTTP Px=8,19,g=24,600法法TT第一步迭代得：x=4.86154,8.21538,g=1.10768,4.4307611求求解解用 DFP 法第二次迭代：s=x x=3.13846,0.78462T010minf(x)=4y=g g=25.10768,1.56924T0

37、10ssTH y yTH00 0 0则H1=H0+0TTs yy H y0000 0因：sTy=80.03071,000，0yTH y=yTy0000=632.85811225）+（x 6），初始点 x=8，9 T，=0.01.9.849932.462509.849932.46250ssT=，ssT=0 00 02.462500.615632.462500.61563100.123080.030770.996110.06226 0.126970.03149H1=01+0.030770.007700.062260.00390=0.031491.0 0 38T则搜索方向p1=Hg1 1=0.280

38、17,4.48248从xp1出发沿1进行直线搜索，即：x+t p=14.861540.28017t,8.21538+4.48248t1=x1由f(x+tp)=0，得t=0.48674Tddt211所以x=x+tp 5.000,6.000，由于g(x)=0,0，所以x=5,6是极小1122TTT点。习题六习题六1.1.用外点罚函数法求解：用外点罚函数法求解：min f(x)=x1+x22g(x)=x+x 012s.t.1g2(x)=x10解：利用外点罚函数法构造增广目标函数，如下：x+x+(x2+x)2+x2121F(x,)=12x1+x2对于xD的情况：(xD)(x D)x()=,1F=0,F

39、=0得：2由xx2+2 4(1+)21112当+时，x()(0,0)即：x=(0,0)，且f(x)=02.2.用外点罚函数法求解：用外点罚函数法求解：2min f(x)=x2+x12s.t.g(x)=1x10解：构造增广目标函数：222x+x+(1x)21F(x,)=122x1+x2(xD)(x D)对于xD的情况：2x(1xFF121)=0得：2x=0由=0,=0 xx212 推出：x()=1+,0当+时，x()(1,0)。即：x=(1,0)且f(x)=1。4.4.用内点罚函数法求解：用内点罚函数法求解：1min f(x)=(x+1)3+x231)=x0g1(x11s.t.g(x)=x 02

40、2解：利用内点罚函数法构造如下增广目标函数：111F(x,r)=(x+1)3+x+r(+)kk2x 1x3112由Fx1=0F=0 x2+*得：x(xk)=(1+*rk,rk)当r 0时，x(x)(1,0)kk8 x*=(1,0)，f(x*)=35.5.用内点罚函数法求解：用内点罚函数法求解：13min(x1+1)+x23x11 0s.t.x 02解法同上。习题七习题七1.1.用动态规划求解：用动态规划求解：2maxE=xxx1 2 3x1+x2+x3 4s.t.x0(i=1,2,3)i解：将原问题表示为：max E=1 2 3uuu2u1+u2+u3 4s.t.ui0(i=1,2,3)由此，

41、确定状态变量为：x1,x2,x3，决策变量为：u1,u2,u3状态转移方程：x1=u1;x2=u2+x1;x3=u3+x24。用动态规划的思想顺推，如下：第一步，k=1:11f(x)=maxu1=x1u=x,且u=x。11*11第二步，k=2:f2(x2)=maxu2 f1(x1)0u2x2=maxu2 f1(x2u2)0u2x2=maxu2(x2u2).0u2x21令：(u)=u(x u)，由(u)=0，得u：=x1211 f(x)=max0，x,0=x2，且u*=x222222442第三步，k=3:2222222233f(x)=max0u3x32332u3 f(x u)0u3x321u(x

42、 u)2.=maxmax0u3x3u f(x)3222343311同理，令：(u)=u2(x u)2，由(u)=0，得u：=x33333332144141 f(x)=max0，x,0=x，且u*=x3333336464214x 4 f(x)=4=433364将f3(x代入上述表达式，逆序递推求出：3)=4x=4,u*=2，x=2,u=1，2233*x=1,u1*1=1.新问题的最优解为：u*=(1,1,2)，且 f(u*)=4原问题的最优解为：x*=(1,1,2)，且 f(x*)=4.2.2.设有设有 5 5 个城市，编号从个城市，编号从 1 1 到到 5 5，记第，记第i个城市与第个城市与第

43、j个城市的距离为个城市的距离为dij，记：，记：0652 2 60 0.5 5 7D=(dij)55=5 0.5 0 1 5，251 0 3275 3 0试分别用函数迭代法和策略迭代法求出各城市到第试分别用函数迭代法和策略迭代法求出各城市到第 5 5 个城市的最短距离。个城市的最短距离。解：法一，函数迭代法：k=1时，f1(i)=di5(i=1,2,3,4,5)f1(1)=2,f1(2)=7,f1(3)=5,f1(4)=3,f1(5)=0.k=2时，f2(i)=mindi j+f1(j)，0 j5f2(1)=min0+2,6+7,5+5,2+3,2+0=2=f1(1),f2(2)=min6+2

44、,0+7,0.5+5,5+3,7+0=5.5f1(2),f2(3)=min5+2,0.5+7,0+5,1+3,5+0=4 f1(3),f2(4)=min2+2,5+7,1+5,0+3,3+0=3=f1(4),f2(5)=0=f1(5).对于所有i,并不满足f2(i)=f1(i)，故须继续迭代。k=3时，f3(i)=mindi j+f2(j)，0 j5f3(1)=min0+2,6+5.5,5+4,2+3,2+0=2=f2(1),f3(2)=min6+2,0+5.5,0.5+4,5+3,7+0=4.5 f2(2),f3(3)=min5+2,0.5+5.5,0+4,1+3,5+0=4=f2(3),f

45、3(4)=min2+2,5+5.5,1+4,0+3,3+0=3=f2(4),f3(5)=0=f2(5).对于i,并不满足f3(i)=f2(i)，故须继续迭代。k=4时,f4(i)=mindi j+f3(j)，0 j5f4(1)=min0+2,6+4.5,5+4,2+3,2+0=2=f3(1),f4(2)=min6+2,0+4.5,0.5+4,5+3,7+0=4.5=f3(2),f4(3)=min5+2,0.5+4.5,0+4,1+3,5+0=4=f3(3),f4(4)=min2+2,5+4.5,1+4,0+3,3+0=3=f3(4),f4(5)=0=f3(5).对于i,满足f4(i)=f3(i

46、)，故f(i)=f3(i)，故各城市到第5个城市的最短距离分别为：f(1)=2,f(2)=4.5,f(3)=4,f(4)=3,f(5)=0.法二，策略迭代法：设初始策略为：u)=2,3,4,5,5,1=u1(i则在策略u1下，由点i到点 5 的路程f1(i)分别为：f1(4)=c45+f1(5)=3+0=3,其中，对k，有fk(5)0.f1(3)=c34+f1(4)=1+3=4,f1(2)=c23+f1(3)=0.5+4=4.5,f1(1)=c12+f1(2)=6+4.5=10.5.计算f2(i)，并确定新策略u2：f2(1)=minc)1j+f1(j=min0+10.5,6+4.5,5+4,

47、2+3,2+0=2,u2(1)=5 u1(1).f2(2)=minc2 j+f1(j)=min6+10.5,0+4.5,0.5+4,5+3,7+0=4.5,u2(2)=3=u1(2).f2(3)=minc3 j+f1(j)=min5+10.5,0.5+4.5,0+4,1+3,5+0=4,u2(3)=4=u1(3).f2(4)=minc4 j+f1(j)=min2+10.5,5+4.5,1+4,0+3,3+0=3,u2(4)=5=u1(4).计算f3(i)，并确定新策略u3：f3(1)=minc)1j+f2(j=min0+2,6+4.5,5+4,2+3,2+0=2,u3(1)=5=u2(1).f

48、3(2)=minc2 j+f2(j)=min6+2,0+4.5,0.5+4,5+3,7+0=4.5,u3(2)=3=u2(2).f3(3)=minc3 j+f2(j)=min5+2,0.5+4.5,0+4,1+3,5+0=4,u3(3)=4=u2(3).f3(4)=minc4 j+f2(j)=min2+2,5+4.5,1+4,0+3,3+0=3,u3(4)=5=u2(4).此时，对于i，有u3(i)=u2(i)，故u2(i)为最优策略。即：最优策略为u2=(5,3,4,5,5)。从各城市到城市 5 的最短距离分别为：2，4.5，4，3，0，且最短路线分别为：15，2345，345，45，55。