运筹学5(动态规划)

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

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

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

3、有9条路线，第3阶段有6条路线,第4阶段有2条路线。12342）、状态(state)各阶段开始时的出发点称作状态。描述各阶段状态的变量，称作状态变量，用sk表示。在例７.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时的决策变量，在例７.1中第二阶段如决定从B1出发，即S2=B1，可选择走C1或C2，C3，如果我们选择，从C2走，则此时的决策变量可表示x2(B1)=C2。12344）、策略（Policy）在各阶段决策确定以后，整个问题的决策序列就构成了一个策略,用P1n(s1)表示。如对于例７.1总共可有18个策略，但最优策略只有一个。12345）、目标函数用于衡量所选定策略优劣的数量指标称作目标函数。一个n阶段的决策过程，从1到n叫作问题的原过程。目标函数的最优值

5、称为最优目标函数，最优目标函数记为fk(sk)，它表示从第K阶段的状态Sk出发采用的最优策略。当K=1时,f1(s1)就是从初始状态S1到全过程结束的整体最优目标函数。,在例７.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段的状态转移规律，所以就称为状态转移方程。在例７.1中,状态转移方程即1+ks＝kx。为了求出例７.1的最短路线,一个简单的方法是,可以求出所有从A到E的可能走法的路长并加以比较。不难知道,从A到E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要求出最短路线需做54次加法

7、运算和17次比较运算,这叫做穷举法。当问题的段数很多,各段的状态也很多时,这种方法的计算量会大大增加,甚至使得寻优成为不可能。下面应用动态规划方法求解例７.1。运用逆序递推方法求解,即由最后一段到第一段逐步求出各点到终点的最短路线,最后求出A点到E点的最短路线。运用逆序递推方法的好处是可以始终盯住目标,不致脱离最终目标。例７.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