最优化方法及其应用课后答案(郭科陈聆魏友华)

1、最优化方法部分课后习题解答习题一1一宜优化问题的数学模型为：niin y%Y）=（再 一 3）2 + （.r2 一 4）2自=.勺_七_|0必憧=-丙-可+ 5 2 0 ©（才）=丙0 吕（丫）=七no试用图解法求出:（1）无约束最优点，并求出最优值。（2）约束最优点，并求出其最优值。（3）如果加一个等式约束（.1） = - = 0,其约束最优解是什么？解：（1）在无约束条件下，的可行域在整个內0勺平而上，不难看出，当（3, 4） 时，/0）取垠小值，即，瑕优点为/=（3, 4）:且最优值为：/1（/）=0（2）在约束条件下，/0丫）的可行域为图中阴影部分所示，此时，求该问题的最优点

2、就是在约束集合即可行域中找一点（刁,吃），使其落在半径瑕小的同心岡上，显然，从图示屮町 以看出，当/ = （-,-）时，/）所在的圆的半径最小。1575_44 4其中：点为&G）和冬（.丫）的交点，令自（"丫）=旳-“ 一亍求解得到:畐（"）=_內_兀 + 5 = 0即最优点为注最优值为:用）哼（3）.若增加一个等式约束,则由图可知,可行域为空集,即此时最优解不存在。2个矩形无盖油箱的外部总面积限定为S,怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为:max /X-t） = 2x3x3 >

3、; 0该优化问题属于三维的优化问题。3 计算一般二次函数/W =丄XtAX bTXc的梯度。2解：设：力=（勺）“Z>= 0，2，.2）；Y=（丙,*2，.心）则：/W =丄£ £勺兀巧+ X勺兀+ c，将它对变最兀（/ = 1,2,.用球偏导数得:2 & /-I7-1W)=W)'s 如dx:叽丫）£ £1 - 2 1 - 21 w1 w亍号+亍£务兀+力”L >=1L z=l5求下列函数的梯度和Hew矩阵2 0 4、(1) f(x) = .Vj2 + 2可 + 3.v32 - 4.斤.才3 解:=040 一4 0

4、6 ,7(2) /) = 3旺尸+ 6勺解:vy（x）=丫2咕°巾6S +小巧+円“2护巧、6七+护巧+再七夕巧6再+还I6判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：（1）/,七）=-彳+ 2才+ 3再兀解：v2A0不是半正定，即/>）非凸，然后判断/（.丫），经验证：v3（-/（.v）不是半 正定，宙此可知：/G）非凸非凹。（2）丙,七）=2丙2 _4.斤七+ 3才?2 _5丙_6解：vy（x）半正定，故/V）为凸函数。(3) yr(x1,x2,A3) =+ 2x22 -3x32 -4.Xpt2解：沪/不是半正定，即/:才)非凸，然后判断-/>),经验证：V2

5、(-/(.v)不是半 正定，由此可知：/V0非凸非凹。7设约束优化问题的数学模型为：niin /(j) = A2 + 4 円 + x22 一 4七 +10&G)” + 2nost“=©(x) = -xx - x2 - 2a + 2x2 > 0试用K-T条件判别点=-l,lf是否为最优点。解：对于点x=-l,lf,昌刃，仝(才)0，点满足约束条件，故点乂是可行解。丫2、( 且是起作用约束，/= 1 /YA) = JgiGX ，由v(.r)>0条件下的 1-2丿I丿KT条件得：7/)-工人Vg(x) = 0,人no,得到入=2,点x=-l,lf满足KT条 /eZ件。又

