第8章动态规划8.1 在设备负荷分配问题中，n =10，a =0.7，b =0.85，g =15，h =10，期初有设备1000台。

试利用公式(8.7)确定10期的设备最优负荷方案。

【解】由公式10()n t n tii i i g h a a g b a ---==-≤≤-∑∑得(g -h )/g (b -a )＝0.2222，a 0＋a 1＋a 2＝1+0.7＋0.49＝2.19＜2.222＜a 0+a 1＋a 2＋a 3＝2.533，n －t －1＝2，t =7，则1~6年低负荷运行，7~10年为高负荷运行。

各年年初投入设备数如下表。

年份1 2 3 4 5 6 7 8 9 10 设备台数 1000 850 723 614 522 444 377 264 184.8 129 8.2如图8－4，求A 到F 的最短路线及最短距离。

【解】A 到F 的最短距离为13；最短路线 A→ B2→ C3 → D2 → E2 → F 及A→C2 → D2 → E2 → F8.3求解下列非线性规划(1) 123123max 0,1,2,3j Z x x x x x x C x j =++=⎧⎪⎨≥=⎪⎩ (2) 22123123123min ,,0Z x x x x x x Cx x x =++++=⎧⎨≥⎩（3）2123123123max 2310,,0Z x x x x x x x x x =++++=⎧⎨≥⎩(4)123123max 42100,1,2,3j Z x x x x x x x j =++=⎧⎪⎨≥=⎪⎩ (5) 123123max 24100,1,2,3j Z x x x x x x x j =++≤⎧⎪⎨≥=⎪⎩（6）221123123123max 228,,0Z x x x x x x x x x x =+++++=⎧⎨≥⎩【解】（1）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有k ＝3，333333()max()x s f s x s ===及最优解 x 3*=s 3k ＝2，22222222233222222000()max [()max [()]max (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤==-=由222222120,2h s x x s x ∂=-=∂则＝22222<0,h x ∂∂＝－故2212x s =为极大值点。

所以22222222111()244f s s s s =-=及最优解x 2*=s 2k =1时，1111112111221*********()max[()]max ()max (,)4x s x s x s f s x f s x s x h s x ≤≤≤≤≤≤==-=，由221111111(43)04h s s x x x ∂=-+=∂，得*1113x s =故23111111111()()12327f s s s s s =-= 已知知x 1 + x 2+ x 3 = C ，因而按计算的顺序推算，可得各阶段的最优决策和最优解如下*113x C =，311()27f C c =由s 2=s 1－x 1*=2C/3，*222211,()39x C f s C ==由s 3=s 2－x 2*=C/3，*33311,()33x C f s C ==最优解为：31111(,,);33327T X C C C z C ==【解】（2）设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=C则有x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=C 用逆推法，从后向前依次有k ＝3，2333333()min()x s f s x s ===及最优解 x 3*=s 3k ＝2，22222222223322222202200()min [()min [()]min (,)x s x s x s f s x f x x s x h s x ≤≤≤≤≤≤=+=+-=由2222221420,2h s x x s x ∂=-=∂则＝2222x h ∂∂=4>0,故x 2=221s 为极小值点。

因而有2*2222211(),22f s s x s ==k ＝1时，1111211111111001()min [()min (,)2x s x s f s x s x h s x ≤≤≤≤=+-=由111110h s x x ∂=-+=∂知*1111111,()2x s f s s =-=-得到最优解1(1,1/2,1/2);2T X C z C =-=-【解】(3) 设s 3=x 3 , s 3+x 2=s 2，s 2+x 1=s 1=10 则有 x 3= s 3 ，0≤x 2≤s 2，0≤x 1≤s 1=10 用逆推法，从后向前依次有k ＝3时，3323333()max()x s f s x s ===及最优解 x 3=s 3k ＝2时，222222222222200()max [3()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=222222332202h s x x s x ∂=-+==-+∂时 而222222320,2h x s x ∂=>=-+∂故不是一个极大值点。

讨论端点：当x 2=0时2222()f s s ＝, x 2= s 2时222()3f s s =如果s 2>3时, 2222()f s s =k ＝1时，111121111111100()max[2()]max (,)x s x s f s x s x h s x ≤≤≤≤=+-=11111122201h s x x s x ∂=-+==-+∂时 21122120,1h x s x ∂=>=-+∂故不是一个极大值点 同理有, x 1=0, f 1（s 1）= s 12= 100，x 1= s 1, f 1（s 1）= 2s 1= 20 (舍去) 得到最优解(0,0,10);100X z ==【解】(4)设s 3=x 3 ,2s 3+4x 2=s 2，s 2+x 1=s 1=10 则有x 3= s 3 ，0≤x 2≤s 2/4，0≤x 1≤s 1=10 用逆推法，从后向前依次有 k ＝1，333333()max()x s f s x s ===及最优解x 3*=s 3k ＝2，22222222222204041()max [(2)max (,)2x s x s f s x s x h s x ≤≤≤≤=-=由22x h ∂∂=21s 2-4x 2=0,则 x 2=81s 2222240h x ∂=-<∂,故2218x s =为极大值点。

则2222()32s f s =及最优解x 2*=s 2/8k ＝1，1111211111111001()max[()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 22*1111111111(43)0,323h s s x x x s x ∂=-+==∂，故31111()216f s s = 得到最优解(10/3,5/6,5/3);125/27T X z ==【解】(5)按问题中变量的个数分为三个阶段s 1，s 2，s 3 ，且s 3≤10，x 1，x 2，x 3为各阶段的决策变量，各阶段指标函数相乘。

设s 1=2x 1 , s 1+4x 2=s 2，s 2+x 3=s 3≤10，则有x 1= s 1/2，0≤x 2≤s 2/4，0≤x 3≤s 3=10 用顺推法，从前向后依次有 k ＝1，111111/2()max ()2x s s f s x ===及最优化解x 1*=s 1/2 k ＝2，2222222222220/40/41()max [(4)max (,)2x s x s f s x s x h s x ≤≤≤≤=-=由22221402h s x x ∂=-=∂,则*2218x s = 222240h x ∂=-<∂,故2218x s =为极大值点。

则32221()32f s s = k ＝3，3333233333333001()max [()]max (,)32x s x s f s x s x h s x ≤≤≤≤=-= 由22*3333333311(43)0,323h s s x x x s x ∂=-+==∂ 故33331()216f s s =，由于s 3≤10，则s 3=10时取最大值，x 3＝10/3，s 2=s 3－x 3＝20/3，x 2＝5/6，s 1=s 2－4x 2＝10/3，x 1＝5/3得到最优解(5/3,5/6,10/3);125/27T X z ==【解】（6）设s 1=x 1, s 1+x 2=s 2，s 2+x 3=s 3=8k ＝1，1122111111()max(2)2x s f s x x s s ==+=+及最优化解x 1*=s 1k ＝2，222222222222222200()max [2()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-=2222622,h x s x ∂=--∂222260h x ∂=>∂ x 2*=0时，f 2（s 2）=s 22+2s 2, x 2*= s 2时，f 2（s 2）=2s 22 故2222222()max{2,2}f s s s s =+ k ＝3，①当x 2*=0时，23333333333033033()max [()2()]max (,)x s x s f s x s x s x h s x ≤≤≤≤=+-+-= 同样得x 3*=0时，f 3（s 3）=s 32+2s 3x 3*=s 3时，f 3（s 3）=s 3 所以， f 3（s 3）= s 32+2s 3=80②当x 2*= s 2时，f 3（s 3）=330max s x ≤≤[x 3+2（s 3-x 3）2]同样得x 3*=0时，f 3（s 3）=2s 32 =128 x 3*=s 3时，f 3（s 3）=s 3 =8 所以， f 3（s 3）= 2s 32=128 最优解为(0,8,0);128X z ==8.4用动态规划求解下列线性规划问题。

12121212max 242624,0Z x x x x x x x x =++≤⎧⎪≤⎪⎨≤⎪⎪≥⎩【解】设s 2=x 2 ,s 2+2x 1=s 1≤6则有 0≤x 2=s 2≤4，0≤x 1≤s 1/2 用逆推法，从后向前依次有 222()4f s s =及最优解x 2*=s 2111111122110/20/2()max [2()]max [46]x s x s f s x f s s x ≤≤≤≤=+=-由 s 2=s 1－2x 1≤4， s 1≤6，取s 1＝6，111110/2()max [246]x s f s x ≤≤=-又1≤x 1≤2，取x 1＝1，11()18f s =最优解(1,4);18T X z ==8.5 10吨集装箱最多只能装9吨，现有3种货物供装载，每种货物的单位重量及相应单位价值如表8.24所示。