运筹学动态规划讲稿.ppt

《运筹学动态规划讲稿.ppt》由会员分享，可在线阅读，更多相关《运筹学动态规划讲稿.ppt（28页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于运筹学动态规划第一页，讲稿共二十八页哦多阶段决策问题：是动态决策问题的一种特殊形式。在多阶段决策过程中，系统的动态过程可以按照时间进程分为相互联系而又相互区别的各个阶段，而且在每个阶段都要进行决策。目的是使整个过程的决策达到最优效果。多阶段决策问题的典型例子：1 生产决策问题：企业在生产过程中，由于需求是随时间变化的，因此企业为了获得全年的最佳生产效益，就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划。2 机器负荷分配问题：某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为g=g(u1)这时，机器的年完好率为a，即如

2、果年初完好机器的数量为u，到年终完好的机器就为au,0a1。12n状态决策状态决策状态状态决策第二页，讲稿共二十八页哦在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为h=h(u2)相应的机器年完好率b,0 b1。假定开始生产时完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。3 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向（姿态）和速度，使之能最省燃料和实现目的（如软着落问题）。不包含时间因素的静

3、态决策问题（本质上是一次决策问题）也可以适当地引入阶段的概念，作为多阶段的决策问题用动态规划方法来解决。4 线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决，后面将详细介绍。第三页，讲稿共二十八页哦 5 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。我们将用此例来说明所有动态规划问题的理论和方法。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第四页，讲稿共二十八页哦 1 阶段、阶段变量阶段、阶段变

4、量：把所给问题的过程，适当地分为若干个相互联系的阶段，目的是能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。阶段的划分，一般是分为时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策的过程。(逆序模型逆序模型、顺序模型)2 状状态态、状状态态变变量量：状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况。通常一个阶段有若干个状态。描述过程状态的变量称为状态变量。常用sk来表示第k阶段的状态变量。一般来说，状态变量的取值有一定的允许集合或范围，此集合称为是状态允许集合。第二节：第二节：动态规划的基本概念和定义动态规划的基本概念和定义 3 决策、决策

5、变量决策、决策变量：决策表示当过程处于某一阶段的某个状态时，可以做出不同的决定（或选择），从而决定下一阶段的状态，这种决定称为决策。在最优控制中也称为控制。描述决策的变量，称为决策变量。常用uk(sk)表示第k阶段当状态为 sk时的决策变量。在实际问题中决策变量的取值往往在某一范围之内，此范围称为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合，显然有uk(sk)Dk(sk)Dk表示第k阶段的允许决策集合。第五页，讲稿共二十八页哦 4 多阶段决策过程多阶段决策过程：就是可以在各个阶段进行决策，去控制过程发展的多段过程。多阶段决策过程的发展是通过一系列的状态转移来实现的，一

6、般来说，系统在某一阶段的状态转移不但于系统的当前（或本阶段）的状态和决策有关，而且还于系统过去的历史状态和决策有关。其状态转移方程如下（一般形式）12ks1u1s2u2s3skuksk+1图示如下：状态转移方程是确定过程由一个状态到另一个状态的演变过程。如果第k阶段状态变量sk的值、该阶段的决策变量一经确定，第k+1阶段状态变量sk+1的值也就确定。第六页，讲稿共二十八页哦 无后效性或马尔可夫性无后效性或马尔可夫性：如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响。换句话说，过程的过去历史只能通过当前的状态去影响它未来的发展，这个性质称为无后效性。在构造决策过程的

7、动态规划模型时，要充分注意是否满足无后效性的要求。如果状态不能满足无后效性的要求，应适当地改变状态的定义或规定方法，以使状态变量能满足无后效性的要求。状态具有无后效性的多阶段决策过程的状态转移方程如下 能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即具有无后效性的多阶段决策过程。动态规划中能处理的状态转移方程的形式。第七页，讲稿共二十八页哦 5 策策略略：策略是一个按顺序排列的决策组成的集合。由过程的第k阶段开始到终止状态为止的过程，称为问题的后后部部子子过过程程（或称为k子过程）。由每段的决策按顺序排列组成的决策函数序列称为k子过程策略，简称子子策策略略，记为pk,n(sk

8、)，即 当k=1时，此决策函数序列成为全过程的一个策略，简称策略策略，记为p1,n(s1).即在实际问题中，可供选择的策略有一定范围，此范围称为允许策略集合，用p表示。从允许策略集合中找出达到最优效果的策略称为最优策略。6 指标函数和最优值函数指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，称为指标函数，它是定义在全过程或所有后部子过程上确定的数量函数。Vk,n表示之。即第八页，讲稿共二十八页哦 动态规划模型的指标函数，应具有可分离性，并满足递推关系。即Vk,n可以表示为sk,uk,Vk+1,n的函数。常见的指标函数的形式是：过程和它的任一子过程的指标是它所包含的各阶段的指标和。即

