文档介绍：§ 动态规划简介
§ 动态规划基本概念
§ 动态规划的特点
§ 动态规划的求解方法
§ 实例
第一章动态规划
§ 动态规划简介
动态规划是现代管理领域中的一种重要的决策方法,其主要应用有最优路径问题、资源分配问题、投资决策问题、生产计划与库存问题、排序问题、货物装载问题以及生产过程中的最优控制问题。
动态规划没有标准的表达式,而是不同的问题有不同的相应的、具体的数学表达式,因此动态规划没有统一的处理格式,属于灵活、动态的数学方法。
动态规划可分为离散随机型、离散确定型、连续确定型和连续随机型四种,其中最基本的是离散确定型
§ 动态规划基本概念
4
3
3
2
3
2
1
4
3
A
B1
C1
B2
C3
C2
D
1
1
最短路线问题
阶段
状态
表示第k阶段的终点,也是第k+1阶段的起点。
描述状态的变量称为状态变量,记为xk.
第一阶段的起点称为初始状态,最后一个阶段的终点称为终止状态。
状态的选取要“无后效性”
第一阶段:{A}到{B1,B2}
第二阶段:{B1,B2}到{C1,C2,C3}
第三阶段:{C1,C2,C3} 到{D}
决策
策略
决策就是做出选择或决定。
用uk(xk)表示处于状态xk时的决策,由于有多种选择,所以称为决策变量。当做出决策由状态xk到状态xk时,记为uk(xk)=xk+1。
一个由初始状态到终止状态的选择称为全过程策略,简称策略,记为p。对含N个阶段的决策问题来说,任何一个决策都是由N个决策的决策序列所组成的,即
其中
策略
确定了一个由xk到终止状态的转移;
确定了一个由开始到第k阶段某状态的转移。
和又称为p的子策略。
状态转移方程确定前一阶段状态转变到后一状态的过程。如果给定了第k个阶段的状态变量xk和决策变量uk(xk),则第k+1阶段的状态变量xk+1也随之确定,记为
状态转移方程
阶段效益
系统某阶段的状态一经决定,执行某一决策所得的效益称为阶段效益,它是整个系统效益的一部分,是阶段状态xk和阶段决策uk的函数,记为dk(xk,uk)。
指标函数与最优指标
在多阶段决策问题中,衡量策略优劣的数量指标是策略的数值函数,称为指标函数,记为J(p)。由xk出发采取策略到终点的指标值记为J(xk, pk),
指标函数是系统执行某一策略所产生的效益,根据不同的实际问题,效益可以是利润、距离、时间、产量、或资源的耗量等。指标函数的最优值称为最优指标,使指标函数取得最优值的策略称为最优策略。
动态规划原理的一般模型
其中fk(xk) 为从状态xk出发到达终点的最优效益,根据问题的性质,上式中的min有事是max。
§ 动态规划的特点
把整个问题分阶段考虑,变为几个子问题
一个子问题的解决借助它所包含的子问题的解答,逐级推算
在前面最短线路问题中,第三阶段到终点作为第一个子问题,由第二、三阶段与终点组成第二个子问题,由第一、二、三阶段与终点构成第三个子问题,第三个子问题也就是原来的问题。在这些子问题中,形成了逐个嵌入的关系。
一个过程的最优策略具有这样的性质:无论其最初状态及其初始决策如何,其后诸决策对以第一个决策所形成的状态作为初始状态而言,必修构成最优决策。
贝尔曼()最优化原理