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

动态规划实例讲解


第九章 动态规划(续)
本章以下内容
动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例

1

动态规划的基本原理
最优化原理 (贝尔曼最优化原理) 作为一个全过程的最优策略具有这样 的性质:对于最优策略过程中的任意状态 而言,无论其过去的状态和决策如何,余 下的诸决策必构成一个最优子策略。该原 理的具体解释是,若某一全过程最优策略 为:
? ? ? p1? ( s1 ) ? {u1? (s1 ), u 2 ( s 2 ), ?, u k ( s k ), ?u n ( s n )}

则对上述策略中所隐含的任一状态而言, 第k子过程上对应于该状态的最优策略必然 包含在上述全过程最优策略p1*中,即为
? ? ? ? p k ( s k ) ? {u k ( s k ), u k ?1 ( s k ?1 ), ?, u n ( s n )}
2

3.动态规划方法的基本步骤
1.应将实际问题恰当地分割成n个子 问题(n个阶段)。通常是根据时间或空间 而划分的,或者在经由静态的数学规划 模型转换为动态规划模型时,常取静态 规划中变量的个数n,即k=n。 2.正确地定义状态变量sk ,使它既 能正确地描述过程的状态,又能满足无 后效性.动态规划中的状态与一般控制 系统中和通常所说的状态的概念是有所 不同的,动态规划中的状态变量必须具 备以下三个特征:
3

3.动态规划方法的基本步骤

(1)要能够正确地描述受控过程的变化特征。 (2)要满足无后效性。即如果在某个阶段状态 已经给定,那么在该阶段以后,过程的发展不受 前面各段状态的影响,如果所选的变量不具备无 后效性,就不能作为状态变量来构造动态规划的 模型。 (3)要满足可知性。即所规定的各段状态变量 的值,可以直接或间接地测算得到。一般在动态 规划模型中,状态变量大都选取那种可以进行累 计的量。此外,在与静态规划模型的对应关系上, 通常根据经验,线性与非线性规划中约束条件的 个数,相当于动态规划中状态变量sk的维数.而 前者约束条件所表示的内容,常就是状态变量sk 4 所代表的内容。

3.动态规划方法的基本步骤
3.正确地定义决策变量及各阶段的允许 决策集合 Uk(sk),根据经验,一般将问题中待 求的量,选作动态规划模型中的决策变量。或 者在把静态规划模型(如线性与非线性规划)转 换为动态规划模型时,常取前者的变量 xj为后 者的决策变量uk。 4. 能够正确地写出状态转移方程,至少 要能正确反映状态转移规律。如果给定第k阶 段状态变量 sk 的值,则该段的决策变量 uk 一经 确定,第k+1段的状态变量sk+1的值也就完全确 定,即有sk+1=Tk(sk ,uk)
5

3.动态规划方法的基本步骤
5.根据题意,正确地构造出目标与变量的 函数关系——目标函数,目标函数应满足下列性 质: (1)可分性,即对于所有 k 后部子过程,其 目 标 函 数 仅 取 决 于 状 态 sk 及 其 以 后 的 决 策 uk ,uk+1,┈,un,就是说它是定义在全过程和所 有后部子过程上的数量函数。 (2)要满足递推关系,即 Rk ,n ( s k , u k , s k ?1 , u k ?1 ,?, s n?1 ) ? ? k [ s k , u k , Rk ?1 (s k ?1 ,?, s n?1 )] (3)函数 ? k [s k , uk , Rk ?1 (sk ?1 ,?, sn?1 )] 对其变元Rk+1来 说要严格单调。
6

3.动态规划方法的基本步骤
6.写出动态规划函数基本方程 例如常见的指标函数是取各段指标和的形 n 式
Rk ( s k ) ?

?g
i ?k

i

( si , u i )

其中 g i ( si , u i ) 表示第i阶段的指标,它 显然是满足上述三个性质的。所以上式 可以写成 :
Rk ? g k (sk , u k ) ? Rk ?1 (sk ?1 ,??, sn?1 )
7

4.动态规划方法应用举例
学习方法建议: 第一步 先看问题,充分理解问题 的条件、情况及求解目标。 第二步 结合前面讲到的理论和解 题过程,考虑如何着手进行求解该问题 的工作。分析针对该动态规划问题的 “四大要素、一个方程”——这一步在 开始时会感到困难,但是一定要下决心 去思考,在思考过程中深入理解前文讲 到的概念和理论。
8

4.动态规划方法应用举例
第三步 动手把求解思路整理出 来,或者说,把该问题作为习题独立的 来做。 第四步 把自己的求解放到一边, 看书中的求解方法,要充分理解教材中 的论述。 第五步 对照自己 的求解,分析成败。
9