9、其中vj(sj,uj)表示第j阶段的阶段指标。这时上式可写成无后效性的结果。第九页，讲稿共二十八页哦 过程和它的任意子过程的指标是它所包含的各阶段的指标的乘积。即则可改写成 最优值函数最优值函数：表示从第k阶段的状态sk开始到第n阶段的终止状态的过程，采取最优策略所得到的指标函数值。即第十页，讲稿共二十八页哦多阶段决策过程的数学模型：（具有无后效性的多阶段决策过程）所谓求解多阶段决策过程问题，就是要求出（1）最优策略，即最优决策序列（2）最优轨线，即执行最优策略时的状态序列第十一页，讲稿共二十八页哦（3）最优目标函数值 f1(s1)从k到终点最优子策略的最优目标函数值第十二页，讲稿共二十八页哦

10、第三节：动态规划的基本思想和基本方程第三节：动态规划的基本思想和基本方程以最短路问题的解法为例来说明。（穷举法48条路线）AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456第十三页，讲稿共二十八页哦最短路的特性最短路的特性：如果已有从起点到终点的一条最短路，那么从最短路线上中间任何一点出发到终点的路线仍然是最短路。（证明:用反证法）当k=6时,由F1到终点G只有一条路线，故f6(F1)=4.同理，f6(F2)=3.当k=5时，出发点有E1,E2,E3三个。u5(E1)=F1E1 F1 Gu5(E2)=F2E2 F

11、2 Gu5(E3)=F2E3 F3 G第十四页，讲稿共二十八页哦当k=4时，有当k=3时，有当k=2时，有第十五页，讲稿共二十八页哦当k=1时，有且u1(A)=B1，于是得到从起点A到终点G的最短距离为18。为了找到最短路线,再按计算的顺序反推之,可求出最优决策函数序列uk：u1(A)=B1,u2(B1)=C2,u3=(C2)=D1,u4(D1)=E2,u5(E2)=F2,u6(F2)=G，即最优策略。最短路线为AB1C2D1E2F2G。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G5313687683533842212333552664360437597681310912131

12、618第十六页，讲稿共二十八页哦用动态规划（逆序法逆序法求解的）基本特性：（1）将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量、及定义最优指标函数，正确写出基本的递推关系式和恰当的边界条件（简言之为基本方程）。从而把问题化成一族同类的子问题，（2）求解时从边界条件开始，逆（或顺）过程行进方向，逐段递推寻优。在每个问题求解时，都要使用它前面已求出的子问题的最优结果，最后问题的最优解，就是整个问题的最优解。（3）动态规划方法是既把当前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。每段决策的选取都是从全局考虑的，与该段的最优选择答案一般是不同的。（4）在求整个问题的

13、最优策略时，由于初始状态是已知的，每段的决策是该段状态的函数，故沿最优化策略所经过的各段状态便可确定了最优路线。第十七页，讲稿共二十八页哦（5）求解的各个阶段,我们利用了k阶段与k+1阶段之间的递推关系:一般情况,k阶段与k+1阶段的递推关系式（动态规划基本方程动态规划基本方程）边界条件为练习：写出乘积形式指标函数的动态规划基本方程。第十八页，讲稿共二十八页哦用动态规划求解时的几点注意：（1）将问题的过程划分成恰当的阶段；（2）正确选择状态变量sk,使它既能描述过程的变量，又要满足无后效应；（3）确定决策变量uk及每一阶段的允许决策集合Dk(sk)；（4）正确写出状态转移方程；（5）正确写出指

14、标函数Vk,n，它应满足下面三个性质：a)是定义在全过程和所有后部子过程上的数量函数；b)要具有可分离性，并满足递推关系。即 c）函数k（sk，uk，Vk+1,n）对于变量Vk+1，n要严格单调。第十九页，讲稿共二十八页哦顺序解法的阶段变量k，决策变量xk，以及决策变量允许集合Qk的含义和逆序解法模型中相应变量的含义相同，而状态变量sk表示第k阶段结束时的状态，其中k=0,1,2,n。记状态转移方程为 sk=g(sk-1,xk)k=1,2,n则 s k-1=g-1(sk,xk)记第k阶段末状态为sk，第k阶段决策为xk的直接指标（或称阶段指标）为dk(sk,xk)，并记从第1阶段到第k阶段末状

15、态为sk所得到的最大效益为fk(sk)，则顺序解法的基本方程（或称指标递推方程及边界条件）为其中 opt=Max or Min顺序解法顺序解法第二十页，讲稿共二十八页哦AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368766835338422123335526643123456 最短路问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或花费），试求从A点到G点的最短距离（总费用最小）。第二十一页，讲稿共二十八页哦按照顺序动态规划求解方法，从第1阶段开始计算，由前向后逐步推移至G点，计算过程为当k=0时，S0=A，f0（A）=0当k=1时，S1=B1，B2，由A到B

16、1只有一条路线，故f1（B1）=5 同理得：f1（B2）=3当k=2时，S2=C1，C2，C3，C4 f2（C 1）=Min d2（B1，C1）+f1（B1）=Min 1+5=6 其相应决策为x2：B1 C1 f2（C 2）=Min d2（B1，C2）+f1（B1），d2（B2，C2）+f1（B2）=Min 3+5，8+3=8 其相应决策为x2：B1 C2 f2（C 3）=Min d2（B1，C3）+f1（B1），d2（B2，C3）+f1（B2）=Min 6+5，7+3=10 其相应决策为x2：B2 C3 f2（C 4）=Min d2（B2，C4）+f1（B2）=Min 6+3=9 其相应决策

17、为x2：B2 C4第二十二页，讲稿共二十八页哦类似地，可计算得当k=3时，S3=D1，D 2，D 3，有 f3（D 1）=11 x3：C 2 D1 f3（D 2）=13 x3：C 2 D2 or C 3 D2 f3（D 3）=13 x3：C 3 D3 or C 4 D3当k=4时，S4=E1，E 2，E 3，有 f4（E 1）=13 x4：D1 E 1 f4（E 2）=13 x4：D 1 E 2 f4（E 3）=15 x4：D 2 E 3 当k=5时，S5=F1，F 2，有 f5（F 1）=16 x5：E 1 F 1 f5（F 2）=15 x5：E 2 F 2 当k=6时，S5=G，有 f6（

18、G）=18 x6：F 2 G再按计算的顺序反推，可得相应的最短线路为：A B1 C2 D1 E 2 F 2 G第二十三页，讲稿共二十八页哦第四节：动态规划的理论基础第四节：动态规划的理论基础 适应于用动态规划方法求解的是具有无后效性的多阶段决策过程。动态规划方法的理论基础是基于R.Bellman提出的最优性原理最优性原理：“一个过程的最优策略具有这样的性质：即无论其初始状态及初始决策如何，对于先前决策所形成的状态而言，余下的诸决策仍构成最优策略。”最优性原理的含义是：最优策略的任何一部分子策略，都是最优策略。每个最优策略只能由最优子策略构成。多阶段决策过程的特点：每个阶段都要进行决策，策略是由

19、n个相继进行的决策构成的决策序列。前一阶段的终止状态又是下一阶段的初始状态，因此，确定阶段最优决策不能只从本阶段的效应来考虑，必须是整个过程通盘考虑，整体规划。即阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优。第二十四页，讲稿共二十八页哦它是由给定的初始状态s0和子策略p0,k-1所确定的k段状态。当V是效益函数时，opt取max;当V是损失函数时，opt取min.动动态态规规划划的的最最优优性性定定理理：设阶段数为n的多阶段决策过程，其阶段编号为k=0,1,.,n-1。允许策略是最优策略的充要条件是对任意一个k,0kn-1和s0S0，有第二十五页，讲稿共二十八页哦证明：必要性（）第二十六页，讲稿共二十八页哦充分性（）设p0,n-1=(p0,k-1,pk,n-1)为任一策略，sk为由（s0，p0,k-1）所确定的k阶段的起始状态，则有（以最大化为例）第二十七页，讲稿共二十八页哦感感谢谢大大家家观观看看第二十八页，讲稿共二十八页哦