=29.33285×1000-7500
? =21832.85 此时x1=0
最优策略为：
??=0， s2=0.9s1-0.2 x1=0.9×100=900辆 x1??=0， s3=0.9s2-0.2x2=0.9×900-0.2×0=810辆 x2??=0， s4=0.9s3-0.2x3=0.9×810-0.2×0=729辆 x3??=0， s5=0.9s4-0.2x4=0.9×729=656.1辆 x4?=4.5s5-2500=4.5×0.9s1-2500=452.45 x54
?=0.9×656.1-0.2×452.45=500辆 s6=0.9 s5-0.2x5其中s5=0.9s4=0.9×0.9s3=?=0.9×0.9×0.9×0.9s1=656.1
答：第一年初：1000辆车全部用于低负荷运输。
第二年初：还有900辆完好的车，也全部用于低负荷运输。 第三年初：还有810辆完好的车，全部用于低负荷运输。 第四年初：还有729辆完好的车，全部用于低负荷运输。
第五年初：还有656.1辆完好的车，其中452台用于高负荷运输，204台在低负荷下运输。
到第五年末，即第六年初，还剩余500辆完好的车。 所创最大利润f1(s1)=f1(1000)=21833万元
第四讲 资源分配问题（一维连续）
例5 某公司有资金10万元，若投资于项目i (i=1,2,3)的投资额为xi时，其收益分别为
2，问应如何分配资金额才能使gi(xi)。其中g1(x1)=4x1，g2(x2)=9x2，g3(x3)=2x3总收益最大？
解： maxz=
?g(x)
iii?13?3xi?10? s.t ?? i?1??x1,x2,x3?0
(一) 逆序解
x1
x2 x3
16
s 2 - x=10-s1=10 s 2 x 1 项目 1 s 3 = 2 项目 1 s 4 = s 3 - x 3
项目1 g ( g ( g ( 2
1x1)=4x1 2x2)=9x2 3x3)=2x3 状态转移方程： sk?1?sk?xk k=1,2,3 基本方程：
x?fk(sk)???f4(s4)?00?xk?skmax?gk(xk)?fk?1(sk?1)?k?3,2,1
对这种初始状态s1=10（万元）已知的资金分配问题，我们采用逆序法。 K=3时
f3(s3)?max{g3(x3)?f4(s4)}=max{2x3}=2s3； 此时，
0?x3?s30?x3?s322?=s3 x32 g3?2x3K=2时
f2(s2)?max{g2(x2)?f3(s2?x2)}
0?x2?s2 =max{9x2?2s3}
0?x2?s22 =max{9x2?2(s2?x2)}
0?x2?s22O s3 x3
问 h2(x2)=9x2?2(s2?x2) x2∈[0，s2] 当x2=？时，h2(x2)最大。且最大值=？
1 x∈（0，s）时。 ○222
?h2=9+4（s2-x2）（-1）=0， x2=s2-9/4 ?x2?2h2且 =4>0。 故h2(x2)在x2=s2-9/4处取得极小值。 2?x22 依题意h(x)在[0，s]上有极大值，故极大值只能在端点处取得，为此考察： ○222 h2(0)=2s2； h2(s2)=9s2 现在问：谁大谁小？
这是以s2为自变量的两个函数的大小比较问题。 从右图上可看出
2h2(s2)h2(0)=2s2 2sh2(s2)=9s2
O 9/2 s2
17
9s2f2(s2)=max???2s20?s2?9/2s2?9/22*x2?s2 *x2?0最后看k=1时
f1(s1)?f1(10)?max{g1(x1)?f2(s2)}
0?x1?s1现在的问题是f2(s2)=？
9s2f2(s2)=max???2s20?s2?9/2s2?9/2*x2?s2 *x2?02
200 90 2(10?x1)2 O 9/2 10 x1
0?10?x1?9/210?x1?9/2(1) (2)9(10?x1)=f2(s1?x1)=f2(10?x1)= max??2?2(10?x1)?90?9x1f1(s1)?f1(10)?max{4x1?max?20?x1?10?2(10?x1) =max?9/2?x1?10}
0?x1?9/2
?90?5x19/2?x1?100?x1?9/22?4x1?2(10?x1)?90?5?9/2max =?2?4?0?2(10?0)逆追最优解：
9/2?x1?100?x1?9/2? =200 此时，x1=0。
????? x1=0， s2=10-x1=10≥9/2 x2=0 s3=s2-x2=10 x3=s3=10
且最大利润
f1(s1)?f1(10)=200（万元）
（二） 顺序解：
xx 3 1 x 2 s =10
4 s 3 =- x 3 s4 s 1 = s 2 - x 1 s 2 = s 3 - x 2 项目2 项目3 项目1 g ( g ( ) =2 x 2 g 3 ( x31x1)=4x1 2x2)=9x2 3 状态转移方程： sk=sk?1-xk k=1,2,3
18
最优指标函数fk(sk?1)：第k阶段，当投资额为sk?1时，从第1到第k阶段所获得的最大收益。 总的收益f3(s4)=f3(10)=？ 基本方程：
??fk(sk?1)?0?maxx?gk(xk)?fk?1(sk)?k?1,2,3k?sk?1
?f0(s1)?0k=1时:
f1(s2)?0max?x{g1(x1)?f0(s1)}=max{4x1}=4s1 此时，x?1=s2
1?s20?x3?s3k=2时：
f2(s3)?0max?x?s{g2(x2)?f1(s2)}=max{9x2?4s2}
230?x2?s3=0max?x?s{9x?4(s?23?x2)}=max{5x2?4s3}=9s3，此时，x2=s3230?x2?s3k=3时：
f10)?23(s4)?f3(0max?x{g3(x3)?f2(s3)}=maxx{2x3?9(10?x3)} 3?s40?3?10令
h2x23(x3)=3?9(10?x3) x3∈[0，10] 下求它的极大值：
h3?= 4x3—9 令其为0，得
x?3=9/4 且h3= 4≥0
故此函数在（0，10）内只有一个极小值点。
极大值点只能在端点处取的。 考虑：
x3=0时， h3(0)=9s4=90
x(10)=2s23=10时， h34=200 所以有 x?3=s4=10 此时，f3(s4)?f3(10)?200。 再用状态转移方程逆推得最优解：
x?3=10，s=s???34-x3=10-10=0，x2=s3=0，s2=s3-x2=0-0=0，x1=s2=0。 此解与逆序相同。
（三）连续变量的离散化解法： 例6 用连续变量的离散化求解：
Max z =4x21+9x2+2x3
19
s.t ??x1?x2?x3?10xi?0?(i?1,2,3)
解：因为这里的0≤xk≤10，k=1，2，3.可在区间[0，10]内选有限个点，比如分割成0，2，4，6，8，10。将来决策变量xk、状态变量均取值集合｛0，2，4，6，8，10｝中的点。尽管这样做可能出现丢失最优解，但作为近似解求解简单。
此时的动态规划基本方程：
?fk(sk)? ??f4(s4)?00?xk?skmax?gk(xk)?fk?1(sk?1)?k?3,2,1
当k=3时， f3(s3)=max{2x3}
0?x3?s32式中的s3，x3均取值于｛0，2，4，6，8，10｝，计算结果见下表
s3 0 0 0 2 8 2 0?x2?s2 4 32 4 6 72 6 8 128 8 10 200 10 f3(s3) ? x3当k=2时，f2(s2)?max{g2(x2)?f3(s2?x2)}
=max{9x2?f3(s2?x2)}，计算结果见下表
0?x2?s2x2 9x2+f3(s2?x2) ?f2(s2) x2 s2 0 2 4 6 8 10 0 0+0 2 0+8 18+0 4 0+32 18+8 36+0 6 0+72 18+32 36+8 54+0 8 0+128 18+72 36+32 54+8 72+0 10 0+200 18+128 36+72 54+32 72+8 90+0 0?x1?s10 18 36 72 128 200 0?x1?100 2 4 0 0 0 k=1时，f1(s1)?f1(10)?max{g1(x1)?f2(s2)}?max{4x1?f2(s1?x1)}， 计算结果见下表 x1 s1
4x1?f2(10?x1) f1(s1) x1? 0 2 4 6 8 10 20