运筹学大学课件10-1动态规划基本概念和基本原理1文档

动态规划

（DynamicProgramming)多阶段决策过程的最优化（简介）动态规划的基本概念和基本原理动态规划模型的解题步骤动态规划简介动态规划——解决多阶段决策过程最优化的一种数学方法。

“动态”——随着“时间”过程的发展而决定各时段的决策，产生一个决策序列。1951年，R.Bellman《动态规划》提出：“最优化原理”------把多阶段过程转化为一系列相互联系的单阶段问题，逐个求解。动态规划模型分类1、离散确定型；2、离散随机型；3、连续确定型；4、离散随机型；应用最短路问题资源分配问题生产调度问题库存问题排序问题设备更新问题生产过程最优控制问题多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策问题也称为序贯决策问题。多阶段决策过程最优化问题举例AD2D1B3B2B1C3C1C2E23877356687463532434

第1阶段

第2阶段

第4阶段

第3阶段

第5阶段1、最短路问题：运输网络如下图，求从A到E的最短路。2、生产与存储问题某厂每月供应市场一定数量的产品，如何安排每月的产量？增加产量成本降低库存费增加一年总费用最低？按月分阶段，全年分为12个阶段逐次决策动态规划的基本概念和基本原理动态规划的基本概念阶段状态、状态变量、状态空间决策、允许决策集合策略状态转移（方程）指标函数无后效性即未来与过去无关动态规划的基本概念和基本原理阶段（Stage）将所给问题的过程，按时间或空间特征分解成若干个相互联系的阶段，以便按次序去求每阶段的解，常用k表示阶段变量。动态规划的基本概念和基本原理状态（State）各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量的取值集合称为状态集合，用Sk表示。动态规划的基本概念和基本原理动态规划中的状态具有如下性质：某阶段的状态，只对该阶段该状态以后过程的演变起作用，而不受以前各阶段状态的影响。即：过程的过去历史只能通过当前状态去影响它未来的发展，这称为无后效性。如果所选定的变量不具备无后效性，就不能作为状态变量来构造动态规划模型。动态规划中的状态变量满足如下3个特性：

（1）代表性。能够反映过程的演变特性。（2）可知性。能够通过某种方式，直接或间接地确定（3）无后效性。动态规划的基本概念和基本原理决策和策略（DecisionandPolicy）

当各段的状态确定以后，就可以做出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量用uk(sk)表示，允许决策集合用Dk(Sk)表示。动态规划的基本概念和基本原理各个阶段决策确定后，整个问题的决策序列就构成一个策略，用p1,n(u1,u2,…un)表示。对每个实际问题，可供选择的策略有一定的范围，称为允许策略集合，用P表示。使整个问题达到最优效果的策略就是最优策略。动态规划的基本概念和基本原理状态转移方程

动态规划中本阶段的状态往往是上一阶段的决策结果。如果给定了第k段的状态sk

，本阶段决策为uk(sk)，则第k+1段的状态sk+1由公式：sk+1=Tk（sk，uk）确定，称为状态转移方程。动态规划的基本概念和基本原理指标函数

用于衡量所选定策略优劣的数量指标称为指标函数。最优指标函数记为fk(sk)。指标函数——表示初始状态为且采取策略时，原（全）过程的指标函数——表示第k阶段状态为且采取策略时，后部子过程的指标函数——表示第k阶段状态为且采取最优策略到终止时的最佳效益值。动态规划的基本思想与基本原理最短路的重要性质：ACBA到C的最短路B到C的最短路逆序递推法逆序递推法用逆序递推法求例1的最短路AD2D1B3B2B1C3C1C2E23877356687463532434用逆序递推方法求解，逐步求出各段各点到E的最短路线，最后求得A点到E点的最短路线。当k=4时，f4(D1)表示在第4段由D1到E的最短距离，故有f4(D1)=4。同理，f4(D2)=3。当k=3时，若从C1出发，则有两个选择，一个是至D1一个是至D2，则：

C1到最终点最短距离为8，最短路线：

C1——D1——E相应决策为

u3*(C1)=D1C2到最终点最短距离为7，最短路线：C2——D1——E相应决策为u3*(C2)=D1C3到最终点最短距离为6，最短路线：C3—D1（D2）—E相应决策为u3*(C3)=D1（D2）依此类推，可得：k=2时，有f2(B1)=14u2*(B1)=C2(C3)f2(B2)=11u2*(B2)=C1

f2(B3)=13u2*(B3)=C3

k=1时，只有一种状态A，则即从A到E的最短距离15，本段决策为u1*(A)=B2。再按计算顺序反推可得最优决策序列{uk},即u1*(A)=B2，u2*(B2)=C1,u3*(C1)=D1,u4*(D1)=E所以最优路线：A—B2—C1—D1—EAD2D1B3B2B1C3C1C2E23877356687463532434动态规划的函数基本方程动态规划的函数基本方程边界条件这种递推关系称为动态规划的函数基本方程。其一般形式为：动态规划方法基本思想总结将多阶段决策过程划分为阶段，恰当选取状态变量、决策变量及定义最优指标函数，从而把问题化为一族同类型的子问题，逐个求解。从边界条件开始，按逆（或顺）过程行进方向，逐段递推寻优。贝尔曼(Ballman)最优化原理

作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优