效益
f (s ) optV (s , x ,, s
k k k ,n k k
n 1
)
可递推
Vk ,n (sk , xk , sk 1 , xk 1 ,, sn1 )
Vk ( sk , xk ) *Vk 1, n (sk 1 , xk 1 , , sn1 )
指标函数形式: 和、
3
பைடு நூலகம்石家庄经济学院
管理科学与工程学院
第一节 多阶段决策
二、多阶段决策问题举例
例1 工厂生产过程：由于市场需求是一随着时间而变化的
因素，因此，为了取得全年最佳经济效益，就要在全年的
生产过程中，逐月或者逐季度地根据库存和需求情况决定 生产计划安排。
4
石家庄经济学院
管理科学与工程学院
第一节 多阶段决策
例2 设备更新问题：一般企业用于生产活动的设备， 刚买来时故障少，经济效益高，即使进行转让，处 理价值也高，随着使用年限的增加，就会逐渐变为 故障多，维修费用增加，可正常使用的工时减少， 加工质量下降，经济效益差，并且，使用的年限越 长、处理价值也越低，自然，如果卖去旧的买新的， 还需要付出更新费。因此就需要综合权衡决定设备 的使用年限，使总的经济效益最好。
• 指标函数
阶段指标函数：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 }
决 策 x1 状态S1 决 策 x2 状态S2 决 策 xk 状态S3 决 策 xk+1 状态Sk+1 决 策 xn
阶段1
阶段2
… 阶段k
阶段k+1
… 阶段n
v1
石家庄经济学院
v2
vk
vk+1
管理科学与工程学院
vn
寻求最优解的方向
13
第二节 动态规划原理
二、动态规划的基本思路
• 递推方程：
加法合成
10
石家庄经济学院
管理科学与工程学院
第二节 动态规划原理
一、动态规划的基本概念
• 决策变量：xk(sk)
变量xk(sk)表示阶段k状态sk的决策，称为决策变量，简记xk 决策变量取值被限制在某一范围内，称允许决策集合Dk(sk) 决策变量组成的序列，称为策略 • 全过程策略 p1,n(s1)= {x1, x2,…, xn} • k子过程策略 pk,n(sk)= {xk, xk+1,…, xn}
5
石家庄经济学院
管理科学与工程学院
第一节 多阶段决策
状态 决策 状态 1 决策 状态 状态 2 决策 n
以上所举问题的发展过程都与时间因素有关，因此在这类多
阶段决策问题中，阶段的划分常取时间区段来表示，并且各 个阶段上的决策往往也与时间因素有关，这就使它具有了 “动态”的含义，所以把处理这类动态问题的方法称为动态 规划方法。不过，实际中尚有许多不包含时间因素的一类
8 石家庄经济学院 管理科学与工程学院
第一节 多阶段决策
特别注意：
动态规划求解的多阶段决策问题的特点： 适合于用动态规划方法求解的只是一类特殊的多 阶段决策问题，即具有“无后效性”的多阶段决 策过程。所谓无后效性，又称马尔柯夫性，是指 系统从某个阶段往后的发展，仅由本阶段所处的 状态及其往后的决策所决定，与系统以前经历的 状态和决策(历史)无关。比如国家政策的制定。
2 1 1 6 3 v3 ( S3 , S 4 ) f 4 ( S 4 ) f3 ( S ) min min 7 2 2 2 3 4 v3 ( S3 , S4 ) f 4 ( S4 ) 2 3
* 2 x3 (S32 ) S4
* 2 x4 ( S4 ) ST
当k=3时， f (S ) Opt{v [S , x (S )] f
3 3 x3 D3 3 3 3 3
4
( S4 )}
，所以
* 1 1 x3 (S3 ) S4
1 1 1 2 3 v3 ( S3 , S 4 ) f 4 ( S 4 ) f3 ( S ) min min 5 1 2 2 6 4 v ( S , S ) f ( S ) 4 4 3 3 4 1 3
动态规划（Dynamic Programming）是运筹学的 一个重要分支，它是解决多阶段决策过程最优化 的一种方法。美国数学家贝尔曼（R. E. Bellman）等人在上世纪50年代初提出了解决多 阶段决策问题的“最优性原理”（Principle of Optimality）。1957年贝尔曼出版了专著“动态 规划”，该书是动态规划的第一本著作。目前动 态规划已经用于解决最优路径问题、资源分配问 题、生产调度问题、设备更新问题、复合系统可 靠性问题及生产过程最优控制等，并且取得了显 著的效果。
15 石家庄经济学院
积
管理科学与工程学院
解多阶段决策过程问题，求出
最优策略，即最优决策序列
{x , x ,, x }
最优轨线，即执行最优策略时的状态序列
* 1
* 2
* n
{ s , s ,, s }
最优目标函数值
* 1
* 2
* n
f 1 ( s1 )
* * * * * * 从 k 到终点最优策略 V V ( s , x , , s , x 1,n 1,n 1 1 n n)
第6章 动态规划
学习要点 Sub title
理解多阶段决策问题的基本特征和阶段划分
区分阶段变量、状态变量、决策变量的含义 理解过程决策、状态方程、指标函数的表述 理解动态规划的最优性原理和状态无后效性 了解动态规划逆序求解思路和递推求解方法
1
石家庄经济学院
管理科学与工程学院
第6章 动态规划
3 S33
1 (S4 , 6)
4
4
S32
3
(ST , 4)
( S32 ,8)
供 应 商
18
阶段1
出 口 港
阶段2
进 口 港
阶段3
城 市
阶段4
某 公 司
石家庄经济学院
管理科学与工程学院
第三节 逆序求解过程
二、递推算法
{v4 [ S 4 , x4 ( S 4 )] f 5 ( S5 )} ，即有 当k=4时，f 4 (S4 ) xOpt D
阶段2
S13 6 S2
2 S14 3 ST S2 4
4
4
4
S22
6
3
3 3
S32
S33
3
阶段3
供 应 商
阶段1
出 口 港
进 口 港
城 市
阶段4
某 公 司
经过枚举计算： 从始点 S1到终点ST共有3×3×2×1=18条不同路线。 1 1 此问题的最短路：( S1 → S 2 → S33 → S 4 → ST )，该最短路的长度为11。
14 石家庄经济学院 管理科学与工程学院
小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量k﹑状态变量sk﹑决策变量xk; 方程 :状态转移方程 sk 1 Tk ( sk , xk ) 指标: Vk ,n Vk ,n (sk , xk , sk1 , xk1,, sn1 )
3 1 1 3 3 v3 ( S3 , S 4 ) f 4 ( S 4 ) f3 ( S ) min min 6 3 2 2 3 4 v ( S , S ) f ( S ) 3 3 4 4 4 3 3
石家庄经济学院 管理科学与工程学院
9
第二节 动态规划原理
一、动态规划的基本概念
• 阶段变量：k
将决策全过程按时空顺序划为若干阶段 用k表示阶段变量，阶段编号为顺序编号
• 状态变量：sk(i)
状态表示过程发展中某阶段的起始状况 描述各阶段状态演进的变量，称为状态变量，用Sk表示 • 第 k 阶段可能有若干状态，用Sk 表示阶段k的状态集合 • sk(i)表示第k阶段的第 i 个状态 选取的状态变量必须满足无后效性
Vk ,n vi ( si , xi )，过程指标等于各阶段指标之和
i k n
基本方程：f k ( sk ) opt vk ( sk , xk ) f k 1 ( sk 1 ) xk X k ( Sk ) 边界条件：f n 1 ( sn 1 ) 0
“静态”决策问题，就其本质而言是一次决策问题，是非动
态决策问题，但是也可以人为地引入阶段的概念当作多阶段 决策问题，应用动态规划方法加以解决。
6 石家庄经济学院 管理科学与工程学院
第一节 多阶段决策
例3 资源分配问题：便属于这类静态问题。如：
某工业部门或公司，拟对其所属企业进行稀缺资
源分配，为此需要制定出收益最大的资源分配方
• 状态转移方程：sk+1 =T(sk, xk(sk))
下一阶段状态sk+1 是本阶段状态sk 和决策xk的函数
sk+1 =T(sk, xk(sk)) =T(sk, xk)
状态sk演进到下一阶段状态sk+1的转移规律称状态转移方程
11
石家庄经济学院
管理科学与工程学院
第二节 动态规划原理
一、动态规划的基本概念