文档介绍：第七章动态规划
第一节多阶段决策问题
最短路问题
如图所示,要从A地到E地铺设管线,中间需要经过三个中间站,两点之间的连线上的数字表示距离,问应该选择什么路线,使总距离最短?
3
5
2
5
6
3
2
1
7
3
7
5
6
2
2
5
4
3
2
1
B1
A
B2
B3
C1
C2
C3
C4
E
D2
D1
例7-2 机器负荷问题
某工厂有100台机器,拟分四个周期使用,在每一个周期有两种生产任务。据经验,把机器x1台投入第一种生产任务,则在一个生产周期中将有1/3台机器报废;余下的机器全部投入第二种生产任务,则有1/10的机器报废,如果干第一种生产任务每台机器可以收益10,干第二种生产任务每台机器可以收益7,问怎样分配机器使总收益最大?
 
例7-3 资源分配问题
假设有一种资源其数量为a,现将它分配给n个使用者。若分配给第i个使用者的数量为xi(i=1,…,n),产生的相应收益为gi(xi),问如何分配使总收益最大?
投资决策问题、生产存贮问题、采购问题、设备更新问题等都具有多阶段决策问题的特征,都可以用动态规划方法求解。
第二节动态规划的基本概念和基本原理
 一、动态规划的基本概念
(stage)
描述阶段的变量称为阶段变量(k)
k=1,A——B;
k=2,B——C;
k=3,C——D;
k=4,D——E。
(state)
状态表示各阶段开始所处的自然状况或客观条件,它既是某阶段过程演变的起点,又是前一阶段某种决策的结果。
描述状态的变量称为状态变量(sk) 。
状态变量sk的取值集合称为状态集合,第k阶段的状态集合记为Sk ,
3
5
2
5
6
3
2
1
7
3
7
5
6
2
2
5
4
3
2
1
B1
A
B2
B3
C1
C2
C3
C4
E
D2
D1
状态的选取应当满足无后效性:系统从某个阶段往后的发展演变,完全由系统本阶段所处的状态及决策所决定,与系统以前的状态及决策无关。也就是说,过去的历史只能通过当前的状态去影响未来的发展,当前的状态是过去历史的一个完整总结。只有具有无后效性的多阶段决策过程才适合于用动态规划方法求解。
各阶段状态集合分别为:
S1={A} S2={B1,B2,B3}
S3={C1,C2,C3,C4} S4={D1,D2}
(decision)
当各阶段的状态选定以后可以做出不同的决定(或选择)从而确定下一个阶段的状态,这种决定(或选择)称为决策。
表述决策的变量称为决策变量,常用uk(sk)表示第k阶段当状态为sk时的决策变量。
实际问题中,决策变量的取值往往限制在某一范围内,此范围称为允许决策集合,常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合,uk(sk)∈Dk(sk)。
从B2出发,可以选择C1,C2,C3,C4,即允许决策集合为:
D2(B2)={C1,C2,C3,C4}
当决定选择C3时,可以表示为:u2(B2)=C3
(policy)
当各个阶段的决策确定以后,各阶段的决策形成一个决策序列,称此决策序列为一个策略。
使系统达到最优效果的策略称为最优策略。
在n阶段决策过程中,从第k阶段到终止状态的过程,称为k后部子过程(或称为k子过程),k后部子过程相应的决策序列称为k后部子过程策略,简称子策略,记为pk,n(sk):
pk,n(sk)={uk(sk),uk+1(sk+1),…,un(sn)}
当k=1时,即由第一阶段某个状态出发做出的决策序列称为全过程策略,简称策略,记为p1,n(s1):
p1,n(s1)={u1(s1),u2(s2),…,un(sn)}
(state transfer equation)
设第k阶段状态为sk,做出的决策为uk(sk),则第k+1阶段的状态sk+1随之确定,他们之间的关系可以表示为:
sk+1=Tk(sk,uk)
表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程,它反映了系统状态转移的递推规律。
状态转移方程为:sk+1= uk(sk)
3
5
2
5
6
3
2
1
7
3
7
5
6
2
2
5
4
3
2
1
B1
A
B2
B3
C1
C2
C3
C4
E
D2
D1
衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程,常用Vk,n表示,即:
Vk,n=Vk,n(sk,uk,sk+1,…,sn+1)
当k=1时,V1,n表示初始状态为s1,采用策略p1,n时的指标函数值。
V1