文档介绍：第8章动态规划基本方法
第1节多阶段决策问题与动态规划
动态规划是运筹学的一个分支,产生于20世纪50年代,1951年由美国数学家贝尔曼等人提出。
例最短路问题
给定下列道路网络,试求由节点A到G的最短路。
第1阶段
第2阶段
第3阶段
第4阶段
第5阶段
第6阶段
例2 机器负荷分配问题
某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时,产品的年产量g和投入生产的机器数量u的关系为 g=g(u),这时机器的年完好率为a(0<a<1);在低负荷下生产时,产品的年产量h和投入生产的机器数量v的关系为h=h(v),这时机器的年完好率为b(a<b<1)。假定开始生产时完好的机器数量为s,要求制定一个五年计划,在每年开始时决定机器在两种不同负荷下生产的数量,使五年内产品的总产量最高。
第1年
第1阶段
第2年
第2阶段
第3年
第3阶段
第4年
第4阶段
第5年
第5阶段
多阶段决策问题和前面遇到的决策问题不同,它是和时间有关的,状态(所处自然状况和客观条件)是随着决策进程而变化的,故有“动态”的含义。
与时间有关的活动过程称为动态过程,处理它的方法称为动态规划。而与时间无关的活动过程称为静态过程,相应的处理方法称为静态规划。
以上两个问题都可以划分为先后多个决策阶段。这类问题就称为多阶段决策问题。
多阶段决策问题的过程如下图所示:
阶段1
状态1
决策1
阶段2
状态2
决策2
阶段n
状态n
决策n
状态3
……
状态n+1
第2节动态规划的基本概念和基本方程
(1)阶段(stage)
(2)状态(state)
把所研究的决策问题,按先后顺序划分为若干相互联系的决策步骤,以便按一定的次序进行求解。这些决策步骤就称为阶段。
描述阶段的变量称阶段变量,常用k表示。
状态表示每个阶段开始时所处的自然状况或客观条件。它描述了影响决策的因素随决策进程的变化情况。它既是前面阶段所作决策的结果,又是本阶段作出决策的出发点和依据。
描述状态的变量称状态变量,第k阶段的状态变量常用sk表示。通常,第一阶段的状态变量s1是确定的,称初始状态。
动态规划的基本概念
描述决策的变量称决策变量,第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约,被限制在某一范围之内,称为允许决策集,记为Dk(sk)。
决策表示在某一阶段处于某种状态时,决策者在若干种方案中作出的选择决定。
(3)决策(decision)
(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的函数,称为(k-子过程)最优值函数,记为fk(sk)。即
fk(sk)= opt Vk,n(sk,uk,…,sn,un)
{uk,…,un}
式中的“opt”(optimization)可根据具体问题而取min或max。
动态规划的基本方程
动态规划的最优性原理(贝尔曼原理):作为整个过程的最优策略具有这样的性质,即无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简言之,最优策略的子策略也必是最优的。
根据此原理,要求全过程最优策略,可从子过程策略的最优化入手。对于过程指标函数是阶段