6、因V3/(.v)正定，故为严格凸函数，该最优化问题是凸规划问题，111Z = -1,1/是kt点，所以+ = -i,i7也是该问题的全局最优点。8 设约束优化问题:min /x) = 3 - 2尸 + 昌(力=一円so x/J2(x) = -2 <0£3(才)=-1 + 可2 + 乃 SO它的当前迭代点为耳=卩,of，试用K-T条件判定它是不是约束最优解。 解：对于点忑=l,o7 ©(.Y=-1 5 0,&2 (忑)=0,g3(x=0 ,点X严1,07是可行点,且起作用的约束条件是,4(",自，/=2,3,Y/R)h 0 > VU)=Vg3Cv

7、k)= Jj,山约束条件为&(x)<°时的KT条件得，应有:Y/U)+工&yg(x)= o,人no 解得：,所以玉=1,0为k.t点。心“3=1 现判断该问题是否为凸规划问题，因v2AO正定，故/W为凸函数，自（“,仝（力为 线性函数，亦为凸函数，v2g3（.v）半正定，所以（切为凸函数，所以该优化问题为凸 规划问题，即点 = 1,07是该问题的约束最优解。习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。max /.r) = 3丑 + “2 + 2 屯12可+ 3.巧+ 6屯+= 9<12 3 6 3 0 0解：1= 81

8、 -4 0 2 0=($ 尽召/£&)30 0 0 0 -1Z(1)垒解 =(0,-1,0,0,0)不是基可行解，36（2）基解兀=（0,10,0,7,0,0）不是基可行解，（3）基解可=（0,3,0,0,3.5,0）是基可行解,且加 =3,（4）基解兀=（扌,_4,0,0,0,手）不是丛可行解，（5）基解冯=（0,0,-,8,0,0）不是基可行解，2（6）丛解;16 = （0,0,-,0,16,0）是基可行解，且 Av） = 3,2（7）基解“7 = （1,0,-丄,0,0,3）不是基可行解，2（8）基解七=（0,0,0,3,5,0）是基可行解,且A0 = 0 ,（9）基解

9、 = （|,0,0-2,0,）不是基可行解。399（10）丛解 0 = （-,0,0,0,4,-）是基可行解，且 Av） = -o（11）基解切=（0,-,0,0,0）不是基可行解。36（12）歴解也=（0,10,0,-7,0,0）不是基可行解。7（13）基解知=（0,3,0,0,_,0）是基可行解,且加 =3。2(14) 基解也=(0,0,-,8,0,0)不是基可行解。2(15) 基解円5 = (0,0丄,0,8,0)是基可行解，且A0 = 3o2(16) 基解% = (0,0,0,3,5,0)是基可行解,且加 =3。2. 用单纯形法求解下列线性规划问题:max/a) = 104j + 5,

10、r2f3jtj + 4x2 <9s.t.< 5丙 + 2.x2 <8xXyx2 >0解：将现行规划问题化为标准形式如下:min(-y%Y) = -10无 一 5七 + 0.r3 + 0兀 3可 + 4x2 + x3 = 9s/.i5.xl + 2x2 + x4 = 8G巧，屯，兀no作初始单纯形表，并按单纯形表步骤进行迭代.如下:Cbb-10-50冯0孔q0934103085?011.60-1050004.202.81-0.61.5-10'11.610.400.24160-102-5“21.501514314-10110172717.5005142514此时，6

11、均为正，目标函数己不能再减小，于是得到最优解为：/ = (1,-,0,0) 2目标函数值为：AO = 17.55. 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题:min /(.x) = 5血 _ lx2 + 3屯 _ 6x4(1)+ 2x2 + 3x3 + 4* = 7s.t.lxx + x2 + x3 + 2x4 = 3解：（1）大M法：把原问题化为标准形式，并加入人工变最如下:min y%Y)= 5.q - 2x2 + 3 屯 一 6x4 + Mx5 + Mxexx + lx2 + 3 屯 + 4 兀 + x = 7XZ<2Aj + x2 + 4 3 + 2x4 + 4g

12、=3作初始单纯形表，并按单纯形表步骤进行迭代.如下:6b5五_23屯-66-6qM71234101.75M32112011.5-10M5-3M-2-3M3-4M-6-6M00M1-30101-21-6】41.510.50.5100.539-M11+3M16-M003M+33130101-2-6兀12.50.501-0.51.5329100M-6M+15因为M是一个很人的正数，此时（7,均为正，所以，得到最优解:/ = （0,0,1,!,/,最优值为/（/） = -3（2）两阶段法首先，构造-个仅含人工变量的新的线性规划如下:mill g(x) = 0 召 + 0 吃 + 0a3 + O.X4

13、+ 土 + 毛*+ 2兀 + 4x4 + 西=7st 2丙+ 壬 + 巧 + 2无 + 斥 =3円,七门二兀，壬no按单纯形法迭代如下:b0vi00屯01兀1q171234101.75139112011.5-10-3-3-4-60011-30101101.510.50.5100.53-140-100301-30101012.50.5010.51.5最优解为:X* = (0,044,0,0),最优值:g(x) = 0因人工变量5 = 46 = 0,则原问题的丛可行解为：F = (0,0丄1,)一进入笫二阶段计算 如下表所示：6Xbb5h兀3屯6313010-6-V412.50.501329100

14、由上表可知，检验数均人于等于0,所以得到最优解：Z = (0,0,1,1,)7 最优值为= -3 o4某糖果厂用原料久B, C加工成三中不同牌号的糖果，甲，乙，丙，己知各种牌号糖果中含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售 价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利鼓大？试建 立这个问题的线性规划数学模型。甲乙丙原料成本（元/千克）毎月限用量（千克）A>60%>15%2.002000B1.502500C<20%<60%<50%1.001200加工费0.500.400.30售价3.402.852.25解：设兀丿= 表

15、示甲、乙、丙中分别含A、B. C的含最，构造此问题的数学规划模型如下:max /i(a) = 09可 +1.42 +1.9.r3 + 0.45 yx + 0.95 j/2 + 1.45 必 一 05q + 0.45r2 + 0.95 二3xx + 必 + 云 <2000 壬+片+彳<2500屯 + 乃+ 6 512000.4打 一0.6才2 -0.6屯 <0M085必一015丿2-015乃>00.2五 + 0.2才2 一 0.8屯 > 00 6必 一 0 6y2 + 0.4y3 > 0 05q+ 0.5二一0.5刁 >0 9儿不0“一 1,2,35求解

16、下列线性规划问题的对偶问题min= 2 州 + 2 才2 + 4 羽2丙+ 3兀+ 5七X 2(1)3可+ “ + 7巧 <3shxx + 4壬 + 6x3 <5丹七书>0max f(x) = 5勺 + 6.r2 + 3 屯+ 2x2 + 2x3 = 5(2) 丙 + 5x> 码 n 3 st4还+ 7七+ 3屯58五无约束,£ no,“3 so解：(1) II表3.7可得该问题的对偶问题为:maxO) = 2必 + 3必 + 5 丿32必+3必+輕2恥0丿2*0(2)该问题的对偶问题为:minO) = 5” + 3y2 + 8乃 工-3此+ 4必=5 2必+

17、5必+ 7必 sh2北一丿2+3丿3 <3无约束，必so,” no6. 用对偶单纯形法求解下列线性规划问题:niin /(a) = 4 斤 +12x2 +18屯x + 3 斗 > 3(1)13才2 + 2屯 >5丙,七*3 no解：(1)首先，将“n”约束条件两边反号，再加入松弛变量，得:niin fx) = 4 坷 +12.r2 +1 8a3 + O.r4 + x5 3 + 斗=3st2兀)2七+才§ = 5丙,兀门3，无，无no建立初始单纯形表如下图所示，所有ay>0o 则对应对偶问题解是可行的，则继续迭代：Cb412180花0屯0310310050卜20

18、14121800计算min-3,-5 = -5 所以屯为换出变疑，0 = mm 6,9 = 6 ,确定七为换入变毘继续迭代，得到如下单纯形表:5b4勺1218屯0L0“50L30卜310040-2.501100.540600min-3 = -3丿4换出,min 4,2 = 2,屯换入 °5b11218冯0科0屯011011r001.51r101r0.5900?6此时，所fla 0,故原问题的最优解为/=0,-,17，最优值为:/+) = 36 2其对偶问题得到最优解为：/=2,67,最优值为：A'*) = 36 o7已知线性规划问题才+才2 +也6先用单纯形法求出最优解，再分

