当前位置:首页 >> 数学 >>

运筹学动态规划


动态规划

第1页

1.动态规划的产生 动态规划是运筹学的一个重要分支,它是解决多阶 段决策过程最优化的一种数学方法。 动态规划产生于20世纪50年代初,由美国数学家贝

尔曼(R. Bellman)等人提出。
第2页

(1)把多阶段决策问题 → 多个互相联系的单阶段

问题,逐个解决。

(2)提出最优性原理,并成功解决了生产管理、工

程技术等方面的多个实际问题。
第3页

2. 动态规划的特点 (1)没有一个标准的数学表达式和明确定义的一组
规则,必须对具体问题进行具体分析处理(线性规 划有标准的数学表达式,任何线性规划问题都可以 利用单纯形法进行求解)。
第4页

(2)动态规划是考查问题的一种途径,而不是一种

特殊算法。

(3)许多问题,特别是离散性问题,用动态规划方

法去处理,常比线性规划和非线性规划更有效。

第5页

3. 动态规划模型的分类 根据动态规划模型中的时间参量是离散变量还是连 续变量:

(1)离散型。
(2)连续型。
第6页

根据动态规划模型中的各类参数是已知的还是未

知的:

(1)确定型。

(2)随机型。

第7页

离散确定型动态规划模型 离散随机型动态规划模型 动态规划模型 连续确定型动态规划模型

连续随机型动态规划模型
本章主要针对离散确定型问题和连续确定型问题,

介绍动态规划的基本思想、原理和方法。
第8页

? 第一节 多阶段决策过程和动态规划方法

? 第二节 动态规划的基本概念和基本原理 ? 第三节 动态规划模型的建立与求解 ?第四节 动态规划基本方程的分段求解算法 ? 第五节 动态规划在经济管理中的应用
第9页

第一节 多阶段决策过程和动态规划方法

一、多阶段决策过程的定义
在生产和科学实验中,有一类特殊的活动过程,它

们可以按时间顺序分解成若干个相互联系的阶段,
而每一个阶段都要做出决策,当每个阶段的决策都 确定后,就形成一个决策序列。
第10页

这种由前后相互联系、具有链状结构的多个阶段所

组成的活动过程称为多阶段决策过程。

决策 决策 状态 状态 状态 2 1

决策 状态 …… 状态 n

第11页

二、多阶段决策过程和动态规划方法
多阶段决策过程的特点:
1. 本阶段的决策依赖于本阶段面临的状态; 2. 本阶段的决策决定着下一阶段的状态(即引起状 态的转移);
第12页

决策序列就是在变化的状态中产生的,故有“动态”

的含义,从而把处理这种多阶段决策过程的方法称

为动态规划方法。

第13页

第二节 动态规划的基本概念和基本原理 一、动态规划的基本概念
使用动态规划方法解决多阶段决策过程问题,首先 要将实际问题写成动态规划模型,此时就要用到以 下几个概念:
第14页

1. 阶段

(1)阶段 为了把问题转化为多阶段决策过程,一般根据时间
或空间的自然特征将问题分解成若干个互相联系的 阶段,以便能按一定的次序去求解。
第15页

(2)阶段变量

描述阶段的变量,常用字母 k 表示第 k 阶段。
C1

5

B1

1 3 6

6 8 3 3 5 8 4 5

D1

C2

2 2
1 2 3 3

D2

A

3

8 7 B2 6

C3

C4

D3

3 5 5 E2 2 6 6
E1
E3

F1

4
3
G

F2

第16页

例:从 A 到 G 可以分成: (1)从 A 到 B(B有两种选择B1,B2) (2)从 B 到 C(C有四种选择C1,C2,C3,C4)

(3)从 C 到 D(D有三种选择D1,D2,D3)
(4)从 D 到 E(E有三种选择E1,E2,E3)

(5)从 E 到 F(F有两种选择F1,F2)
(6)从 F 到 G 六个阶段。 k = 1, 2, 3, 4, 5, 6。
第17页

2. 状态 (1)状态 各阶段开始时所处的自然状况或客观条件。 通常一个阶段有若干个状态。 (2)状态变量 描述各阶段状态的变量,常用 sk 来表示第 k 阶段的 状态变量。
第18页

(3)状态变量集合

各阶段状态变量的集合,常用 Sk 来表示第 k 阶段状

态变量 sk 的取值集合。

第19页

(4)状态变量的无后效性(马尔科夫性) 如果某阶段状态确定后,则以后各阶段的决策仅同

该阶段的状态有关,而同该阶段以前各阶段的状态
无关。(即仅仅根据该阶段的状态就可以对以后各 阶段进行决策了。)

注意:如果所选择的状态变量不满足无后效性,则
不能构造动态规划模型。
第20页

例:
1 3 6
C1

6 8

5 A 3

B1

C2 C3

3
3

D1

5
D2

2 2 1 2 3

8 7 B2 6

5

8
C4

4

D3

3

3 5 5 E2 2 6 6
E1 E3

F1

4 3
G

F2

设定每个阶段的出发位置为该阶段的状态变量。
第21页

因为每个阶段的出发位置选定后,从该位置以后的

铺管路线只与该位置有关,不受以前铺管路线的影

响,所以满足状态的无后效性,故可以作为状态变

量。
第22页

从 A 到 G 可以的 6 个阶段的状态分别为:

S1={A}:第一阶段只有一个状态 A S2={B1,B2}:第二阶段有两个状态B1、B2

S3={C1,C2,C3,C4}:第三阶段有四个状态C1、C2、
C3 、 C4
第23页

S4={ D1,D2,D3}:第四阶段有三个状态D1、D2、D3

S5= { E1,E2,E3}:第五阶段有三个状态E1、E2、E3

S6 = { F1,F2}:第六阶段有二个状态 F1、F2
第24页

3. 决策 (1)决策 当某阶段的状态确定以后,就可以作出不同的决定 (或选择),从而确定下一阶段的状态,这种决定

称为决策。
第25页

(2)决策变量

描述决策的变量,常用 uk(sk) 表示第 k 阶段状态为

sk 时的决策变量,它是状态变量的函数。

第26页

(3)允许决策集合

决策变量的取值范围,常用 Dk(sk) 表示第 k 阶段状

态为 sk 时的允许决策集合,显然 uk(sk) ∈ Dk(sk)。

第27页

例:

从第二阶段的状态 B1 出发,可选择下一阶段的C1、 C2、C3,即允许决策集合为:D2(B1)= {C1,C2,C3};

若选择点C2,则该决策可表示为:u2(B1)=C2

第28页

4. 策略

(1)全过程
一个 n 阶段决策过程,从第 1 阶段开始到第 n 阶段 终止的过程。 (2)后部子过程或 k 子过程 一个 n 阶段决策过程,从第 k 阶段开始到第 n 阶段 终止的过程。
第29页

(3)全过程策略(简称策略)
一个 n 阶段决策过程,从第 1 阶段开始到第 n 阶段 为止的各阶段的决策按顺序排列组成的集合,记作 p1,n ( s1 ) = { u1(s1) , u2(s2) , …… ,un(sn) } ={ s1 , u1 , s2 , u2 , …… , sn , un , sn+1 } 。
第30页

(4)后部子过程策略或 k 子过程策略(简称子策略) 一个 n 阶段决策过程,从第 k 阶段开始到第 n 阶段 为止的各阶段的决策按顺序排列组成的集合,记作 pk,n ( sk ) = { uk(sk) , uk+1(sk+1) , …… , un(sn) }

={ sk , uk+1 , sk+1 , uk+1 , …… , sn , un , sn+1}。
第31页

(5)允许策略集合

在实际问题中,可供选择的策略有一定的范围,此
范围称为允许策略集合。 (6)最优策略 从允许策略集合中找出达到最优效果的策略称为最

优策略。
第32页

5. 状态转移方程 状态转移方程 —— 由一个阶段的状态到下一个阶段 的状态的演变过程。

动态规划中,本阶段的状态往往是上一阶段状态和 上一阶段决策的结果。
第33页

由第 k 阶段到第 k+1 阶段的状态转移方程:

第 k 阶段的状态 sk 和决策 uk(sk) 一旦确定,则第

k+1 阶段的状态 sk+1 也就完全确定,即

sk+1 = Tk ( sk , uk(sk) ),其中 Tk 称为状态转移函数。
第34页

例:
C1

5
A 3

B1

1 3 6

6 8 3

D1

C2
C3

5
D2

2 2

3 5
8 4

8 7 B2 6

1 2
3 3

C4

D3

3 5 5 E2 2 6 6
E1 E3

F1

4

3
F2

G

状态转移方程为: sk+1 = uk(sk)
第35页

6. 指标函数
(1)过程指标函数定义 用于衡量所选定策略优劣的数量指标,常用 Vk,n 表 示之,即 Vk,n= Vk ,n ( sk , uk , sk ?1 , uk ?1 ,...,sn , un , sn?1 ) ,k=1,2,…,n
第36页

Vk ,n ( sk , uk , sk ?1 , uk ?1 ,...,sn , un , sn?1 ) 表示从第 k 阶段

的状态 sk 开始,到第 n 阶段终止的过程,采取策

略 pk, n = { sk , uk , sk ?1 , uk ?1 ,...,sn , un , sn?1 } 时的数量指

标值。
第37页

(2)过程指标函数的含义
注意:不同的问题中,指标函数的含义是不同的, 它可能是距离、利润、成本、产品的产量或资源消

耗等。
例:在最短路线问题中过程指标函数
n(sk,uk,…,sn+1)

Vk,

表示在第 k 阶段由点 sk 至终点 sn+1 的
第38页

距离。

(3)过程指标函数的可分离性和递推关系 构成动态规划模型的过程指标函数要具有可分离性, 必须满足递推关系,即 Vk, 可以表示为 sk 、uk 、

n

Vk+1,n的函数,记为:

Vk ,n ( sk , uk ,.., sn?1 ) ? ? k [sk , uk ,Vk ?1,n ( sk ?1 , uk ?1 ,.., sn?1 )]
第39页

(4)常见过程指标函数的形式

① 过程指标函数为阶段指标函数的和形式,即
n

Vk ,n ( sk , uk ,.., sn?1 ) ? ? v j ( s j , u j )
j?k

式中 v j ( s j , u j ) 表示第 j 阶段的指标函数值。

第40页

Vk ,n ( sk , uk ,.., sn?1 ) ? vk ( sk , uk ) ? Vk ?1,n ( sk ?1 , uk ?1 ,.., sn?1 )

满足递推关系

第41页

② 过程指标函数为阶段指标函数的积形式,即

Vk ,n ( sk , uk ,.., sn?1 ) ? ? v j ( s j , u j )
j?k

n

Vk ,n ( sk , uk ,..,sn?1 ) ? vk ( sk , uk )Vk ?1,n ( sk ?1 , uk ?1 ,..,sn?1 )

满足递推关系
第42页

例:在最短路线问题中:

过程指标函数 Vk, n(sk, uk,…, sn+1):表示从第 k 阶段

的点 sk 到终点 sn+1 的距离。
第43页

阶段指标函数 dk (sk , uk) :第 k 阶段由点 sk 到点 uk(sk)

= sk+1 的距离。

Vk, n(sk, uk,…, sn+1)= dk(sk , uk)+ Vk+1,n(sk+1, uk+1,…, sn+1)

第44页

7. 最优指标函数

最优指标函数:过程指标函数的最优值,记为 fk(sk),

它表示从第 k 阶段的状态 sk 开始,到第 n 阶段终止

的过程,采取最优策略时的数量指标值。
第45页

f k (sk ) ? opt Vk ,n ( sk , uk ,...,sn , un , sn?1 )
{ uk ,..., n } u

V ?m ax{ k ,n ( sk , uk ,...,sn , un , sn?1 )}? ? ? ?? ? V ?m i n { k ,n ( sk , uk ,...,sn , un , sn?1 )} ? ? ?
式中 opt(optimum)表示最优化,根据具体问题取
min或max。
第46页

例:在最短路线问题中用最优指标函数 fk(sk) 表示

从第 k阶段点 sk 到终点 G 的最短距离。

f4(D1) 表示从第 4 阶段中的点 D1 到点 G 的最短距离。

第47页

二、动态规划的基本方程
1. 例子
6 8 3

5
A 3

B1

1 3 6

C1

D1

C2
C3

5
D2

2 2

3 5
8 4

8 7 B2 6

1 2
3 3

C4

D3

3 5 5 E2 2 6 6
E1 E3

F1

4

3
F2

G

第48页

求解:

第一步:当 k = 7,S7 = { G } → f7(G)=0

第二步:当 k = 6,S6={F1, F2} →

第49页

s6=F1时:f6(F1) = d6 ( F1 , G) ? f 7 (G) ? 4 ? 0 ? 4

→ F1 到 G 最短距离为 4

u6(F1)=G,s7=G

线路为F1G
第50页

s6=F2时:f6(F2) = d6 ( F2 , G) ? f 7 (G) ? 3 ? 0 ? 3

→F2 到 G 最短距离为 3

u6(F1)=G,s7=G

线路为F2G
第51页

第三步:当k = 5,S5={E1, E2, E3} →
?d 5 ( E1 , F1 ) ? f 6 ( F1 ) ? ? 3 ? 4? s5=E1时:f5(E1)= min? ? ? min? ??7 ? 5 ? 3? ?d 5 ( E1 , F2 ) ? f 6 ( F2 )?

→ E1 到 G 最短距离为 7 u5(E1)=F1,s6=F1 线路为E1 F1G
第52页

?d 5 ( E2 , F1 ) ? f 6 ( F1 ) ? ?5 ? 4 ? s5=E2时:f5(E2)= min? ? ? min? ??5 ? 2 ? 3? ?d 5 ( E2 , F2 ) ? f 6 ( F2 )?

→ E2 到 G 最短距离为 5

u5(E2)=F2,s6=F2

线路为E2 F2G
第53页

?d 5 ( E3 , F1 ) ? f 6 ( F1 ) ? ?6 ? 4 ? s5=E3时:f5(E3)= min? ? ? min? ??9 ? 6 ? 3? ?d 5 ( E3 , F2 ) ? f 6 ( F2 )?

→ E3到G最短距离为9

u5(E3)=F2,s6=F2

线路为E3 F2G
第54页

第四步:当 k = 4,S4={ D1, D2, D3 } →
?d 4 ( D1 , E1 ) ? f 5 ( E1 ) ? ? 2 ? 7? s4=D1时:f4(D1)= min? ? ? min? ??7 ? 2 ? 5? ?d 4 ( D1 , E2 ) ? f 5 ( E2 )?

→ D1 到 G 最短距离为 7

u4(D1)=E2,s5= E2
线路为D1E2 F2G
第55页

?d 4 ( D2 , E2 ) ? f 5 ( E2 )? ?1 ? 5 ? s4=D2 时:f4(D2)= min? ? ? min? ??6 ? 2 ? 9? ?d 4 ( D2 , E3 ) ? f 5 ( E3 )?

→ D2 到 G 最短距离为6 u4(D2)=E2,s5= E2 线路为D2E2 F2G

第56页

s4=D3 时:f4(D3)=

?d 4 ( D3 , E2 ) ? f 5 ( E2 )? ? 3 ? 5? min? ? ? min? ??8 ? 3 ? 9? ?d 4 ( D3 , E3 ) ? f 5 ( E2 )?

→ D3到G最短距离为 8 u4(D3)=E2,s5= E2 线路为D3 E2 F2G
第57页

第五步:当 k =3,S3={C1,C2,C3,C4} →
?d 3 (C1 , D1 ) ? f 4 ( D1 ) ? ?6 ? 7 ? s3=C1时:f3(C1)= min? ? ? min? ? ? 13 ?8 ? 6 ? ?d 3 (C1 , D2 ) ? f 4 ( D2 )?

→ C1 到 G 最短距离为 13 u3(C1)=D1,s4= D1, 线路为C1D1E2 F2G
第58页

s3 = C2 时:f3(C2)=

?d 3 (C 2 , D1 ) ? f 4 ( D1 ) ? ?3 ? 7? min? ? ? min? ? ? 10 ?5 ? 6 ? ?d 3 (C 2 , D2 ) ? f 4 ( D2 )?

→C2 到 G 最短距离为10

u3(C2)=D1,s4= D1

线路为C2 D1E2 F2G
第59页

s3= C3时:f3(C3)=

?d 3 (C 3 , D2 ) ? f 4 ( D2 )? ? 3 ? 6? min? ? ? min? ??9 ? 3 ? 8? ?d 3 (C 3 , D3 ) ? f 4 ( D3 )?

→ C3 到 G 最短距离为9

u3(C3)=D2,s4= D2

线路为C3D2E2 F2G
第60页

?d 3 (C4 , D2 ) ? f 4 ( D2 )? ? 8 ? 6? s3= C4 时:f3(C4)= min? ? ? min? ? ? 12 ? 4 ? 8? ?d 3 (C4 , D3 ) ? f 4 ( D3 )?

→C4 到 G 最短距离为12

u3(C4)=D3,s4= D3

线路为C4D3 E2 F2G
第61页

第六步:当k=2,S2={B1,B2 } → s2=B1时:f2(B1)=
?d 2 ( B1 , C1 ) ? f 3 (C1 ) ? ?1 ? 13 ? ? ? ? ? m in?d 2 ( B1 , C 2 ) ? f 3 (C 2 )? ? m in? 3 ? 10? ? 13 ? d ( B , C ) ? f (C )? ?6 ? 9 ? ? ? 3 3 ? ? 2 1 3

→B1到G最短距离为13 u2(B1)=C2,s3= C2 线路为B 1C2 D1E2 F2G
第62页

s2=B2时:f2(B2)=

?d 2 ( B2 , C 2 ) ? f 3 (C 2 )? ?8 ? 10? ? ? ? ? m in?d 2 ( B2 , C 3 ) ? f 3 (C 3 )? ? m in?7 ? 9 ? ? 16 ? d ( B , C ) ? f (C ) ? ?6 ? 12? ? ? 3 4 ? ? 2 2 4

→B2到G最短距离为16

u2(B2)=C3,s3= C3

线路为B2C3D2E2 F2G
第63页

第七步:当k=1,S1={A} →
?d1 ( A, B1 ) ? f 2 ( B1 ) ? ?5 ? 13? s1=A时:f1(A)= min? ? ? min? ? ? 18 ?3 ? 16? ?d1 ( A, B2 ) ? f 2 ( B2 )?

→A到G最短距离为18 u1(A)=B1,s2= B1 线路为AB 1C2 D1E2 F2G
第64页





最优决策={s1,u1,s2,u2,s3,u3,s4,u4,s5,u5, s6,u6,s7}

={ s1=A , u1(A)=B1 , s2=B1 , u2(B1)=C2 , s3=C2 ,
u3(C2)=D1 ,s4=D1 ,u4(D1)=E2 ,s5=E2 ,u5(E2)=F2 , s6=F2,u6(F2)=G,s7=G }
第65页

求解过程分析
从上面的计算过程中可以看出,在各个阶段求解过 程中,利用了k 阶段与 k+1 阶段的递推关系:
d ? f k ( sk ) ? m in { k ( sk , uk ( sk )) ? f k ?1 ( sk ?1 )}, k ? 6,5,4,3,2,1 ? ? ? f ( s ) ? f (G ) ? 0 7 ? 7 7
第66页

2. 动态规划的基本方程 一般情况,k 阶段与 k+1 阶段的递推关系式可以写

成:
? f k ( sk ) ? opt{v k ( sk , uk ( sk )) ? f k ?1 ( sk ?1 )}, k ? n, n ? 1,...,1 ? ? ? f (s ) ? 0 ? n?1 n?1

上述递推关系称为动态规划的基本方程,其中第二
个式子称为边界条件。
第67页

三、动态规划的基本思想
现在把动态规划方法的基本思想总结如下:

1. 将多阶段决策过程划分阶段,恰当地选取状态变
量sk、决策变量uk(sk)、最优指标函数 fk(sk),从 而把问题化成一族同类型的子问题,然后逐个 求解。
第68页

2. 求解时从边界条件开始,逆过程行进方向(或顺 过程行进方向),逐段递推寻优。在每个子问题 的求解时,都要使用它前面已求出的子问题的最 优结果,依次进行,最后一个子问题所得的最优 解,就是整个问题的最优解。
第69页

3. 动态规划方法是既把当前一段与未来各段分开,

又把当前效益和未来效益结合起来考虑的一种最

优化方法,因此每段的最优决策选取是从全局考

虑的,与该段的最优选择一般是不同的。
第70页

4. 在求解整个问题的最优策略时,由于初始状态是

已知的,而每段的决策都是该段状态的函数,故

最优策略所经过的各段状态便可逐次变换得到,

从而确定最优路线。

第71页

u1(A)

u2(B1)

u3(C2)

u4(D1)

u5(E2)

u6(F2)

A

B1

C2

D1

E2

F2

G

第72页

四、动态规划的最优性原理和最优性定理
1. 最优性原理 作为整个过程的最优策略具有这样的性质:即无论 过去的状态和决策如何,对前面的决策所形成的状 态而言,余下的诸决策必须构成最优策略。

即:一个最优策略的子策略总是最优的。
第73页

2. 最优性定理

如果一个决策问题有最优策略,则该问题的最优指 标函数一定可用动态规划的基本方程来表示,反之 亦真。

第74页

最优性定理为人们用动态规划方法处理决策问题提

供了理论依据、并指明了方法:

要充分分析决策问题的结构,使它满足动态规划的

条件,正确地写出动态规划的基本方程。

第75页

第三节 动态规划模型的建立与求解
一、动态规划模型的建立
? 识别问题的多阶段特性,按时间或空间的先后顺 序适当地划分为满足递推关系的若干阶段,对非 时序的静态问题要人为地赋予“时段”的概念。
第76页

? 正确选择状态变量,使其具备:

?各阶段的状态变量取值,能直接或间接地确定,

且能够描述过程的演变。

?状态变量要满足无后效性。
第77页

例如,著名的“货郎担问题”,有 N 个城镇,要求

一个售货员从某城出发,到各城镇去售货,每个城

镇去且仅去一次,最后回到原来的出发城镇,求最

短路线。
第78页

这个问题如果象前面处理最短路问题一样,把城镇

位置作为状态变量,显然不满足无后效性;

如果把含该城镇在内及以前走过的全部城镇的集合

定义为状态,则能实现无后效性。
第79页

?根据状态变量与决策变量的含义,正确写出状态
转移方程 sk ?1 ? Tk ( sk , uk ) 。 ?根据题意确定指标函数、最优指标函数 fk(sk) 、第 k 阶段的指标 vk ( sk , uk ) 的含义。

?正确列出最优指标函数的递推关系及边界条件,
即动态规划基本方程。
第80页

例:某公司有资金10万元,若投资于项目 i(i = 1, 2,

3)的投资额为 xi 时,其收益分别为 g1(x1)=4x1 ,

g2(x2) = 9x2,g3(x3) = 2 x 2 ,问应如何分配投资额才 3 能使总收益最大?
第81页

解:
(1)建立问题的静态模型 这是一个与时间无明显关系的静态最优化问题,可 列出其静态模型:
2 m axz ? 4 x1 ? 9 x 2 ? 2 x 3

? x1 ? x 2 ? x 3 ? 10 ? ? x i ? 0( i ? 1,2,3)
第82页

