文档介绍：动态规划
多阶段决策问题与动态规划
动态规划的基本概念
动态规划的步骤
动态规划的应用
1 求解静态规划问题
2 资源分配问题
3 不确定性采购问题
4 排序问题
例2 机器负荷分配问题
,产品的年产量g和投入生产的机器数量u的关系为 g=g(u), 这时机器的年完好率为a(0<a<1).在低负荷下生产时,产品的年产量h和投入生产的机器数量v的关系为h=h(v), 这时机器的年完好率为b(a<b<1).假定开始生产时完好的机器数量为s1,要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。
多阶段决策问题与动态规划
多阶段决策问题和我们前面遇到的决策问题不同,它是和时间有关的。与时间有关的活动过程称为动态过程,其优化方法称为动态规划。而与时间无关的活动过程称为静态过程,相应的的优化方法称为静态规划。
(1)阶段(stage)把所研究的决策问题,按先后顺序划分为若干相互联系的决策步骤,以便按一定的次序进行求解。描述阶段的变量称阶段变量,常用k表示。
(2)状态(state)状态表示每个阶段开始时所处的自然状况或客观条件,它描述了影响决策的因素随决策进程的变化情况,它既是前面阶段所作决策的结果,又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量,第k阶段的状态变量常用sk表示。通常,在第一阶段状态变量s1是确定的,称初始状态。
(3)决策(decision)决策表示在某一阶段处于某种状态时,决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量,第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约,被限制在某一范围之内。
动态规划的基本概念(一)
(4)策略(policy)把从第一阶段开始到最后阶段终止的整个决策过程,称为问题的全过程;而把从第k阶段开始到最后阶段终止的决策过程,或称为k子过程。在全过程上,各阶段的决策按顺序排列组成的决策序列p1,n={ u1,u2,……,un }称为全过程策略,简称策略;而在k子过程上的决策序列pk,n={ uk,uk+1,……,un }称为k子过程策略,也简称子策略。
(5)状态转移方程若第k阶段的状态变量值为sk,当决策变量uk的取值决定后,下一阶段状态变量sk+1的值也就完全确定。即sk+1的值对应于sk和uk的值。这种对应关系记为sk+1=Tk(sk,uk),称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。
动态规划的基本概念(二)
(6)指标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量,用vk(sk,uk)表示。过程指标函数是指过程所包含的各阶段的状态和决策所产生的总的效益值,记为
Vk,n=Vk,n(sk,uk,sk+1,uk+1,……,sn,un)
动态规划所要求的过程指标函数应具有可分离性,即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是:
①各阶段指标函数的和 Vk,n=∑vj(sj,uj);
②各阶段指标函数的积 Vk,n=∏vj(sj,uj)。
把过程指标函数Vk,n对k子过程策略pk,n求最优,得到一个关于状态sk的函数,称为最优值函数,记为fk(sk)。即
fk(sk)= opt Vk,n(sk,uk,……,sn,un)
uk,…,un
式中的“opt”(optimization)可根据具体问题而取min或max。
(7)基本方程通常动态规划问题的最优值函数满足递推关系式。设过程指标函数为各阶段指标函数的和的形式,即Vk,n=∑vj(sj,uj),则有
fk(sk)= opt {vk(sk,uk)+fk+1(sk+1)}
uk∈Dk(sk) (k=n,n-1,…,1) 递推方程
fn+1(sn+1)=0 边界条件
递推方程和边界条件一起称为动态规划的基本方程。
可根据边界条件,从k=n开始,由后向前逆推,逐步求得各阶段的最优决策和相应的最优值,最后求出f1(s1)时,就得到整个问题的最优解。
此问题的基本方程为
fk(sk)=Min{dk(uk)+fk+1(sk+1)}
uk∈Dk(sk)
k=6,5,4,3,2,1
f7(s7)=0
动态规划的步骤(一)
当k=6时
按基本方程由后向前继续递推有:
当k=5时
当k=4时
当k=3时
当k=2时
当k=1时
由此可以看出,A到G的最短路长为18,路径为: A→B1→C2→D1→E2→F2→G