19、别就下列情况进行分析:(1)目标函数中变量丐,七，屯的系数分别在什么范围内变化，问题的最优解不变;(2)两个约束条件的右端分别在什么范围内变化，问题的最优解不变解：将该规划问题化为标准型，引入松弛变量兀山5用单纯形法求解，如下表:CbXbb?-1x>1才30兀0才5q0L11111060V51.5-12001?-11000-V441.5011-0.5-1才22-0.51000.51.50100.5由上表可知，所冇的检验数均大于等于零，得最优解：/ = (0,2,0,4,0)rz所以原问题的 最优解为：/ = (0,2,0,/.最优值/(/) = -2(1)变最丙，“2，“3中，勺&quo

20、t;丫3为非基变最，七为基变量。3X11由5 =亍，当g »-亍时，q+ M »亍，所以，当qw亍,+s),此时最优解不变。由a3 =L当4q 2-1时nq + Aq »0,所以，当勺0,+6),此时最优解不变。°w(-3,1),最优解不变。综上，当qw丄,+s), 6-2 G-4,0, qw0,+s),此时最优解不变。2最优解保持不变。(2) 44的变化范闱 4+-05 020.504 4+1 -05M4+14 >"o"0B2o 0.5 J|_0 j2 0A0得至lj： 4 + M no 二则4的变化范圉是得到：-4<厶

21、<8,则厶的变化范围是0, 12,最优解保持不变。 习题四9用Newton法求解(p(/) = /3-2/+l用第1题求得的区间，按精度f = 0.01计算。解：g) = <p(o)=i,zm + 4)=i,g) = o,% = o,因为火)wg),则A = 4 = 2>0.0LA=4 + Z1=1, 火=22,隹=22,火)5网,反向，因为K=2工0,所以(z=0, b=3 则搜索区间为 t w0,3 00) = 3尸 一 2,0(0 = 6,0(0) = 一2 v 0,0=25 > 0 取：4)= 1，0(G = 1，0(4) = 6,所以 t = i-i =o/=

22、4)-=竺，则卜4)1 = >0.01,令心=,贝Ijm0.8165, 0(4) 60 1 1 60 60匕一引=0.0005 V0.01，所以工=0.817、0 =(p(t J 兀一0.088。4 用黄金分割法求解min (p(f) = /(/+2)已知初始单谷区间釦b=-3, 5,按精度£ = 0.001计算。解:4 =-3 + 0.382x8 = 0.056,A = -3 + 5-0.056 = 1.944 ,(X4)= 0.115136,<p(A) = 7.667136，因为g)<g)，则新的搜索区间为卜3, 1.944：A=4= 0.056,也)=0.11

23、5136,4 = -1 11392,<p(/；) = -0.987592 ,|幼>£,继续迭代，因为仅G>仅右)，则新的搜索区间为卜3, 0.056：4 = -1.832608,仅4)= -0.306764,A = -1.111392,(p(A) = -0.987592,|仆却>£,继续迭代，因为仅厶)> 仅勺，所以新的搜索区间为-1.832608, 0.056：4 = -1.111292,(/)(4)= -0.987592,A = -0.665448g) = -0.888075,|<-/2|>,继续，<p(4)><

24、;p(A)> 所以新的搜索区间为-1.832608, -0.665448:4 = -1.386753，仅/J) = -0.854402,A = -1.111392,仅右)=-0.987592 ,K-引£,继续，因为仅。0©)，所以新的搜索区间为-1.386753, -0.665448A = -0.940987,仅色)=0.996518占=一 1.111392,g) = -0.987592,R-幼£,继续，因为0(G仅勺，所以新的搜索区间为-1.111392, -0.665448: 4 = -0.940987,仅/J) = -0.996518易=-0.8357

25、99,仅小=-0 973038,h-斗£,继续，因为所以新的搜索区间为卜1.111392, 0835799:A = -0.940987,g) = -0.996518占=一1.006115、仅 Q = -0.999962,|4-幼£,继续，因为g)g),所以新的搜索区间为-1.111392, -0.940987: 4 = -1.046295,仅。=-0.997857,A = -1.006115,仅=-0.999962,|4-引£,继续，因为 g)g),所以新的搜索区间为-1.046295, -0.940987:刍= 0.981215,也)=-0.999647,4 =

