文档介绍：第七章动态规划
§1　多阶段决策过程最优化问题举例
§2　基本概念、基本方程与最优化原理
§3　动态规划的应用(1)
§4　动态规划的应用(2)
第1页，共28页。
1
§1　多阶段决策过程最优化问题举例
例1 最载重量为W
公斤的背包，求各种物品应各取多少件放入背包，使背
包中物品的价值最高。
这个问题可以用整数规划模型来描述。设xi为第i种
物品装入背包的件数（i =1, 2, …, n），背包中物品的总
价值为z，则
Max z = c1x1+c2x2+ … +cnxn
. w1x1+w2x2+…+wnxn≤W
x1, x2, …, xn0 且为整数。
§3 动态规划的应用(1)
第8页，共28页。
8
下面用动态规划逆序解法求解它。设
阶段变量k：第k次装载第k种物品（k=1, 2, …, n）
状态变量sk：第k次装载时背包还可以装载的重量；
决策变量uk = xk：第k次装载第k种物品的件数；
决策允许集合：Dk(sk) = { xk | 0 xksk/wk，xk为整数}；
状态转移方程： sk+1 = sk wkxk；
阶段指标： vk = ckxk；
最优过程指标函数fk(sk)：第k到n阶段容许装入物品的最大使
用价值；
递推方程： fk(sk) = max {ckxk+fk+1(sk+1)}
= max {ckxk+fk+1(sk wkxk)}；
xDk(sk)
终端条件： fn+1(sn+1) = 0。
§3 动态规划的应用(1)
第9页，共28页。
9
例3.　某咨询公司有10个工作日可以去处理四种类型的咨
询项目，每种类型的咨询项目中待处理的客户数量、处理每个
客户所需工作日数以及所获得的利润如表所示。显然该公
司在10天内不能处理完所有的客户，它可以自己挑选一些客
户，其余的请其他咨询公司去做，应如何选择客户使得在这10
个工作日中获利最大？
咨询项目类型
待处理客户数
处理每个客户所需工作日数
处理每个客户所获利润
1
　2
　3
　4
4
　　3
　　2
　　2
1
　　　3
　　　4
　　　7
2
　　8
　　11
　　20
§3 动态规划的应用(1)
第10页，共28页。
10
实际上，背包问题我们也可以用整数规划来求解，如果背包携带物品重量的限制为W公斤，这N种物品中第i种物品的重量为　，价值为　，第i种物品的总数量的　，我们可以设　表示携带第i种物品的数量，则其数学模型为：
　　　　.
且为整数。
　　
我们不妨用此模型去求解例3，也一定得出同样的结果。
§3　动态规划的应用(1)
第11页，共28页。
11
三、生产与存贮问题
　例4.　某公司为主要电力公司生产大型变压器，由于电力
采取预订方式购买，所以该公司可以预测未来几个月的需求
量。为确保需求，该公司为新的一年前四个月制定一项生产
计划，这四个月的需求如表1所示。
　　生产成本随着生产数量而变化。调试费为4，除了调度费
用外，每月生产的头两台各花费为2，后两台花费为1。最大
生产能力每月为4台，生产成本如表2所示。
　　　　　　　　　　　表1
§3　动态规划的应用(1)
第12页，共28页。
12
表2
　　每台变压器在仓库中由这个月存到下个月的储存费为1，
仓库的最大储存能力为3台，另外，知道在1月1日时仓库里存
有一台变压器，要求在4月30日仓库的库存量为零。试问该公
司应如何制定生产计划，使得四个月的生产成本和储存总费
用最少？
§3　动态规划的应用(1)
第13页，共28页。
13
§3　动态规划的应用(1)
四、系统可靠性问题
，，，。为了减少三个小组都失败的可能性，现决定给三个小组中增派两名高级科学家，到各小组后，各小组科研项目失败概率如下表：
问如何分派科学家才能使三个小组都失败的概率（即科研项目最终失败的概率）最小？
高级科学家
小组
1
2
3
0

1

2

0.