当前位置:文档之家› 运筹学04动态规划1-123页文档

运筹学04动态规划1-123页文档


s3 ... sk
阶段k
状态
状态
sk+1 ... sn
阶段n
状态 sn+1
g1
g2
gk
gn
例1(不定阶段最短路线问题)
如图是一个五座城市的及其相连道路的交通图,线上的数字是对应的路 长。问:应如何选择行驶路线,才能使从A、B、C、D各城市到E城市的行 驶路程最短?
E
2
3
2
A
D
7
5
6
5
5
1
B
C
0.5
2 状态(State)
各阶段开始时的客观条件叫做状态。描述各阶段 状态的变量称为状态变量,常用sk表示第k阶段的状 态变量,状态变量的取值集合称为状态集合,用Sk 表示。状态集合可以是一离散取值的集合,也可以为 一连续的取值区间,视具体问题而定。
按照过程进行的先后,每个阶段的状 态可分为初始状态和终止状态,或称
fk(Sk)为当第k阶段初始状态为Sk时,从第k阶段 到最后阶段所得最大利润。
fk(Sk)=Max rk(dk) + fk+1(Sk+1)
dk (Sk)
k=1,2,3
f4(S4)= 0
k=3 时, 计算如下:
d d S3 f3(S3)
* 3
S3
f3(S3)
* 3
0 0 03 9 3
1 4 1 4 10 4
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
例 设备更新问题
企业在使用设备时都要考虑设备的更新问题,因 为设备越陈旧所需的维修费用越多,但购买新设备 则要一次性支出较大的费用。
多阶段决策问题
(Multi-Stage decision process)
多阶段决策过程特点:
决策d1
决策d2
决策dk
决策dn
状态 s1
阶段1
状态 s2
阶段2
状态
状态
在上面的计算过程中,利用了第k阶段与第k+1阶 段的关系:
fk(Sk)= Min r(Sk,dk(Sk))+fk+1(Sk+1)
dk(Sk)
k=1,2,3,4,5
f6(S6)=0
这种递推关系称为动态规划的函数基本方程。
贝尔曼(Ballman)最优化原理
作为整个过程的最优策略具有这样的性质:即无论 过去的状态和决策如何,对前面的决策所形成的状态 而言,余下的诸决策必须构成最优策略。这就是说, 不管引导到这个现时状态的头一个状态和决策是什么, 所有的未来决策应是最优的。
1.从A城市直达E城市,一个阶段。
2.从A城市通过其他B、C、D三城市之一到E城市,二个阶 段。 3.从A城市通过其他B、C、D三城市之二到E城市,三个阶 段。 4.从A城市通过其他B、C、D三城市各一次到E城市,四个 阶段。
例2(一定阶段最短路问题)
W先生每天驾车去公司上班。如图,W先生的住所位于A,公司位于F,图中的直线段代表公 路,交叉点代表路口,直线段上的数字代表两路口之间的平均行驶时间。现在W先生的问题是 要确定一条最省时的上班路线。
•正确地选择状态变量,使其具备两个必要特征:
(1)可知性:即过去演变过程的各阶段状态变量的取 值,能直接或间接地确定。
(2)能够确切地描述过程的演变且满足无后效性。
建立动态规划模型的要点:
•根据状态变量与决策变量的含义,正确写出状态转移
0
0000
1
5141
2
10 2 7 2
3
14 2,3 9 3
4
18 3 10 4
5 22 3 21 3 11 5
建立动态规划模型的要点:
•分析题意,识别问题的多阶段性,按时间或空间
的先后顺序适当地划分满足递推关系的若干阶段, 对非时序的静态问题要人为地赋予“时段”的概 念。
建立动态规划模型的要点:
2 7 9 10 - - - 10 2 3 9 12 14 14 - - 14 2,3, 4 10 14 17 18 16 - 18 3 5 11 15 19 21 20 16 21 3
k=1 时, 计算如下:
最优解:d*1 =3, d*2 =2,d*3 =0
即:在区1建3个分店,在区2建2个分店,而不在 区3建立分店。最大总利润=22。
动态规划数学模型由最优指标函数递推表达式、边界条件及状态转移方程构成。
fk(sk) Opt {rk(sk,dk}fk1(sk1)}, k1,2, ,n fn(sn)0dkDk(sk) sk1 Tr(sk,dk)
动态规划的优点:
•可把一个N维优化问题化成N个一维优化问题求解。 •DP方程中附加某些约束条件,可使求解更加容易。 •求得最优解以后,可得所有子问题的最优解。
3 决策和策略
(Decision and Policy)
当各段的状态确定以后,就可以做出不同的决定 (或选择),从而确定下一阶段的状态,这种决定 称为决策。决策变量用xk(Sk)表示,允许决策集合 用Dk(Sk)表示。
各个阶段决策确定后,整个问题的决策序列就构 成一个策略,用p1,n(x1,x2,…xn)表示。对每个实 际问题,可供选择的策略有一定的范围,称为允许 策略集合,用P表示。使整个问题达到最优效果的策 略就是最优策略。
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
C3
B2
2
2
3
C2
5
3
B1
4
C1
3
D3
5
E2
3
2
D2
4
F
4
2
E1
D1
A
B
C
D
E
F
4
A
3
4
1
4 状态转移方程
动态规划中本阶段的状态往往是上一阶段的决 策结果。如果给定了第k段的状态Sk ,本阶段决 策为xk(Sk) ,则第k+1段的状态Sk+1由公式: Sk+1=Tk( Sk, xk)
确定,称为状态转移方程。
5 指标函数
用于衡量所选定策略优劣的数量指标称为指标函数
v(Sk,xk(Sk))。
第四章 动态规划
Dynamic Programming
本章内容重点
多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划方法的基本步骤 动态规划方法应用举例
动态规划是解决多阶段决策过程最优化问题的一 种方法。由美国数学家贝尔曼(Bellman)等人在 20世纪50年代提出。他们针对多阶段决策问题的特 点,提出了解决这类问题的“最优化原理”,并成功 地解决了生产管理 、 工程技术等方面的许多实际问 题。
C3 4 D3
5 E2
2F
1
2
3
4
B2 2 C2 3 D2
E1
4
5
3
2
A3
B1 4 C1 3
D1
动态规划的基本概念 阶段; 状态; 决策和策略; 状态转移; 指标函数。
1 阶段(Stage)
将所给问题的过程,按时间或空间特征分解成若 干个相互联系的阶段,以便按次序去求每阶段的解。 用以描述阶段的变量叫作阶段变量,一般以k表示阶 段变量。
输入状态和输出状态,阶段k的初始 状态记作sk,终止状态记为sk+1。但
为了清楚起见,通常定义阶段的状态 即指其初始状态。
动态规划中的状态具有如下性质:
当某阶段状态给定以后,在这阶段以后的过程的 发展不受这段以前各段状态的影响。即:过程的过去 历史只能通过当前状态去影响它未来的发展,这称为 无后效性。如果所选定的变量不具备无后效性,就不 能作为状态变量来构造动态规划模型。
相关主题