第8章 动态规划11-5-8

第八章动态规划北京物资学院运筹学教学课件北京物资学院信息学院2011-5-8动态规划多阶段决策问题最优化原理与动态规划的数学模型动态规划模型的建立与求解多阶段决策问题

动态规划是一种研究多阶段决策问题的理论和方法。

多阶段决策问题是指一类活动过程，它可以分为若干个相互联系的阶段，在每个阶段都需要作出决策。这个决策不仅决定这一阶段的效益，而且决定下一阶段的初始状态。

策略：每个阶段的决策确定以后，就得到一个决策序列，称为策略。多阶段决策问题就是求一个策略，使各阶段的总效益达到最优。例1最短路问题设有一个旅行者从下图中的A点出发，途中要经过B、C、D等处，最后到达终点E。从A到E有很多条路线可以选择，各点之间的距离如图所示，问该旅行者应该选择哪一条路线，才能使从A到达E的总行程最短？AB1B2B3C3C2C1D1D2E25375632451514633334状态A决策阶段1状态B1阶段2决策状态D1状态C3阶段3决策阶段4决策状态E行程1行程2行程3行程4例2多阶段资源分配问题

设有某种机器设备，可用于完成两类工作A和B。若第k年初完好机器的数量为sk,若以数量xk用于工作A，余下的sk-xk用于工作B，则该年的预期收入为g(xk)+h(sk-xk)，其中g(xk)

和h(sk-xk)

是已知函数，并且g(0)=h(0)=0。又机器设备在使用中会有损坏，设机器用于工作A时，一年后能继续使用的完好机器数占年初投入量的a倍（0<a<1），若用于工作B时，一年后能继续使用的完好机器数占年初投入量的b倍(0<b<1)，即下一年初能继续用于完成这两项工作的机器数为sk+1=axk+b(sk-xk)。设第一年初完好的机器数为s1，问在连续三年内，每年应如何分配用于A、B两项工作的机器数，才能使三年的总收益达到最大。状态S1决策第一年阶段1状态S2第二年阶段2决策状态S4状态S3第三年阶段3决策收益1收益2收益3最优化原理与动态规划的数学模型动态规划问题的解题思路动态规划的基本概念最优化原理与动态规划的数学模型动态规划模型的分类动态规划问题的解题思路思路：将一个n阶段的决策问题转化为依次求n个具有递推关系的单阶段决策问题，从而简化计算。在例1中，这种转化的实现是从终点E出发一步步进行反推（逆序算法）（1）考虑一个阶段的选择。到达E之前，上一步必然到达D1或D2，D1到E的最优策略是：D1E，距离d(D1,E)=3,记f(D1)=3.D2到E的最优策略是：D2E，距离d(D2,E)=4,记f(D2)=4.1AB1B2B3C3C2C1D1D2E2537563245154633334(2)联合考虑两个阶段的最优选择。当旅行者离终点还有两站时，他必然处在C1，C2或C3的某一点上。C1到终点的路有两条：C1D1E，C1D2E，旅行者从这两条路线中选最短的一条，并且不管是经过D1或D2，到达该点后，他应循着从D1或D2到E的最短路线继续走。因此从C1到E的最短路程为：即从C1到E的最短路线为C1D1E，记如果从C2出发如果从C3出发（3）再联合起来考虑三个阶段的最优选择。从B1点出发的最优选择为从B2点出发的最优选择为从B3点出发的最优选择为（4）四个阶段联合考虑时从A到E的最优选择。从A到E的最短路线为AB3C2D2E，距离为11。1AB1B2B3C3C2C1D1D2E253756324515463333434476117811以上计算过程可以在图上通过标号法实现动态规划的基本概念1.阶段(stage)：指一个问题需要作出决策的步数。

通常用k表示问题的阶段数。阶段一般是根据时间和空间的自然特征来划分的。2.状态(state)：表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，是动态规划中最关键的一个参数。它既反映前面各个阶段决策的结局，又是本阶段决策的出发点和依据。它是动态规划问题各个阶段信息的传递点和结合点。通常一个阶段有多个状态。如例1中第一阶段有1个状态，A.第三阶段有三个状态C1,C2,C3。状态变量：描述状态的变量。可以是数、数组或向量。通常用Sk表示k阶段的状态集。如例1中S3={C1,C2,C3}.状态的性质：无后效性。3.决策(decision)

是指某阶段初从给定的状态出发，决策者在面临的若干种不同方案中做出的选择。决策变量xk(sk)表示第k阶段状态为sk时对方案的选择。用Dk(sk)表示在第k阶段状态为sk时决策允许的取值范围，称为允许决策集合。即xk(sk)Dk(sk)。

D2(B1)={C1,C2,C3}

xk*(sk)表示第k阶段状态为sk时的最优决策。决策的性质：第k阶段某一状态下的决策直接决定第k+1阶段的状态。4.策略（policy）和子策略（subpolicy）:策略：多阶段决策过程中，由各阶段决策组成的序列总体称作一个策略（全过程策略）。

{x1(s1),x2(s2),…,xn(sn)}从过程的某一阶段开始到过程最终阶段结束的决策序列称为问题的子过程策略或子策略。从k阶段起的子策略可以写为{xk(sk),xk+1(sk+1),…,xn(sn)}每一阶段有若干状态，每个状态又有若干不同的决策，从而形成许多可供选择的策略（子策略），能使预期目标达到最优效果的策略称为最优策略（子策略）。

5.状态转移方程从第k阶段的状态sk到第k+1阶段的状态sk+1的演变过程的解析表达式。记为：或简写为

状态转移方程6.指标函数阶段的指标函数：用来衡量每一阶段决策效果优劣的数量指标。阶段指标函数是状态变量和决策变量的函数，即vk(sk,xk)。过程的指标函数：从第k阶段的状态sk

出发到过程的最后阶段结束，当采取某种子策略时，按预定标准得到的效益值，称为过程指标函数。过程指标函数值取决于从第k阶段到最后阶段所采取的子策略，它是sk和子策略的函数值。记作根据实际问题的性质，过程指标函数可以是各个阶段指标函数的和或积。最优指标函数：从状态sk出发，选取最优子策略所得到的指标函数值称为最优指标函数值，记作fk(sk).

Opt代表最优化，可以是min或max状态s1决策x1(s1)阶段1T(S1,x1)状态s2阶段2T(S2,x2)决策x2(s2)阶段nT(Sn,xn)状态sn决策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)最优化原理与动态规划的数学模型最优化原理：作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。作为全过程的最优策略的组成部分的任一后部子策略一定是从该状态出发至终点的最优子策略。逆序解法：逆着阶段顺序的方向，由后向前推算。求解思路：从最后一个阶段开始，逆着过程的进展方向依次求出各阶段的各个状态对应的最优子策略。每一阶段的求解过程都是在其后部子过程最优子策略的基础上，再考虑本阶段的指标函数，求出本阶段的最优策略。直到求出整个过程的最优策略为止。基本递推方程据最优性原理，阶段k的阶段指标值vk(sk)加上(或乘以)从下一阶段k+1开始到过程结束采取最优策略取得的最优指标函数值fk+1(sk+1)

，再从中选出最优，便是阶段k从状态sk出发到全过程结束的最优指标函数值。状态s1决策x1(s1)阶段1T(S1,x1)状态s2阶段2T(S2,x2)决策x2(s2)阶段nT(Sn,xn)状态sn决策xn(sn)v1(s1,x1)v2(s2,x2)vn(sn,xn)寻求最优解的方向递推方程边界条件动态规划的数学模型：建模步骤（小结）划分阶段，确定阶段变量k。确定状态变量sk。确定决策变量xk和允许决策集合Dk(xk)写出状态转移方程sk+1=T(sk,

xk

)写出指标函数的基本递推方程明确边界条件

动态规划模型的分类按过程演变特征：确定性动态规划随机性动态规划根据状态变量：离散型动态规划连续型动态规划

过程变量确定随机离散离散确定型离散随机型连续连续确定型连续随机型动态规划模型的建立与求解例3：某一警卫部门共有9支巡逻队，负责3个要害部位A、B、C的警卫巡逻。每个部位可分别派出2--4支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时间内可能造成的损失有差别，具体数字见下表1，问警卫部门应往各部位分别派多少支巡逻队，才能使总的预期损失为最少？213110422351432438182CBA预期损失部位巡逻队数表1解：把9支巡逻队派往3个部位看成依次分三个阶段（用k表示，k=1,2,3）。状态变量sk：每个阶段初拥有的可派遣的巡逻队数。决策变量xk：每个阶段对相应部位派出的巡逻队数。状态转移方程：决策变量x1x2x3状态变量允许集95,6,72,3,4,5决策变量允许集2,3,42,3,42,3,4状态变量S1S2S3状态转移方程S1=9S2=S1-x1S3=S2-x2阶段123若用pk(xk)表示k阶段派出巡逻队数为xk时，该阶段的部位预期损失值，则过程的指标函数可写成因此有k=3时，考虑对C部位派巡逻队k=4时，k=2时，联合考虑对B,C两个部位派巡逻队k=1时，对A,B,C三个部位派巡逻队例4.投资问题现有资金5万元,可对三个项目进行投资,投资额均为整数(单位为万元),其中第二项目投资不得超过3万元,第一和第三项目投资不得超过4万元,第三项目投资至少要1万元,每个项目投资五年后,预计可获得的收益由下表给出,问如何投资可望获得最大的利润?

投资额收益项目01234项目10361012项目2051012项目3481115解：这个问题用动态规划求解，可分为3个阶段，k=1，2，3.状态变量Sk:

第k阶段初拥有的资金额。（可用于第k,k+1,..3项目的投资额）决策变量xk(Sk

):对第

k

个项目的投资额.状态转移方程:Sk+1

=Sk

-xk决策变量x1x2x3状态变量允许集51,2,3,4,51,2,3,4,5决策变量允