12

求 最 短 路 径

求 最 短 路 径
例5.5
2 A 1 5 B1 10 6 B2 4 13 B3 12 11 10 C2 5 8 C3 10 D2 2 12 14 9 6 E D1 5 C1 3

阶段 1 阶段 2

阶段 3 阶段 4

阶段 5
13

求 最 短 路 径
将问题分成五个阶段,第k阶段到 达的具体地点用状态变量xk表示,例 如:x2=B3表示第二阶段到达位置B3, 等等。这里状态变量取字符值而不是 数值。 将决策定义为到达下一站所选择的 路径,例如目前的状态是 x2=B3 ,这时 决策允许集合包含三个决策,它们是 D2(x2)=D2(B3)={B3?C1,B3?C2,B3?C3}
14

求 最 短 路 径
最优指标函数fk(xk)表示从目前状态 到E的最短路径。终端条件为 f5(x5)=f5(E)=0 其含义是从E到E的最短路径为0。 第四阶段的递推方程为 :
f 4 (x4 ) ?
d4 ? 4 ( x4 ) D

min {v4 (x4 , d 4 ) ? f5 (x5 )}

从 f5 (x5 )到 f4 (x4 )的递推过程用下表表示:
x4 D4 (x4 ) x5 v4 (x4 ,d4 ) v4 (x4 ,d4 )+f5 (x5 ) f4 (x4 ) 最优决策 d4 *

D1 D1 ?E E D2 D2 ?E E

5 2

5+0=5* 2+0=2*

5 2

D1 ?E D2 ?E
15

求 最 短 路 径
其中*表示最优值,在上表中,由于决策允 许集合D4(x4)中的决策是唯一的,因此这个 值就是最优值。 由此得到f4(x4)的表达式。由于这是 一个离散的函数,取值用列表表示:
f4 (x4 ) 的表达式 x4 f4 (x4 ) D1 5 D2 2 最优决策 d4 * D1 ?E D2 ?E
16

求 最 短 路 径
第三阶段的递推方程为:

f 3 ( x3 ) ? min {v3 ( x3 , d 3 ) ? f 4 ( x4 )}
d 3 ?D3 ( x3 )
x3 D3 (x3 ) x4 v3 (x3 ,d3 v3 (x3 ,d3 )+f4 (x f3 (x3 最优决策 d3 * ) ) 4)

从 f4 (x4 )到 f3 (x3 )的递推过程用表格表示如下:
C1 ?D1 C1 ?D2 C2 ?D1 C2 ?D2 C3 ?D1 C3 ?D2 D1 D2 D1 D2 D1 D2 3 9 6 5 8 10 3+5=8* 9+2=11 6+5=11 5+2=7* 8+5=13 10+2=12*

C1 C2 C3

8 7 12

C1 ?D1 C2 ?D2 C3 ?D2
17

求 最 短 路 径
由此得到f3(x3)的表达式:

x3 f3 (x3 ) C1 8 C2 7 C3 12

最优决策 d3 * C1 ?D1 C2 ?D2 C3 ?D2

第二阶段的递推方程为:

f 2 ( x2 ) ? min {v2 ( x2 , d 2 ) ? f 3 ( x3 )}
d 2 ?D2 ( x2 )

从 f3(x3)到 f2(x2)的递推过程用表格表 示如下:
18

求 最 短 路 径
x2 D2 (x2 ) x3 v2 (x2 ,d2 ) v2 (x2 ,d2 )+f3 (x3 ) f2 (x2 ) 最优决策 d2 *

B1 ?C1 B1 B1 ?C2 B1 ?C3 B2 ?C1 B2 B2 ?C2 B2 ?C3 B3 ?C1 B3 B3 ?C2 B3 ?C3

C1 C2 C3 C1 C2 C3 C1 C2 C3

12 14 10 6 10 4 13 12 11

12+8=20* 14+7=21 10+12=22 6+8=14* 10+7=17 4+12=16 13+8=21 12+7=19* 11+12=23

20

B1 ?C1

14

B2 ?C1

19

B3 ?C2
19

求 最 短 路 径
由此得到f2(x2)的表达式:
x2 B1 B2 B3 f2 (x2 ) 20 14 19 最优决策 d2 * B1 ?C1 B2 ?C1 B3 ?C2
20

求 最 短 路 径
第一阶段的递推方程为:

f 1 ( x 1 ) ? min { v 1 ( x 1 , d 1 ) ? f 2 ( x 2 )}
d 1 ? D 1 ( x1 )

从 f2 (x2 )到 f1 (x1 )的递推过程用表格表 示如下:
x1 D1 (x1 ) x2 v1 (x1 ,d1 ) v1 (x1 ,d1 )+f2 (x2 ) f1 (x1 ) 最优决策 d1 *

