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

运筹学 第五章 动态规划(


第五章 动态规划(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 其余相同,求解。


相关文章:
运筹学第五章动态规划.ppt
运筹学第五章动态规划_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 运筹学第五章动态规划_数学_自然科学_专业资料。动态规划 (Dynamic programming...
运筹学--第五章 动态规划.pdf
运筹学--Part III 动态规划 Dynamic Programming 动态规划-概述 ? 1951年,Bellman提出,1957《动态规划动态规划是解决多阶段决策问题的一种数学方...
第五章动态规划.ppt
运筹学 ”编写 组 2008年12月 第五章 动态规划 内容多阶段决策过程与方法 动态规划的基本概念和递归方程 最优性原理与建模方程 动态规划的应用案例 实际应用案...
运筹学第五章 动态规划2_图文.ppt
运筹学第五章 动态规划2 - 第五章 动态规划 动态规划简介 动态规划所解决的问题:多阶段问题 动态规划的核心。 核心: 在于将问题公式化,也可以说,动态规划是将...
大学运筹学经典课件第五章动态规划_图文.ppt
大学运筹学经典课件第五章动态规划 - 第五章 动态规划(Dynamic pr
运筹学教案 第5章 动态规划 58p_图文.ppt
运筹学第五章 动态规划 (Dynamic Programming) 第五章 动态规划 5.1 多阶段决策问题与动态规划 5.2 动态规划的基本概念 5.3 动态规划的算法 5.4 动态...
运筹学教程课件五 动态规划_图文.ppt
运筹学教程课件五 动态规划 - 第五章 动态规划 不要过河拆桥 1 动态规划 D
运筹学动态规划_图文.ppt
运筹学动态规划 - 运筹学 课程主要内容 第一章 第二章 第三章 第四章 第五章 第七章 第八章 第九章 线性规划与单纯形法 对偶理论与灵敏度分析 运输问题 ...
运筹学_5动态规划.ppt
运筹学 第五章 动态规划( 30页 1财富值喜欢此文档的还喜欢 动态规划(北京大学) 21页 免费 第八章 网络计划 58页 2财富值 运筹学-动态规划 54页 免费 运筹...
运筹学 天津大学第五章_图文.ppt
运筹学 天津大学第五章 - 第五章 动态规划(Dynamic programmi
运筹学课件 第五章动态规划_图文.ppt
运筹学课件 第五章动态规划 - 第五章 动态规划 2013-11-30 1 ? ? 一、综 述 动态规划解决多阶段决策过程最优化的一种 数学方法,大约产生于50年代。 ? ...
动态规划的基本概念_图文.ppt
动态规划的基本概念 - 运筹学 动态规划 第五章 动态规划 动态规划运筹学的一
第八章 动态规划(运筹学讲义).ppt
运筹学讲义 第八章 动态规划 Dynamic Programming ? §1 动态规划问题实例 ? ? ? §2 动态规划的基本概念§3 基本原理和基本方程 §4 动态规划的应用 1 §1...
第5章 动态规划_图文.ppt
第5章 动态规划 - 管理运筹学 第五章 动态规划 5.1. 动态规划的基本概念和最优化原理 5.2. 动态规划模型的建立与求解 5.3. 动态规划在经济管理中的应用 ...
1 动态规划的基本概念_图文.ppt
1 动态规划的基本概念 - 运筹学 动态规划 第五章 动态规划 动态规划运筹学的一个重要分支,它是从1951年开始,由美国人贝尔曼 (R.Belman)为首的一个学派发展...
运筹五 动态规划_图文.ppt
运筹五 动态规划_管理学_高等教育_教育专区。北京邮电大学林齐宁教授的运筹学授课教程 第五章 动态规划不要过河拆桥 1 动态规划 Dynamic programming ? ? ? ? ...
运筹学04_动态规划(2).ppt
运筹学第五章 动态规划2 48页 免费 2.运筹学 动态规划解法 29页 免费如
运筹学 动态规划-作业及答案.doc
运筹学 动态规划-作业及答案 - 第五章 动态规划作业题及答案 1.用动态规划法求解求最短路径 从起点 A 到终点 E 之间各点的距离如图所示。求 A 到 E 的最...
第五章动态规划_图文.ppt
第五章动态规划_经管营销_专业资料。运筹学课件 第五章 动态规划§5.1多阶段决策问题 §5.2动态规划的基本概念 §5.3动态规划的基本思想及最优性原理 §5.4...
《运筹学》 第五章习题及 答案.doc
运筹学第五章习题 运筹学》 1.思考题 . (1)试述动态规划的"最优化原理"及它同动态规划基本方程之间的关系. (2)动态规划的阶段如何划分? (3)试述用...
更多相关文章: