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

运筹学 动态规划


第6章 动态规划
? 动态规划是一种研究多阶段决策问题的理论和 方法。这种方法把一个多阶段决策问题转化成 一系列相互联系的单阶段决策问题来求解。 ? 动态规划主要应用于最短路问题、装载问题、 库存问题、资源分配、生产过程最优化问题。 ? 动态规划模型可以分为离散确定性、离散随机 性、连续确定性、连续随机性四种决策过程。 其中最基本的是离散确定性过程。

第6章 动态规划
§1 多阶段的决策问题 §2 最优化原理与动态规划的数学 模型 §3 动态规划应用举例

§1 多阶段的决策问题
? 多阶段决策问题:可以分为若干个互相联系的 阶段,在每个阶段分别对应着一组可以选取的 决策,当每个阶段的决策选定以后,过程也就 随之确定。 ? 多阶段决策问题,就是要在所有可能采取的策 略中间选取一个最优的策略,是在预定的标准 下得到最好的效果。

[例1] 最短路线问题。设有一旅行者从下图中 的A点出发,途中要经过B、C、D等处,最后到 达终点E。从A到E有很多条路可以选择,各点之 间的距离如图所示,问该旅行者应选择哪一条路 线,使从A到E的总路程最短?
B1 2 A 3 5 B2 6 3 7 5 2 C1 4 C2 1 5 6 3 3 1

D1

3 E

4
5

D2
3

4

B3

C3

用穷举法的计算量:

如果从A到E的站点有k个,除A、E之外每站有3个位置则
总共有3k-1×2条路径; 计算各路径长度总共要进行 (k+1) 3k-1×2次加法以及3k1×2-1次比较。随着

k 的值增加时,需要进行的加法和比较的

次数将迅速增加; 例如当 k=20时,加法次数为 4.2550833966227×1015 次, 比较 1.3726075472977×1014 次。若用1亿次/秒的计算机计算 需要约508天。

[例2] 设有某种机器设备,用于完成两类工作 A和B.若k年初完好机器的数量为sk,若以数量xk 用于A,余下的(sk-xk)用于工作B,则该年的预期 收入为g(xk)+h(sk-xk).这里g(xk)和h(sk-xk)是已知函 数,且g(0)=h(0)=0.又机器设备在使用中会有损坏, 设机器用于工作A时,一年后能继续使用的完好 机器数占年初投入量的a%;若用于B项工作时, 一年后能继续使用的完好机器数占年初投入量的 b%,即下一年初能继续用于完成这两项工作的设 备数为sk+1=axk+b(sk-xk).设第一年初完好的机器总 数为s0,问在连续三年内每年应如何分配用于A、 B两项工作的机器数,使三年的总收益最大?

[例3] 将一个数c(c>0)分成n个部分c1,c2,...,cn 之和,且ci>0(i=1,...,n),问应如何分割使其乘积 n ? ci 为最大?
i ?1

max Z ? ? Ci
i ?1 n ? Ci ? C ? ? s.t ? i ?1 ? C ? 0, (i ? 1, 2, ) ? i

n

§2 最优化原理与动态规划的数学模型

? ? ? ? ?

动态规划问题的解题思路 动态规划的基本概念 最优化原理与动态规划的数学模型 逆序解法与顺序解法 动态规划模型的分类

2.1 动态规划问题的解题思路
? 基本思路:是将一个n阶段的决策问题转化为 依次求解n个具有递推关系的单阶段的决策问 题,从而简化计算过程。

? 在例1中,这种转化的实现是从终点E出发一步 步进行反推,这种算法称为逆序算法。

[例1] 最短路线问题。设有一旅行者从下图中 的A点出发,途中要经过B、C、D等处,最后到 达终点E。从A到E有很多条路可以选择,各点之 间的距离如图所示,问该旅行者应选择哪一条路 线,使从A到E的总路程最短?
B1 2 A 3 5 B2 6 3 7 5 2 C1 4 C2 1 5 6 3 3 1

D1

3 E

4
5

D2
3

4

B3

C3

按逆序推算,例1的计算步骤为: ? 从D出发,f(D1)=3;f(D2)=4。 ? 从C出发,f(C1)=4;f(C2)=7;f(C3)=6。 ? 从B出发,f(B1)=11;f(B2)=7;f(B3)=8。 ? 从A出发,f(A)=11。

