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

运筹学 第五章 动态规划(


第五章 动态规划(Dynamic programming)
§1.引言
研究多阶段决策问题 R.E.Bellman 1951年提出动态规划。 1957年出版Dynamic Programming 应用:最优调度、资源分配 最优路径、最优控制 设备更新、库存问题

§ 2.多阶段决策问题
例. 某产品从A城运至F城,其间要经过若干 个城镇和若干条道路,路线结构如图所示, 图中给出了每段道路的运费(元),试选 择一条合理的运输路线,使总运费最小?

1

2

3

4

分析:方案① :A→B1→C1→E1→F 运费:26元 方案② : A→B3→C3→E3→F 运费:22元 方案③ : A→B2→C1→E2→F 运费:18元 最优方案:方案③

§ 3.基本概念
1.阶段和阶段变量 阶段:过程的划分,包括时间、空间的划分, 阶段数:n 阶段变量:描述阶段的变量用k 表示,k=1,2,…..,n 2.状态和状态变量 状态:描述过程的必要信息。 状态应具有无后效性: 若给定了某阶段状态,则在这阶 段以后过程的发展不受这阶段以前各阶段状态的影响.

状态变量:描述状态的变量,用s表示。

sk : 表示第阶段的状态变量 S k : 表示第阶段状态变量的集合 sk ∈ S k 如s1 = A = S1 , s 2 = B1 ∈ S 2 = {B1 , B2 , B3} S3 = {C1 , C2 , C3} , S 4 = {E1 , E2 , E3} S 4+1 = {F } = F

3.决策和决策变量 决策:决定(选择),从一个阶段的状态到 下一个阶段状态的选择。 决策变量:描述决策的变量,用u表示.

uk = uk ( sk ) 表示第k阶段处于sk的决策变量. Dk = Dk ( sk )表示第k阶段处于sk时 决策变量的集合. uk ∈ Dk ( sk ) 如 D2 ( B1 ) = {u2 ( B1 ) = C1 , u2 ( B1 ) = C2 } u2 ( B1 ) = C1 ∈ D2 ( B1 )

4.策略 策略:决策按顺序构成的序列,用p表示。

p k ,n ( sk ) : 第 k阶段起至第 n阶段止的策略 p k ,n ( s k ) = {u k ( sk ), u k +1 ( sk +1 )... , u n ( sn )} Pk ,n ( sk ) : 第 k阶段起至第 n阶段止的策略 p k ,n ( s k ) ∈ Pk ,n ( sk ) 当 k = 1时. p1,n ( s1 )为全过程策略 . p1,n ( s1 ) ∈ P ,n ( s1 ) 1
* 使目标达最优的策略为 最优策略 : p1,n ( s1 )

5.状态转移方程 确定过程由一个状态到 另一个状态的变换方程 . S k +1 = Tk {S k , u k }, Tk : 变换算子 6.指标函数和最优值函数 (1) 指标函数 指标函数 : 描述问题的数量函数用 Vk ,n 表示 . Vk ,n = Vk,n ( sk ,u k ,....., sn , u n , s n +1 ) k = 1,2,.., n 要求 Vk,n 满足可分离性及递推关 系 .

10 指标和
n

Vk,n为阶段指标v j ( s j , u j )之和
j = k +1

Vk,n = ∑ v j ( s j , u j ) = vk ( sk , uk ) +
j =k

∑ v j (s j , u j )

n

= vk ( sk , uk ) + Vk +1,n 20 指标积 Vk,n为阶段指标v j ( s j , u j )之积 Vk,n = ∏ v j ( s j , u j ) = vk ( sk , uk )
j =k n j = k +1

∏ v j (s j , u j )

n

= vk ( sk , uk ) Vk +1,n

(2) 最优值函数 最优值函数f k ( sk ) : 指标函数的最优值 f k ( sk ) = opt Vk .n ( sk , uk ,..., sn , un , sn +1 )
{uk un }

opt : 最优化, 取 max 或 min

7.多阶段过程 对于动态系统,

设状态为s1 , s2 , , sn ; T表示变换. 则状态变换过程为 s2 = T ( s1 ) , s3 = T ( s2 ) = T (T ( s1 )) = T ( 2) ( s1 ) sn+1 = T ( sn ) = T ( n ) ( s1 )

s1

1

s2

2

s3



sk

k

sk +1 sn

n

sn +1

8.多阶段决策过程 多阶段决策过程就是在各个阶段都要进行决策。

s2 = T1 (s1, u1 ), 无后效性: = T1 (s1, u1 ) s2 s3 = T2 (s1, u1, s2 , u2 )... s3 = T2 (s2 , u2 ) ...... sn+1 = Tn (sn , un ) sn+1 = Tn (s1, u1,.., sn , un )
u1 u2 uk
un

s1

1

s2

2

s3



sk

k

sk +1 sn

n

sn +1

v1

v2

vk ( s k , u k )

vn

数学描述

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

sk +1 = Tk ( sk , uk ) , sk ∈ S k , uk ∈ Dk , k = 1, , n

求解 : 最优值
* f1 ( s1 )

* * * * 最优策略 p1,n ( s1 ) = u1 , u2 , , un

{

} }