A ?B1 B1 A A ?B2 B2 A?B3 B3

2 5 1

2+20=22 5+14=19* 1+19=20

19

A ?B

2

21

求 最 短 路 径
由此得到f1(x1)的表达式
x1 f1 (x1 ) 最优决策 d1 * A 19 A ?B2

22

23

资 源 分 配 问 题

资 源 分 配 问 题
例5.6: 有资金4万元,投资A、B、C三个项 目,每个项目的投资效益与投入该项目的 资金有关。三个项目A、B、C的投资效益 (万吨)和投入资金(万元)关系见下表:

求对三个项目的最优投资分配,使 总投资效益最大。

24

资 源 分 配 问 题
1. 2. 3. 4.

5.
6. 7. 8.

阶段k:每投资一个项目作为一个阶段; 状态变量xk:投资第k个项目前的资金 数; 决策变量dk:第k个项目的投资; 决策允许集合:0≤dk≤xk 状态转移方程:xk+1=xk-dk 阶段指标:vk(xk ,dk)见表中所示; 递推方程: fk(xk)=max{vk(xk ,dk)+fk+1(xk+1)} 终端条件:f4(x4)=0
25

资 源 分 配 问 题
k=4,f4(x4)=0 k=3,0≤d3≤x3,x4=x3-d3

26

k=2,0≤d2≤x2,x3=x2-d2

资 源 分 配 问 题

27

资 源 分 配 问 题
k=1,0≤d1≤x1,x2=x1-d1

28

29

背 包 问 题

背 包 问 题

30

背 包 问 题
则 Max s.t.
1. 2. 3.

z= c1x1+c2x2+…+cnxn w1x1+w2x2+…+wnxn≤W x1,x2,…,xn为正整数

阶段k:第k次装载第k种物品 (k=1,2,…,n) 状态变量 xk :第 k 次装载时背包还 可以装载的重量; 决策变量 dk:第 k次装载第k 种物品 的件数;
31

背 包 问 题
决策允许集合: Dk(xk)={dk|0? dk?xk/wk,dk为整数}; 5. 状态转移方程:xk+1=xk-wkdk 6. 阶段指标:vk=ckdk 7. 递推方程 fk(xk)=max{ckdk+fk+1(xk+1)} =max{ckdk+fk+1(xk-wkdk)} 8. 终端条件:fn+1(xn+1)=0
4.
32

例5.7:对于一个具体问题c1=65, c2=80,c3=30;w1=2,w2=3,w3=1;以 及 W=5 用动态规划求解 f4(x4)=0 对于k=3

背 包 问 题

列出 f3(x3)的数值表
33

对于k =3

列出 f3(x3)的数值表如下:

34

对于k=2
f 2 ( x2 ) ? ?
0? d 2 ? x2 / w2 0 ? d 2 ? x2 / 3

max {c 2 d 2 ? f 3 ( x3 )}

max {80d 2 ? f 3 ( x 2 ? 3d 2 )}

列出f2(x2)的数值表

35

对于k=1
f 1 ( x1 ) ? ?
0? d1 ? x1 / w1 0? d1 ? x1 / 2

max {c1 d1 ? f 2 ( x 2 )}

max {65d1 ? f 2 ( x1 ? 2d1 )}

列出f1(x1)的数值表

36

由题意知,x1 =5,由表 f1 (x1 )、f2 (x2 )、

f3 (x3 ),经回朔可得: d1 *=2,x2 =x1 -2d1 =1,d2 *=0,x3 =x2 -3d2 =1, d3 *=1,x4 =x3 -d3 =0
即应取第一种物品 2 件,第三种物品 1 件,最 高价值为 160 元,背包没有余量。由 f1 (x1 ) 得列表可以看出,如果背包得容量为 W=4,

W=3,W=2 和 W=1 时,相应的最优解立即可以
得到。
37

38

机器负荷分配问题

最短路径问题和背包问题的状态变量和决策变 量都只能取离散的整数值。 当状态变量和决策变量的 取值范围很大, 或者这些变量是连续的,用列举的方 法就比较困难或者根本不可能了。 这就需要用连续变 量的处理方法。 例 5.8:某种机器可以在高、低两种负荷下生产。 高负荷生产条件下机器完好率为 0.7,即如果年初有 u 台完好机器投入生产,则年末完好的机器数量为 0.7u 台。系数 0.7 称为完好率。年初投入高负荷运 行的 u 台机器的年产量为 8u 吨。系数 8 称为单台产 量。低负荷运行时,机器完好率为 0.9,单台产量为 5 吨。设开始时有 1000 台完好机器,要制订五年计 划,每年年初将完好的机器一部分分配到高负荷生 产, 剩下的机器分配到低负荷生产,使五年的总产量 为最高。
39

机器负荷分配问题

构造动态规划模型如下: 阶段k:运行年份(k=1,2,3,4,5,6), 其中k=1表示第一年初,…,依次类推; k=6表示第五年末(即第六年初)。 状态变量xk:第k年初完好的机器数 (k=1,2,3,4,5,6),其中x6表示第五年末 (即第六年初)的完好机器数。 决策变量dk:第k年投入高负荷运行的 机器数; 状态转移方程:xk+1=0.7dk+0.9(xk-dk) 决策允许集合:Dk(xk)={dk|0?dk?xk} 阶段指标:vk(xk ,dk)=8dk+5(xk-dk) 40 终端条件:f6(x6)=0

机器负荷分配问题
递推方程:

fk(xk)=max{vk(xk,dk)+fk+1(xk+1)}
dk?Dk(xk)

=

0?dk?xk

max{8dk+5(xk- dk)+fk+1[0.7dk+0.9(xk-dk)]}

根据题意,本题的决策允许集合应该是 一个整数集合,但由于决策允许集合中可取 的决策数量很大,一一列举计算量很大,不 妨认为状态变量和决策变量都是连续的,得 到最优解后,再作取整处理。
41

机器负荷分配问题
f5(x5)=max{8d5+5(x5-d5)+f6(x6)}
0?d5?x5

=max{3d5+5x5}=8x5, d5*=x5
0?d5?x5

f4(x4)=max{8d4+5(x4-d4)+f5(x5)}
0?d4?x4

=max{8d4+5(x4-d4)+8x5}
0?d4?x4 0?d4?x4

=max{8d4+5(x4-d4)+8[0.7d4+0.9(x4-d4)]}
=max{1.4d4+12.3x4}=13.7x4, d4*=x4
0?d4?x4
42

机器负荷分配问题
f3(x3)=max{8d3+5(x3-d3)+f4(x4)}
0?d3?x3

=max{8d3+5(x3-d3)+13.7x4}
0?d3?x3

=max{8d3+5(x3-d3)+13.7[0.7d3+0.9(x3-d3)]}
0?d3?x3 0?d3?x3

=max{0.28d3+17.24x3}=17.52x3, d3*=x3

43

机器负荷分配问题
f2(x2)=max{8d2+5(x2-d2)+f3(x3)}
0?d2?x2

=max{8d2+5(x2-d2)+17.52x3}
0?d2?x2 0?d2?x2 0?d2?x2

=max{8d2+5(x2-d2)+17.52[0.7d2+0.9(x2-d2)]}
=max{-0.504d2+20.77x2}=20.77x2,d2*=0

44

机器负荷分配问题
f1(x1)=max{8d1+5(x1-d1)+f2(x2)} 0?d ?x =max{8d1+5(x1-d1)+20.77x2}
1 1

=max{8d1+5(x1-d1)+20.77[0.7d1+0.9(x1-d1)]} =max{-0.05d1+23.69x1}=23.69x1,d1*=0
0?d1?x1
0?d1?x1

0?d1?x1

45

机器负荷分配问题
由此可以得到: ? f1(x1)=23.69x1, d1*=0 ? f2(x2)=20.77x2, d2*=0 ? f3(x3)=17.52x3, d3*=x3 ? f4(x4)=13.60x4, d4*=x4 ? f5(x5)=8x5 d5*=x5 用x1=1000代入,得到五年最大产量为 ? f1(x1)=f1(1000)=23690
46

机器负荷分配问题
每年投入高负荷运行的机器数以每年初完 好的机器数为:
?
?

?
? ? ?

x1=1000 d1*=0, x2=0.7d1+0.9(x1-d1)=900 d2*=0, x3=0.7d2+0.9(x2-d2)=810 d3*=x3=810, x4=0.7d3+0.9(x3-d3)=567 d4*=x4=567, x5=0.7d4+0.9(x4-d4)=397 d5*=x5=397, x6=0.7d5+0.9(x5-d5)=278
47

?

在这个例子中,状态变量的终端值x6 是未加约束的,如果要求在第五年末(即 第六年初)完好的机器数不少于500台,这 时决策变量d5的决策允许集合将成为: D5(x5)={d5|0.7d5+0.9(x5-d5)?500, d5?0} 即 0.9x5-0.2d5?500 d5?0 或 0?d5?4.5x5-2500 容易想象,这时的最大产量将比 x6是 自由的情况下小。 这个例子可以推广到一般情况。设 高负荷生产时机器的完好率为 k1 ,单台 产量为p1;低负荷完好率为k2,单台产量 48 为p2。若有t满足:

机器负荷分配问题

机器负荷分配问题
n ? ( t ?1) n ?t p1 ? p2 i i ? k1 ? p (k ? k ) ? ? k1 i ?0 i ?0 1 2 1

则从1—t-1年,年初将全部完好机器 投入低负荷运行,从t—n年,年初将 全部完好机器投入高负荷运行,这样 的决策,将使总产量达到最大。
49

50

生 产 库 存 问 题

例5.9:一个工厂生产某种产品,17月份生产成本和产品需求量的变化情 况如下表:
月份(k) 生产成本(ck ) 需求量(rk ) 1 0 2 8 3 5 4 3 5 2 6 7 7 4 11 18 13 17 20 10 15

生 产 库 存 问 题

为了调节生产生产和需求, 工厂设 有一个产品仓库, 库容量 H=9。 已知期 初库存量为 2,要求期末(七月低)库 存量为 0。 每个月生产的产品在月末入 库,月初根据当月需求发货。求七个 月的生产量,能满足各月的需求,并 使生产成本最低。 51

生 产 库 存 问 题
? ? ? ? ? ? ? ?

阶段k:月份,k=1,2,…,7,8; 状态变量 xk:第 k个月初(发货以前)的 库存量; 决策变量dk:第k个月的生产量; 状态转移方程:xk+1=xk-rk+dk; 决策允许集合: Dk(xk)={dk | dk?0, rk+1?xk+1?H } ={dk | dk?0, rk+1?xk-rk+dk?H }; 阶段指标:vk(xk ,dk)=ckdk; 终端条件:f8(x8)=0, x8=0;
52

生 产 库 存 问 题
递推方程: fk(xk)=min{vk(xk ,dk)+fk+1(xk+1)}
dk?Dk(xk)

? 对于k=7 ? 因为 x8=0 ?有 d7=0 ? 递推方程为 ? f7(x7)=min{c7d7+f8(x8)}=0

dk?Dk(xk)

=min{ckdk+fk+1(xk-rk+dk)}

d7=0

53

生 产 库 存 问 题
对于k=6 因为 d7=0,所以 x7=r7=4 而 x6-r6+d6=x7=4 因此有 d6=x7+r6-x6=4+7-x6=11-x6 也是唯一的决策。因此递推方程 为: f6(x6)=min{c6d6+f7(x7)}
d6=11-x6

=10d6=10(11-x6)=110-10x6
54

生 产 库 存 问 题
对于k=5 f5(x5)=min{c5d5+f6(x6)} d5?D5(x5) =min{20d5+110-10x6} d5?D5(x5) =min{20d5+110-10(x5-r5+d5)}
d 5 ? D 5(x 5) d 5 ? D 5(x 5)

=min{20d5+110-10(x5-2+d5)}
=min{10d5-10x5+130}
d 5 ? D 5( x5)

D5(x5) ={d5| d5?0, r6?x5-r5+d5?H } ={d5|d5?0, r6+r5-x5?d5?H+r5-x5} ={d5| d5?0, 9-x5?d5?11-x5}
55

生 产 库 存 问 题
因为x5?H=9,因此9-x5?0,决策允 许集合可以简化为 D5(x5)={d5| 9-x5?d5?11-x5} 递推方程成为 f5(x5)=min{10d5-10x5+130}
9-x5?d5?11-x5

=10(9-x5)-10x5+130 =220-20x5 d5*=9-x5
56

生 产 库 存 问 题
对于k=4 f4(x4)=min{c4d4+f5(x5)}
d4?D4(x4)

=min{17d4+220-20x5}
d4?D4(x4)
d4?D4(x4) d4?D4(x4) d4?D4(x4)

=min{17d4+220-20(x4-r4+d4)} =min{17d4+220-20(x4-3+d4)} =min{-3d4-20x4+280}
57

生 产 库 存 问 题
D4(x4)={d4| d4?0, r5?x4-r4+d4?H} ={d4| d4?0, r5+r4-x4?d4?H+r4-x4} ={d4| d4?0, 5-x4?d4?12-x4} ={d4| max[0,5-x4]?d4?12-x4}

由于 在f4(x4)的表达式中d4的系数是-3, 因此d4在决策允许集合中应取集合中的 最大值,即d4=12-x4 由此 f4(x4)=-3(12-x4)-20x4+280 =-17x4+244
58

生 产 库 存 问 题
对于k=3 f3(x3)=min {c3d3+f4(x4)} d3?D3(x3) =min {13d3+244-17x4} d3?D3(x3) =min {13d3+244-17(x3-r3+d3)}

=min {-4d3-17x3+329} d3?D3(x3) D3(x3)={d3| d3?0,r4?x3-r3+d3?H} ={d3| d3?0,r4+r3-x3?d3?H+r3-x3} ={d3| d3?0,8-x3?d3?14-x3} ={d3| max[0,8-x3]?d3?14-x3} 由此 f3(x3)=-4(14-x3)-17x3+329 =-13x3+273, d3*=14-x3

d3?D3(x3)

59

生 产 库 存 问 题
对于k=2 f2(x2)=min{c2d2+f3(x3)} d2?D2(x2) =min{18d2+273-13x3} d2?D2(x2) =min{18d2+273-13(x2-r2+d2)}
d2?D2(x2)

=min{18d2+273-13(x2-8+d2)}
=min{5d2-13x2+377} d2?D2(x2) D2(x2)={d2|d2?0,r3?x2-r2+d2?H} ={d2|d2?0,r3+r2-x2?d2?H+r2-x2} ={d2|d2?0,13-x2?d2?17-x2}
60

d2?D2(x2)

生 产 库 存 问 题
因为 13-x2>0 所以 d2(x2)={d2|13-x2?d2?17-x2} 由此 f2(x2)=5(13-x2)-13x2+377 =-18x2+442, d2*=13-x2

61

生 产 库 存 问 题
对于k=1 f1(x1)=min{c1d1+f2(x2)} d1?D1(x1) =min{11d1+442-18x2} d1?D1(x1) =min{11d1+442-18(x1-r1+d1)}

=min{11d1+442-18(x1-0+d1)}
=min{-7d1-18x1+442}
d1?D1(x1)
d1?D1(x1)

d1?D1(x1)

D1(x1)={d1|d1?0,r2?x1-r1+d1?H} ={d1|d1?0,r2+r1-x1?d1?H+r1-x1} ={d1|d1?0,8-x1?d1?9-x1}

62

生 产 库 存 问 题
根据题意 x1=2 所以 D1(x1)={d1| 6?d1?7} 由此 d1=7 f1(x1)=-7d1-18x1+442 =-7×7-18×2+442 =357
将以上结果总结成下表:
k ck rk xk dk 1 2 3 4 5 6 7 11 18 13 17 20 10 15 0 8 5 3 2 7 4 2 9 5 9 9 7 4 7 13-x2=4 14-x3=9 12-x4=3 9-x5=0 11-x6=4 0
63

64

设 备 更 新 问 题

设 备 更 新 问 题

一台设备的价格为P,运行寿命为n年, 每年的维修费用是设备役龄的函数,记 为C(t),新设备的役龄为t=0。旧设备出 售的价格是设备役龄的函数,记为 S(t)。 在 n 年末,役龄为 t 的设备残值为 R(t)。 现有一台役龄为T的设备,在使用过程中, 使用者每年都面临“继续使用”或“更 新”的策略,

65

阶段 k:运行年份; 状态变量 xk :设备的役龄 t; 决策变量 dk :
?R dk ? ? ?K (Re place )更新 ( Keep )继续使用

状态转移方程:
x k ?1

阶段指标:

?1 ? ? ? xk ? 1

dk ? R dk ? K
dk ? R dk ? K dk ? R dk ? K
66

? P ? C (0) ? S ( xk ) vk ? ? ?C ( x k ) ? P ? C (0 ) ? S (t ) ? ? ?C (t )

设 备 更 新 问 题
递推方程:
? P ? C (0) ? S ( xk ) ? f k ?1 ( xk ?1 ) f k ( xk ) ? min ? ?C ( xk ) ? f k ?1 ( xk ?1 ) ? P ? C (0) ? S (t ) ? f k ?1 (1) ? min ? ?C (t ) ? f k ?1 (t ? 1) dk ? R dk ? K dk ? R dk ? K

终端条件: fn(t)=-R(t)

67

设 备 更 新 问 题
例5.10:设具体数据如下:
T C(t) S(t) R(t) 0 1 2 3 4 5 6 10 13 20 40 70 100 100 -- 32 21 11 5 0 0 -- 25 17 8 0 0 0 7 -0 0

且 n=5,T=2,P=50
由上表开始,终端条件为: f6 (1)=-25,f6 (2)=-17,f6 (3)=-8 f6 (4)=f6 (5)=f6 (6)=f6 (7)=0
68

对于 k=5:

?P ? C(0) ? S (t ) ? f 6 (1)? f5 (t ) ? min? ? ?C(t ) ? f 6 (t ? 1) ?

d5 ? R d5 ? K

?P ? C(0) ? S (1) ? f6 (1)? ?50 ?10 ? 32 ? (?25)? f5 (1) ? min? ? ? min? ? ?13? (?17) ? ?C(1) ? f6 (2) ? ?3? ? min? ? ? ?4 , ?? 4?
* d5 ? K

