文档介绍：第2讲动态规划模型
动态规划是运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家贝尔曼()等人,根据一类多阶段决策问题的特点,提出了解决这类问题的“最优性原理”,研究了许多实际问题,从而创建了解决最优化问题的一种新方法——动态规划。
动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。
下面,以最短路径问题为例,说明动态规划的基本思想方法和特点。
(一)、最短路径问题
问题提出
如图1-10所示(P56),从地要铺设一条管道到
地,中间必须经过五个中间站,第一站可以在两地中任选一个,类似的,第二、三、四、五站可供选择的地点分别是
连接两点间的距离用图上两点连线上的数字表示,两点间没有连线的表示相应两点不能铺设管道,现要选择一条从到的铺
管线路,使总距离最短。
2、问题分析
解决最短路径问题,最容易想到的方法是穷举法,即列出所有可能发生的方案和结果,再针对题目的要求对它们一一进行比较,求出最优方案。这种方法,在变量(或节点)的数目较小时有效;在变量数目很大时,计算量将会变得十分庞大,行不通。因此,需要根据问题的特性,寻求一种简便的算法。
最短路径问题有一个特性:如果最短路径在第站通过点,则这一线路在由
出发到达终点的那一部分线路,对于从点终点的所有可能选择的不同线路来说,必定也是距离最短的。这就是最优性原理。这就启发我们从最后一段开始,采用从后向前逐步递推的方法,求出各点到的最短线路,最后求得从到的最短线路。
(归结为一句话:最有策略的子策略仍然是最优策略)
3、问题求解
为求解方便,将整个过程分为6个阶段,用表示。
(1)时,设表示由到的最短距离,表示由到的最短距离,有
,
(2)时,
从出发,有两种选择,到或,如果表示到的最短距离,
表示到的距离,则
再用表示相应的选择或决策,则。得到由出发到的最短线路是。
从出发,也有两种选择,到或,如果的定义与中相似,则
。得到由出发到的最短线路是。
从出发,同样有
。得到由出发到的最短线路是。
(3)时,分别以为出发点来计算,有
,由出发的最短线路是。
,由出发的最短线路是
,由出发的最短线路是。
(4)时,分别以为出发点来计算,有
,由出发的最短线路是。
,由出发的最短线路是。
,由出发的最短线路是。
,由出发的最短线路是。
(5)时,分别以为出发点来计算,有
,由出发的最短线路是。
,由出发的最短线路是。
(6)时,出发点只有,有
,由出发的最短线路是,距离为18。
综上所述,动态规划方法的基本思想是,把一个复杂的问题分解为一系列同一类型更容易求解的子问题,使计算过程单一化,便于应用计算机。求解过程分为两个阶段,先按照整体最优的思想逆序地求出各个可能状态的最优决策。然后,再顺序地求出整个问题的最优策略和最优路线
。由于把最优化应用到每个子问题上,于是,就系统地删去了所有中间非最优的方案组合,使计算工作量比直接枚举法大大减少。
(二)、基本概念和基本方程
1、动态规划的基本概念
(1)阶段和阶段变量
用动态规划求解多阶段决策系统问题时,要根据具体情况,将系统适当地分成若干个阶段,以便分阶段决策。通常阶段是按照决策进行的时间或空间上的先后次序划分的,描述阶段的变量称为阶段变量。由系统的最后阶段向初始阶段求最优解的过程,称为动态规划的逆推解法。
(2)状态和状态变量
状态表示系统在某阶段所处的“起点”位置或状态。各阶段的状态可用状态变量来描述,阶段的状态变量记为。第阶段所有可能状态的全体,可用状态集合来描述。上例中
(3)决策、决策变量和策略
从一个阶段的某个状态出发,到达下一阶段,都有若干种选择。把过程从一个状态演变到下一阶段某一状态所作的选择或决定称为决策。描述决策的变量称为决策变量,记为。表示从第阶段的状态出发所作的决策。并用表示第阶段从出发的所有决策的集合。
由每阶段的决策组成的决策序列称为全过程策略或策略,表示为。由系统的第阶段出发到终点的决策过程称为全过程的后部子过程,相应的策略称为子策略。表示为。
对于每一实际的多阶段决策过程,可供选择的策略有一定的范围限制,这个范围称为允许集合。允许集合中达到最优效果的策略称为
最优策略。
(4)状态转移方程
由第阶段的状态,采用决策变到第阶段的状态的过程称为状态转移,并记为
该式表达了从阶段到阶段的状态转移规律,故称为状态转移方程。
(5)阶段效益
多阶段决策过程中,在阶段的状态执行决策转到状态,不仅带来系统状态的转移,而且也将对整个决策的结果或效益产生影响。用表示在第阶段中,从状态出