* * * * * = V1,n ( s1 , u1 , , sn , un , sn+1 )

* * * * 最优状态序列 S * = s1 , s2 , , sn , sn+1

{

§4 动态规划的基本方程
4.1最优性原理 作为整个过程的最优策略具有这样的性质,

即无论过去的状态和决策如何,对前面决策 所形成的状态而言,余下的诸决策必须构成 最优决策。 简言之, 一个最优策略的子策略也是最优的. 例 最优路线 : A → B2 → C1 → E2 → F
子路线 : C1 → E2 → F也是最优的 .

4.2基本方程 设指标函数为 n

Vk ,n =

∑ v j ( s j , u j ) = v k ( s k , u k ) + V k + 1, n
j=k

当初始状态给定时

, 过程的策略被确定

,则

V k , n = V k .n ( s k , u k ,..., s n , u n , s n +1 ) = V k , n ( s k , p k , n ) = v k ( s k , u k ) + V k + 1, n ( s k + 1 , p k + 1, n ) 而 p k , n = {u k , p k +1, n }

* p k , n 表示 s k → s n的最优策略 , 则最优值函数 * f k ( s k ) = Vk ,n ( s k , p k ,n ) = p k , n ∈ Pk , n

opt

Vk ,n ( s k , p k ,n )

=

opt
u k , p k +1, n

{v k ( s k , u k ) + V k +1, n ( s k +1 , p k +1, n ) }

= opt v k ( s k , u k ) + opt V k +1, n ( s k +1 , p k +1, n ) uk p k +1, n = opt {v k ( s k , u k ) + f k +1 ( s k +1 ) }
uk

* p k , n 表示 s k → s n的最优策略 , 则最优值函数

基本方程 f k ( s k ) = opt {v k ( s k , u k ) + f k +1 ( s k +1 ) } u k ∈Dk s k +1 = Tk ( s k , u k ) k = 1, 2 , , n f (s ) = 0 n + 1 n +1 这是一个逆推方程 .

基本方程的解法

逆推找决策 : k = n 时 , f n +1 ( s n + 1 ) = 0 f n ( s n ) = opt {v n ( s n , u n ) + f n +1 ( s n +1 ) }
* = opt {v n ( s n , u n )} u n , u n ∈Dn u n ∈Dn

k = n 1, f n 1 ( s n 1 ) =

u n 1∈ D n 1

opt

{v n 1 ( s n 1 , u n 1 ) +

f n ( sn ) }

* u n 1 , 此时要用到 s n = Tk 1 ( s k 1 , u k 1 )

逆推找决策 : k = 1,

f1 ( s1 ) = opt {v1 ( s1 , u1 ) + f 2 ( s 2 )
u1∈ D1

}

* u1 , 此时要用到 s 2 = T1 ( s1 , u1 )

顺序定策略 : 最优值 : f1 ( s1 )

* * * * 最优策略 : p1, n = u1 , u 2 , , u n

{

}
n

1

划分阶段 k 2 逆推找决策 顺序定策略

例:如图所示, 选择A → E的运输路线, 使总运费(百元)最小

解:阶段n = 3, k = 1,2,3 s1 = A, s 2 = {B1 , B2 , B3}, s3 = {C1 , C2 }s4 = E u k = uk ( sk ) vk = vk ( sk , uk ) → 阶段运费 f k ( sk ) = min {vk ( sk , uk ) + f k +1 ( sk +1 )} k = 1,2,3 u ( k )∈Dk f 3+1 ( s3+1 ) = f 4 ( E ) = 0

解之:k = 3, f 3 (C1 ) = min{v3 (C1 , E ) + f 4 ( S 4 )} = min{6 + 0)} = 6 ∴ u3 (C1 ) = E f 3 (C2 ) = min{v3 (C2 , E ) + f 4 (S 4 )} = min{5 + 0} = 5 ∴ u3 (C2 ) = E v2 ( B1 , C1 ) + f 3 (C1 ) 9 + 6 k = 2, f 2 ( B1 ) = min = min =7 v2 ( B1 , C2 ) + f 3 (C2 ) 2 + 5 ∴ u2 ( B1 ) = C2

k = 2, v2 ( B2 , C1 ) + f 3 (C1 ) f 2 ( B2 ) = min v2 ( B2 , C2 ) + f 3 (C2 ) 5 + 6 = min = 11∴ u2 ( B2 ) = C1 7 + 5

v2 ( B3 , C1 ) + f 3 (C1 ) f 2 ( B3 ) = min v2 ( B3 , C2 ) + f 3 (C 2 ) 6 + 6 = min = 12 ∴ u 2 ( B3 ) = C1 8 + 5

k = 1, v1 ( A, B1 ) + f 2 ( B1 ) 3+ 7 * f1 ( A) = min v1 ( A, B2 ) + f 2 ( B2 ) = min 2 + 11 = 10 ∴ u1 ( A) = B1 v ( A, B ) + f ( B ) 1 + 12 3 2 3 1

u3 (C1 ) = E u3 (C2 ) = E u2 ( B1 ) = C2 u2 ( B2 ) = C1 u2 ( B3 ) = C1 u1 ( A) = B1
* * * ∴ P *3 = {u1 ( A) = B1 , u 2 ( B1 ) = C2 , u3 (C2 ) = E} 1.

f1 ( A) = 3 + 2 + 5 = 10(百元 )

§5 资源分配问题
例( P219 , 例2) 某种机器可以在高低两 种不同的负荷下生产, 设机器在高负荷

下的生产的产量函数为g = 8u , 其中u为投入生产的机器台数, 年完好率为a = 0.7,在低负荷下生产的产量函数为h = 5 y,其 中y为投入生产的机器台数,年完好率为b = 0.9, 若开始生产时 完好的机器台数为S1 = 1000台,问每年如何安排机器在高低负 荷下生产,使在五年内的生产总产量最高?

解:建立方程 设:n = 5, k = 1,2,3,4,5. sk : 状态变量,第k年完好的机器台数; uk : 决策变量,第k年用于高负荷下的生产的机器台数, 低负荷台数 : sk uk 状态转移方程:sk +1 = 0.7uk + 0.9( sk uk ) 阶段指标: vk = 8uk + 5( sk uk ) f k ( sk ) = max {8uk + 5( sk uk ) + f k +1 ( sk +1 )} 0 ≤ u k ≤ sk f 5+1 ( s5+1 ) = 0

逆推求解 令: k = 5, f 6 ( s 6 ) = 0
0 ≤ u 5 ≤ s5

f 5 ( s5 ) = max {8u 5 + 5( s5 u 5 ) + 0}
* = max{ 5 s5 + 3 s5 } = 8 s5 ∴ u 5 = s5 f 4 ( s 4 ) = max {8u 4 + 5( s 4 u 4 ) + f 5 ( s5 )} 0 ≤ u 4 ≤ s4

Q f 5 ( s5 ) = 8 s5 = 8[ 0 .7 u 4 + 0 .9 ( s 4 u 4 )] = 8( 0 .9 s 4 0 .2 u 4 ) ∴ f 4 ( s 4 ) = max {1 .4u 4 + 12 .2 s 4 }
0 ≤ u 4 ≤ s4

= 13 .6 s 4

∴ u * = s4 4

同理:f 3 ( s3 ) = max {8u3 + 5( s3 u3 )}
0≤u3 ≤ s3

= max {17.24 s3 + 0.28u3}
0≤u3 ≤ s3

= 17.52 s3
0≤u 2 ≤ s 2

∴ u * = s3 3 ∴ u* = 0 2

f 2 ( s2 ) = max {8u2 + 5( s2 u2 ) + f 3 ( s3 )} = max {20.8s2 0.5u2 } = 20.8s2
0 ≤u 2 ≤ s 2

f1 ( s1 ) = max {8u1 + 5( s1 u1 ) + f 2 ( s2 )}
0≤u1 ≤ s1 * = max {23.72 s1 1.16u1} = 23.72 s3 ∴ u1 = 0 0≤u1 ≤ s1

最优策略 :
* * * * * * p1,5 = {u1 = 0, u2 = 0, u3 = s3 , u4 = s4 , u5 = s5 }

即前两年完好的机器全部投入低负荷生产, 后三年完好的机器全部投入高负荷生产, 总产量最高. f1 ( s1 ) = 23.72s1 = 23720

状态变量:s1 = 1000
* * s 2 = 0.7u1 + 0.9( s1 u1 ) = 900 * * s3 = 0.7u2 + 0.9( s2 u2 ) = 810 * * s 4 = 0.7u3 + 0.9( s3 u3 ) = 567 * * s5 = 0.7u4 + 0.9( s4 u4 ) = 397 * * s 6 = 0.7u5 + 0.9( s5 u5 ) = 278(台)

作业:本例取n = 3, h = 6 y 其余相同,求解。


赞助商链接
相关文章:
5动态规划
大学运筹学课件大学运筹学课件隐藏>> 第五章【教学内容 教学内容】 教学内容 动态规划 动态规划问题,动态规划问题的基本要素和最优化原理,动态规划应用,用 LINGO 软...
《运筹学》教案_2016
第一章《绪论》 ,让学生了解运筹学在物流领域中的作用和意义,明确运筹学是物流...5. 第五章动态规划》 ,在之前单步建模的基础上,使学生掌握动态规划中多...
运筹学动态规划
MATLAB 基础及在运筹学中的应用 第 7 章 动态规划动态规划是 Bellman 在 1957 年提出的解多阶决策问题的方法,在那个时期,线性规划很 流行,它是研究静态问题的,...
运筹学之动态规划(东南大学)
运筹学动态规划(东南大学)_管理学_高等教育_教育专区。运筹学 引言——由一个问题引出的算法 引言——由一个问题引出的算法 ——考虑以下问题 [例 1] 最短...
第二章运筹学 线性规划
运筹学第四章 运输问题 运筹学第五章 整数规划 运筹学第六章 动态规划 运筹学第七章 图论1121 第九章 运筹学 决策论1/2 相关文档推荐 ...
动态规划--运筹学课程设计
运筹学——动态规划 80页 免费 运筹学—第七章 动态规划... 52页 1下载券...湖南农业大学 综合设计报告 综合设计五 动态规划算法 学生姓名:曾俊扬学号:...
大工11春《运筹学》辅导资料十五
大连理工大学网络教育学院 大连理工大学网络教育学院 运筹学辅导资料十五 运筹学辅导...月 24 日 学习时间 容: 我们这周主要对第五章动态规划”的相关内容进行...
运筹学实验报告2
实验报告 课程名称 运筹学 班姓学 级名号 实验日期 经济与管理学院 经济与...第五章实验名称:第五章 动态规划上机实验 【一、实验目的】 运用管理运筹学...
第一章 绪论 山大刁在筠 运筹学讲义
第四章 非线性规划 山... 第五章 动态规划 山大刁...1/2 相关文档推荐 ...第一章 绪论 教学重点:运筹学的主要内容和模型 教学难点:随机规划模型 教学课时...
运筹学 第七章
运筹学 第五章 运筹学 第六章 运筹学 第八章 运筹学 第九章 运筹学 第十...运筹学—第七章 动态规划... 52页 1下载券运​筹​学​ ​第​七...
更多相关文章: