- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
5
A 3
B1
6
8 B2 7
C2
5
D2 1 2
2
E2
5
2
F1
4
G 3
C3
C4
3
8 4 D3
3
3 4 E3
6
6
F2
1
2
3
5
6
例
2 A 4
B1
1 D
C3
解：整个过程分三个阶段，从最后一个阶段开始。 第一步（C →D）： C 有三条路线到终点D 。 显然有 f1 (C1 ) = 1 ；f1(C2 ) = 3 ；f1 (C3 ) = 4
2 1
3 2 A 4 B2 B1 2 1 3
C1
C2 4 C3 3
1 D
3 1
第三阶段（ A → B ）： A 到B 有二条路线。 ∴ f3 (A) = min d(A, B1 )＋ f2 ( B1 ) = min｛6,7｝=6 d(A, B2 )＋ f2 ( B2 ) (最短路线为A→B1→C1 →D)
f ( x ) max kx f ( x ) 基本方程： k k k k 1 k 1 x D ( s )
基本方程的具体形式
模型：max
z x1 2 x2 3x3 kxk
k 1
3
f (x ) 基本： k k
具体：
xk Dk ( s k
3 2 A 4 B2 B1 2 1 3
C1
C2 4 C3 3
1 D
3 1
d( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min d( B2,C2 ) + f1 (C2 ) = min 3+3 d( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B →C →D) 2 1 5 f ( B )=4
当k=3时：
s3 3 * f 3 ( s3 ) max 3x3 s3 , x3 0 x3 s3 / 2 2 2
图示如下：
s1 u1 1 s2 u2 2 s3 sk uk k sk+1
能用动态规划方法求解的是一类特殊 的多阶段决策过程，即具有无后效性(马 尔可夫性)的多阶段决策过程。 如果某阶段状态给定后，则在这个阶 段以后过程的发展不受这个阶段以前各段 状态的影响；过程的过去历史只能通过当 前的状态去影响它未来的发展。
5.2 动态规划的基本概念
1、阶段：
把一个问题的过程分为若干个相互联系 的阶段，以便于按一定的次序去求解。 描述阶段的变量称为阶段变量。阶段的 划分，一般是根据时间和空间的自然特征 来进行的，但要便于问题转化为多阶段决 策。 年、月、
路段
2、状态：表示每个阶段开始所处的自 然状况或客观条件。通常一个阶段有若 干个状态，描述过程状态的变量称为状 态变量。
动态规划有更多成果
(C1,4) B1 3 1 3 1 (D,1) C1 1 3 4 D
(B1,6) A
2
(C1,3) 2 3 B2 4
(D,3) C2
(D,4) C3
动态规划不仅得到A-D的最佳路径，中间结点的最佳路径 也同时得到，比如B1-D的最佳路径。 枚举法只能得到A-D的最佳路径，如果要得到所有中间 最有路径，需要更多的排序计算。
max
z x1 2 x2 3x3 kxk
k 1
3
偶然的
-状态转移方程与基本方程-设状态变量为sk，表示阶段决策变量的取值范围
x1 3x2 2 x3 12
递推方程： s1=12 ; s2=s1-x1 ; x1 x2 s2/3
s3=s2-3x2 ;
k
x3
k k
s3/2
2 1
DP建模要点 1、正确选择状态变量 选择变量既要能确切描述过程演变又 要满足无后效性。 2、确定决策变量及允许决策集合 通常选择所求解问题的关键控制变量 作为决策变量，同时要给出决策变量的取 值范围，即确定允许决策集合。
4、确定状态转移方程
根据k 阶段状态变量和决策变量，写出 k+1阶段状态变量，状态转移方程应当具有 递推关系。 5、确定阶段指标函数和最优指标函数， 建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最 优指标函数是指从第k 阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动 态规划基本方程。
按过程演变的特征，动态规划模型划分
为确定性模型和随机性模型两大类。 根据状态变量的取值是离散还是连续， 它们又可区分为连续和离散两类。 因此有离散确定性模型，连续确定性模 型，离散随机性模型和连续随机性模型 四大类。
-例 用动态规划求解非线性规划问题max z x1 2 x2 3 x3 x1 3 x2 2 x3 12 xi 0 解： x1,x2,x3三变量依次取值，所以可划分出 3个阶段,k=1,2,3；xk为决策变量；
5、策略 是一个按顺序排列的决策组成的集合。
u1 (s1 ),u2 (s2 ),...,uk (sk ),...,un (sn )
在实际问题中，可供选择的策略有一定 的范围，称为允许策略集合。
uk (sk ) Dk (sk )
从允许策略集合中找出达到最优效果 的策略称为最优策略。
6、指标函数
max
kx k )
f k 1 ( xk 1 )
f 3 ( s3 ) max3 x3 f 2 ( s2 ) max2 x2 f 3 ( s3 ) f1 ( s1 ) maxx1 f 2 ( s2 )
x1D1 x2 D2 x3 D3
逆推：相对于前面状态的最优
第5章 动态规划
2008.2.29
5.1 动态规划的基本原理
许多问题属于动态系统，随时间或空间变 化。 1951年美国Bellman提出了最优化原理。 动态规划-DP是解决多阶段决策问题的一种 方法：根据问题的空间或时间特性将过程分为若 干阶段, 在每一阶段中都需作出决策,这种连续 不断的作出的多阶段决策,构成一个策略。
(5,G) F 1 3 2 I (6,G) 4
(4,B) G 4 B K 3
(9,F)
(3,B)
问题复杂度
(C1,4) (B1,6) A 2 B1 1 3 3
(D,1) C1
(D,3) C2 (D,4) C3 3
1
D
(C1,3) 2 3 4 B2 1
4
如果枚举所有路径，共（2*3*1）=6条路径 需要计算3*（2*3*1）=18次加 5次比较 动态规划：2*3+2=8次加 2*（3-1）+1=5次比较
(D,1) (C1,4) (B1,6) A 2 B1 3 3 1 C1 (D,3) C2 (D,4) C3 4 3 D 1
(C1,3) 2 3 4 B2 1
最短路线为 A→B1→C1 →D 路长为 6
课堂练习
6 1 3 6 A 5 4 H 5 I 2 4 K 3
4
E
F
G
4 B
(11,F) 4 (14,H) A 5 E 6 4 H 5 6
4、状态转移方程
s2 T1 ( s1 , u1 ) s3 T2 ( s1 , u1 , s2 , u2 ) sk 1 Tk ( s1 , u1 , s2 , u2 ,, sk , uk )
状态转移方程确定过程由一个状 态到另一个状态的演变过程。如 果第k阶段状态变量sk的值、该阶 段的决策变量uk一经确定，第k+1 阶段状态变量sk+1的值也就确定。
B A
C
D E F
o
注意避免歧义
相对于前面的决策所形成的状态 而言， 余下的决策序列必然构成最优子策略。
(C1,4) B1 3 1 3 1
(D,1) C1
(D,3) C2 (D,4) C3 3 4
(B1,6) A
2
1 D
(C1,3) 2 3 B 4 2
B1-C1-D不是阶段2到阶段4的最佳路径，但对于 A来说，B1-C1-D形成最优子策略。
状态变量的取值有一定的允许集合 或范围，此集合称为状态允许集合。
3、决策：表示当过程处于某一阶段 的某个状态时，可以作出不同的决定， 从而确定下一阶段的状态，这种决定称 为决策。 描述决策的变量，称为决策变量。 决策变量是状态变量的函数。可用一个 数、一组数或一向量来描述。 在实际问题中决策变量的取值往往 在某一范围之内，称为允许决策集合。
3
2 A 4 B2 B1 2 1 3
C1
C2 4 C3 3
1 D
3 1
第二步（B →C）： B 到C 有六条路线。
d( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min d( B1,C2 ) + f1 (C2 ) = min 3+3 d( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5
(4)状态转移方程：
Vt 1 Vt Qt Pt xt WS t Et , t 1,2, N
(5)指标函数：t阶段的指标函数为该阶段的供水 效益，如发电效益,可表示为rt(vt,xt).
max Z rt (Vt , xt ) ( gHx )
t 1 N
指标的最优化
vi vi ( si , ui )
Vk ,n vi ( si , ui )
i k n
f (s ) opt v (s , u
k k k k u k Dk ( s k )
k
) f k 1 ( sk 1 )
Vk ,n vi ( si , ui )
