Operational Research
23
动态规划的数学模型
动态规划的函数方程
f k ( xk ) opt
{ Dk S k }
rk Sk , xk rk 1 Sk 1, xk 1 rn Sn , xn
f k ( xk ) opt
{ Dk S k }
• 动态规划方法丌能解决所有的多阶段决策问题，只解决符合无后效性
的问题
• 无后效性：指系统从某个阶段往后的发展演变，完全由系统本阶段所
处的状态不策略决定，不系统以前的状态及决策无关
xk (Sk )
xk (Sk , Sk 1 )
Operational Research
7
动态规划方法的术语
（一）阶段
注意：最优性原理起作 用了！ d C1 , D1 f 4 D1 2 3 C1状态下： f 3 C1 min min 5 5 5 d C1 , D2 f 4 D2
C1 B1 A 4 3 B2 3 5 B3
5
4 C2 5 6 5 2 2 C4 C3 3 2 1
D2状态下： f 4 D2 d D2 , E f5 E 5 0 3
C1 B1 A 4 3 5 B3 B2 3 5 7 5 5 4 6 C3 C2 5 3 2 1 D2 7 C4 2 6
D1
3 E
5
2
2
Operational Research
动态规划中的最短路问题
xk (Sk )
表示k阶段，Sk状态下决策选择
策略：从初始阶段到终止阶段，系统的每个阶段都有一个决策，将多个 决策按顺序排列组成的序列或集合，称为系统的一个策略
Operational Research
10
动态规划方法的术语
（四）状态转移方程(state transfer equation)
对于无后效性的多阶段决策过程，系统由k到k＋1的状态转移方程是
2 6 D1
7
3
E
5
5
D2 7
Operational Research
动态规划中的最短路问题
6 3 2 3 C 2状态下： f 3 C2 min 8; C3状态下： f 3 C3 min 5 3 5 1 5 C4状态下： f 3 C4 7 5 12
（五）阶段效应
状态转移了，但是考察什么呢？
• 在阶段k状态为Sk，同时得到一个反映效应的数量指标——rk(sk,xk) • rk完全是由本阶段的状态和效应决定的，可能是利润、成本、距离等 （六）最优指标函数 k阶段到n阶段可获得的效应：
f k ( xk ) opt
{ Dk S k }
rk Sk , xk rk 1 Sk 1, xk 1 rn Sn , xn
B1 A 4 3 5 B3 B2 7 5 2 C2 5 6 5 2 2 C4 C3 3 2 1 D2 7 6 D1 4
3
E
3 5
5
Operational Research
22
动态规划的步骤
（1）划分阶段 （2）确定状态变量及取值范围 （3）确定决策变量及其取值范围 （4）建立状态转移方程 （5）确定阶段效应和最优指标函数 动态规划建模的过程比静态规划更为复杂多变
• 对于一个多阶段决策问题，根据问题的性质和特点，将其划
分为若干个相互联系的部分，各部分按照一定的逻辑关系组 成给定的多阶段决策过程，每一个部分称为一个阶段。
• 阶段变量 k • k＝4
Operational Research
8
动态规划方法的术语
（二）状态 • 多阶段决策中，各阶段的初始状况称为“状态”
• 是一类问题，而非一个问题 • 分为离散确定、连续确定、离散随机、连续随机四类问题
Operational Research
5
动态规划方法
启示 • 我们的生活也许是这一类问题中的一个 • 是每一步都看最短路？还是在整个过程中最优？
Operational Research
6
动态规划方法
• 适用条件
• •
状态变量
sk，每个状态编号sk （1） ， sk （2）……，允许状态集合
、B3，即s3＝
对于例题来说，第一阶段有一个状态A，第二阶段有三个状态B1、B2
｛s3 （1） ， s3 （2）}={C1,C2}
Operational Research
9
动态规划方法的术语
（三）决策与策略 决策：当某个阶段状态给定后，从该状态演变到下阶段某种状态的选择 决策变量：描述决策的变量，称为决策变量。决策变量是状态变量的函 数，通常表示为
• •
Operational Research
3
举例
交通网络图
•
两点之间的数字表示距离，试求从起点到终点的最短距离
Operational Research
4
多阶段决策问题总结
多阶段决策问题
• 这些问题可以划分成几个相互联系的阶段，每个阶段都有若
干方案可供选择，而决策的任务是在每个阶段选择一个适当 的方案，使整个过程取得最优效果
B1 A 4 3 5 B3 B2 7 5 2 C2 5 6 5 2 2 C4 C3 3 2 1 D2 7 6 D1 4
3
E
3 5
5
Operational Research
动态规划中的最短路问题
4 10 A状态下： f1 A min3 10 12 5 7C1
rk Sk , xk f k 1 ( xk 1 )
f n1 Sn1 0or1 加法运算时取 0，乘法运算时取 1
Operational Research
24
动态规划的求解方法
逆序解法：backward induction 顺序解法：forward induction
Operational Research
Operational Research
动态规划中的最短路问题
设从A到E铺设输油管道,中间经过三个站。
•几个阶段？每阶段各有几个状态？几种决策？效应指标r与最优指标 函数f？ C1
B1
4 A 3 5 B2 3 5 5 2 7 5 2
4
6 C3
C2
3 2Байду номын сангаас
5 6
D1 3 E
1
5
D2 7
C4
B3
2
Operational Research
B1
2 6 D1
4 A 4 3 5 B3 B2 7 6 5 2 2 C4
C2 5 3 2 1
3
E
C3
3 5
5 D2 7
Operational Research
动态规划中的最短路问题
4 10 A状态下： f1 A min3 10 12 5 7C1
13
动态规划方法的术语：最优性原理
最优性原理
• “作为整个过程的最优策略具有这样的性质：无论过去的状态和决策
如何，相对于前面决策所形成的状态而言，余下的决策序列必然构成
最优子策略。”
• 这是处理动态规划这一“类”问题的基础性原理
A-B3-C3-D1-E 如果是最优策略，
单独看C3-D1-E，一定是C3和E之间的最优策略
S 2 T1 (S1 , x1 S1 ) S3 T2 ( S 2 , x2 S 2 ) S k 1 Tk ( S k , xk S k )
x1 1 S1
x2 2 S2
即：下一阶段的状态是由本状态和本状态下的决策确定的
Operational Research
11
动态规划方法的术语
动态规划中的最短路问题
E状态下： f5 E 0
C1
E之后最优是0
B1
4 A 3 5 B2 3 5 7
5
2
4
6 5 2 C3
C2
3 2
5 6
D1 3 E
1
5
D2 7
C4
B3
2
Operational Research
动态规划中的最短路问题
D1状态下： f 4 D1 d D1 , E f5 E 3 0 3
Operational Research
12
动态规划方法的术语：最优性原理
最优性原理
• “作为整个过程的最优策略具有这样的性质：无论过去的状态和决策
如何，相对于前面决策所形成的状态而言，余下的决策序列必然构成
最优子策略。”
• 这是处理动态规划这一“类”问题的基础性原理
Operational Research
25
动态规划可以求解哪些问题
• 运输路线 • 工序安排 • 库存管理 ……
Home
Operational Research 动态规划
2011.12
ZHU Tong Chang’an University E-mail: zhutongtraffic@
Operational Research
2
什么是动态规划问题
问题 —— 方法
•
前面研究的优化问题，没有随着时间的变化而变化。其解法， 如线性规划、整数规划等方法通称为“静态规划方法”，丌存在 阶段的概念 事实上，很多问题是“多阶段的决策问题” “动态规划方法”是处理“多阶段决策问题”的方法
C1 B1 A 4 3 5 B3 B2 7 5 4 6 5 2 2 C4 C3 C2 5 3 2 1 D2 7 2 6 D1
3
E
3 5
5
Operational Research