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

运筹学 动态规划应用


第七章 动态规划
动态规划问题的基本概念和基本原理 动态规划模型的建立与求解 应用举例

应用举例
1。背包问题 2。设备更新问题 3。货郎担问题 4。离散最优控制问题

背包问题
一般提法: 旅行者携带背包登山,能承受的背包重量 上限是b千克,现有n种物品,每件的重量 是ai千克,每种物品的价值为ci(xi),是其数 量xi的函数,问旅行者如何规划,使携带 物品的总价值最大? 推广:装载问题、资源分配问题等

背包问题标准模型
max z ? ? ci ( xi )
i ?1 n

?a x
i ?1

n

i i

?b
xi为整数

xi ? 0

(i ? 1,?, n)

背包问题的动态规划描述
阶段: 分为n个阶段 k = 1, 2, …,n 状态变量sk:k阶段可携带物品的重量,则s1=b 决策变量uk: k阶段选择物品的数量,即uk= xk 状态转移方程: sk +1= sk - ak xk 决策集合Dk(sk) : {xk|0?xk ?[sk/ak]} 阶段指标函数:k阶段放入物品价值,即vk(sk, uk)= ck(xk) 递推方程: fk(sk) = max { ck(xk) + fk+1(sk+1) } 0?xk ?[sk/ak] fn+1(sn+1)=0

装载问题
例1:最大载重为10吨的卡车,其货物的单 位重量及相应单位价值如下表所示,问如 何装载使货物的总价值最大?
货物i 1 2 3

单位重量ai
单位价值ci

3
4

4
5

5
6

例1 模型
max z = 4x1+ 5x2+ 6x3 s.t. 3x1+ 4x2+ 5x3 ? 10 xi ? 0 xi为整数 i =1,2,3

动态规划描述

max z= 4x1+ 5x2 + 6x3 s.t. 3x1+ 4x2 + 5x3 ? 10 xj?0,整数

分为3个阶段 k = 1, 2, 3 阶段: 状态变量sk: k阶段时的资源剩余,则s1=10 决策变量uk:uk= xk 转移方程: s2=s1-3x1 ?0 ; s3=s2-4x2 ?0 ; s4=s3-5x3 ?0 阶段指标: v1(s1, u1)=4x1; v2(s2, u2)=5x2; v3(s3, u3)=6x3

算法复杂度分析
算法的复杂度与允许状态的多少直接 相关,故应尽可能缩小允许状态的范围。

状态:s1=10; s2=s1-3x1 ?0 ; s3=s2-4x2 ?0 ; s4=s3-5x3 ?0

允 许 状 态 集 合

0 10 1 2 3

0 10 1 2 0 7 1

10 6 2

7 3 4
0 S4

4 0 1
1 0

1

f3(s3) = max { 6x3 + f4(s4)}
0?x3 ? [s3/5]

x3*=[s3/5]

第 1 步

0 10

10

0 1 2 0
1 0 1

10 12 2 6 6 2 0

1
0 1 0 0 0 0 S4

1 2
3

7 4
1

7 6 3 0 4 0
0 0 1 0

0

f2(s2) = max { 5x2 + f3(s3) }
0?x2 ?[s2/4]

12

第 2 步

0 10

10

0 1 2 0
1 0 1

12 2 10

6 6 2 0

1
0 1 0 0 0 0 S4

1 2
3

7 4
1

6 5

7 6 3 0 4 0
0 0 1 0

0

0

f1(s1) = max { 4x1 + f2(s2 )}
0?x1 ? [10/3]

12

第 3 步

13

0

10

0 1 2 0
1 0 1

12 2 10

6 6 2 0

1
0 1 0 0 0 0 S4

10

1 2
3

7 4
1

6 5

7 6 3 0 4 0
0 0 1 0

0

0

解法总结
初始条件已知 ? 逆序解法 初始条件已知 终点状态多个 ? 顺序确定状态集+逆序解法

设备更新问题
设备使用时间t : 效益r(t): 维修费u(t): 更新费c (t): 越长 越小 越大 越大

问:如何确定更新方案,使n期总收益最大?

问题分析
阶段: 分为n个阶段 k = 1, 2, …,n 状态变量sk:设备已使用时间 决策变量xk: xk= Keep 保留 xk= Replacement 更新 状态转移方程: sk +1= sk +1 xk= K sk +1= 1 xk= R 阶段指标:第k阶段的总收益 xk ? K ?rk ( sk ) ? uk ( sk ) vk ( sk , xk ) ? ? ? rk (0) ? uk (0) ? ck ( sk ) xk ? R

迭代方程
最优指标函数fk(sk):第k阶段起的最大总收益。

xk ? K
? rk ( sk ) ? uk ( sk ) ? ? f k ?1 ( sk +1)) f k ( sk ) ? max ? ?rk (0) ? uk (0) ? ck ( sk ) ? ? f k ?1 (1))
fn+1(sn+1)= 0

?为折扣因子

xk ? R

例2
例2:某新设备的收益、维修费和更新费如 下表,折扣因子?=1,设计5年内的最优更 新方案。
t
收益 rk(sk)

(单位:万元)

0
5

1
4.5

2
4

3
3.75

4
3

维修费 uk(sk)
更新费 ck(sk)

0.5
0.5

1
1.5

1.5
2.2

2
2.5

2.5
3

迭代方程
xk ? K

?rk ( sk ) ? uk ( sk ) ? f k ?1 (sk +1)) f k ( sk ) ? max ? ? 5 ? 0.5 ? ck (sk ) ? f k ?1 (1))
k =5 k =1 s5 = 1,2,3,4 s1 = 0

xk ? R

顺序确定状态集+逆序解法

顺 序 确 定 状 态 集

?S k ? 1 状态转移方程: S k ?1 ? ? ?1
0 K R
1

xk ? K xk ? R
4 1

K

2

K
R

3

K R

R 1

R K

1 2

R K R K

2 3

S6

f k ( sk ) ? max ? ?

k =5

rk1,2,3,4 ( sk ) ? uk (f s6k(s )6? f k ?1 ( sk ? 1)) s5? = )=0 4.5 ? ck ( sk ) ? f k ?1 (1))
x5(1)= K x5(2)= K

第 5 年

? 4.5 ? 1 ? f 5 (1) ? max ? ? ? 3.5 ?4.5 ? 1.5?
? 4 ? 1.5 ? f 5 (2) ? max ? ? ? 2.5 ?4.5 ? 2.2?

? 3.75 ? 2 ? f 5 (3) ? max ? ??2 ?4.5 ? 2.5? ?3 ? 2.5? f 5 (4) ? max ? ? ? 1.5 ?4.5 ? 3?

x5(3)= R
x5(4)= R

第 5 年

0

K R

1

K

2

K
R

3

K
R

4
1

1.5

R

3.5K

R 1

R K

1 2

R K R K

2 2.5K 3 2 R

S6

f k ( sk ) ? max ? ? 4.5 ? ck ( sk ) ? f k ?1 (1)) ? 4.5 ? 1 ? 2.5 ? f 4 (1) ? max ? ? ? 6.5 x4(1)= R 第 ?4.5 ? 1.5 ? 3.5?

k =4, s4 = 1,2,3 ?rk ( sk ) ? uk ( sk ) ? f k ?1 ( sk ? 1))

4 ? 4 ? 1.5 ? 2 ? 年 f 4 (2) ? max ? ? ? 5.8

x4(2)= R

?4.5 ? 2.2 ? 3.5? ? 3.75 ? 2 ? 1.5 ? f 4 (3) ? max ? ? ? 5.5 x4(3)= R ?4.5 ? 2.5 ? 3.5?

第 4 年

0

K R

1

K

2

K
R

5.5

3
6.5

K
R

1.5

4
1
3.5

R K S6

R 1

R K

1 2
5.8

R K R K

2 2.5 K 3
2

R

?rk ( sk ) ? uk ( sk ) ? f k ?1 ( sk ? 1)) f k ( sk ) ? max ? ? 4.5 ? ck ( sk ) ? f k ?1 (1))

第 3 ? 4.5 ? 1 ? 5.8 ? 年 f 3 (1) ? max ?4.5 ? 1.5 ? 6.5? ? 9.5
? ?

k =3 s3 = 1,2

x3(1)= R

? 4 ? 1.5 ? 5.5 ? x (2)= R 3 f 3 (2) ? max ? ? 8 . 8 ? ?4.5 ? 2.2 ? 6.5?

第 3 年

0

K R

1

K

8.8

2

K R

5.5

3

K
R

1.5

4
1 2 3
2 3.5

R K K
2.5

R 1
9.5

6.5 R

R K

1 2
5.8

K R K

S6

R

?rk ( sk ) ? uk ( sk ) ? f k ?1 ( sk ? 1)) f k ( sk ) ? max ? ? 4.5 ? ck ( sk ) ? f k ?1 (1))

第 2 年

k =2

s2 = 1

? 4.5 ? 1 ? 8.8 ? f 2 (1) ? max ? ? ? 12.5 ?4.5 ? 1.5 ? 9.5?
x2*= R

第 2 年

0

K R

12.5

1

K

8.8

2

K R

5.5

3

K
R

1.5

4
1 2 3
2 3.5

R K K
2.5

R 1
9.5

6.5 R

R K

1 2
5.8

K R K

S6

R

?rk ( sk ) ? uk ( sk ) ? f k ?1 ( sk ? 1)) f k ( sk ) ? max ? ? 4.5 ? ck ( sk ) ? f k ?1 (1))

第 1 年

k =1 s1 = 0

?5 ? 0.5 ? 12.5 ? f1 (0) ? max ? ? ? 17 ?4.5 ? 0.5 ? 12.5?
x1* = K

17

第 1 年

0

K R

12.5

1

K

8.8

2

K
R

5.5

3

K
R

1.5

4
1 2 3
2 3.5

R K K
2.5

R 1
9.5

6.5 R

R K

1 2
5.8

K R K

S6

R

结果

k sk

1 0 K

2 1 R

3 1 R

4 1 R

5 1 K

6 2

x*

货郎担问题(TSP )
n个城镇vi, vi到vj的距离为dij,一个货郎从 城镇v1出发,经过且仅经过其他每个城镇1 次,回到v1 ,应如何选择路线,使总的行 程最短?

穷举法复杂度
m ? (n ? 1)!
若n=20,m=1.22?1017, 设计算机每秒搜索1亿条路径, 需38.6年。

问题分析
阶段: 分为n个阶段 k = 1, 2, …,n

状态sk:第k步所在的城市? 前k步走过的城市? 不能保证无后效性!

货郎担问题的动态规划描述
ek:第k步所在城市 ck:到达ek前已走过的城市集合 状态sk:(ck , ek ) 决策uk: 第k步的目的地, uk=ek+1 状态转移方程: sk ?1 ? (ck ?1 , ek ?1 ) ? (ck ? {ek } , uk ) k ? 0,1,...n ? 1

s0 ? (c0 , e0 ) ? (? , v1 ) un ?1 ? en ? v1 uk ? ck ? {ek } k ? 0,1,...n ? 2

指标函数
阶段指标函数:v(sk,uk)=d(ek,uk) 最优指标函数: fk(ck ,ek),表示从v1出发, 经过ck中的城市,到达ek的最短距离。

递推关系

f k ?1 (ck ?1 , ek ?1 ) ?

ek ?ck ,ek ? ek ?1

min {d (ek , ek ?1 ) ? f k (ck , ek )}

f 0 (? , v1 ) ? 0

例3
例3:四个城市间的距离如下表,求从城市 1出发的货郎担问题。
dij 1 2 3 4 1 0 8 5 6 2 6 0 8 5 3 7 9 0 5 4 9 7 8 0

第 1步
k =1

dij 1 2 3 4

1 0 8 5 6

2 6 0 8 5

3 7 9 0 5

4 9 7 8 0

f1 ({1}, 2) ? d12 ? f 0 (? ,1) ? 6 f1 ({1},3) ? d13 ? f 0 (? ,1) ? 7 f1 ({1}, 4) ? d14 ? f 0 (? ,1) ? 9

第 2步
k =2

dij 1 2 3 4

1 0 8 5 6

2 6 0 8 5

3 7 9 0 5

4 9 7 8 0

f1 ({1}, 2) ? 6 f1 ({1},3) ? 7 f1 ({1}, 4) ? 9

f 2 ( {1,3}, 2) ? d32 ? f1 ({1},3) ? 8 ? 7 ? 15 f 2 ( {1, 4}, 2) ? d 42 ? f1 ({1}, 4) ? 5 ? 9 ? 14 f 2 ( {1, 2},3) ? d 23 ? f1 ({1}, 2) ? 9 ? 6 ? 15 f 2 ( {1, 4},3) ? d 43 ? f1 ({1}, 4) ? 5 ? 9 ? 14 f 2 ( {1, 2}, 4) ? d 24 ? f1 ({1}, 2) ? 7 ? 6 ? 13 f 2 ( {1,3}, 4) ? d34 ? f1 ({1},3) ? 8 ? 7 ? 15

第 3步
k =3

dij 1 2 3 4

1 0 8 5 6

2 6 0 8 5

3 7 9 0 5

4 9 7 8 0

f 2 ( {1,3}, 2) ? 15 f 2 ( {1, 4}, 2) ? 14 f 2 ( {1, 2},3) ? 15 f 2 ( {1, 4},3) ? 14 f 2 ( {1, 2}, 4) ? 13 f 2 ( {1,3}, 4) ? 15

f3({1,3,4},2)= min{ d32+ f2({1,4},3), d42+ f2({1,3},4)} =min{ 8+14, 5+15 }=20 f3({1,2,4},3)= min{ d23+ f2({1,4},2), d43+ f2({1,2},4)} =min{ 9+14, 5+13 }=18 f3({1,2,3},4)= min{ d24+ f2({1,3},2), d34+ f2({1,2},3)} =min{ 7+15, 8+15 }=22

第 4步

k =4 f4({1,2,3,4},1)=min{ d21+f3({1,3,4},2), d31+f3 ({1,2,4},3), d41+f3({1,2,3},4) } =min{ 8+20, 5+18, 6+22}=23

dij 1 2 3 4

1 0 8 5 6

2 6 0 8 5

3 7 9 0 5

4 9 7 8 0

f3({1,3,4},2)=20 f3({1,2,4},3)=18 f3({1,2,3},4)=22

最优路线:1?2 ?4 ?3 ?1

例4 离散系统最优控制
例4:一阶系统

x(k ? 1) ? 2 x(k ) ? u (k ) x(0) ? 1
求最优控制u*,使下列目标最小:
2

min J ? ? [ x (k ) ? u (k )]
2 2 k ?0

问题分析
阶段: 分为3个阶段 k = 0, 1,2 状态变量xk : x0 = 1 决策变量uk : 状态转移方程:xk+1 = 2xk+ uk 阶段指标函数:vk = xk2 + uk2 最优指标函数: Jk*(xk)= min{( xk2 + uk2 ) + Jk+1*(xk +1)}

J3*(x3)=0

第 1步
Jk*(xk)= min{( xk2 + uk2 ) + Jk+1*(xk +1)}
k =2

J ( x2 ) ? min {[ x ? u ] ? J ( x3 )}
* 2 u2 2 2 2 2 * 3

?

u2 * ? 0
J ( x2 ) ? x
* 2 2 2

Jk*(xk)= min{( xk2 + uk2 ) + Jk+1*(xk +1)}

第 2步
k =1
* 1 u1 2 1 2 1 * 2

xk ?1 ? 2 xk ? uk J ( x2 ) ? x
* 2 2 2

J ( x1 ) ? min {[ x ? u ] ? J ( x2 )} ? min {[ x ? u ] ? [2 x1 ? u1 ] } ? min{2u ? 4 x1u1 ? 5 x }
u1 2 1 2 1

u1

2 1

2 1

2

?

u1* ? ? x1

J ( x1 ) ? 3x
* 1

2 1

Jk*(xk)= min{( xk2 + uk2 ) + Jk+1*(xk +1)}

第 3步
k =0
* 0 u0 2 0 2 0 * 1

xk ?1 ? 2 xk ? uk
J ( x1 ) ? 3x
* 1 2 1

J ( x0 ) ? min {[ x ? u ] ? J ( x1 )} ? min {[1 ? u ] ? 3(2 ? u0 ) } ? min{4u ? 12u0 ? 13}
u0 2 0

u0

2 0

2

? ?

u0 * ? ?3 / 2 u1* ? ? x1 ? ?1/ 2

J ( x0 ) ? 4
* 0

u2 * ? 0

线性规划与动态规划
线性规划非常方便,有一般性解法,但只 适合求解线性规划问题 动态规划非常灵活,适应面广,但无一般 性解法

连续问题解法
连续变量解法: 1)每一阶段都要寻优,可能要结合线 性规划、非线性规划的内容 2)离散化处理?近似解

作业
第四版: P223 题7.9(1) P225 题7.15 第三版: P229 题7.9(1) P232 题7.16


相关文章:
运筹学 动态规划应用.ppt
运筹学 动态规划应用_数学_自然科学_专业资料。第七章 动态规划动态规划问题的基
运筹学7动态规划.ppt
运筹学7动态规划_数学_自然科学_专业资料。运筹学7动态规划 第七 章动态规划 ...概念和基本原理 §7.3 动态规划模型的建立与求解 §7.4 动态规划应用举例 ...
运筹学动态规划_图文.ppt
运筹学动态规划 - 动态规划(Dynamic Programming) 动态规划是美国数学家Bellman创立的。Bellman50年代执教于普林 斯顿和斯坦福大学,后进入兰德(Rand)研究所...
运筹学动态规划应用_图文.ppt
运筹学动态规划应用_生产/经营管理_经管营销_专业资料。运筹学动态规划应用 第十章 动态规划应用举例 1 第一节 一维资源分配问题一、一维资源分配问题基本模型及...
运筹学第八章 动态规划_图文.ppt
运筹学第八章 动态规划 - 第八章 动态规划 8.1 8.2 8.3 8.4 动态规划的研究对象和特点 动态规划的基本概念与最优化原理 动态规划的求解与应用 随机动态规划 ...
运筹学(二)动态规划(1-2014)_图文.ppt
运筹学(二)动态规划(1-2014) - 运筹学(二) 动态规划 动态规划 ? 动态规划运筹学的一个分支,它是 解决多阶段决策问题的一种数学方法。大 约产生...
运筹学中excel的运用(用excel解决线性规划、动态规划、....doc
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题)_电脑基础知识_IT/计算机_专业资料。用excel解决运筹学中基础模型的求解问题。 ...
15《运筹学》(第四版)连续动态规划_图文.pdf
15《运筹学》(第四版)连续动态规划_工学_高等教育_教育专区。对应教材为《...连续动态规划★ 4 在水库调度中的应用 水电与数字化工程学院 莫莉 3.1 连续...
运筹学中excel的运用(用excel解决线性规划、动态规划、....doc
运筹学中excel的运用(用excel解决线性规划、动态规划、排队论等问题)_数学_自然科学_专业资料。山东大学运筹学资料 1.线性规划......
运筹学-动态规划应用举例_图文.ppt
运筹学-动态规划应用举例 - 运筹学课件,网络图,博弈论... 运筹学-动态规划应用举例_管理学_高等教育_教育专区。运筹学课件,网络图,博弈论 第九章 动态规划应用举例...
运筹学第九章 动态规划_图文.ppt
运筹学第九章 动态规划 - 第九章 动态规划 9.1 多阶段决策问题 9.2 动态规划的基本概念 9.3 最优性原理与递推方程 9.4 动态规划应用例解 9.1 多阶段决策问题...
运筹学课件(动态规划)_图文.ppt
运筹学课件(动态规划) - 动态规划 (Dynamic programming) 动态规划的基本思想 最短路径问题 投资分配问题 背包问题 动态规划是用来解决多阶段决策过程最优 化...
运筹学第七章动态规划._图文.ppt
运筹学第七章动态规划. - 第七章 动态规划 Dynamic Programmi
动态规划(运筹学讲义)_图文.ppt
动态规划(运筹学讲义) - 第八章 动态规划 Dynamic Programming §1 动态规划问题实例 动态规划的基本概念 §2 动态规划的基本概念 §3 基本原理和基本方程 动态...
第六章(上课) 运筹学动态规划04修改_图文.ppt
第六章(上课) 运筹学动态规划04修改_理学_高等教育_教育专区。(Dynamic ...动态规 划模型的具体准则 (2)求解时存在维数灾难 49 七、动态规划问题应用...
运筹学 动态规划应用二_图文.ppt
运筹学 动态规划应用二 - 动态规划应用举例之二 1.设备更新问题 2.机器负荷问题 3.生产存储问题 动态规划应用举例之二 1.动态规划的四大要素 ① 状态...
管理运筹学 第5章 动态规划_图文.ppt
管理运筹学 第5章 动态规划 - 第五章 动态规划 5.1. 动态规划的基本概念和最优化原理 5.2. 动态规划模型的建立与求解 5.3. 动态规划在经济管理中的应用 ...
动态规划运筹学基础及其应用胡运权第五版_图文.ppt
动态规划运筹学基础及其应用胡运权第五版 - 第九章 动态规划(续) 本章以下内容 动态规划的基本原理 动态规划方法的基本步骤 动态规划方法应用举例 1 动态规划的...
100717_05_运筹学动态规划_图文.ppt
100717_05_运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第
运筹学教案(动态规划)_图文.ppt
运筹学教案(动态规划) - 运筹学教案 动态规划 陈安明 概述 动态规划运筹学的一个分支, 动态规划运筹学的一个分支,是用于求解 多个阶段决策过程的最优化数学...
更多相关文章: