文档介绍：管理运筹学-管理科学方法
广东培正学院
王雄志副教授
1
第6 章动态规划
Sub title
学习要点
理解多阶段决策问题的基本特征和阶段划分
区分阶段变量、状态变量、决策变量的含义
理解过程决策、状态方程、指标函数的表述
理解动态规划的最优性原理和状态无后效性
了解动态规划逆序求解思路和递推求解方法
2
第6 章动态规划
动态规划Dynamic Programming:多阶段决策的最优化
有的管理决策问题呈现出明显的阶段性,
按时序顺序或空间演变划分成多个相互联系的阶段;
每个阶段的决策即为原有复杂决策的一个子问题;
原有复杂决策就化为逐个求解几个简单的阶段子问题;
每个阶段的决策一旦确定,整个决策过程也随之确定。
例如:
企业生产物流:物料供应、生产制造、分销零售等阶段
物流运输配送的最短路问题:可以按空间顺序划分阶段
3
第一节多阶段决策
例:有供应商要运输一批货物去公司,试求一条运输路径最短。
经过枚举计算:
从始点 S1到终点ST共有3×3×2×1=18条不同路线。
此问题的最短路:( →→→→),
该最短路的长度为11。
S1
ST
S12
S22
S32
S13
S23
S33
S14
S24
2
4
4
7
4
3
4
3
4
5
1
5
1
4
6
3
3
3
3
4
供应
商
某
公
司
出
口
港
进
口
港
城
市
阶段1
阶段2
阶段3
阶段4
4
第二节动态规划原理
一、动态规划的基本概念
阶段变量
将决策全过程按时空顺序划为若干阶段
用k表示阶段变量,阶段编号为顺序编号
状态变量
状态表示过程发展中某阶段的起始状况
描述各阶段状态演进的变量,称为状态变量,用Sk表示
第 k 阶段可能有若干状态,用Sk 表示阶段k的状态集合
sk(i)表示第k阶段的第 i 个状态
选取的状态变量必须满足无后效性
5
第二节动态规划原理
一、动态规划的基本概念
决策变量
变量xk(sk)表示阶段k状态sk的决策,称为决策变量,简记xk
决策变量取值被限制在某一范围内,称允许决策集合Xk(sk)
决策变量组成的序列,称为策略
全过程策略 p1,n(s1)= {x1, x2,…, xn}
k子过程策略 pk,n(sk)= {xk, xk+1,…, xn}
状态转移方程
下一阶段状态sk+1 是本阶段状态sk 和决策xk的函数
sk+1 =T(sk, xk(sk)) =T(sk, xk)
状态sk演进到下一阶段状态sk+1的转移规律称状态转移方程
6
第二节动态规划原理
一、动态规划的基本概念
指标函数
阶段指标函数vk
衡量每一阶段决策效果的优劣的数量指标
是状态变量和相应决策变量的函数,即vk = vk(sk , xk )
过程指标函数Vk,n
从第k阶段的状态sk出发到最后阶段结束的综合绩效度量
取决于阶段k到阶段n所采取的策略,即Vk,n (sk,xk,xk+1 ,…,sn)
指标函数Vk,n可以是各阶段指标的和或积
最优指标函数值fk(sk)
从状态sk出发,选取最优策略所得的指标函数值
fk(sk)=opt{Vk,n }
7
第二节动态规划原理
二、动态规划的基本思路
最优性原理:美国运筹学家贝尔曼提出
无论过去的状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。
逆序算法:逆着阶段顺序的方向,由后向前推算。
各阶段求解都是在后部子过程最优策略基础上,再考虑本阶段的指标函数,求出本阶段的最优策略。
阶段1
阶段2
阶段k
阶段k+1
阶段n
…
…
状态S1
决
策
x1
状态S2
v1
决
策
x2
状态S3
v2
决
策
xk
状态Sk+1
vk
决
策
xk+1
vk+1
决
策
xn
vn
寻求最优解的方向
8
第二节动态规划原理
二、动态规划的基本思路
递推方程:
加法合成
乘法合成
9
第二节动态规划原理
三、动态规划的数学模型
1. 动态规划建模过程
2. 动态规划模型分类
对问题进行阶段划分,确定阶段变量k
确定状态变量sk
确定决策变量xk 、允许决策集合Xk (sk )
写出状态转移方程sk+1 =Tk (sk,xk)
写出指标函数的基本递推方程
明确边界条件
过程
变量
确定
随机
离散
连续
离散确定型
离散随机型
连续确定型
连续随机型
10