26、 -1.006115,必)=-0.999962,|4-引£,继续，因为仅厶) 仅勺，所以新的搜索区间为卜1.046295, 0981215:4 = -1.021434,(/)(4)= -0.999540,A = -1.006115,(p(/3) = -0.999962,山-幼£,继续，因为仅厶) 仅勺，所以新的搜索区间为卜1.021434, 0981215:3 =-0.996579,仅© =-0.999987山= -1.006115,仅4)=-0.999962 ,R-引£,继续，因为 g)g),所以新的搜索区间为-1.006115, -0.981215:

27、4 = -0.996579,仅4)= -0.999987,A = -0.990727,仅勺=-0.999914,山-引£,继续，因为g) (P©，所以新的搜索区间为-1.006115, -0.990727:A = -0.996579,也)=-0.999987,厶=-1.000237,仅右)=-1.00000016,-幼£,继续，因为/(4)P(A)»所以新的搜索区间为-1.006115, -0.996579: t、= -1.000237,(/)(4)= -0.99999364,右=-1.000237,仅右)=-1.00000016,|-A|r,继续，因为

28、卩 仅右)，所以新的搜索区间为-1.002472, -0.9965 79: t2 = -0.998830,仅 Q = -0.999998505,4 = 一1 000237,仅 Q = -1.00000016, K-巧|>£,继续，因为g) < g),新的搜索区间为-1.002472, -0.9988304 = -1.001081,(/)(4)= 0.999999075,右=-1.000237,(/>(/2) = -1.00000016, 因为£-勺<£，停止迭代。所以：F =上兰=-1.000659, (p = W) = -0.999999

29、9565。25 用抛物线插值法求解niin - 8.V3 一 2, - 7x+ 3已知初始单谷区间, b=p>, 2, 8 = -0.001 o解：4 = 0,牛 2,取 4)=1, 7 « 0.5227, |4)-F| > ej <4),<p(7) = -0.063 < <p(4) = 2 新搜索区间为0, 1, 4 =0心=1虫".5227, 7«0.5704,|4)-?|>,/>4), (p(F) = -0.1588 < <p(4) = -0.063 ,所以,新的搜索区间为0.5227, 1,4 =

30、0.5227,A =1,4)« 0.5704, 7« 0.6146,-?|> ,7 > 4>,<p(7) = -0.2004 < 仅心)=-0.1588所以，新的搜索区间为：0.5704 1,=0.5704/, =1,4)« 0.6146, 7 « 06232,|4)-7| > Ej > 4),<p(F) = -0.2029 <= -0.2004 ,所以新的搜索区间为：0.6146, 1.4 = 0.6146,刍=1，4)« 0.6232, 7 « 0.6260,|心-?|>

31、 ,7 > 尙,(p(f) = -0.2032 <(p(4) = -0.2029 ,新的搜索区间为：0.6232, 1, <= 0.6232,/； =1,4 «0.6260, ? a0.6284,0-可>£了>给,仅7) = -0.2034 <帙4) =-0.2032新的搜索区间为0.6260, 1,厶=0.6260心=1,心 ”0.6284, 了0.6276,|4)一习<£,.产是仅0在区间上的近似最优解，/ =7=0.6276,(P =(/>(/*) = -0.2034 o习题五九用最速下降法求解 min/()

32、= x12 + 25x22, .=2»2r>= 0.01.1、解：y/%r) = %50幼2 0 0 50_耳=W)= 4,100f ,|>0|= 100.07997 代一聽討;卜。吨 /()=3.68655 = 7) = (3 83976-0 15f,1 91988'_-0 003阈>£ 同理继续迭代，最后至"即此时最优解"冒，/&)"2用Newton法求解4 iri 91988100j-0.003kll>e3 8976- 048089min /a) = 60- 10.斤-4x2 + 彳 + xj-旺勺

33、 初始点砧=0. 07, Z0.01.W：gW = Y 厂W = -10 + lxl-x2,-4 + lx2-xlf132323*)=2=>*)】=:3132亍%) = 0,0 网五)卜 0 50.01最优解为f = 8,6/(/) = 8-10= 6f3用修正Newton法求解miny(x) = 4(五 +1F + 2(x2-l)2 + xx + 眄+10,初始点州=0, 07,C = 0.01.解:gG) = YA O = 8工1 + 9,4七 _ 37 五=s + Vo =*)=0 1,0(丫宀4则A = -久丫尸8（忑）=1.49一3&（5）= 9，-3孑一雳令石=忑+抽

34、0 =99 “99/(X1) = l?r_Tz+16z=1W,/（丫）最小9 3 rr"广一厂丁，Wi)= o,of, o 4 r 93-7 /V *157“ =hi7 ,/(x) = lT|Wi)|=o<o.oi4用共純梯度法求解min（V + 4.rf）,取初始点兀=1，1门6： = 0.01.6868解：令/W =彳 + 4亿7/©) = 2.<p842Z,必二-Y/ts) = -2,87+ 4)令min(l- 2心) + 4(1 - 8心)=niin(p(f),则(p(/)= 520心 一 68 = 0 二 = 0.130969 dt比=0.738062

35、,-0047752 V/) = 1.476124,-0382016768682.324878« 0.03418968新搜索方向为p =+-1.476124"+ 0.034189 -2-1.544502"0.382016-80.108504因此有七=丙 + 5 = 0.738062 1.5445024,-0.047752 + 0.1085044d由一/(円 + 個)=0=>4 « 0.477127dt因而得下一迭代点吃=石+厶刃=0.738062+ 0.477127-0.047752-1.5445020.108504= 0.00,0.007|W2)|

36、 = 0 S0.01 停止迭代，. + = 0,07,/) = 05用共純梯度法求解minAv） = 2Y + V-rp2,门定初始点，£ = 0.01.解：V/(x) = 4 - x2,lx2 - Ai7,取初始点 =o,l7, p0 = -1,-27=1" -2 =Zo,12/o7令 min2 石 + (1 _ 2)' _ 心(1 _ 2心)=min(p(f)则W6 = 16心一 5 = 0 = 4)= 0.125 at:.丙=0.3125厂0.375门 丫/召)=0.875,0.4375o _11)|3. l|Wo)|f=0 95703125 « 0

37、.1914065新搜索方向为门=-丫/円）+也）'-0.875 '+ 0.191406 1=-0.683594'-0.4375-2 -0.82012 因而得下一迭代点驻=才+21 = -0.3125-0.68359铭,0.375-0.8203124由+個)= 0=4 = 0.456927 , dt则七= 0.000,0.OOOf, V/(x2) = 0,07,|V4)|=0<0.01 停止迭代则扌二七=0,0广，综上所述，原问题的最优解Z = 0,0f,最优值为/Z)= o6用 DFP 法求解 min 丿©) = 4(石-5)2 + (才2-6尸，初始=

38、 8 , e = 0.01.6、解：取厶八°£g(jr)=蜩 _40,2 羽 _12了则搜索方向 / = -0.28017,4.48248则搜索方向 / = -0.28017,4.482489.8499324625(f, 仓仓，=2.462500.61563:、H0.123080.030770.030770.00770-0.99611 0.062260.06226 0.003900.12697-0.03149 0.031491.0038A0 = 8,19f,0 = 24,6f第一步迭代得： 込=4.86154,8.21538：© = -1.10768,4.4307

39、6?用 DFP 法第二次迭代： = -0 = -3.13846,-0.784627o=i-o = -25.10768,-1.569247HqJo Jo -oJb因：必久= 80.03071, VoJb=V>b = 632.858119.84993 2.462502.46250 0.61563则搜索方向 / = -0.28017,4.48248从丙出发沿力进行直线搜索，即:五二可 + 01 = 4.86154 - 0.28017/,8.21538 + 4.48248小山空金+勿)=0,得/=-0.48674dt所以也=内+如a5.000,6.000$, ill于&(七)=0,07,

40、所以吃=5,6卩是极小 点。习题六九用外点罚函数法求解:niin f(x)=五 + 才20(*)= -彳 +勺 nog2(a) = 4i >0解：利用外点罚函数法构造增广目标函数.如下:冲也“）=0+花+"【（-彳+兀）2+彳】（虫®, 1勺 + 壬（丫 61J_、2+ 2“4(1 +“)，2“对于ZD的悄况:rti = o,- = o 得：x*(ji)= dxl dx2当“一+ s 时，/仏）（0、0） 即：Z = (o,o),且/(Z) = o2用外点罚函数法求解:St g(.Y)= 1 _ 五 50解：构造增广冃标函数:对于2D的情况:得：2 円2 “（1 勺）

41、=02x2 = 0推出:“ 一> +S 时 9 X （J.L）> （1,0）O即：Z = （l,0）4用内点罚函数法求解:min /.v）= 一 （无 +1）3 + 七 自（力=西-1»0 2（r）= "St解：利用内点罚函数法构造如下增广H标函数:（心2）=：（丙+1）3 + 才2 + /（兀&0小 2得：，（»）=（J14历，历）=0当 70+时，/（才T（l,0）Q.Z=（i,o）, Av*）=-5用内点罚函数法求解:解法同上。习题七 九用动态规划求解：maxg=无兀st (西+七+可54' U>0 (z = 1,2,3)解

42、:将原问题表示为:max E =p/j + "2 + "3 < 4 U>0(/ = 1,2,3)山此，确圧状态变量为：内,七，兀3，决策变量为： 状态转移方程：丙= "1； K = 2 +还；.r3 = u3 + x> <4 0用动态规划的思想顺推，如下:第一步.?=1:XC'i) = max<zzi)= * 且；=円 °第二步，?=2:ZCV2）= max% X（xi）=max2 XCV2 u2） 00勺 S.q= max2 （x? - " OS/）-1!令：</X/2）=/2 -（X> -“

43、2），由卩匕）二°，得® = -22. &（兀,）=max0,丄£,0=44第三步，?=3:Z（r3）= max佃 ZCr2）os竹冬巧= max；Z（x3-3）= max；+（x3-3）'o<<jj q同理,令:曲3）詔丄（屯-冷尸，4rhp絹）=°尿）5双0,右易0=右对冏号<4* &（*3）= 77乂4° = 464将Z（3）= 4代入上述表达式逆序递推求出:= 4, 3 =2,兀）=2，*）= 1,召=1, /j =1.*.新问题的最优解为：u - （1丄2）,戌（"*） = 4原问题

44、的最优解为:Z = （1,1,2> W） = 4.2设有5个城市，编号从丄到5,记第，个城市与第丿个城市的距离为冷，记:06522600.557D=(4)5x5 =50.50152510327530试分别用函数迭代法和策略迭代法求出各城市到第5个城市的最短距离。解：法一，函数迭代法：上=10寸，久0)=比(/ = 1,2,3,4,5)x(l) = 2,久(2) = 7,久(3) = 5,久=3,久(5) = 0.k = 2 时，应)=min©+ZV)卜0</<5/=niin0 + 2,6 + 7,5 + 5,2 + 3,2 + 0=2M(l),&(2) =

45、niin6 + 2,0 + 7,0.5 + 5,5 + 3,7 + 0=5. 5 丰 yf(2), Z(3) = min5 + 2,0.5+ 7,0 + 5,1 + 3,5 + 0二4 工片, /(4) = niin2 + 2,5 + 7,1 + 5,0 + 3,3 + 0二 3 = /(4), Z=0 =久(5).对于所有厶并不满足E0)=久，故须继续迭代。八涮，Z0 = min他 + &(/)，0</<5&=iiiin0 + 2,6 + 5.5,5 + 4,2+ 3,2 + 0尸2 坯(1),&(2) = niin6 + 2,0 + 5.5,0.5 + 4,5 + 3,7 + 0=4. 5 丰工(2), &(3) = min5 + 2,0.5 + 5.5,0 + 4,1 + 3,5 +