(2)将问题转化为多阶段决策过程

为了应用动态规划方法求解,需要人为地赋予它
“时段”: 把问题划分为 3 个阶段,每个阶段只确定对一个项 目的投资金额,首先考虑对项目 1 投资,然后考虑 对项目 2 投资,最后考虑对项目 3 投资。

这样问题就转化为一个 3 段决策过程。
第83页

(3)选择决策变量 因为 xi 为每阶段的投资额,故第 k 阶段的决策变量

定义为:
uk = xk :表示第 k 阶段确定的投资额。 uk = xk ,k =1, 2, 3
第84页

(4)选择状态变量
状态变量一般为随递推过程变化的量,这里选取每 阶段可供使用的资金数量,故第 k 阶段的状态变量 定义为: sk:表示第 k 阶段到第 3 阶段可供使用投资使用的 资金数量。(满足无后效性)
第85页

s1 = 10; s 2 = s 1 - u 1;

s3 = s2 - u2 。
即 s1 = 10; s 2 = s 1 - x 1;

s3 = s2 - x 2 。
第86页

(5)状态转移方程

sk ?1 ? sk ? xk

第87页

(6)选择指数函数

Vk,3:表示从第 k 阶段的状态 sk 开始,到第 3 阶段为 止,采取投资策略(xk,…,x3)时所创造的收益。

Vk,3=

? g ( x ) ,k = 1, 2, 3(满足分离性和递推关系)
i?k i i
第88页

3

(7)选择最优指标函数

fk(sk):表示从第 k 阶段的状态 sk 开始,到第 3 阶段

为止,采取最优投资策略(xk ,…,x3 )时所创造

的收益。
第89页

(8)确定动态规划的基本方程

? f k ( sk ) ? max { gk ( xk ) ? f k ?1 ( sk ?1 )}, k ? 3,2,1 0? x k ? sk ? ? ? ? f (s ) ? 0 ? 4 4 ?

第90页

二、逆序解法和顺序解法
动态规划的求解有两种基本方法:

?逆序解法(后向动态规划方法)

?顺序解法(前向动态规划方法)。
第91页

1. 逆序解法(后向动态规划方法) (1)定义 ?寻优的方向与多阶段决策过程的实际行进方向相 反; ?从最后一阶段开始计算,逐段前推; ?计算前一阶段要用到后一阶段的计算结果;

?第一阶段的计算结果就是全过程的最优结果。
第92页

(2)基本方程

第 k 阶段与 k + 1 阶段的递推关系为:

? f k ( sk ) ? opt{v k ( sk , uk ( sk )) ? f k ?1 ( sk ?1 )}, k ? n, n ? 1,...,1 ? ? ? f (s ) ? 0 ? n?1 n?1

第93页

(3)算 例



第94页

2. 顺序解法(前向动态规划方法)
(1)定义 ?寻优的方向与多阶段决策过程的实际行进方向相

同;
?从第一阶段开始计算,逐段后推; ?计算后一阶段要用到前一阶段的计算结果;

?最后一阶段的计算结果就是全过程的最优结果。
第95页

(2)基本方程

第 k 阶段与 k + 1 阶段的递推关系为:

? f k ( sk ?1 ) ? opt{v k ( sk ?1 , uk ( sk ?1 )) ? f k ?1 ( sk )}, k ? 1,2,...,n ? ? ? f (s ) ? 0 ? 0 1

第96页

(3)算例

5 A

B1

1 3 6

C1

6 8 3 3 5 8 4 5

D1

C2 C3

2 2 1 2 3 3

D2

3

8 7 B2 6

C4

D3

3 5 5 E2 2 6 6
E1 E3

F1

4 3
G

F2

第97页

第一步:当 k = 0,S1 = { A } → f0( A ) = 0
第二步:当 k = 1,S2= {B1 , B2} → s2= B1时:f1(B1)= d1 ( B1 , A) ? f0 ( A) ? 5 ? 0 ? 5 → B1 到 A 最短距离为 5 , 决策为 u1(B1) = A,s1= A,

线路为B1A
第98页

s2 = B2时:f1(B2)= d1 ( B2 , A) ? f0 ( A) ? 3 ? 0 ? 3

→ B2 到 A 最短距离为 3,

u1(B2)=A,s1= A,

线路为B2A
第99页

第三步:当 k = 2,S3= { C1, C2, C3, C4 } → s3=C1时:f2(C1)= d 2 (C1 , B1 ) ? f1 ( B1 ) ? 1 ? 5 ? 6 → C1到 A 最短距离为6, u2(C1)=B1,s2= B1,

线路为C1B1A
第100页

?d 2 (C 2 , B1 ) ? f1 ( B1 ) ? ? 3 ? 5? s3= C2时:f2(C2) = min? ? ? min? ??8 ? 8 ? 3? ?d 2 (C 2 , B2 ) ? f1 ( B2 )?

→ C2 到 A 最短距离为8,

u2(C2)=B1,s2= B1,

线路为C2 B1A
第101页

s3= C3时:f2(C3)= min? ?

d 2 (C 3 , B1 ) ? f1 ( B1 ) ? ?6 ? 5 ? ? ? min? ? ? 10 ? 7 ? 3? ?d 2 (C 3 , B2 ) ? f1 ( B2 )?

→ C3到 A 最短距离为10, u2(C3)=B2,s2= B2, 线路为C3B2A
第102页

s3= C4 时:f2(C4)= d 2 (C4 , B2 ) ? f1 ( B2 ) ? 6 ? 3 ? 9 → C4 到 A 最短距离为 9, u2(C4)=B2,s2= B2, 线路为C4B2 A
第103页

第四步:当 k = 3,S4={D1,D2,D3} →
?d 3 ( D1 , C1 ) ? f 2 (C1 ) ? ?6 ? 6 ? s4=D1时:f3(D1)= min? ? ? min? ? ? 11 ? 3 ? 8? ?d 3 ( D1 , C 2 ) ? f 2 (C 2 )?

→ D1 到 A 最短距离为 11, u3(D1)=C2,s3= C2,
线路为D1C2 B1A
第104页

s4=D2时:f3(D2)=

?d 3 ( D2 , C1 ) ? ? ?d 3 ( D2 , C 2 ) ? m in? ?d 3 ( D2 , C 3 ) ? ?d 3 ( D2 , C 4 ) ? ?

f 2 (C 1 ) ? ?8 ? 6 ? ? ?5 ? 8 ? f 2 (C 2 )? ? ? ? m in? ? ? ? 13 f 2 (C 3 )? ? 3 ? 10? ?8 ? 9 ? f 2 (C 4 ) ? ? ? ?

→ D2 到 A 最短距离为 13,

u3(D2)=C2,s3= C2,线路为D2C2 B1A

或 u3(D2)=C3,s3= C3,线路为D2C3 B2A
第105页

s4= D3时:f3(D3)= min? ?

d 3 ( D3 , C 3 ) ? f 2 (C 3 )? ?3 ? 10? ? ? min? ? ? 13 ?4 ? 9 ? ?d 3 ( D3 , C 4 ) ? f 2 (C 4 )?

→ D3到 A 最短距离为13,

u3(D3)=C3,s3= C3,线路为D3C3B2A

或 u3(D3)=C4,s3= C4,线路为D3C4B2A
第106页

第五步:当 k = 4,S5={E1, E2, E3 } → s5=E1时:f4(E1)= d4 ( E1 , D1 ) ? f 3 ( D1 ) ? 2 ? 11 ? 13 → E1 到 A 最短距离为 13, u4(E1)=D1,s4= D1, 线路为E1D1C2 B1G
第107页

s5 = E2 时:f4(E2)=

?d 4 ( E 2 , D1 ) ? f 3 ( D1 ) ? ? 2 ? 11? ? ? ? ? m in?d 4 ( E 2 , D2 ) ? f 3 ( D2 )? ? m in?1 ? 13 ? ? 13 ? d ( E , D ) ? f ( D )? ? 3 ? 13? ? ? 3 3 ? ? 4 2 3

→ E2 到 A 最短距离为13,

u4(E2)=D1,s4= D1,

线路为E2D1C2 B1G
第108页

S5 = E3时:f4(E3)=

?d 4 ( E3 , D2 ) ? f 3 ( D2 )? ?2 ? 13? min? ? ? min? ? ? 15 ?3 ? 13? ?d 4 ( E3 , D3 ) ? f 3 ( D3 )?

→ E3 到 A 最短距离为15,

u4(E3)=D2,s4= D2,

线路为 E3D2D2C2 B1A 或 E3D2C3 B2A

第109页

第六步:当 k = 5,S6={F1, F2 } →

s6=F1 时:f5(F1)=

?d 5 ( F1 , E1 ) ? f 4 ( E1 ) ? ? 3 ? 13? ? ? ? ? m in?d 5 ( F1 , E 2 ) ? f 4 ( E 2 )? ? m in?5 ? 13? ? 16 ? d ( F , E ) ? f ( E )? ?6 ? 15? ? ? 4 3 ? ? 5 1 3

→ F1 到 A 最短距离为16,

u5(F1)=E1,s5= E1,
线路为 F1 E1 D1 C2 B1 G
第110页

s6=F2时:f5(F2)=

?d 5 ( F2 , E1 ) ? f 4 ( E1 ) ? ?5 ? 13? ? ? ? ? m in?d 5 ( F2 , E 2 ) ? f 4 ( E 2 )? ? m in? 2 ? 13? ? 15 ? d ( F , E ) ? f ( E )? ?6 ? 15? ? ? 4 3 ? ? 5 2 3

→F2 到 A 最短距离为15,

决策为u5(F2)=E2,s5= E2,

线路为F2 E2 D1 C2 B1 G
第111页

第七步:当 k = 6,S7={G } →
?d 6 (G , F1 ) ? f 5 ( F1 ) ? ?4 ? 16? S7=G 时:f6(G)= min? ? ? min? ? ? 18 ?3 ? 15? ?d 6 (G , F2 ) ? f 5 ( F2 )?

→ G 到 A 最短距离为 18, 决策为u6(G)=F2,s6= F2, 线路为 G F2 E2 D1 C2 B1 A
第112页

结 论
最优决策={ s1,u1,s2,u2,s3,u3,s4,u4,s5,u5, s6,u6,s7 }

={s1=A , u1(A)=B1 , s2=B1 , u2(B1)=C2 , s3=C2 ,
u3(C2)=D1 ,s4=D1 ,u4(D1)=E2 ,s5=E2 ,u5(E2)=F2 , s6=F2,u6(F2)=G,s7=G }
第113页

求解过程分析

从上面的计算过程中可以看出,在求解的各个阶段, 利用了 k 阶段与 k+1 阶段的递推关系:
v ? f k ( sk ?1 ) ? m in { k ( sk ?1 , uk ( sk ?1 )) ? f k ?1 ( sk ))}, k ? 1,2,...,6 ? ? ? f (s ) ? 0 ? 0 1
第114页

3. 顺序解法和逆序解法的关系

顺序解法和逆序解法本质上并无区别,一般来说:

(1)当终止状态给定时:用顺序解法;

(2)当初始状态给定时:用逆序解法;
第115页

(3)当定了一个初始状态与一个终止状态:两种方 法均可使用。

(4)当终止状态为多个时:求出到达不同终止状态

的最优指标函数值,选取最优指标函数值最优的终

点状态。
第116页

(5)当初始状态为多个时:求出从不同初始状态 出发的最优指标函数值,选取最优指标函数值最优 的初始状态。

针对问题的不同特点,灵活地选用两种方法之一, 可以使求解过程简化。
第117页

使用顺序法和逆序法为问题建立模型时,要注意以 下区别:

(1)状态转移方式不同 逆序解法:
① 第 k 阶段的输入状态为 sk,决策为uk → 输出为状态 sk+1
第118页

② 状态转移方程为:sk+1 = Tk (sk , uk)

称为状态 sk 到 sk+1 的顺序状态转移方程。

③ 阶段指标为:vk (sk , uk)
u1 s1 1 v1(s1,u1) s2

uk …
sk k vk(sk,uk) sk+1

un



sn

n vn(sn,un)

sn+1

第119页

顺序解法: ① 第 k 阶段的输入状态为 sk+1,决策为 uk → 输出状态为 sk ② 状态转移方程为:sk=Tk (sk+1 , uk ) , 称为状态 sk+1 到 sk 的逆序状态转移方程
第120页

③ 阶段指标为:vk ( sk+1 , uk )

u1 s1 1 s2 … sk

uk k vk(sk+1,uk) sk+1 …

un

sn

n

sn+1

v1(s2,u1)

vn(sn+1,un)

第121页

(2)指标函数定义不同
逆序解法: ① 阶段指标 vk(sk , uk) 表示第 k 阶段的指标函数值。 ② 过程指标函数

Vk,n 表示从第 k 阶段的状态 sk 开始,到第 n 阶段为
止,采取策略{ sk , uk , sk+1 , uk+1 , … , sn , un , sn+1 }时

的数量指标值。
第122页

当过程指标函数为阶段指标函数的和形式时:

Vk ,n ? ? v j ( s j , u j )
j?k

n

当过程指标函数为阶段指标函数的积形式时:

Vk ,n ? ? v j ( s j , u j )
j?k
第123页

n

③ 最优指标函数
fk(sk) 表示从第 k 阶段的状态 sk 开始,到最后一阶段 为止,采取最优策略时的数量指标值。 f1(s1) 为整体最优指标函数值。

f k ( sk ) ? optVk ,n ? opt{? v j ( s j , u j )}
j?k
第124页

n

顺序解法:
①阶段指标 vk(sk+1 , uk)表示第 k 阶段的指标函数值。

② 过程指标函数
V1,k 表示从第 1 阶段开始到第 k+1 阶段的状态 sk+1 为止,采取策略 { s0 , s1 , u1 , s2 , u2 ,… , sk , uk , sk+1 }

时的数量指标值。
第125页

当过程指标函数为阶段指标和形式时:

V1,k ? ? v j ( s j ?1 , u j )
j ?1

k

当过程指标函数为阶段指标积形式时:

V1,k ? ? v j ( s j ?1 , u j )
j ?1
第126页

k

③ 最优指标函数 fk(sk+1) 表示从第 1 阶段开始到第 k+1 阶段的状态
sk+1为止,采取最优策略时的数量指标值。 fn(sn+1) 为整体最优指标函数值。
f k ( sk ?1 ) ? optV1,k ? opt{? v j ( s j ?1 , u j )}
j ?1
第127页

k

(3)基本方程形式不同 逆序解法: 当过程指标函数为阶段指标函数的和形式

Vk ,n ? ? v j ( s j , u j ) 时:
j?k

n

? f k ( sk ) ? opt{v k ( sk , uk ) ? f k ?1 ( sk ?1 )}, k ? n, n ? 1,...,1 ? ? ? f (s ) ? 0 ? n?1 n?1
第128页

当过程指标函数为阶段指标函数的积形式
n

Vk ,n ? ? v j ( s j , u j ) 时:
j?k

? f k ( sk ) ? opt{v k ( sk , uk ) ? f k ?1 ( sk ?1 )}, k ? n, n ? 1,...,1 ? ? ? f (s ) ? 1 ? n?1 n?1

第129页

顺序解法:
当过程指标函数为阶段指标函数的和形式
V1,k ? ? v j ( s j ?1 , u j ) 时:
j ?1 k

? f k ( sk ?1 ) ? opt{v k ( sk ?1 , uk ) ? f k ?1 ( sk )}, k ? 1,2,...,n ? ? ? f (s ) ? 0 ? 0 1
第130页

当过程指标函数为阶段指标函数的积形式

V1,k ? ? v j ( s j ?1 , u j ) 时:
j ?1

k

? f k ( sk ?1 ) ? opt{v k ( sk ?1 , uk ) ? f k ?1 ( sk )}, k ? 1,2,...,n ? ? ? f (s ) ? 1 ? 0 1
第131页

第四节 动态规划基本方程的分段求解算法
动态规划模型建立后,对基本方程分段求解,不像 线性规划那样有固定的解法,必须根据具体问题的 特点,结合数学技巧灵活求解,大体有以下几种方

法。
第132页

一、离散变量的分段穷举算法
动态规划模型中的状态变量与决策变量若被限定只 能取离散值,则可采用分段穷举法。 前面的最短路问题的求解方法就是分段穷举算法, 由于每段的状态变量和决策变量离散取值个数较少,

所以动态规划的穷举法要比一般的穷举法有效。用
分段穷举法求最优指标函数值时,最重要的是正确

确定每段状态变量取值范围和允许决策集合范围。
第133页

二、连续确定性动态规划模型的逆序解法
例:某公司有资金10万元,若投资于项目i(i=1,2,3) 的 投 资 额 为 xi 时 , 其 收 益 分 别 为 g1(x1)=4x1 , g2(x2)=9x2 ,g3(x3)=2x32 ,问应如何分配投资额才能

使总收益最大?

第134页

解:

1. 建立模型 (1)选择决策变量
uk= xk :表示第 k 阶段确定的投资额。 uk= xk ,k =1, 2, 3
第135页

(2)选择状态变量

sk:表示第 k 阶段到第 3 阶段可供用于投资使用的 资金数量。(满足无后效性)
设状态变量为s1、s2、s3、s4: s1=10;s2= s1 - x1;s3= s2 - x2 ;s4= s3 - x3 = 0 → 0 ? x1 ? s1 、 0 ? x2 ? s2 、 0 ? x3 ? s3
第136页

(3)状态转移方程

sk ?1 ? sk ? xk
(4)选择指数函数
Vk,3:表示从第 k 阶段的状态 sk 开始,到第 3 阶段 为止,采取投资策略(xk ,…,x3 )时所创造的收

益。
Vk,3=

? g ( x ) ,k=1,2,3(满足分离性和递推关系)
i?k i i
第137页

3

(5)选择最优指标函数 fk(sk):表示从第 k 阶段的状态 sk 开始,到第 3 阶段 为止,采取最优投资策略(xk ,…,x3 )时所创造 的收益。

f k ( sk ) ? maxVk ,3 ( xk ,..., x3 )
第138页

(6)确定动态规划的基本方程

? f k ( sk ) ? max { gk ( xk ) ? f k ?1 ( sk ?1 )}, k ? 3,2,1 0? x k ? sk ? ? ? ? f (s ) ? 0 ? 4 4 ?

第139页

2. 逆序解法 第一步:当 k = 4,S4={ s4 } → f4( s4 ) = 0 第二步:当 k = 3,S3={ s3 } →
2 2 2 f3(s3)= max{ g3 ( x3 ) ? f 4 ( s4 )} ? max{2 x3 ? 0} ? max 2 x3 ? 2s3 0? x 3 ? s 3 0? x 3 ? s 3 0? x 3 ? s 3

→ u3(s3) = x3= s3
第140页

第三步:当 k = 2 ,S2= { s2 } →

2 f2 ( s2 ) = max{ g2 ( x2 ) ? f 3 ( s3 )} ? max{9 x2 ? 2s3 } 0? x 2 ? s 2 0? x 2 ? s 2

? max{9 x2 ? 2( s2 ? x2 )2 }
0? x 2 ? s 2

问题:max Z ( x2 ) ? 9 x2 ? 2( s2 ? x2 )2
第141页

?Z 9 ? ? 0 ? 9 ? 4( s2 ? x2 ) ? 0 ? x2 ? s2 ? ?x2 4

?2Z 又 ? 2 ?4?0 ?x2

9 ? x 2 ? s2 ? 不是极大值点,舍去。 4
第142页

故极大值只能在 x2 = 0 或 x2 = s2 处取得。
2 x2= 0 → f2(s2) = 2s2 ;x2= s2 → f2(s2) = 9s2

9 时: (1)如果x2=0为极大值点,即 2 s ? 9 s2 ? s2 ? 2
2 2

2 f 2 ( s2 ) ? max{9 x2 ? 2( s2 ? x2 )2 } ? 2 s2 0? x 2 ? s 2

→ u2(s2) = x2 = 0
第143页

(2)如果x2=s2为极大值点,即 2 s 2 ? 9 s ? s ? 9 时: 2 2 2

2

f 2 ( s2 ) ? max{9 x2 ? 2( s2 ? x2 )2 } ? 9 s2
0? x 2 ? s 2

→u2(s2) = x2= s2

第144页

第四步:当k=1,S1={s1} → f1(s1) = max { g1 ( x1 ) ? f 2 ( s2 )} ? max {4 x1 ? f 2 ( s2 )}
0? x1 ? s1 0? x1 ? s1

(1)f2(s2) = 2s

2 2

9 时:s2 ? ,u2(s2) = x2 = 0 2
0? x1 ? s1

2 f1(s1) = max{4 x1 ? 2 s2 } ? max{4 x1 ? 2( s1 ? x1 )2 } 0? x1 ? s1

问题: maxZ ( x1 ) ? 4 x1 ? 2( s1 ? x1 )2
第145页

?Z ? ? 0 ? 4 ? 4( s1 ? x1 ) ? 0 ? x1 ? s1 ? 1 ?x1

又 ?

? Z ?4?0 2 ?x1
2

? x1 ? s1 ? 1 不是极大值点,舍去。
第146页

故极大值只能在 x1 = 0 或 x1 = s1 处取得。
2 x1 = 0 → f1(s1) = 2s1 ;x1 = s1 → f1(s1) = 4 s1

2 ① 如果 x1 =0为极大值点,即 2s1 ? 4s1 ? s1 ? 2 :
2 f1 ( s1 ) ? max{4 x1 ? 2( s1 ? x1 )2 } ? 2 s1 0? x1 ? s1

→u1(s1)=x1=0
第147页

最优策略为:{ s1=10,x1=0,s2=10,x2=0,s3=10, x3= s3=10 } → 该策略中: 状态 s1 = 10 同 s1 > 2 不矛盾;

9 状态 s2 = 10 同 s2 ? 不矛盾,为最优策略。 2
第148页

2 ② 如果x1 = s1为极大值点,即 2s1 ? 4s1 ? s1 ? 2 时 :

f1(s1) = max{4 x1 ? 2( s1 ? x1 )2 } ? 4 s1
0? x1 ? s1

→u1(s1)=x1=s1=10
第149页

最优策略为:{ s1=10,x1=10,s2=0,x2=0,s3=0, x3= s3= 0}

→ 该策略中:
状态 s1 = 10 同 s1 < 2 矛盾; 状态 s2 = 0 同 s2 ?

9 矛盾,故该策略舍去。 2
第150页

(2)f2(s2) = 9s2 时: 2 ? 9 ,u2(s2)=x2=s2 s 2

f1(s1)= max {4 x1 ? 9 s2 } ? max {4 x1 ? 9( s1 ? x1 )}
0? x1 ? s1 0? x1 ? s1

= max {9 s1 ? 5 x1 } ? 9 s1
0? x1 ? s1

→ u1(s1)= x1 = 0
第151页

最优策略为:{s1=10,x1=0,s2=10,x2=10,s3=0,

x3=s3=0}

→该策略中:

9 状态 s2 = 10 同 s2 ? 矛盾,故该策略舍去。 2
第152页

三、连续确定性动态规划模型的顺序解法
解: 1. 建立模型

(1)选择决策变量
uk = xk :表示第 k 阶段确定的投资额。 uk = xk ,k=1 , 2 , 3
第153页

(2)选择状态变量 sk+1:表示第 1 阶段到第 k 阶段的总投资额。(满足

无后效性)
设状态变量为s1、s2、s3、s4: s1= s2 - x1;s2 = s3 -x2;s3= s4 - x3;s4 = 10 → 0 ? x1 ? s2 、 0 ? x2 ? s3 、 0 ? x3 ? s4
第154页

(3)状态转移方程

sk ? sk ?1 ? xk
(4)选择指数函数
V1,k:表示从第 1 阶段到第 k 阶段的总投资额为 sk+1 时,采取投资策略(x1 ,…,xk )时所创造的收益。 V1,k = ,k = 1, 2, 3(满足分离性和递推
k i ?1

关系) ? gi ( xi )

第155页

(5)选择最优指标函数 fk(sk+1):表示从第 1 阶段到第 k 阶段的总投资额为 sk+1 时,采取最优投资策略(x1,…,xk)时所创造

的收益。
f k ( sk ?1 ) ? maxV1,k ( x1 ,..., xk )

第156页

(6)确定动态规划的基本方程

? f k ( sk ?1 ) ? max { gk ( xk ) ? f k ?1 ( sk )}, k ? 1,2,3 0 ? x k ? s k ?1 ? ? ? ? f (s ) ? 0 ? 0 1 ?

第157页

2. 顺序解法 第一步:当k = 0,S1= {s1} → f0(s1) = 0 第二步:当k = 1,S2={s2} → f1(s2)= max { g1 ( x1 ) ? f 0 ( s1 )} ? max {4 x1 ? 0} ? max 4 x1 ? 4 s2
0? x1 ? s2 0? x1 ? s2 0? x1 ? s2

→u1(s2) = x1 = s2
第158页

第三步:当k = 2,S3 = {s3} →

f2(s3)= max { g2 ( x2 ) ? f1 ( s2 )} ? max {9 x2 ? 4 s2 }
0? x 2 ? s3 0? x 2 ? s3

? max {9 x2 ? 4( s3 ? x2 )} ? max {4 s3 ? 5 x2 } ? 4 s3 ? 5 s3 ? 9 s3
0? x 2 ? s3 0? x 2 ? s 3

→u2(s3) = x2 = s3
第159页

第四步:当k = 3,S4={s4} →

2 f3(s4)= max{ g3 ( x3 ) ? f 2 ( s3 )} ? max{2 x3 ? 9s3 } 0 ? x 3 ? s4 0 ? x 3 ? s4

2 ? max{2 x3 ? 9( s4 ? x3 )} 0 ? x 3 ? s4

2 问题:maxZ ( x3 ) ? 2 x3 ? 9( s4 ? x3 )

第160页

?Z 9 ? ? 0 ? 4 x3 ? 9 ? 0 ? x3 ? ?x3 4

?2Z 又 ? 2 ?4?0 ?x3

9 ? x 3 ? 不是极大值点,舍去。 4
第161页

故极大值只能在 x3 = 0 或 x3 = s4 处取得。

x3 = 0 → f3(s4) = 9s4;

x3 = s4 → f3(s4) = 2s 2
4

第162页

2 ① 如果x3 = 0为极大值点,即 9 s4 ? 2 s4 ? s4 ? 9 : 2

2 f3(s4)= max{2 x3 ? 9( s4 ? x3 )} ? 9 s4 0 ? x 3 ? s4

→ u3(s4) = x3 = 0
第163页

最优策略为:

{s1 = 0,x1 = s2= 0,s2 = 0,x2=s3=10,s3 = 10,x3 = 0, s4 = 10 }
9 → 该策略中状态 s4 = 10 同 s4 ? 矛盾,故该策略舍 2

去。
第164页

② 如果x3 = s4为极大值点,即 9 s ? 2 s 2 ? s ? 9 : 4 4 4 2

f3(s4)= max{2 x 2 ? 9( s ? x )} ? 2 s 2 3 4 3 4
0 ? x 3 ? s4

→u3(s4) = x3 = s4
第165页

最优策略为:

{s1 = 0,x1 = s2 = 0,s2 = 0,x2 =s3= 0,s3 = 0,x3 = s4= 10,s4 = 10}

9 不矛盾,为最优 →该策略中状态 s4 = 10 同 s4 ? 2
策略。
第166页

四、其他形式的连续确定性动态规划模

型的解法
例:用逆序解法求解

2 m axz ? x1 x 2 x 3

? x1 ? x 2 ? x 3 ? c ? ? x i ? 0, i ? 1,2,3
第167页

解:令g1(x1)=x1,g2(x2)=

x

2 2

,g3(x3) = x3

过程指标函数为阶段指标函数的积形式。

设状态变量为s1、s2、s3、s4: s1 = c;s2 = s1 - x1;s3= s2 - x2;s4 = s3 - x3 > 0
→ 0 ? x1 ? s1 、0 ? x2 ? s2 、0 ? x3 ? s3
第168页

第一步:当k = 4,S4= {s4} → f4(s4) = 1

第二步:当k = 3,S3= {s3} →

f3(s3)= max { g3 ( x3 ) f 4 ( s4 )} ? max { x3 ? 1} ? max x3 ? s3
0? x 3 ? s3 0? x 3 ? s 3 0? x 3 ? s3

→u3(s3) = x3 = s3
第169页

第三步:当k = 2,S2={s2} →

2 2 f2(s2)= max{ g2 ( x2 ) f 3 ( s3 )} ? max{ x2 ? s3 } ? max{ x2 ? ( s2 ? x2 )} 0? x 2 ? s 2 0? x 2 ? s 2 0? x 2 ? s 2

问题:maxZ ( x ) ? x 2 ? ( s ? x ) 2 2 2 2

第170页

?Z 2 2 ? ? 0 ? 2s2 x2 ? 3 x2 ? 0 ? x2 ? 0或x2 ? s2 ?x2 3

?2Z 又 ? 2 ? 2 s2 ? 6 x 2 ?x2

?2Z 当x2= 0 时: ? 2s2 ? 0 ,不是极大值点,舍去。 2 ?x2
第171页

?2Z 当 x2 = 2 s2 时: ? ?2 s2 ? 0 ,为极大值点。 2 ?x2 3
3 x2= 2 s2 → f3(s4) = 4 s 2 27 3

→u2(s2)=x2= 2 s2
3
第172页

第四步:当k = 1,S1={s1} →

f1(s1)= max{ g1 ( x1 ) ? f 2 ( s2 )} ? max{ x1 ? 4 s23 } ? max{ x1 ? 4 ( s1 ? x1 )3 } 0? x ? s 0? x ? s 0? x ? s
1 1 1 1

27

1

1

27

问题:m axZ ( x ) ? 4 x ? ( s ? x )3 1 1 1 1
27

第173页

?Z 4 1 2 ? ? 0 ? ( s1 ? x1 ) ( s1 ? 4 x1 ) ? 0 ? x1 ? s1或x1 ? s1 ?x1 27 4



?2Z 8 ? 2 ? ? ( s1 ? x1 )(s1 ? 2 x1 ) ?x1 9

?2Z 当 x1 = s1 时: ? 0 ,不是极大值点,舍去。 2 ?x1
第174页

2 1 2 1 时: ? Z 当 x1 = s1 ? ? s1 ? 0 ,为极大值点。 2 ?x2 3 4

x1 = 1 s1 4
1 4 → f1(s1) = s1 64

→u1(s1) = x1 = 1 s1 ? 1 c
4 4
第175页

最优策略为:{s1=c,x1= 1 c,s2= 3 c,x2= 2 s2= 1 c, 2 3 4 4 s3= 1 c ,x3=s3= 1 c ,s4=0 } 4 4

最优解为:x1= 1 c ,x2= 1 c ,x3= 1 c
4 2

4

第176页

例:用顺序解法求解

m axz ? 4 x ? x ? 2 x ? 12
2 1 2 2 2 3

?3 x1 ? 2 x2 ? x3 ? 9 ? ? xi ? 0, i ? 1,2,3

第177页

2 2 2 解:令g1(x1) = 4x1 ,g2(x2) = ? x2 ,g3(x3) = 2 x3 ? 12

指标函数为阶段指标函数的和形式。 设状态变量为s1、s2、s3、s4: s1 = s2 - 3x1= 0;s2 = s3 - 2x2;s3= s4 - x3;s4≤9

→ 0 ? 3 x1 ? s2 、 0 ? 2 x2 ? s3 、 0 ? x3 ? s4
1 → 0 ? x1 ? s2 、0 ? x2 ? 1 s3 、 0 ? x3 ? s4 3 2

第178页

第一步:当k = 0,S1 = {s1} → f0(s1) = 0

第二步:当k = 1,S2 = {s2} →

2 f1(s2)= max { g1 ( x1 ) ? f 0 ( s1 )} ? max {4 x12 ? 0} ? max 4 x12 ? 4 s2 1 1 1 0? x1 ? s2 3 0? x1 ? s2 3 0? x1 ? s2 3

9

→u1(s2) = x1 = 1 s2
3
第179页

第三步:当k = 2,S3 = {s3} →

2 2 f2(s3) = max { g 2 ( x 2 ) ? f1 ( s2 )} ? max {? x 2 ? 4 s2 } 1 1 0? x 2 ? s3 2 0? x 2 ? s3 2

9

4 4 2 7 2 16 2 ? max {? x ? ( s3 ? 2 x 2 ) } ? max { s3 ? x 2 ? s3 x 2 } 1 0? x 2 ? s3 9 9 9 9 0? x 2 ? s3
2 2 2

2 2 问题:m ax Z ( x2 ) ? 4 s3 ? 7 x2 ? 16 s3 x2

9

9

9

第180页

?Z 14 16 8 ? ? 0 ? x 2 ? s3 ? 0 ? x 2 ? s 3 ?x2 9 9 7
? 2 Z 14 又 ? ? ?0 2 ?x2 9
8 ? x2 ? s3 不是极大值点,舍去。 7

故极大值只能在 x2= 0 或 x2 ? 1 s3 处取得。 2
第181页

x 2= 0

2 → f2 ( s3 ) = 4 s 3 ;

9

1 →f (s )= 1 2<0 ? s3 x 2 ? s3 2 3 4 2
2 ∴x2 = 0 为极大值点,f3(s4) = 4 s3 9

→u2(s3) = x2 = 0
第182页

第四步:当k = 3,S4={s4} →

4 2 f3(s4)= max{ g3 ( x3 ) ? f 2 ( s3 )} ? max{2 x ? 12 ? s3 } 0 ? x 3 ? s4 0 ? x 3 ? s4 9
2 3

4 ? m ax{2 x ? 12 ? ( s4 ? x3 )2 } 0 ? x 3 ? s4 9
2 3

4 问题: ax Z ( x3 ) ? 2 x ? 12 ? ( s4 ? x3 ) 2 m 9
2 3
第183页

?Z 44 8 2 ? ?0? x3 ? s4 ? 0 ? x3 ? s4 ?x3 9 9 11

? 2 Z 44 又 ? ? ?0 2 ?x3 9

2 ? x3 ? s4 不是极大值点,舍去。 11
故极大值只能在 x3 = 0 或 x3 = s4 处取得。
第184页

2 x3 = 0 → f3( s4 ) = 4 s4 ? 12

9

2 x3 = s4 → f3( s4 ) = 2s4 ? 12

4 2 2 ? s4 ? 12 ? 2 s4 ? 12 9
2 x3 = s4为极大值点,f3(s4) = 2s4 ? 12

→u3(s4) = x3 = s4
第185页

问题:max f ( s ) ? 2 s 2 ? 12 3 4 4
0? s4 ? 9

当 s4 = 9 时,f3(s4)达到最大值,f3(s4) = 174

所以可得:u3(s4) = x3 = s4 = 9

第186页

最优策略为:

1 { s1 = 0,x1= s= 0,s2 = 0,x2 = 0,s3= 0,x3 = s4= 9, 2 3
s4 = 9 } 最优解为:x1 = 0,x2 = 0,x3 = 9

第187页

五、连续确定性动态规划模型的离散 化解法
m axz ? ? g i ( x i )
i ?1 n

? n ?? xi ? a ? i ?1 ? x ? 0, i ? 1,2,...,n ? i
第188页

其动态规划模型的基本方程为:

? f k ( sk ) ? max { gk ( xk ) ? f k ?1 ( sk ?1 )}, k ? n, n ? 1,...,1 0? x k ? s k ? ? ? ? f (s ) ? 0 ? n?1 n?1 ?

第189页

1. 令 sk = 0 , △ , 2△ , … , m△,把区间 [ 0 , a ] 进行

分割,△的大小可依据问题所要求的精度以及计算
机的容量来定; 2. 规定状态变量及决策变量只在离散点 0 , △ , 2△ , … , m△上取值,相应的指标函数 fk(sk)就被定 义在这些离散值上,递推方程变为:
第190页

? f k ( sk ) ? m ax { gk ( p? ) ? f k ?1 ( sk ? p? )}, k ? 3,2,1 p ? 0 ,1,..., m ? ? ? ? f (s ) ? 0 ? n?1 n?1 ?

3. 按逆序方法,逐步递推求出 fn(sn) , … , f1(s1) ,最
后求出最优方案。

第191页

例 用连续变量的离散化方法求解下列问题。

m axz ? 4 x1 ? 9 x 2 ? 2 x ? x1 ? x 2 ? x 3 ? 10 ? ? ? x ? 0( i ? 1,2,3) ? i

2 3

第192页

解:

令△=2,
将区间 [ 0 , 10 ] 分割成 0 , 2 , 4 , 6 , 8 , 10 六个点, 即状态 sk 集合为 { 0 , 2 , 4 , 6 , 8 , 10 } 。 允许决策集合为 0≤ xk ≤ sk , xk 与 sk 均在分割点上

取值。
第193页

第一步: 当k = 3,S3= { 0 , 2 , 4 , 6 , 8 , 10 }
2 → f3(s3) = m ax{2 x 3 } 0? x 3 ? s 3

s3 0
x3

2 0 2 0

4 2 4
32

6 0 2 4 6 0 2

8 4 6 8 0 2 4

10 6 8
10

0

g3 0
f3(s3) 0
* x3

0

8 8
2

0

8

0

8

32 72

0

8

32 72 128 128

0

8

32 72 128 200 200 10
第194页

32

72

0

4

6

8

第二步: 当 k = 2,S2= { 0 , 2 , 4 , 6 , 8 , 10 } → f2(s2) = max {9 x2 ? f 3 ( s2 ? x2 )}
0? x 2 ? s2

s2 0
x2

2 0 8 2 0

4 2 4 0 2

6 4 6 0 2

8 4 6 8 0 2 4

10 6 8
10

0

g2+f3 0
f2(s2)
* x2

18 32 26 36 72 50 44 54 128 90 68 62 128 200 146 108 86 80 200

0 0

18
2

36 4

72 0

128

200

0

0
第195页

第三步: 当 k = 1,S1= { 0 , 2 , 4 , 6 , 8 , 10 } → f1(s1) = max {4 x1 ? f 2 ( s1 ? x1 )}
0? x1 ? s10

s1

10

x1 g1+f2
f1
* x1

0 200
200 0

2 136

4 88

6 60

8 50

10 40

第196页

最优解为: x1 = 0,x2 = 0,x3 = 10

第197页


赞助商链接
相关文章:
9-《运筹学》-第九章
9-《运筹学》-第九章 - 第九章 第九章 动态规划应用举例 §1 资源分配问题与背包问题 1. 一维分配问题 问题:一种数量为 a 的资源,分配给 n 个用户。若...
更多相关文章: