当前位置:首页 >> 信息与通信 >>

运筹学课件动态规划


第十章 动态规划(DP) Dynamic Programming
§1 多阶段决策过程最优化问题(掌握)

§2 基本概念、基本方程与最优化原理
(掌握) §3 动态规划应用(掌握)

动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特点在于,可以把困难 的多阶段决策问题变换成一系列互相联系较容 易的单阶段问题,解决了这一系列较容易的单 阶段问题,也就解决了这个困难的多阶段决策 问题。

多阶段决策问题:
是动态决策问题的一种特殊形式; 在多阶段决策过程中,系统的动态过程可以按照时间 进程分为状态相互联系而又相互区别的各个阶段; 每个阶段都要进行决策,目的是使整个过程的决策 达到最优效果。

需指出:动态规划是求解某类问题的一种方法, 是考察问题的一种途径,而不是一种算法。必 须对具体问题进行具体分析,运用动态规划的 原理和方法,建立相应的模型,然后再用动态 规划方法去求解。

决策 状态 状态 1

决策 决策 状态 ? 状态 2 n

多阶段决策问题的典型例子:

1 . 生产决策问题:企业在生产过程 中,由于需求是随时间变化的,因此企 业为了获得全年的最佳生产效益,就要 在整个生产过程中逐月或逐季度地根据 库存和需求决定生产计划。

2. 航天飞机飞行控制问题:由于航天 飞机的运动的环境是不断变化的,因此就要 根据航天飞机飞行在不同环境中的情况,不 断地决定航天飞机的飞行方向和速度(状 态),使之能最省燃料和实现目的(如软着 落问题)。
不包含时间因素的静态决策问题(本质 上是一次决策问题)也可以适当地引入阶段 的概念,作为多阶段的决策问题用动态规划 方法来解决。

3 . 最短路问题:给定一个交通网络图如下,

其中两点之间的数字表示距离(或花费),试 求从A点到G点的最短距离(总费用最小)。
1 C1 3 6 3 3 6 C3 8 C4 1 2 3 8 D1 1 2 2 2 D2 E2 5 B1 E1 3

5
A 3

6
8 B2 7

C2

5

5
2

F1
3

4
G

3
4 D3

3
3 4 E3

6

6

F2

5

6

§1 最短路径问题
?

P201 例1。

§2 基本概念、基本方程及最优化原理

一、基本概念 1、阶段(stage) 指一个问题需要作出决策的步骤。通常 按时间和空间的自然特征划分阶段。 如例1是按距A点距离划分的阶段。

2、状态(state)--最关键参数
指每个阶段初所处的自然状况或客观 条件。 ? 它既反映前面各阶段决策的结局,又 是本阶段作出决策的出发点和依据。 ? 通常第k个阶段的有若干个状态,用 状状态变量sk来描述。 例1中某个阶段的状态就是所在的位置。 通常状态数比阶段数多1。
?

3、决策(decision)
指某一阶段内的抉择,通常用决策变量 xk(sk)表示第k阶段状态是sk时所做的 选择,这个决策决定了第k+1阶段的 状态。 如: x2(B1)=C2表示第2阶段处于状态B1 时选择了由B1到C2,即以C2做终点。 又如: x3(C1)=D2

4、策略(policy)
?

?

?

由所有各阶段的决策组成的序列称为 全过程策略,记作p1,n(s1) 能够达到总体最优的策略叫做最优策 略。 从第k个阶段开始到最后阶段的决策 组成序列称为k子过程策略简称K子策 略(subpolicy)。记作pk,n(sk)

5、指标函数
?

?

?

指标函数和最优值函数:用来衡量所实现 过程优劣的一种数量指标,为指标函数。 指标函数的最优值,称为最优值函数,记 作f1(s1)或fk(sk) 。在不同的问题中,指标函 数的含义是不同的,它可能是距离、利润、 成本、产量或资源消耗等。 fk(sk)就是指对某一确定状态选取最优策略 后得到的指标函数值,即对某一最优子策 略的效益度量值。 阶段指标函数:rk(sk,xk)表示在第k阶段的 sk状态下做出xk决策时的指标值。

6、状态转移方程(状态转移率)
从sk的某一状态值出发,当决策变量 xk(sk)的取值决定后,下一阶段状态 变量sk+1的取值也随之确定。这种从上 一阶段的某状态值到下阶段某状态值 的转移的规律称为状态转移率,又叫 状态转移方程。 sk+1=Tk(sk,xk)

图示:
决策 xk(sk) 决策 xk+1(sk+1)

状态
sk

阶段k T(sk,xk)

状态
Sk+1

阶段k+1 T(sk+1,xk+1)

状态
Sk+2

rk(sk,xk

rk+1(sk+1,xk+1)

二、基本方程
逆序算法

? f k (sk ) ? opt{rk (sk , xk ) ? f k ?1 (sk ?1 )}, k ? n, n ? 1,? 2,1
终点条件 f n?1 ( sn?1 ) ? 0 顺序算法

? f k (sk ) ? opt{rk (sk , xk ) ? f k ?1 (sk ?1 )}, k ? 1,2,? n ? 1, n
始点条件 f 0 ( s0 ) ? 0

三、最优化原理
最优策略的性质: 不管在此最优策略上的某个状态以前的 状态和决策如何,对该状态来说,以 后的所有决策必定构成最优子策略。 也就是说最优策略的任一个子策略也 是最优的。

小结: 无后效性 动态规划本质上是多阶段决策过程;
概念 : 阶段变量k﹑状态变量sk﹑决策变量uk; 方程 :状态转移方程 sk ?1 ? Tk (sk , uk ) 指标 :
Vk ,n ? Vk ,n (sk , uk , sk ?1, uk ?1,?, sn?1 )
效益

f k ( sk ) ? opt V k ,n ( sk , u k ,?, sn?1)
?u k ,?,u n?
可递推

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

? ? k [ sk , u k , Vk ?1, n ( sk ?1 , u k ?1 , ?, sn ?1 )]
指标函数形式: 和、 积

解多阶段决策过程问题,求出
最优策略,即最优决策序列
* * * {u1 , u2 ,?, un }

最优路线,即执行最优策略时的状态序列

{ s , s ,?, s }
最优目标函数值
* V1,n

* 1

* 2

* n

f 1 ( s1 )

* * * 从 k 到终点最优策略 * * ? V1,n ( s1 , u1 ,?, sn , un )

子策略的最优目标函数值

f ?s ? ? opt v ?s , u
k k

?u ,?,u ?
k n

k ,n

k

k

, ? , sn ?1

?

§3 动态规划的应用
动态规划求解步骤: 1、确定问题的阶段和编号 2、确定状态变量 sk 3、确定决策变量 xk(用 xk*表示该阶段的最
优决策)

4、确定状态转移方程 5、确定指标函数

二、最短路径问题
例一、从A 地到D 地要铺设一条煤气管道,其中需经过 两级中间站,两点之间的连线上的数字表示距离,如 图所示。问应该选择什么路线,使总距离最短?
3
2 A 4 B2 B1 2 1 3 C2 4 C3 3

C1

1 D

3 1

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

解:整个计算过程分三个阶段,从最后一个阶段开始。

第三阶段(C →D): C 有三条路线到终点D 。
显然有 f3 (C1 ) = 1 ; f3(C2 ) = 3 ; f3 (C3 ) = 4

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第二阶段(B →C): B 到C 有六条路线。
r( B1,C1 ) + f1 (C1 ) 3+1 f2 ( B1 ) = min r( B1,C2 ) + f1 (C2 ) = min 3+3 r( B1,C3 ) + f1 (C3 ) 1+4 4 = min 6 = 4 (最短路线为B1→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

r( B2,C1 ) + f1 (C1 ) 2+1 f2 ( B2 ) = min r( B2,C2 ) + f1 (C2 ) = min 3+3 r( B2,C3 ) + f1 (C3 ) 1+4 3 = min 6 = 3 (最短路线为B2→C1 →D) 5

3
2 A 4 B2 B1 2 1 3

C1
C2 4 C3 3

1 D

3 1

第一阶段( A → B ): A 到B 有二条路线。
f1(A)1 = r(A, B1 )+ f2 ( B1 ) =2+4=6 f1 (A)2 = r(A, B2 )+ f2 ( B2 ) =4+3=7 ∴ f1 (A) = min r(A, B1 )+ f2 ( B1 ) r(A, B2 )+ f2 ( B2 ) = min{6,7}=6

(最短路线为A→B1→C1 →D)

3 2 A 4 B2 B1 2 3 1 3 1

C1 C2 4 3

1 D

C3

最短路线为

A→B1→C1 →D

路长为 6

例:
12 B1 14 10 2 5 1 6 10 B2 4 1312

C1

3 9 6

D1 5 E
D2 2

A

C2 5
8

B3 11

C3 10

求从A到E的最短路径

例:
19

20

8

12 B1 14 10 10 B2 4

C1

3 9

5 D1 5 2
D2 2

2

14 6
5 1

A

7 6 C2 5 12
8

E

19 13

12

B3 11

C3 10

状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态 第1阶段 第 3 阶段 (D , 第 4阶段 A ( A,B2) B2 ( B22 ,阶段 C1) C1 (C1第 ,D E) E 1) D 1 1 从A到E的最短路径为19,路线为A→B 2→C1 →D1 →E

例:资源分配问题 P206

?

?

? ? ? ?

解:将问题按工厂分为三个阶段,甲、 乙、丙三厂分别编号为1,2,3。 设sk=分配给第K个厂至第3个厂的设备台 数(K=1,2,3) Xk=分配给第K个厂的设备台数。 已知 s1=5 s2=s1-x1 s3=s2-x2

? ? ?

以下我们从第三阶段开始计算: 第三阶段 显然将s3(s3=0,1,2,3,4,5)台设备都分 配给第3工厂时,也就是s3=x3时,第3 阶段的指标值为最大,

第三阶段( s3=0,1,2,3,4,5 )
x3 r3(s3,x3)

s3 0 1 2 3 4 5

0 0

1
4

2

3

4

5

f3(s3)

x 3*

6 11 12

12

0 4 6 11 12 12

0 1 2 3 4 5

第三阶段( s3=0,1,2,3,4,5 )
x3 r3(s3,x3)

s3 0 1 2 3 4 5

0 0

1
4

2

3

4

5

f3(s3)

x 3*

6 11 12

12

0 4 6 11 12 12

0 1 2 3 4 5

第二阶段( s2=0,1,2,3,4,5 )台设备分 配给第2工厂和第3工厂
x2 r2(s2,x2)+ f3(s2-x2)

s2
0 1 2 3 4 5

0

1

2

3

4

5

f2(s2) x2*

0+0 0+4 5+0 0+6 5+4 10+0 0+11 5+6 10+4 11+0 0+12 5+11 10+6 11+4 11+0 0+12 5+12 10+11 11+6 11+4 11+0

0 5 10 14 16 21

0 1 2 2
1,2 2

第二阶段( s2=0,1,2,3,4,5 )台设备分 配给第2工厂和第3工厂
x2 r2(s2,x2)+ f3(s2-x2)

s2
0 1 2 3 4 5

0

1

2

3

4

5

f2(s2) x2*

0+0 0+4 5+0 0+6 5+4 10+0 0+11 5+6 10+4 11+0 0+12 5+11 10+6 11+4 11+0 0+12 5+12 10+11 11+6 11+4 11+0

0 5 10 14 16 21

0 1 2 2
1, 2

2

x2

第一阶段(s1=5)

s2
0 1 2 3 4 5

f2(s2) x2*

0 5 10 14 16 21

0 1 2 2
1, 2

2

x1 s1
5

r1(5,x1)+ f2(5-x1) 0 1 2 3 4 5

f1(x x1* )

0+21 3+16 7+14 9+10 12+5 13+0 21 0,2

第一阶段(s1=5)
x3 r1(5,x1)+ f2(5-x1)

s3
5

0

1

2

3

4

5

f1(x x1 * )

0+21 3+16 7+14 9+19 12+5 13+0 21 0,2

最优分配方案有两个:

(1)由于x1*=0,根据s2=s1- x1*=5,可知x2*=2,可 求得x3*=3。即分配给甲厂0台,乙厂2台,丙厂3台。
(2)由于x1*=2,根据s2=s1- x1*=3,可知x2*=2,可 求得x3*=1。即分配给甲厂2台,乙厂2台,丙厂1台。

?

例4-2:某公司拟将400万元,向A、B、 C三个项目追加投资,三个项目可以有 不同的投资额度,相应的效益值如表所 示,问如何分配资金,才使总效益值最 大?
0 1 2 3 4

习题2(P226)

A B C

47 49 46

51 52 70

59 61 76

71 71 88

76 78 88

习题2(P226)
将问题按项目分为三个阶段:A、B、 C分别编号为1,2,3。 ? 设sk—分配给第k项目至第3个项目可 供分配的资金数。 xk—分配给第k个项目的资金数。 s1=4(百万) sk+1 = sk - xk s3= x3
?

s 3 = s 2 – x2

第3阶段: s3=0,1,2,3,4
x3 s3 0 r3(s3,x3)+ f4(s3-x3) 1 70 76 88 88 2 3 4 f3(s3) x 3*

0 1 2 3 4

46

46 70 76 88 88

0 1 2 3 4

第2阶段: s2=0,1,2,3,4
x2 s2 0 1 2 3 4 r2(s2,x2)+ f3(s2-x2) 0 1 2 3 4 49+46 49+70 52+46 49+76 52+70 61+46 49+88 52+76 61+70 71+46 49+88 52+88 61+76 71+70 78+46 f2(s2 x2* ) 95 119 125 137 141 0 0 0 0 3

第2阶段: s2=0,1,2,3,4
x2 s2 0 1 2 3 4 0 r2(s2,x2)+ f3(s2-x2) 1 2 3 4

f2(s2) x2*
0 119 125 137 141 0 0 0 2 3

49+0 49+70 52+0 49+76 52+70 61+0 49+88 52+76 61+70 71+0 49+88 52+88 61+76 71+70 78+0

第1阶段: s1=4
x1 s1
4 结论:

r1(s1,x1)+ f2(s1-x1) 0 1 2 3 4 f1(s1) x1*

(1)由于x1*=0,根据s2=s1- x1*=4,可知 x2*=3,可求得x3*=1。
最优策略:分配给A 0万B 300万C 100万 最优值:188

第1阶段: s1=4
x1 s1
4

r1(s1,x1)+ f2(s1-x1) 0 1 2 3 4 f1(s1) x1*
3

47+141 51+13759+125 71+119 76+95 190

(1)由于x1*=3,根据s2=s1- x1*=1,可知 x2*=0,可求得x3*=1。 最优策略:分配给A 300万 B 0万 C 100万

最优值:190

第1阶段: s1=4
x1 s1
4

r1(s1,x1)+ f2(s1-x1) 0 1 2 3 4 f1(s1) x1*
188 0

47+141 51+13159+122 71+70 76+0

(1)由于x1*=0,根据s2=s1- x1*=4,可知 x2*=3,可求得x3*=1。 最优策略:分配给A 0万B 300万C 100万

最优值:188

例:
某一警卫部门共有12支巡逻队,负责4 个要害部位A、B、C、D的警卫巡逻。 对每个部位可分别派出2~4支巡逻队, 并且由于派出巡逻队数的不同,各部 位预期在一段时期内可能造成的损失 有差别,具体数字见下表。 问警卫部门应往各部位分别派多少支巡 逻队,使总的预期损失为最小。

部位 A B C D

巡逻队数
2 3 4 18 14 10 38 35 31 24 22 21 34 31 25

第4阶段:2 ≤s4≤6
x4 s4 2 r4(s4,x4) 3 31 31 31 31 4 f4(s4) x 4*

2 3 4 5 6

34 34 34 34 34

25 25 25

34 31 25 25 25

2 3 4 4 4

第3阶段: 4 ≤s3≤8
x3 s3 r3(s3,x3)+ f4(s3-x3) 2 3 4 f3(s3) x 3*

4 5 6 7 8

24+34 24+31 24+25 24+25 24+25

22+34 22+31 21+34 22+25 21+31 22+25 21+25

58 55 49 47 46

2 2 2 3 4

第2阶段: 8 ≤s3≤10
x2
s2 8 9 10

r2(s2,x2)+ f3(s2-x2)
2 3 4 38+49 35+55 31+58 38+47 35+49 31+55 38+46 35+47 31+49

f2(s2) 87 84 80

x 2* 2 3 4

第1阶段: s1=12
x1 s1 r1(s1,x1)+ f2(s2-x2) 2 3 4 f1(s1) x 1*

12

18+80 14+84 10+87

97

4

例:
设有某种机器设备,用于完成两类工作A和B。 若k年初完好机器的数量为sk,若以数量xk用 于A,余下的(sk-xk)用于工作B,则该年 的预期收入为g(xk)+h(sk-xk),g(xk)=8 xk, h(sk-xk)=5 (sk-xk) ,且g(0)=h(0)=0。又机器 设备在使用中会有损耗,设机器用于工作A 时,一年后能继续使用的完好机器数占年初 投入量的70%,用于工作B时,完好率为 90%,第一年初完好机器数为1000台。问连 续五年内每年应如何分配用A、B两项工作 的机器数,使五年的总收益为最大。

1、确定阶段:将五年对机器的分配看成是5 个阶段的决策过程,因而k=5。 2、确定状态变量 sk:每个阶段初拥有的完 好机器数用状态变量sk来表示。 3、确定决策变量 xk:表示每个阶段投入工 作A的完好机器数。 4、确定状态转移方程: sk+1 =0.7xk+0.9(sk-xk) 5、确定指标函数:每个阶段的收入为 8xk+5(sk-xk)

fk(sk)=max{8xk+5(sk-xk)+ fk+1(sk+1)} f5(s5)=max{8x5+5(s5-x5)+ f6(s6)}=max{5s5+3x5}=8s5 ( x5*= s5 ) f4(s4)=max{8x4+5(s4-x4)+ 8[0.7x4+0.9(s4-x4)]}= max{12.2s4+1.4x4}= 13.6s4 ( x4*= s4 ) f3(s3)=max{8x3+5(s3-x3)+ 13.6 [0.7x3+0.9(s3-x3)]} =max{17.24s3+0.28x3} =17.52s3 ( x3*= s3 )
?

f2(s2)=max{8x2+5(s2-x2)+ 17.52 [0.7x2+0.9(s2x2)]} =max{20.77s5-0.50x2} =20.77x2 ( x2*=0 ) f1(s1)=max{8x1+5(s1-x1)+20.77 [0.7x1+0.9(s1x1)]} =max{23.69s1-1.15x1} =23.69x1 ( x1*=0 ) 前两年将全部完好机器投入工作B,后三年 应将全部完好机器投入工作A,总收入 23690元。


赞助商链接
相关文章:
动态规划--运筹学课程设计
运筹学课程设计论文 17页 1下载券 运筹学课程设计 20页 1下载券 运筹学PPT完整...动态规划之最短线路问题 1 设计目的、要求熟悉动态规划的相关概念,掌握使用动态...
第五章 动态规划 山大刁在筠 运筹学讲义
山东大学 运筹学课件及... 85页 1下载券 运筹学[第八章动态规划的... 暂无...第五章 动态规划教学重点:用递推的方法求解最短路线问题,有限资源分配问题,旅行...
动态规划习题详解
搜试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 文学...动态规划动态规划运筹学的一个分支,它是解决多阶段决策过程最优化问题的一种...
动态规划习题答案
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 工...由复旦大学出版社出版,傅家良主编的运筹学方法与模型第八章动态规划习题答案...
运筹学动态规划
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 ...运筹学动态规划_管理学_高等教育_教育专区。MATLAB 基础及在运筹学中的应用 第...
动态规划讲解大全(含例题及答案)
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 资格考试/认证...动态规划讲解大全动态规划(dynamic programming)是运筹学的一个分支,是求解决策...
运筹学中excel的运用(用excel解决线性规划、动态规划、...
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 专业资料 自然科学 数学...运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题)_数学_自然...
运筹学试卷及答案完整版
搜试试 3 悬赏文档 全部 DOC PPT TXT PDF XLS ...运筹学试卷及答案完整版_管理学_高等教育_教育专区...动态规划中运用图解法的顺推方法和网络最短路径的...
天大《运筹学》2016年6月考试期末大作业
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS ...天大《运筹学》2016年6月考试期末大作业_远程、网络...(每小题 25 分,共 100 分) 1、下图为动态规划...
运筹学中excel的运用(用excel解决线性规划、动态规划、...
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题)_电脑基础知识_IT/计算机_专业资料。用excel解决运筹学中基础模型的求解问题。1...
更多相关标签: