第六章动态规划

1、用动态规划方法求下面交通图由A到B的最短时间。

A E C I F D 图1

注：各点之间的连线旁边数字，表示时间。

2、设有三种机器，使用也分三个时期。第一个时期使用三种机器的耗费分别为6，8，9；第二个时期使用三种机器的耗费分别为10，12，8；第三个时期使用三种机器的耗费分别为2，5，6。但是机器的使用不是任意的，只能按图的顺序使用。问题是如何安排机器使总耗费最小？（化为网络最短路问题求解）

机器2 机器3

图2

3、某工厂进行甲、乙、…………………………………………………………………表1丙三种新产品的试制，估计这些新产品试制成功的概率分别为0.6，0.4和0.3。由于工厂急于推出新产品，故厂方领导决定再拨2万元的研制费，以期提高新产品研制的概率。据有关专家估计，

把增加的研制费用于各种新产品试制时，试制成功概率如表1所示。试把这批研制费分配给各新产品试制项目（不分配，分配给1万元或分配给2万元），以使这三种新产品均研制成功的概率最大。

增加研制费 （万元） 0 1 2 甲 0.60 0.80 0.85 新产品成功的概率

乙 0.40 0.70 0.90 丙 0.30 0.60 0.70 时期1

机器1

时期2

时期3

M J G K P N

Q L O B 4、用动态规划方法求 表2 maxf(x)9x110x2 约束条件：

月 份 1 2 3 4 销 售 量（百件） 4 5 3 2 x132x15x215 x1,x20

5、某厂生产一种产品，该产品在未来四个月的销售量估计如表2所示。该项产品的生产准备费用为每批5百元，每件的生产费用1元，每件的存储费用每月为1元。假定1月初的存货为1百件。5月初的存货为0。试求该厂在四个月内的最优生产计划。

6、现有一批资金，总额为5万元拟投资于改造三个工厂。先对三个工厂拟订了几个不同的技术改造方案，其所需资金和投产后新增收益如表3所示。

各工厂改造所需资金和投产后新增收益 表3 各工厂改造投产后新增年收益值（万元） 投资（万元） 工厂1 0 1 2 3 4 0 1.5 2.6 — — 工厂2 0 — 2.8 3.9 4.2 工厂3 0 1.3 — — — 问总投资额5万元应如何分配使用，才能使三个工厂改造后的新增收益最大？

7、用动态规划方法求

2 maxf(x)4x19x22x3约束条件：

x1x2x310x1,x2,x30,且为整数

8、写出下列问题的动态规划的基本方程。

maxZi(xi)

i1n约束条件：

xi1nib,(b0)

xi0,(i1,2,...,n)