?P ? C(0) ? S (2) ? f6 (1)? ?50 ?10 ? 21? (?25)? f5 (2) ? min? ? ? min? ? ?20 ? (?8) ? ?C(2) ? f6 (3) ? ?14? ? min? ? ? 12, ?12?
* d5 ? K

69

? P ? C (0) ? S (3) ? f 6 (1)? ?50 ? 10 ? 11 ? (?25)? f 5 (3) ? min ? ? ? min ? ? ?40 ? 0 ? ?C (3) ? f 6 (4) ? ?24? ? min ? ? ? 24 , ?40?
* d5 ? R

? P ? C (0) ? S (4) ? f 6 (1)? ?50 ? 10 ? 5 ? (?25)? f 5 (4) ? min ? ? ? min ? ? ?70 ? 0 ? ?C (4) ? f 6 (5) ? ?30? ? min ? ? ? 30 , ?70?
* d5 ? R

? P ? C (0) ? S (5) ? f 6 (1)? ?50 ? 10 ? 0 ? (?25)? f 5 (5) ? min ? ? ? min ? ? ?100 ? 0 ? ?C (5) ? f 6 (6) ? ? 35 ? ? min ? ? ? 35 ,
* d5 ? R
70

? P ? C (0) ? S (6) ? f 6 (1)? ?50 ? 10 ? 0 ? (?25)? f 5 (6) ? min ? ? ? min ? ? ?100 ? 0 ? ?C (6) ? f 6 (7) ? ? 35 ? ? min ? ? ? 35 , ?100? d 5* ? R

对于 k=4:

?P?C(0) ? S(t) ? f5(1)? f4(t) ? min ? ? ?C(t) ? f5(t ?1) ?

d4 ? R d4 ? K

?P ? C(0) ? S(1) ? f5 (1)? ?50 ?10 ? 32 ? (?4)? f4 (1) ? min? ? ? min? ? C(1) ? f5 (2) ?13?12 ? ? ? ?24? ? min? ? ? 24, ?25?
* d4 ? R
71

? P ? C ( 0 ) ? S ( 2 ) ? f 5 (1) ? f 4 ( 2 ) ? min ? ? ? C ( 2 ) ? f 5 ( 3) ? ?50 ? 10 ? 21 ? ( ? 4 ) ? ? min ? ? ? 20 ? 24 ? ? 35 ? ? min ? ? ? 35 , ? 44 ?
* d4 ? R

? P ? C (0) ? S (3) ? f 5 (1)? f 4 (3) ? min ? ? ?C (3) ? f 5 (4) ? ?50 ? 10 ? 11 ? (?4)? ? min ? ? ?40 ? 30 ? ?45? ? min ? ? ? 45 , 70 d ?R
* 4
72

?P ? C(0) ? S (4) ? f5 (1)? f 4 (4) ? min? ? ?C(4) ? f5 (5) ? ?50 ?10 ? 5 ? (?4)? ? min? ? ?70 ? 35 ? ? 51 ? ? min? ? ? 51, ?105?
* d4 ? R

?P ? C(0) ? S(5) ? f5 (1)? f4 (5) ? min? ? ?C(5) ? f5 (6) ? ?50?10? 0 ? (?4)? ? min? ? ?100? 35 ? ? 56 ? ? min? ? ? 56, 135 d ?R
* 5
73

对于 k=3:

?P ? C(0) ? S(t) ? f4 (1)? f3 (t) ? min? ? ?C(t) ? f4 (t ?1) ?
? P ? C (0) ? S (1) ? f 4 (1) ? f 3 (1) ? min ? ? ?C (1) ? f 4 (2) ? ?50 ? 10 ? 32 ? 24? ? min ? ? ?13 ? 35 ? ?52 ? ? min ? ? ? 48 , ?48? d ?K
* 3

d3 ? R d3 ? K

74

? P ? C (0) ? S (2) ? f 4 (1)? ?50 ? 10 ? 21 ? 24? f 3 (2) ? min ? ? ? min ? ? ?20 ? 45 ? ?C (2) ? f 4 (3) ? ?63? ? min ? ? ? 63 , ?65?
* d3 ? R

? P ? C (0) ? S (3) ? f 4 (1)? ?50 ? 10 ? 11 ? 24? f 3 (3) ? min ? ? ? min ? ? ?40 ? 51 ? ?C (3) ? f 4 (4) ? ?73? ? min ? ? ? 73 , ?91? d ?R
* 3

? P ? C (0) ? S (4) ? f 4 (1)? ?50 ? 10 ? 5 ? 24? f 3 (4) ? min ? ? ? min ? ? ?70 ? 56 ? ?C (4) ? f 4 (5) ? ? 79 ? ? min ? ? ? 79 , ?126?
* d3 ? R
75

(1) ? d2 ? R f 2 (t ) ? min ? ? d2 ? K ?C (t ) ? f 3 (t ? 1) ? ? P ? C ( 0 ) ? S (1) ? f 3 (1) ? f 2 (1) ? min ? ? ? C (1) ? f 3 ( 2 ) ? ? 50 ? 10 ? 32 ? 48 ? ? min ? ? ?13 ? 63 ? ? 76 ? * * ? min ? ? ? 76 , d2 ? K 或者 d 2 ? R ? 76 ? ? P ? C ( 0 ) ? S ( 2 ) ? f 3 (1) ? ?50 ? 10 ? 21 ? 48 ? f 2 ( 2 ) ? min ? ? ? min ? ? ? 20 ? 73 ? ? C ( 2 ) ? f 3 ( 3) ?
3

对于 k=2: C (0) ? S (t ) ? f ?P ?

?87 ? ? min ? ? ? 87 , 93

* d2 ? R

76

? P ? C (0) ? S (3) ? f 3 (1)? ?50 ? 10 ? 11 ? 48? f 2 (3) ? min ? ? ? min ? ? ?40 ? 79 ? ?C (3) ? f 3 (4) ? ? 97 ? ? min ? ? ? 73 , 97 ?119?
* d2 ? R

对于 k=1:
?P ? C (0) ? S (t ) ? f 2 (1)? f1 (t ) ? min ? ? ?C (t ) ? f 2 (t ? 1) ? d1 ? R d1 ? K

? P ? C (0) ? S (2) ? f 2 (1)? ?50 ? 10 ? 21 ? 76? f1 (2) ? min ? ? ? min ? ? ?20 ? 97 ? ?C (2) ? f 2 (3) ? ?115? ? min ? ? ? 115 , ?117? d1* ? R
77

设 备 更 新 问 题
由以上计算可知,本问题有两个 决策,它们对应的最小费用都是115。

这两个决策是
年份 1 2 3 4 5 决策 1 更新 更新 继续 更新 继续 决策 2 更新 继续 更新 更新 继续

78


赞助商链接
相关文章:
动态规划讲解
动态规划详解 19页 免费 动态规划讲解 暂无评价 39页 7下载券 动态规划入门讲解(一) 36页 1下载券 动态规划实例讲解 78页 免费 动态规划基础讲解及经典... 60...
树型动态规划的实例分析(完美整理)
树型动态规划实例分析(完美整理)_计算机软件及应用_IT/计算机_专业资料。树型...样例输入 5 1 1 2 3 2 3 4 3 5 1 10 20 20 样例输出 21 解析:因为...
动态规划理论(精华)
四.动态规划方法实现的灵活性与技巧性上述例子给出了一般情况下的动态规划思维...动态规划讲解大全(含例题... 13页 1下载券 现代控制理论_第9章_动态... ...
动态规划实例源代码
动态规划实例源代码_理学_高等教育_教育专区。动态规划实例源代码今日...动态规划实例详解 52页 2下载券 动态规划实例分析 95页 3下载券喜欢...
动态规划算法举例分析
动态规划算法介绍 基本思想是将待求解问题分解成若干子问题,先求解子问题,最后用...算法合集之《动态规划的... 30页 免费 动态规划实例讲解 78页 免费 程序设计...
动态规划入门篇
动态规划思想在信息奥赛中的应用作者:陈喻(2008 年 10 月 7 日)关键字:动态...(牛X)动态规划入门篇 60页 5下载券 喜欢此文档的还喜欢 动态规划实例讲解 78...
动态规划:从新手到专家
使用动态规划来解题只需要多项式时间 复杂度,因此它比回溯法、暴力法等要快许多。 现在让我们通过一个例子来了解一下DP的基本原理。 首先,我们要找到某个状态的最...
动态规划算法原理与应用
的基本思想 和基本步骤, 并通过几个实例的分析, 研究了利用动态规划设计算法的...特别是对于离 散的问题, 由于解析数学无法发挥作用, 动态规划便成为了一种非常...
动态规划入门(论文)
下面通过对具体实例的分析, 帮助大家领会动态规划的这两个性质和动态规划的 算法设计思想 例:导弹拦截 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统.但是...
动态规划算法原理及应用
的基本思想 和基本步骤, 并通过几个实例的分析, 研究了利用动态规划设计算法的...特别是对于离 散的问题, 由于解析数学无法发挥作用, 动态规划便成为了一种非常...
更多相关标签: