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

1、最优化方法部分课后习题解答习题一1.直优化问题的数学模型为：min/(A)= (-3)2 + (x2- 4)2&Q)二忑 2 0试用图解法求出：(1)无约束最优点，并求出最优值(2 )约束最优点，并求出其最优值。(3 )如果加一个等式约束MR二/ -忑二0 .其约束最优解是什么？解：(1)在无约束条件下，/(.I)的可行域在整个0也平面上，不难看出，当(*3，4) 时，/(»取最小值，即，最优点为f = ( 3 » 4 ):且最优值为：f(X)=0 (2)在约束条件下，的可行域为图中阴影部分所示，此时，求该问题的最优点就是在约束集合即可行域中找一点(*,忑)，使其落

2、在半径最小的同心圜上.显然，从图示中可 以看出，当£ =(号，寸)时，/(»所在的圆的半径最小。其中：点为&(»和於(的交点 > 令求解得到:14即最优点为f = (y,|):最优值为：/(A?)=6(3 ).若増加一个等式约束，则由图可知，可行域为空集，即此时最优解不存在。2.个矩形无盖油箱的外部总面积限定为S，怎样设计可使油箱的容量最大？试列出这个优 化问题的数学模型，并回答这属于几维的优化问题.解：列出这个优化问题的数学模型为:max/(a)=忑忑该优化问题属于三维的优化问题。习题二3计算一般二次函数/(»扌XM¥ + X

3、+ c的梯度。解：设：A二 打”上二(b#，2.b)：,X二(AX,.xy 则bx + c »将它对变量的球偏导数得:Hr2户i勿V/(A)= |il=_+it11 I:辿L ” 訂霸+Lz户1aS2 i.2 .I lb Il3j5求下列函数的梯度和Hesse矩阵|'2 0 屮(1)2x2 / 3x2 3 4xx i3 解：V2/(. = 'o 4 0 ''-4 0 6：(2)=3.2+0、解w(沪费眶+占+叶；| 13 12 13 11 26v +严七6x+x若6判断下列函数是凸函数，凹函数，还是既不凸也不凹函数：(1) /(XX-X2 fix2 3

4、xx 1 2 解：V7W不是半正定，即/W非凸，然后判断，经验证：V2(-/(a)不是半 正定，由此可知：/(»非凸非凹。(2 ) /(x1xX= 2,v2 p4.vx j+3x2 x -6j解：v2/(a)半正定，故/(»为凸因数。(3 )= 4 2 + 2忑 2 -3月 2 _ 4幸解：v3/«不是半正定，即/Q)非凸，然后判断-/(»，经验证：v3(-/W)不是半 正定，由此可知：/(»非凸非凹。7设约束优化问题的数学模型为：niin/(» = F+ 4.v x2 2 4x +10&(R 二禺+2 2 0 文 I-

5、87;->lg的二卞厂0亍2"3 >9试用KT条件判别点X二卜1,1'是否为最优点。解：对于点x= -u7 » gG)=o，g(»o >点满足约束条件，故点x是可行解。且&(助是起作用约束 I-1,=4 ，由V&Q)2 0条件下的KT条件得：W - W = 0 > 0 ,得到入=2 .点x=-l,l '满足KT条 «/件。又因V7W正定，故/(»为严格凸函数，该最优化问题是凸规划问题，由x =-1,17是KT点，所以x =-14也是该问题的全局最优点。8设约束优化问题：min/(A)=(A

6、-?2)2+x22|1&(力=*0J P Q)= -牙 * |lSW = -l + xf+x2<0它的当前迭代点为x,= l,0f .试用KT条件判定它是不是约束最优解。解：对于点母二1,0丫 gG)二T S0,g (x)二,g(x)亍0衣'点x = l,py是可行点'且起作用的约束条件是 > &W，g(A)> / = 2,3,Vf() = |2| » Vg2() = /°'°) r 亠亠 亠 可3(切二y 由约束条件为&(»< °时的k.t条件得应有： V/a)+工爭&a

7、mp;(» 二 0,壮 0 解得： ' "，所以X = l,or 为 K-T 点。现判断该问题是否为凸规划问题，因沪代9正定，故/(R为凸函数，g (心gQ)內线性函数，亦为凸函数，v2g(人)書正定，所以g(»为凸函数，所以该优化问题为凸 规划间题，即点无二1,0丫是该问题矗勺束最优解习题三1. 对于下列线性规划问题找出所有基解，指出哪些是基可行解，并确定出最优解。max /(a) = 3q + 忑 + 2月+3勺+6.§+月=9(1)百+ 忑+ 2马=103- 电二0Jp 0,(j= 1,2.6)12 3 6 3 0 0解:令4= |81 -

8、4 0 2 0 二 阴，&切3 0 0 0 0 -1(1) 基解x产(01分7計0,0)不是基可行解，(2) 基解忑二(0,10,0,7,0,0)不是基可行解，(3 )基解勺=(0,3,0,03.5,0)是基可行解，且/(a) = 3，(4 )基解五=(#-4,0,0,0,手)不是基可行解»(5 )基解马=(0,0,-舟,8,0,0)不是基可行解，(6 )基解x6- (0,0,3tO,16,0)是基可行解，且= 3 »(7 )基解心二(10,- 1鸟0,3)不是基可行解，2(8)基解氐=(0,0,03,5,0)是基可行解，且/(a) = 0 »(9)(10

9、)(11)(12)基解%9=(50,0,-2,0?-不是基可行解。基解也=(f 0,0,0,4, $是基可行解，且/(» =丄444基解无二(0, y- 3o,O,O)不是基可行解。36基解七二(010,0,-7,0,0)不是基可行解。(13)基解= (03,0,0, ,3 是基可行解，且 f(.x) = 3 2(14 )基解x J (0,0,",8,0,0)不是基可行解。2(15 )基解m二(0.0,'寸),8,0)是基可行解»且fQ = 3。(16 )基解*6 = (0,0,0350)是基可行解 > 且 /(a) = 3。2. 用单纯形法求解下列

10、线性规划问题：max /(a) =10. + 5忑(1)戸+仆9si ;5 + 2x2< 8> 0解：将现行规划问题化为标准形式如下：min(-/(A) = -IO4 - 5禺 + 0召 + 0不 円+空+召=9st 5 4 + 2.r2+x 4= 8呂,.> 0作初始单纯形表，并按单纯形表步骤进行迭代，如下：qXbb-105X,0号0曲0109341030852011.60-10-5000s4.202-81-0.61.5-101.610.400.24160-10-51.501514314-10110172717.5005142514比时，o岁为正，目标函数已不能再减小，于是

11、得到最优解为：x = (1?0,0) 目标函数值为：/(.V) = 17.53. 分别用单纯形法中的大M法和两阶段法求解下列线性规划问题:mill f© 二 - 2忑 + 3月 _ 6忑 (1)卜+2心+3.丫扌4x亍74 +召+ 2不二3 L，忑,®忑2 0解：(1 )大M法：把原间题化为标准形式，并加入人工变量如下：niin /(a) =- 2忑 + 3$ - 6. + 咙 + 唯 + 2忑+ 3月+ 4忑+忑二7Jgx fx x +?兀 + # 二2“,林,却 0作初始单纯形表，并按单纯形表步骤进行迭代，如下：Xrb5孑3勺-66-6qMX571?34101.75MX

12、632112011.5-10M5-3M-2-3M3-4M-6-6M00M*1-30101161.510.50.5100.539-M11+3M16-M003M+331-30101-612.50.501-0.51.5329100M-6M+15因为M是一个很大的正数 此时q均为正 所以，得到最优解：a?= (O,O,Ll)r »最优值为/(X)= -3(2)两阶段法首先 构造一个仅含入工变量的新的线性规划如下:min酌= 0j + 0忑+ 0号+ 0易+忑+忑千+ 2勺+ 3召+ 4壬+马=7f X +?x + # 二；心忑，毎，易, 0按单纯形法迭代如下：Xrb00x>00忑1托1

13、片ei171934101.75132112011.5-10-3-3-4-60011-30101101.510.50.5100.53-140-100301-30101012.50.501-0.51.5最优解为:X = (O,O,L1,0,0) 最优值:酌二0因人工变量芒二忑=0 .则原问题的基可行解为：x*=(0,0,Ll,)J进入第二阶段计算如下表所示：Xbh5-9Xy3S63s1-3010612.50.501329100由上表可知，检验数均大于等于0，所以得到最优解：x = (0,0,1,L)r 最优值为/(/) = -3 °4某糖果厂用原料A，B，C加工成三中不同牌号的糖果，甲，

14、乙，丙，已知各种牌号糖果中A,B,C含量，原料成本，各种原料的每月限用量，三中牌号糖果的单位加工费及售价如下表所示，问该厂每月应生产这三种牌号糖果各多少千克，使该厂获利最大？试建 立这个问题的线性规划数学模型。甲乙丙原料成本（元/千克）每月限用星（千克）A>60%>15%2.002000B1.502500C<20%<60%<50%1.001200加工费0.500.400.30售价3.402.852.25解：设斗,”碇叮=1,2,3表示甲、乙、丙中分别含A、B、C的含量，构造此问题的数学规划模型如下：max /(a) = 0.9. +1.4忑 +1.9忑 + 0.4

15、5、+ 0.95为 +1.45 滋-0.5 +0.45色 + 0.95召 y & < 2000勺 + % + & < 2500+ + <12000.4 -0.6 -0.6号 < 0文"f.85y 亍0.15y -0.15y >30Q.ZxQ.lx fO.Sx 彳 00.6川 一 0.6月 +0.4号 > 00.5& +0.5 一0.5召 > 0沙"1,2,35求解下列线性规划问题的对偶问题min =2勺 +2忑 +4月2千+3 忑+5§2 2(1) | 打+"7x$3 siq + 4忑 +

16、 6 月 < 5|不恥> 0max /(» =5jj + 6 忑 + 3$ 勺+ 2忑+ 2月=5 -齐+5忑一月23 4千+7忑+3勺<5 x无约束,乳玄(U 00(2)解：(1 )由表37可得该问题的对偶问题为：max() = 2)i+3v>+52)i+3乂+以2申+$+4彤25为+7月+6泸4(2)该问题的对偶问题为：minMM = 5)j+3K + 8为必-3月+4站5 剛+5月+7胖6|2)力+3以3|y无约束,y2<0,y 36-用对偶单纯形法求解下列线性规划问题:min = 4千 +12 忑 +18月(1)1+3>3st 2Xy +

17、2. > 5解：(1 )首先，将 约束条件两边反号，再加入松弛变量 > 得:mill fQ = 4丫 +12忑 +18g + 0 忑 + 忑|一齐_3号+忑二3口 -2勺-2x3+x5= -51$心心斗4'0建立初始单纯形表如下图所示 > 所有巧2 0。则对应对偶问题解是可行的 > 则继续迭代:qb412勺180不0冯0-310-310050卜2014121800计算min-3, 5 = 5 '所以奪为换出变量0 = min6,9 = 6 '确定勺为换入变豊继 续迭代，得到如下单纯形表：qXBb41218S0无00310卜3100Xi-2.501

18、100.540600min-3=3,忑换出min(4 i = 2 马换入°qXbb441218S00V011011001.511010.5?00946此时，所有0,>0，故原问题的最优解为x二0, -a 已知线性规划问题niin /(。=2. _ 忑 + 月低+屮吓6文 -x f 2.v $ 4 孑必，忑2 0先用单纯形法求出最优解，再分别就下列情况进行分析：(1)目标函数中变量.,忑,召的系数分别在什么范围内变化，问题的最优解不变；(2 )两个约束条件的右端分别在什么范围内变化，问题的最优解不变。解：将该规划问题化为标准型，引入松弛变量忑,§mill /(a) =

19、2. 一忑 + 月 + 0 ( + 0蚣，产+忑+月+忑=6口| -+2x?+x 亍4* X，忑，忑，壬眄2 0；®优值为：/(町二36 2其对偶问题得到最优解为：£二2,6' >最优值为：/(f) =36。用单纯形法求解 > 如下表：b9-11S0忑0马0i011111060电1.5-120012?-1100041.5011-0.5-12-0.51000.51.5()100.5由上表可知 > 所有的检验数均大于等于零 > 得最优解：f二(02X0)：所以原问题的最优解为：x = (020,)7 >最优值/(x) = -2(1 )变量4

20、 >忑1忑中1 4 1 、为非基变量1忑为基变量°3 31由 °i = ，当&-护寸 c j= c Ac亠所以，当c ql ,亠8),此时餵优解不变°2 2由。3 =1 1当Aq > -1时q =q + Zkq > 0 >所以»当q wO,+8),此时最优解不变。&匹(-3,1)，最优解不变。综上，当 qe-,+w)» c2e-4,0 > c3e0,+w),此时最仇解不变。2(2)仙的变化范围-0.5 仙1 'i 0 0.501b丄 1“皿TW 10*2得到：4 + A/pO = A/p -

21、4 >则/?的变化范围是/?> 2 >最优解保持不变歹b+歹°1 卩 _0-51 r° 1 L°® r°i=+=+A/? >LMJ LO 0.5得到:-4<A/a<8 >则包的变化范围是0,12，最优解保持不变习题四3用Newton法求解(X0 = p -2f+l用第1题求得的区间，按精度£ = 0.01计算。解:<X6)=<K0)二M 二6+4 =i,<X) = o,<h 二o,因为<K()他) > 则巾 *=2A =(+/ =1 > 帼)二 22,

22、轴=22,<K0 s帼)'反向 1 因为 K=2 H0,所以 o=0 » b=3则捜索区间为t e0,3<t>'(0 =3r -2，b(D = 6,0(0) = -2 <O,*'(3) =25 >0 取:）齐，所以 t 二1| 4 o o o01，继续迭代t=4 5 -，6ii49> 0.01,令 tn 1 则件 0.8165 »6060|/-()| 二 0.0005 < 0.0诵以十二 0.817.E 二讽门=-0.088。4 = -1.386753,啊)=-0.854402,A = -1.111392,(

23、X9 = -0.987592，|(-t> |>&继续，因为側)>牠)，所以新的搜索区间为-1.386753，-0.665448A = -0.940987,艳)=-0.996518,( = 7.111392,啊)=-0.987592 >，-A |>&继续，因为帕)>艳)，所以新的搜索区间为-1 111392，-0.665448:4 = -0.940987,(X0 = -0.996518,A = -0.835799,<X0 = -0.973038，|>&继续，因为g()>惟)，所以新的搜索区间为卜1.111392，.0.

24、835799：A = -0.940987,(X0 = -0.996518,( = -l.OO6115,4>() = -0.999962，|>&继续，因为帕)>惟)> 所以新的搜索区间为-1.111392 » O940987：(=-1.046295,4)(0 = -0.997857,A = -1.006115,()(9 = -0.999962，|(|>&继续，因为哄()>弛)，所以新的搜索区间为卜1.046295 . -0.940987:A = -0.981215,= -0.999647, = -1.006115.()(0 = -0.

25、999962 »»|(|>&继续，因为帕)>弛)，所以新的搜索区间为-1.046295 . -0.981215:=-1.021434,<X0 = -0.999540,A = -1.006115,牠)=-0.999962 >.|( -A |>&继续，因为忸)> 弛)，所以新的搜索区间为-1.021434 . -0.981215:g =0.996579,(Xg) = -0.999987,( = -1.0061150() = -0.999962，|( -A |>&继续，因为忸)>弛)，所以新的搜索区间>

26、9(-1.006115 . -0.981215:(=-0.996579,(|)() = -0.999987,A = -0.990727,牠)=-0.999914 > -/> |>&继续，因为<K)<(XA) »所以新的搜索区间为卜1.006115，-0.990727:A = -0.996579,(X0 = -0.999987,( = -1.000237,恤)=-1.00000016 >. -/> |>&继续，因为帕)<報)，所以新的搜索区间为卜1.006115，-0.996579:(=-1.000237,0(0 =

27、 -0.99999364,A = -1.000237,*) = -1.00000016 »> -/> |>&继续，因为 <K)>(X)，所以新的搜索区间为-1.002472 . -0.996579:A = -0.998830,(X0 = -0.999998505,( = -1.000237,<X() = -1.00000016，|(-tj |>&继续，因为(X)<<XA)，新的搜索区间为-1.002472 > -0.9988304 = -1.001081,(X0 = -0.999999075,A = -1.0

28、00237,(X9 = -100000016， 因为|(-'停止迭代。所以：t 二匕鼻-1.000659,$ =<K/) =-0.9999999565 25 用抛物线拯值法求解niin fQ = 8a3 - 2r - 7x+ 3已知初始单谷区间a，b=0 . 2，£= -0.001。解：$ 二0仏二 2,取 6 二1，I =0.5227 t 一|>& 几6，帕)三一 °°63<(X6)二 2 新搜索区间为0 » 1 » < = 0,A 二 1,6 =0.5227 > t = 0.5704,一|>

29、;&厂>(),<KI= -0.1588 <<X0 = -0.063，所以.新的搜索区间为0.5227，1，4 = 0.5227,A =1,6 =0.5704 > 十 0.6146, (J- / 一| >&C (),(Xf)三一0.2004 <哄6)二 一0.1588所以 > 新的搜索区间为:0.5704 . 1 » < =0.5704詛=1,(, =0.6146 > t =06232,|6-厂|>&C6，W)三一°2029 <(|)(6)二-0.2004，所以新的搜索区间为:0.

30、6146-1>4 二 0.6146仏=1,(, =0.6232 » t 三0.6260,6 ” _| >£,/>(),<XJ= -0.2032 <(X0 = -0.2029，新的搜索区间为:0.6232，1，( =0.6232,A =1, = 0.6260，戶 0.6284, &-f 一| >匕呎。三-0.2034 <(Xb) = -0.2032 新的搜索区间为0.6260 . 1 . 4 二 0.6260仏=1,(, =0.6284 > t 三0.6276, |,-r|<£ .在区间上的近似最优解*二

31、厂二0.6276，(t>* =<XO - -0.2034 习题五1用最速下降法求解min/(R =坊+25疋？ x 0 =2 27 > £ = 0.01.1、解：W = ,50 &=) = 4,100 7,|&| = 100 07997r">-4 11 91988'-0 02003 -=ioojI-0.003您=3.68655389760 15 0 07348-0 06913.卩 5988卜 0 48089I-0 003J/(再)=0 124872同理继续迭代，最后至V。«=W = 3 83976-0 15 :|g

32、|>8此时最优解“用，f（s）- 02用Newton法求解niin= 60-10. - 4 +2 + . 2 -x. » 初始点五=0，0 7 » £=0.01.解：g.i) = V/*(a)二10 + 2x p,-g + 2x !f2 12 -nL _刚二=>%宀3 31-1 211 2怙32 1' , roi h 一 r-ioi=>才产雪GW壇C 'r|3 |3 I |=8.6fL°J |12|L 4 J3 3W=0,0 I|恥)| = o <0.01最优解为 x =8,6f,f(x) = 8 3用修正Newt

33、on法求解min /(a) = < +1) 12(. -1)打+勺 + 10，初始点弔=0 > 0 »7£ = 0.01.解：X a) = W) = 89,4-3r-s=+u =6( a) =°1 > 31f0 41'.0I4则p二-Q.旷曲）二0 018令4二弔+矶=|W) II二 0< 0.01/(a)=勒-列/#6 = / = 1 时最<1' vi= - »f Vf(J)r0,0, o 44专旳(小】备4用共觇梯度法求解niinCxf +4x；) >取初始点x0 =1 > I7 > &

34、#163; = 0.01. 解：/(A)二卄4r,y/(.) = 2x,8订 HP 0 = -WUJ =计2,町fll 2 rir仃屮矶=1护I叫令min(l - 2£) 3 +4(1 - 8Q = niin(|)(0 >= 0.130969心二0.738062,-0.047752/ > 欧工人二1 476124,-0.382016J7|V/(.S) |f = 2324878 =o Q34i89 iiw)ir新搜索方向为-1.4761241-2-1.544502"I +0.034189=0.382016卜80.108504因此有忑=* + /p 打0.73806

35、2-1.544502(辽0047752+0.108504/；由纟©扛刃亍0 = / = P.477127dt因而得下一迭代点勺=4+(" = |严严 10 477127110.0477521 J宀沁。2°0.108504 1 J阿G)| = owooi停止迭代0期7(巧二0 5用共觇梯度法求解min /(a) = lx2x23xx彳目定初始点 £ = 0.01.解：V/Q 二你-呂,2呂-打 T '取初始点不二o,l' PQ= -V/(x)b= -l,-2f0. *1=+U = |6 | L_2 =<)4-2令 min2略 + Q

36、- 2/-£Q - 2Q = ming=16/ -q5 =0/ =00.125.= 0.3125,-0.375f > W)r 0 875,0.4375f新搜索方向为a = 一7/()+入/j-0.875+ 0.191406 1-0.4375卜2-0.683594-0.82012因而得下一迭代点勺二卯 + /p 卜0.3125 - 0.683594/ £.375 - 0.820312/ f 】 由 4/(x ftp)亍 0 =t = p.456927，dt则心二0.000,0.000/ ' w )2= 0,0f, |V/a)11 = 0 < 0.01 停止

37、迭代则亡.厅°，0丁，综上所述，原问题的最优解V =0,07，最优值为/(f) = 06用 DFP法求解min/(j) = 4( xx5 j2 +(x<6)2，初始点r8 » »e = 0.01.6、解：取弘二 /,人=,曲)二&丫 -40,2忑-12 T=8,19r,S=24,6r第一步迭代得: 二4.86154,8.21538，&二-1.10768,4.43076用 DFP 法第二次迭代：50=xr.v 亍-3.13846,0.78462yQ=grS 亍-25.10768,-1.569247riiii o - lj 1 Jd _ Hddo

38、/ o则HHo+ 7U'因：=80.03071,比验嘗 7” =632.85811r 9.849932.46250' r _ 9.849932.46250'% °一(2 462500.61563.' 一 '2.46250 0.61563J.Hi = I0r0996110.06226"0.062260.003900.12697- 0.03149-0.031491.0038 012308 0.030770.030770.00770则搜索方向 H = 一“& =-0.28017,448248从Aj出发沿H进行直线搜索，即：“+“ =

39、 4.86154-0.2801748.21538 + 4.48248/由 fp） f 0 - §/= -0.48674所以勺二 X+“ =|5.000,6.0007> 由于厲丫二0,0F» 所以x2=5,6f 是极小点。习题六1用外点罚函数法求解：解：利用外点罚函数法构造増广目标函数 > 如下：尸（3）=k +? +丄（"1+打 +" h XO K + 占（XG D）对于x年£>的情况： 1 _ 1 2+ 2卩 4（1 + 0 2 丽当 pT +8 时，f （p） T（0.0）即：f 二（0,0），且/（/） =02用外点罚函

40、数法求解：niin/（A）= f+ Y尸(3) =1£+毘+呗7）；五+才2(联D(.ve D对于x年D的情况：解：构造増广目标函数：由2齐-2如-。二021 =0得：推出：x (g) = ',o(1 +卩当 g> +00 时，Z(g) > (1,0)° 即：f 二(1,0)且 /(/) =1。4用内点罚函数法求解:解：利用内点罚函数法构造如下増广目标函数:得:x(x) = ( #+盯aT当T0 +时，gTQ,0)x*乙(1,0) » /(/)= -min /(a) = 1于 I)3 + .V5用内点罚函数法求解：niin-(x1 + l)3

41、+x12 0>0习题七1用动态规划求解：max E =3口卜+忑+咔4k >0(/= 1,2,3)解:将原问题表示为:maxE=uq«4 3M +u>< 4耳 >0（匸 1,2,3）由此»确定状态变量为：»决策变量为：",冷站状态转移方程:二M；忑=地+；忑二均+忑§4 °用动态规划的思想顺推 > 如下： 第一步» k = l :人=max®】=几1且i： i “。zlsl第二步> k二2:尿)二 maxEd)二 maxW'/Q -色)二 maxW'Q =)

42、0轲 £、令：<Kn )=W2 lt2)' 由0 0 2 )=°，得 = -22/2() = max0 扌氐 0 = $ $ Si 3= j 2第三步，k=3:f©= maxOG71-v)=max心/a ") g,巧同理 > 令：喲円卩/予亏"由1> 3)= °'得二y-V3二 fix) = max0 士塔，0二Si3 = * 364042：X3<4心）=将ZG）二4代入上述表达式 > 逆序递推求出： 勺=4,iZ f 2 x2 = 2,« -r 1 »xx = l,z

43、Z1 = 1. 新问题的最优解为:/二Q,L2)，W) = 4 原问题的最优解为：x二(14,2)，耳G)二4.2设有5个城市，编号从1到5，记第/个城市与第j个城市的距离为4，记：065221600.5 570.5 01 5I>25103275301试分别用函数迭代法和策略迭代法求出各城市到第5个城市的最短距离解：法一，函数迭代法：R = 1时/(/) =(/ = 1,2,3,4,5)Jf(l) = 2,jf =7, jf(3) = 5,/(4) = 3,朕5) = 0.“2时为(XminM + e)，OS矣5£(1)二 niin0 + 2,6 + 7,5 + 5,2 + 3

44、,2 + 0=2#Q),£(2) = niin6 + 2,0 + 7,0.5 + 5,5 + 3,7 + 0=5.5 t jf(2), J§(3) = niin5 + 2,0.5 + 7,0 + 5,1 + 3,5 + 0=4 H jf(3), £(4) = niin2 + 吊 + 7,1 +5,0 +3,3 +0二 3 =jf(4), 朋)=0 = jf(5).对于所有/并不满足£0 =.(0，故须继续迭代。"3时幣(D 二minWHU)，ZQ) = min0 + 2,6 + 5.5,5 +4,2+3,2 + 0=2=j(l),£(

45、2) = niin6 + 2.0 + 5.5,0.5 + 停 + 3,7 + 0二4.5 H/(2),Z(3) = niin5 + 2.0.5 + 5.5,0 + 4,1+ 3,5 + 0=4 = £(3), £(4) = min2 + 2d + 5.5,1 + 4,0 + 3,3 十 0=3 = £(4), 0) = 0 =(5).对于0)并不满足£(»二故须继续迭代。Os卫5J$(l) = niin0 + 2,6 + 4.5,5 + 4,2 + 戈2 +0二2巧(1),/(2) = niin6 + 2,0 + 45,0.5 + 45 + 3,7 + 0=4.5 二 £(2), k(3) = niin5 + 2,0.5 + 4.5,0 + 4,1+ 3,5 十 0=4 =£(3),/(4) = min2 + 吊 + 4.5,1 + 4,0 + 3,3 + 0二3 二 £(4), J$(5) = 0 = J§(5).对于口满足歩(D二的，故几)=£("，故