2.2 动态规划的基本概念
1、阶段(stage).是指一个问题需要做出决策的步 数。如例1中旅行者需要在A、B、C、D四个阶 段做出下一步的决策。通常用k来表示问题包 含的阶段数,称为阶段变量。 2、状态(state).这是动态规划中最关键的参数,它 既反映前面各阶段决策的结局,又是本阶段做 出决策的出发点和依据。状态是动态规划问题 各阶段信息的传递点和结合点,第k阶段的状 态通常用状态变量sk来描述。在例1中第2阶段 的状态s2=(B1,B2,B3)。

3、决策(decision).是指某阶段初从给定的状态出 发,决策者在面临的若干种不同方案中做出的 选择。用Dk(sk)表示k阶段状态为sk时决策允许 的取值范围,xk(sk)表示第k阶段状态为sk时对方 案的选择。如例1中D2(B1)={C1,C2,C3}。 4、策略(policy)和子策略(sub policy).动态规划问 题各阶段决策组成的序列总体称作一个策略。 如:{x1(s1),x2(s2),...,xn(sn)}。 ? 把从某一阶段开始到过程最终的决策序列称为 问题的子过程策略或子策略。如: {xk(sk),xk+1(sk+1),...,xn(sn)}。

5、状态转移律,也称状态转移方程.从sk的某一 状态值出发,当决策变量xk(sk)的取值决定后, 下一阶段状态变量sk+1的取值也就随之确定。 这种从上一阶段的某一状态值到下一阶段某一 状态值的转移的规律成为状态转移律。如 sk+1=T(sk,xk(sk))。 6、指标函数.阶段的指标函数是对应某一阶段状 态和从该状态出发的一个阶段的决策的某种效 益度量,用rk(sk,xk)表示。过程的指标函数是指 从状态sk(k=1,2,...,n)出发至过程最终,当采取 某种子策略时,按预定标准得到的效益值。所 谓最优指标函数,是指对某一确定状态选取最 优策略后得到的指标函数值。记作fk(sk)。

2.3 最优化原理与动态规划的数学模型
? 求解动态规划的最优化原理(R.Bellman):作为 整个过程的最优策略具有这样的性质,无论过 去的状态和决策如何,对先前决策所形成的状 态而言,余下的诸决策必构成最优策略。 ? 基本方程:对于n阶段的动态规划问题,在求 子过程上的最优指标函数时,k子过程与k+1过 程有如下递推关系: fk(sk)=min{rk(sk,xk)+fk+1(xk+1)},k=n,...,2,1 边界条件(终点条件):fn+1(xn+1)=0 ? 边界条件是指从最后一个阶段向前逆推时需要 确定的条件。

关于阶段的划分、状态变量、决策变量、允 许决策集合和状态转移方程,应注意如下几点:
? 状态变量的确定是构造动态规划模型中最关键的一步, 状态变量首先应描述反映研究过程的演变特征,其次 它应包含到达这个状态前的足够信息,并具有无后效 性,还应具有可知性。 ? 决策变量是对过程进行控制的手段,复杂的问题决策 变量也可以是多维的向量,允许决策集合相当于线性 规划问题中的约束条件。 ? 状态转移律。当给出sk、xk的取值后,如果sk+1的取值 唯一确定,相应的决策过程称为确定性的多阶段决策 过程,否则称为随机性的多阶段决策过程。 ? 指标函数是衡量决策过程效益高低的指标,它是一个 定义在全过程或从k到n阶段的子过程上的函数,指标 函数必须具有递推性。

2.4 逆序解法与顺序解法
? 动态规划有两种基本方法:逆序解法与顺序解 法。 ? 所谓逆序解法,是从问题的最后一个阶段开始, 逆多阶段决策的实际过程反向寻优。 ? 顺序解法则从问题的最初阶段开始,同多阶段 决策的实际过程顺序寻优。 ? 具体采取哪一种解法,应根据问题的初始条件 和终端条件来决定。

2.5 动态规划模型的分类
动态规划 (按过程演变特征)
动态规划 (状态变量的取值)
离散性动态规划 连续性动态规划

确定性动态规划

随机性动态规划

动态规划 (阶段数是否固定)

定期的决策过程

不定期决策过程

§3 动态规划应用举例

? ? ? ?

资源分配问题 背包问题 生产与存贮问题 其它

资源分配问题
? 某公司拟将某种设备5台,分配给所属的甲、乙、丙三 个工厂,各工厂获得此设备后,预测可创造的利润如 下表所示,问应如何分配这5台设备给3个工厂,可使 所创造利润最大?
工厂 甲 0 3 7 9 12 13 乙 0 5 10 11 11 11 丙 0 4 6 11 12 12

设备台时
0 1 2 3 4 5

解:将问题按工厂分为三个阶段,甲、乙、丙三厂分 别编号为1、2、3厂。设: sk=在第k阶段可供分配的机器台数(k=1,2,3);或者说, 分配给第k个厂至第三个厂的设备台数(k=1,2,3) 。 xk=分配给第k个工厂的设备台数。 已知 s1=5,并有s2=T1(s1,x1)=s1-x1,s3=T2(s2,x2)=s2-x2,从sk 与xk的定义,可知s3=x3. 采用逆序算法:

第三阶段:
? 显然将s3(s3=0,1,2,3,4,5)台机器设备都分配给第3个工厂 时,也就是s3=x3时,第三阶段的指标值(即第3厂的盈 利)最大,即 max r3(s3,x3)=r3(s3,s3) 由于第3 阶段是最后的阶段,故有 f3(s3) =max r3(s3,x3)=r3(s3,s3) 其中x3可能取值为0,1,2,3,4,5.其数值计算见下 表:

其中x3*表示第3子过程上最优指标值f3(s3)时的x3的决 策即为最优决策。例如s3=4时,有r3(4,4)=12,有f3(4)=12,此 时x3*=4,即为最优决策。
x3 r3(s3,x3) 0 0 1 2 3 0 —— —— —— 1 —— 4 —— —— 2 —— —— 6 —— 3 —— —— —— 11 4 —— —— —— —— 5 —— —— —— ——

s3

f3(s3)
0 4 6 11

x 3*
0 1 2 3

4
5

——
——

——
——

——
——

——
——

12
——

——
12

12
12

4
5

第二阶段:
? 当把s2(s2=0,1,2,3,4,5)台设备分配给第2 个工厂和第3个 工厂时,则对每个s2值,有一种最优分配方案,使最大 盈利即最优。2子过程最优指标函数值为: f2(s2)=max [r2(s2,x2)+f3(s3)] 因为s3=s2-x2,上式也可以写成 f2(s2)=max [r2(s2,x2)+f3(s2-x2)] 其中,x2可取值0,1,2,3,4,5,其数值计算结果 如下表:

其中,在s2=4的这一行里,当x2=1时 r2(s2,x2)+f3(s2-x2)=r2(4,1)+f3(4-1) =r2(4,1)+f(3)=5+11=16 同样可知,当x2=2时,f2(s2) 也等于16。故这一行的最优 决策有两种。
x2 r2(s2,x2)+f3(s2-x2) 0 0 1 2 3 0+0 0+4 0+6 0+11 1 —— 5+0 5+4 5+6 2 —— —— 10+0 10+4 3 —— —— —— 11+0 4 —— —— —— —— 5 —— —— —— ——

s2

f2(s2)
0 5 10 14

x 2*
0 1 2 2

4
5

0+12
0+12

5+11
5+12

10+6
10+11

11+4
11+6

11+0
11+4

——
11+0

16
21

1,2
2

第一阶段:
? 把s1(s1=5)台设备分配给第1,第2,第3厂时,最大盈利 为 f1(5)=max [r1(5,x1)+f2(5-x1)] 其中x1可取值0,1,2,3,4,5。数值计算结果见下 表:

x1

r1(5,x1)+f2(5-x1)

s1
5

0
0+21

1
3+16

2
7+14

3
9+10

4
12+5

5
13+0

f1(x)
21

x1*
0,2

最终的最优分配结果有两个:
? 甲厂0台,乙厂2台,丙厂3台。 ? 甲厂2台,乙厂2台,丙厂1台。 ? 这两种分配方案都能得到最高的总盈利21万元。

背包问题

背包问题是指在携带物品总重量一定 的情况下,怎样将N种不同重量和不同价 值的物品装入背包,使得背包所装物品的 总价值最大?

? 某咨询公司有10 个工作日可以去处理四种类型的咨询项目,每种 类型的咨询项目中待处理的客户数量、处理每个客户所需的工作 日数以及所获得的利润如下表所示。显然该公司在10天内不能处 理完所有的客户,它可以自己挑选一些客户,其余的请其他咨询 公司去做,该咨询公司应如何选择客户使得在这10个工作日中获 利最大? 咨询项目类 型 1 2 3 4 待处理客户数 4 3 2 2 处理每个客户 处理每个客户 所需工作日 所获利润 1 3 4 7 2 8 11 20

按照咨询类型将决策分为四个阶段,第一阶段处理 第一种咨询类型的客户;第二、三、四阶段处理第二、 三、四种咨询类型的客户。设: sk=分配给第k种咨询项目到第四种咨询项目的所有 客户的总工作日(状态变量); xk=在第k种咨询项目中处理客户的数量(决策变 量)。 ? 显然,s1=10, s2=T1(s1,x1)=s1-x1, s3=T2(s2,x2)=s2-3x2, s4=T3(s3,x3)=s3-4x3=7x4.

第四阶段: s4=0,1,...,10,x4=[s4/7],中括号[ ]为取整符号, 因为s4≤10,所以x4可取0或1。 f4(s4)=max r4(s4,x4)=r4(s4,[s4/7]).计算结果如下
x4 s4 0 r4(s4,x4) 0 0 1 — 0 0 f4(s4) x4*

1
2 3 4 5 6 7

0
0 0 0 0 0 0


— — — — — 20

0
0 0 0 0 0 20

0
0 0 0 0 0 1

8
9 10

0
0 0

20
20 20

20
20 20

1
1 1

第三阶段:s3≤10,x3只可能为0,1,2。 f3(s3)=max[r3(s3,x3)+f4 (s3-4x3)]
x3 s3 0 1 2 0 0+0 0+0 0+0 r3(s3,x3) +f4(s3-4x3) 1 — — — 2 — — — 0 0 0 0 0 0 f3(s3) x3*

3
4 5

0+0
0+0 0+0


11+0 11+0


— —

0
11 11

0
1 1

6
7 8 9

0+0
0+20 0+20 0+20

11+0
11+0 11+0 11+0


— 22+0 22+0

20
20 22 22

1
0 2 2

10

0+20

11+0

22+0

22

2

第二阶段:s2≤10,x2只能取0,1,2,3。 f2(s2)=max[r2(s2,x2)+f3(s2-3x2)]
x2 r2(s2,x2)+f3(s2-3x2) f2(s2) x2* 0 0 0 1 0 0

s2
0 1 2 3 4 5

0
0+0 0+0 0+0 0+0 0+11 0+11

1
— — — 8+0 8+0 8+0

2
— — — — — —

3
— — — — — — 0 0 0 8 11 11

6
7 8

0+11
0+20 0+22

8+0
8+11 8+11

16+0
16+0 16+0


— —

16
20 22

2
0 0

9
10

0+22
0+22

8+11
8+20

16+0
16+11

24+0
24+0

24
28

3
1

第一阶段:s1=10,x1可取0,1,2,...,10。 f1(10)=max[r1(10,x1)+f2(10-x1)]

x1 s1
10

r1(10,x1)+f2(10-x1) 0
0+28

1
2+24

2
4+22

3
6+20

4
8+16

5
10+11

6
12+11

7
14+8

8
16+0

9
18+0

10
20+0

f1(s1) x1*
28 0

生产存贮问题
? 某公司为主要电力公司生产大型变压器,由于电力公 司采取预定方式购买,所以该公司可以预测未来几个 月的需求量。为确保需求,该公司为新的一年前四个 月制定一项生产计划,这四个月的需求如表所示。 ? 生产成本随着生产数量而变化。调试费为4,除了调试 费用外,每月生产的头两台各花费为2,后两台各花费 为1。最大生产能力为每月4台,生产成本如表所示。 ? 每台变压器在仓库中由这个月存到下个月的储存费用 为1,仓库的最大储存能力为3台,另外,知道在1月1 日时仓库里存有1台变压器,要求在4月30日仓库的库 存量为0。该如何制定生产计划,使得四个月的生产成 本和储存总费用最少?

表1、需求表
月份n 需求量(台)dn

1 2 3 4

2 4 1 3

表2、成本表
生产件数 0 1 2 3 4 总成本 0 6 8 9 10

按月份划分为四个阶段,设: sk为第k阶段期初库存量;k=1,2,3,4 xk为第k阶段的生产量;k=1,2,3,4 dk为第k阶段需求量;k=1,2,3,4 各个阶段的状态转移方程: s1=1 s2=1+x1-d1, s3=s2+x2-d2, s4=s3+x3-d3, 边界条件: 0=s4+x4-d4. 必须满足需求和生产能力约束。 每一阶段的效益函数由本阶段生产成本、上阶段生 产成本、存储费三部分构成。

生产费用

存储费用

第四阶段: s4=0,1,2,3. x4=0,1,2,3. d4=3. x4=d4-s4=3-s4. f4(s4)=min r4(s4,x4)=c4(3-s4)+h4(s4,3-s4)=c4(3-s4).

x4 s4 0 1 2 3 0 — — — 0

r4(s4,3-s4)=c4(3-s4) 1 — — 6 — 2 — 8 — — 3 9 — — —

f4(s4) 9 8 6 0

x4* 3 2 1 0

生产成本

存储费

第4阶段最优指 标函数

第三阶段: s3=0,1,2,3. x3=0,1,2,3,4. d3=1 s4=s3+x3-d3=s3+x3-1 f3(s3)=min [c3(x3)+1*(s3+x3-1)+f4(s3+x3-1)].
x3 s3 0 1 2 3 0 — 0+0+9 0+1+8 0+2+6 r3(s3,x3)+f4(s3+x3-1) 1 6+0+9 6+1+8 6+2+6 6+3+0 2 8+1+8 8+2+6 8+3+0 — 3 9+2+6 9+3+0 — — 4 10+3+0 — — — 13 9 9 8 4 0 0 0 f3(s3) x3*

第二阶段: s2=0,1,2,3. x2=0,1,2,3,4. d2=4 s3=s2+x2-d2=s2+x2-4 f2(s2)=min [c2(x2)+1*(s2+x2-4)+f3(s2+x2-4)].
x2 s2 0 1 2 3 0 — — — — 1 r2(s2,x2)+f3(s2+x2-4) 2 3 4 23 20 19 18 4 4 3 2 — — — 10+0+13 — — 9+0+13 10+1+9 — 8+0+13 9+1+9 10+2+9 6+0+13 8+1+9 9+2+9 10+3+8 f2(s2) x2*

第一阶段: s1=1, x1=0,1,2,3,4. d1=2 s2=s1+x1-d1=s1+x1-2=1+x1-2 f1(s1)=min [c1(x1)+1*(1+x1-2)+f2(1+x1-2)].

x1 s1 0 1 — 1

r1(s1,x1)+f2(1+x1-2)
2 8+1+20 3 9+2+19 4 10+3+18

f1(s1)

x1*

6+0+23

29

1; 2

其它问题

? 前面分析的主要是离散确定性问题的动态规划解法, 需要说明的是有的问题还可以用其他方法来求解。 ? 动态规划的其他问题还包括离散随机性问题,这时候 多了概率值,需要予以考虑。 ? 动态规划还包括连续性,这一类问题相对较复杂,超 出了本课程的研究范围。 ? 动态规划模型还可以用来求解线性规划、非线性规划、 整数规划,有兴趣的同学可以参看其他书籍。


相关文章:
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学-第3版-课件-动态规划例题_图文.ppt
运筹学-第3版-课件-动态规划例题 - 8.1 用动态规划方法求整数规划模型,而
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《运筹学》(第四版)清华大学出版社,融合多个版本运筹学课件优点。...
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 主要内容: §7.1 多阶段决策过程的最优化 §7.2 动态规划的基本概念和基本原理 ...
运筹学74动态规划应用举例.ppt
运筹学74动态规划应用举例_金融/投资_经管营销_专业资料。第七章 动态规划 ? ? ? ? 多阶段决策过程的最优化 动态规划的基本概念和基本原理 动态规划模型的建立...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划 (Dynamic programming) 背包问
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基本概念和基本原理 动态规划模型的建立与求解 应用举例 应用举例 1。背包问题 2。...
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划是用来解决多阶段决策过程最优 化的一种数量方法。其特
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件五 动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
第六章(上课) 运筹学动态规划04修改_图文.ppt
第六章(上课) 运筹学动态规划04修改_理学_高等教育_教育专区。(Dynamic programming) 1 主要内容一、多阶段决策问题 二、动态规划的基本概念三、动态规划的基本...
第八章 动态规划(运筹学讲义).ppt
? ? §2 动态规划的基本概念§3 基本原理和基本方程 §4 动态规划的应用 1 §1动态规划问题实例动态规划DP是运筹学的一个分支,是解决多阶段决策过程 最优化的...
运筹学第七章_动态规划(见28页)_图文.ppt
运筹学第七章_动态规划(见28页) - 第七章 动态规划 第一节 多阶段决策问
第七章运筹学动态规划_图文.ppt
第七章运筹学动态规划 - 动态规划 引言 □动态规划是解决多阶段决策过程最优化的
运筹学 07 动态规划_图文.ppt
运筹学 07 动态规划 - 1 多阶段决策过程的最优化 ? 概述 ? 多阶段决策过程及其最优化 ? 多阶段决策过程举例 ? 动态规划求解的多阶段决策问题的特点 ? 动态...
运筹学第10章 动态规划_图文.ppt
运筹学第10章 动态规划 - Page:1 管理运筹学 动态规划 Page:2 综 述 动态规划是解决多阶段决策过程最优 化问题的一种方法。动态规划所研究 的对象是多阶段...
运筹学中excel的运用(用excel解决线性规划、动态规划、....pdf
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题) - 1 . 线性规划 2 . 动态规划 3 . 图与网络分析 4 . 决策分析 ...
更多相关文章: