动态规划试题

1． 某公司打算向它的三个营业区增设6个销售店，每个营业区至少增设1个。各营业区每

年增加的利润与增设的销售店个数有关，具体关系如表1所示。试规划各营业区应增设销售店的个数，以使公司总利润增加额最大。

表1

增设销售店个数 1 2 3 4 营业区A 100（万元） 160 190 200 营业区B 120（万元） 150 170 180 营业区C 150（万元） 165 175 190

解：将问题按区分为三个阶段k?1,2,3，设状态变量Sk（k?1,2,3）代表从第k个区到第3个区的增设个数，决策变量xk代表第k个区的增设个数。于是有状态转移率

Sk?1?Sk?xk、允许决策集合Dk(Sk)?{xk|0?xk?Sk}和递推关系式：

fk(Sk)?max{gk(xk)?fk?1(Sk?xk)} (k?3,2,1)

0?xk?Skf4(S4)?0

当k?3时：

f3(S3)?max{g3(x3)?0}?max{g3(x3)}

0?x3?S30?x3?S3?于是有表7-2，表中x3表示第三个阶段的最优决策。

表7-2 （单位：百万元） S3 ? x30 0 0 1 1 1.5 2 2 1.65 3 3 1.75 4 4 1.90 f3(S3) 当k?2时：

f2(S2)?max{g2(x2)?f3(S2?x2)}

0?x2?S2于是有表7-3。

表7-3 （单位：百万元）

x2 g2（x2）+f3（s2 - x2） 0 0+0 0+1.5 1 1.2+0 2 1.5+0 3 1.7+0 4 1.8+0 S2 0 1 2 3 4 5

f2(S2) 0 1.5 1.5 3.0 3.2 3.35 ? x20 1 1 2 3 3 0+1.65 1.2+1.5 0+1.75 1.2+1.65 1.5+1.5 0+1.90 1.2+1.75 1.5+1.65 1.7+1.5 0+1.90 1.2+1.90 1.5+1.75 1.7+1.65 1.8+1.5 当k?1时：

f1(S1)?max{g1(x1)?f2(S1?x1)}

0?x1?S1于是有表7-4。

表7-4 x1 g1（x1）+f2（s1 – x1） 0 0+3.45 1 1+3.75 2 3 4 2+2.7 1.6+3.2 1.9+3.0 S1 6 f1(S1) 4.9 ? x13

故最优分配方案为：A区建3个销售店，B区建2个销售店，C区建1个销售店， 总利润为490万元。

2． 某工厂有100台机器，拟分4个周期使用，在每一周期有两种生产任务，据经验把机器

投入第一种生产任务，则在一个周期中将有六分之一的机器报废，投入第二种生产任务，则有十分之一的机器报废。如果投入第一种生产任务每台机器可收益1万元，投入第二种生产任务每台机器可收益0.5万元。问怎样分配机器在4个周期内的使用才能使总收益最大？ 解：

阶段：将每个周期作为一个阶段，即k=1,2,3，4 状态变量：第k阶段的状态变量Sk代表第k个周期初拥有的完好机器数

决策变量：决策变量xk为第k周期分配与第一种任务的机器数量，于是Sk?xk该周期分

配在第二种任务的机器数量。

状态转移律：SK?1?5/6SK?0.9(SK?xK)?0.9SK?1/15xK 允许决策集合DK?SK??xK0?xK?SK 令最优函数：fk?SK??maxxK?DK?SK????0.5SK?0.5xK?fk?1?0.9SK?1/15xK??

边界条件：f5?S5?=0 当k=4时：

f4(S4)?max{0.5S4?0.5x4?f5(S5)}

0?x4?S4?max{0.5S4?0.5x4}

0?x4?S4?因f4(S4)是关于x4的单调递增函数，故取x4?S4，相应有f4(S4)?S4；依次类推，可求

得：

?当k?3时：x3?S3，f3(S3)?11/6S3 ?当k?2时：x2?S2，f2(S2)?91/36S2

?当k?1时：x1?S1，f1(S1?100)?671/216S1?310.65

计算表明，每一期都将全部机器投入第一种任务中，其中

S1?100，S2=83，S3=69，S4=58

3． 某公司生产一种产品，估计该产品在未来四个月的销售量分别为300、400、350和250

件。生产该产品每批的固定费用为600元，每件的变动费用为5元，存储费用为每件每月2元。假定第一个月月初的库存为100件，第四个月月底的存货为50件。试求该公司在这四个月内的最优生产计划。 解：阶段：将今后4个月中的每一个月作为一个阶段，即k?1,2,3,4；

状态变量：第k阶段的状态变量Sk代表第k个月初产品存储量； 决策变量：决策变量xk代表第k个月的生产量；

状态转移律：Sk?1?Sk?xk?dk（dk是第k个月的销售量）； 边界条件：S1?100，S5?50，f5(S5)?0； 固定生产费用 0,

?k?0

C?? 600, ?k?0

和存贮费Zk?2Sk?1?2(Sk?xk?dk) 变动生产费用 G??5?k 最优指标函数：最优指标函数具有如下递推形式 fk(Sk)?min{Ck?G??Zk?fk?1(Sk?1)

xkfk(Sk)?min?Ck?5xk?2?Sk?xk?dk??fk?1(Sk?xk?dk)?

xk 当k?4时： 表1 S4 X4 F4（S4） 0 300 2200 50 250 1950 100 200 1700 150 150 1450 200 100 1200 250 50 950 300 0 100

当K=3时：

f3(S3)?min?C3?5x3?2?S3?x3?d3??f4?S4??

x3 表2 x3 0 50 100 150 200 250 300 350 400 450 ? x3f3(S3) 4550 4300 4050 3800 3550 3300 3050 2200 2050 S3 0 50 100 150 200 250 300 4550 4650 4750 350 300 250 200 4300 4400 4500 4600 4050 4150 4250 4350 4450 3800 3900 4000 4100 4200 4300 3550 3650 3750 3850 3950 4050 3550 150，450 100，400 50，350 0 3300 3400 3500 3600 3700 3800 3300 3050 3150 3250 3350 3450 3550 3050 350 2200 2900 3000 3100 3200 3300 2800 400 2050 2250 2850 2950 3050 2550

当K=2时： 表3 S3 0 50 100 150 0 50 100 150 200 250 300 350 400 450 ? x2f2(S2) 7150 6900 6650 6400 7150 7250 400 6900 7000 7100 350 6650 6750 6850 6950 300 6400 6500 6600 6700 6800 250 200 6150 6250 6350 6450 6550 6650 200 6150 当K=1时: 表4 x1 S1 100

利用状态转移律，按上述计算的逆序可推算出最优策略为：第1个月生产200件，第20 50 100 150 200 250 300 350 400 450 ? x1f1(S1) 8750 8750 8850 8950 9050 9150 9250 200 个月生产400件，第3个月生产350件，最后一个月生产300件。

本文来源：https://www.bwwdw.com/article/6dyo.html