运筹学5(动态规划)

运筹学5(动态规划)

ID:38742723

大小:1.33 MB

页数:63页

时间:2019-06-18

运筹学5(动态规划)_第1页
运筹学5(动态规划)_第2页
运筹学5(动态规划)_第3页
运筹学5(动态规划)_第4页
运筹学5(动态规划)_第5页
资源描述:

《运筹学5(动态规划)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、第七章动态规划7.1动态规划问题和基本概念7.2动态规划的基本原理7.3动态规划的应用引言动态规划与多阶段决策:多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是一个决策序列,所以多阶段决策问题又称为序贯决策问题。多阶段决策的目标是要达到整个活动过程的总体效果最优,所以多阶段决策又叫做过程最优化。所谓动态规划,就是解决多阶段决策和过程最优化问题的一种规划方法。例7.1最短路问题设A地的某一企业要把一批货物由A地运到E城销售,其间要经过八个

2、城市,各城市间的交通路线及距离如下图所示,问应选择什么路线才能使总的距离最短?7.1动态规划问题和基本概念例中,路线图(共18条路线,3×3×2×1=18)枚举法:例中,路线图(共18条路线,3×3×2×1=18)为解决这个最短路径问题,首先给出几个定义。1)、阶段(stage)将所给问题的过程,按时间或空间特征分解成若干相互联系的段落,以便按次序求解就形成了阶段,阶段变量常用字母K来表示。如例7.1有四个阶段,K就等于1,2,3,4。第一阶段共有3条路线即(A,B1),(A,B2)和(A,B3),第二阶段

3、有9条路线,第3阶段有6条路线,第4阶段有2条路线。12342)、状态(state)各阶段开始时的出发点称作状态。描述各阶段状态的变量,称作状态变量,用sk表示。在例7.1中,第一阶段的状态为A,第二阶段的状态为城市B1,B2和B3。所以状态变量S1的集合S1={A},S2的集合是S2={B1,B2,B3},依次有S3={C1,C2,C3},S4={D1,D2}。12343)、决策(Decision)当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确定下一阶段的状态,这种决定就是决策,表示决策的变量

4、称为决策变量。常用kX(ks)表示第K阶段当状态为ks时的决策变量,在例7.1中第二阶段如决定从B1出发,即S2=B1,可选择走C1或C2,C3,如果我们选择,从C2走,则此时的决策变量可表示x2(B1)=C2。12344)、策略(Policy)在各阶段决策确定以后,整个问题的决策序列就构成了一个策略,用P1n(s1)表示。如对于例7.1总共可有18个策略,但最优策略只有一个。12345)、目标函数用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程,从1到n叫作问题的原过程。目标函数的最优值

5、称为最优目标函数,最优目标函数记为fk(sk),它表示从第K阶段的状态Sk出发采用的最优策略。当K=1时,f1(s1)就是从初始状态S1到全过程结束的整体最优目标函数。,在例7.1中,目标函数就是距离。如在第2阶段,状态为B2时,f2(B2)则表示从B2到E的最短距离。本问题的总目标是求f1(A),即从A到E的最短距离。12346)、状态转移方程在动态规划中,本阶段的状态往往是上阶段决策的结果。所以如果给定了第K阶段的状态ks和该阶段的决策kx(ks),则第K+1段的状态1+ks由于K阶段决策的完成也就完全

6、确定了,它们之间的关系可用如下公式表示:1+ks=kT(ks,kx)其中,kT表示从状态ks出发经过kx向下一阶段的转移(Transfer),换言之,即1+ks是从状态ks出发经过决策kx转移的结果。由于上式表示了由K段到第K+1段的状态转移规律,所以就称为状态转移方程。在例7.1中,状态转移方程即1+ks=kx。为了求出例7.1的最短路线,一个简单的方法是,可以求出所有从A到E的可能走法的路长并加以比较。不难知道,从A到E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要求出最短路线需做54次加法

7、运算和17次比较运算,这叫做穷举法。当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。下面应用动态规划方法求解例7.1。运用逆序递推方法求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出A点到E点的最短路线。运用逆序递推方法的好处是可以始终盯住目标,不致脱离最终目标。例7.1是一个四阶段决策问题,一般可分为四步:1234第一步,从K=4开始1234S1S2S3S4●逆序法求解最短路问题状态变量S4可取两种状态D1,D2,它们到E点的距离分别为4和3,这也

8、就是由D1和D2到终点E的最短距离,即f4(D1)=4,f4(D2)=3.第二步,K=3状态变量S3可取3个值即C1,C2和C3。为方便应用,规定用d(sk,sk+1)表示由状态sk出发,到达下一阶段sk+1时的两点距离。3f(1C)=min++)(),()(),(24211411DfDCdDfDCd=min++3543=7这说明,由1c到E的最短距离为7,其路径为以1C→1D→E,相应的决策为*3x(1C)=1

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。