动态规划习题课.ppt

动态规划习题课
资源分配问题
例1
某公司拟将500万元的资本投入所属的甲、乙、丙三个工厂,各工厂获得投资后年利润将有相应的增长,一定投资下的利润增长额如下表所示,试确定最优的投资分配方案,使公司年利润增长额最大。
投资(百万元) 1 2 3 4 5
甲
乙
丙
例1的求解
按工厂分为三个阶段: 甲乙丙
k : 1 2 3
设Sk为第k个工厂至第3个工厂可利用的投资额,
xk为第k个工厂获得的投资额,则Sk+1=Sk - xk。因而有最优指标函数:
fk(Sk)=max{rk(xk)+fk+1(Sk-xk)}
f4(S4)=0

例1的求解
k =3:
f3(S3)=max{r3(x3)+f4(S4)}=max{r3(x3)}
S3 0 1 2 3 4 5
*x3 0 1 2 3 4 4, 5
f3(S3) 0
k =2:
f2(S2)=max{r2(x2)+f3(S2 - x2)}

例1的求解
x2 r2(x2)+f3(S2-x2)
S2 0 1 2 3 4 5 f2(S2) *x2

0 0+0 0 0
1 0+.4 .5+0 1
2 0+.6 .5+.4 1+0 2
3 0+ .5+.6 1+.4 2
4 0+ .5+ 1+.6 +.4 =0 1,2
5 0+ .5+ 1+ +.6 +.4 +0 2

例1的求解
k =1:
f1(S1)=max{r1(x1)+f2(S1-x1)}
x1 r1(x1)+f2(S1-x1)
S1 0 1 2 3 4 5 f1(S1) *x1
5 0+ .3+ .7+ .9+ + +0 0, 2
然后按计算表格的顺序反推算,可得如下两个最优分配方案:
1. x1=0 S2=S1-x1=5-0=5 x2=2S3=3x3=3
2. x1=2, x2=2, x3=1

存贮控制问题
例2
某鞋店销售一种雪地防潮鞋,以往的销售经历表明,此种鞋的销售季节是从10月1日至3月31日。下一个销售季节各月的需求量预测值为:
月份 10 11 12 1 2 3
需求(双) 40 20 30 40 30 20
该鞋店直接从生产商进货,基础进货价为每双4美元。进货批量有10、20、30、40和50双五种规模,对应不同的进货批量享受一定的价格折扣,具体数值如下:
批量 10 20 30 40 50
折扣(%) 4 5 10 20 25

例2的求解
假设需求是按一定速度均匀发生的,订货不需要时间,但订货只能在月初办理,每次订货的费用为10美元。月存贮费用是按每月底鞋的存量计算的,。由于订货不需要时间,所以销售季节以外的月份无存货。试确定最佳的进货方案,以使总的销售费用最小。
阶段:k = 1, 2, 3, 4, 5, 6
状态: Sk 代表第k月初鞋的存量
决策变量:dk 代表第k月鞋的采购量
状态转移律: Sk+1=Sk + dk - Dk ,S1 = S7 = 0
费用函数: rk (Sk, dk )=(dk)+ (Sk + dk - Dk),其中(dk)为订货费用,订货费用由两部分构成,一部分是固定的采购费10美元,另一部分是货款, dk= 0时(dk)= 0。
最优指标函数: fk (Sk )=min {(dk) + (Sk + dk - Dk)+ fk+1 (Sk+1)}

例2的求解
K=6(三月):
S6 0 10 20
*d6 20 10 0
f6 (S6 )=(*d6 ) 86 48 0
K=5(二月):
d5 0 10 20 30 40 50 * d5 f5 (S5 )
S5
0 204 188 164 50 164
10 172 168 142 40 142
20 134 136 122 30 122
30 86 98 90 0 86
40 50 52 0 50
50 4 0 4

例2的求解
K=4(一月):
d4 0 10 20 30 40 50 * d4 f4 (S4 )
S4
0 302 304 40 302
10 282 282 286 30, 40 282
20 250 262 264 252 20 250
30 212 230 244 230 218 10 212
40 164 1