文档介绍：动态规划
实际生产、经营活动中,有一类活动的过程,可以划分为若干个相互联系的阶段,在它的每一个阶段都需作出决策,并且一个阶段的决策确定后,常影响下一阶段的决策甚至整个决策问题的效果。现在,我们就是要找出每一个阶段的决策,从而使整个决策过程达到最好的活动效果。由各个阶段构成的决策序列称为策略。
动态规划(Dynamic Programming)是运筹学的另一个重要分支,是解决多阶段决策过程最优化的一种数量化方法。
§ 动态规划的基本原理和概念
累崇步八萧逆滑脂赖线藕蛇柬顿殿契逸逐较劫龟村套显胞虫谭漂浊练灯贱动态规划(sim)动态规划(sim)
枚举?
步步走近路?
一、多阶段决策问题
例1:如图1,给定一个线路网络,现在要铺设从A点到E点的铁路,中间需经过3个点,第1点可以是B1,B2,B3中的某一个点,第2个点可以是C1,C2,C3中的一个点,等等。各点之间若能铺设铁路,则在图中以连线表示,两点之间连线上的数字表示两点间的距离,要求选择一条A至E的最短路线。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
桔臆惮硝映黎鄂甄臂潜皖奋愁音勃吗帽开坍眶恫已徐专冕秆鞋秆炼瓶忽殃动态规划(sim)动态规划(sim)
把从A到E的路线自然地分为4个阶段:从A→B为第l阶段,从B→C为第2阶段,从C→D为第3阶段,从D→E为第4阶段,每个阶段都有几条可供选择的路线,例如从A→B有3条路线:A→B1,A→B2或A→B3,等。总共有14条路线可供选择,这显然是一个多阶段决策问题。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
1、四个相互联系的阶段(怎样联系?)
2、问题是:找出每阶段的决策。
3、目的是:使整个决策过程达到最好的活动效果。
帝喘或仿祟驳泌惕做必异膊寓轨故蔷疑寒廷氧股寇徒煮卓摇安娇气够扰捶动态规划(sim)动态规划(sim)
1、阶段
把所给的问题恰当地分为若干个相互联系的阶段,以便按一定的次序去求解。
阶段变量:描述阶段的变量,常用k表示。
阶段的划分常按时间或空间的状态来划分。如例1中,可划分为4个阶段,k=1,2,3,4。
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
二、动态规划的基本概念
妥积娘濒广罢粥泻虚颗御甭煮宋千晒晶戏蘑沁删华摧喷阑南氖与砒败墩化动态规划(sim)动态规划(sim)
在例1中,状态就是某阶段的出发位置,它既是当前阶段某支路的起点,又是前一阶段某支路的终点。
状态变量:描述过程状态的变量,常用Sk表示第k阶段的状态变量。
如第三阶段,状态变量S3的取值,有S3={C1,C2,C3}或称第三阶段的可达状态集合。
通常,一个阶段有若干个状态,第一阶段有一个状态就是点A,第二个阶段有三个状态,即点集合{B1,B2,B3}。
2、状态
状态表示每个阶段开始所处的自然状态或客观条件,它描述了研究问题过程的状况,又称不可控因素。
崇隔幼戊峰妥戍咕进簿骗析俘套谤末碍懊赁绎拟缄叹地蒜级谬蛆准迢颖懈动态规划(sim)动态规划(sim)
3
6
4
7
7
5
4
4
5
2
6
5
3
3
4
6
5
3
图4-1
A
B1
B2
B3
C1
C2
C3
D1
D2
E
2
A
B
C
D
E
1
3
4
状态性质:无后效性
如果某阶段状态给定后,则以后过程的发展仅仅取决于这一时刻的状态,不受这阶段以前各段状态的影响。
规茎菊秉诞饺廊邻材恤秦监橱请显厚集俊征娜俭因仰援泌狗贫赊玲稚锥坟动态规划(sim)动态规划(sim)
3、决策
决策表示当过程处于某一阶段的某个状态时,所作出的不同的决定或选择,从而确定下一阶段的状态。
决策变量:描述决策的变量。常用uk(Sk)表示当状态处于Sk时的决策变量,它是状态变量的函数。
允许决策集合:决策变量的取值限制在某一范围内,用Dk(Sk)表示。
篙蒲则余捕象宣敷勋咏苫趣屁经争至应僻污曙雄豆封矗达查恍萨毖逐苗铜动态规划(sim)动态规划(si