数学规划在测量中的应用-第四章.pptVIP

第四章 动态规划 §4-1 概述 动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种方法。 1951年，美国数学家贝尔曼根据一类多阶段决策问题的特性，提出了解决这类问题的“最优化原理”，并研究了许多实际问题，从而创建了解决多阶段决策最优化问题的一种新方法。1957年发表了《动态规划》。 动态规划把比较复杂的问题划分为若干阶段，通过逐段求解，最终求得全局最优解。这种“分而治之，逐步改善”的方法已在一些较难解决的问题，尤其是在离散性问题中，显示出优越性，常常成为解决它的一个非常有效的工具。 动态规划不是解决某一个具体数学模型的某种算法，而是一般的求解问题的思路或方法。而线性规划是给定一个目标函数和一些约束条件，用它来确定某一阶段的最佳决策。 因此动态规划问题中，最佳决策是由一连串的决策所构成的，也就是一个整体系统的最佳决策包含了若干阶段的决策，并且每一阶段的决策会对其它阶段的决策产生影响。 对于这一类问题，可以按照决策问题的时间或空间关系所构成的若干相互联系的阶段，顺序地(依次地)为每一阶段作出最优决策。但在每一阶段作出最优决策时，应该考虑和包含这一阶段以前所有阶段在内的最优决策。这样，当最后一个阶段的最优决策确定后，整个问题的最优决策方案也就随之而完全确定。动态规划就是根据这种基本思想处理多阶段决策问题的一种数学方法。 动态规划的优点： ①减少计算量； ②计算结果丰富。 动态规划的两个缺陷： ①利用“最优化原理”得出函数方程后，尚没有统一的处理方法，必须根据问题的各种性质结合其它数学技巧来求解； ②存在“维数障碍”，动态规划问题中，状态变量需要用向量来表达，当向量维数增大时，计算量会异常增大。 既是解决多阶段问题，就需划分阶段。阶段可按时间划分，也可按空间划分。 如从武汉→北京。 在各阶段中的变量可能是连续变化的，也可能是离散的，因此决策过程可分为离散型和连续型两种； 在每一阶段中，下一个目标（决定或决策）可能是确定的，也可能能是随机的，因此根据决策过程的演变可分为确定型、随机型和模糊型三种。 本章讨论的动态规划是： 离散确定型决策过程。 §4-2 动态规划的基本概念和基本方程 一、基本概念 示例 最能体现动态规划特点和基本思想的问题是网络最短线路问题。 找出从A→G的最短线路 从A出发有两个选择，一是到B1，一是到B2；如果选择走B2，则B2是第一阶段的决策结果，它是第一阶段的终点，也是第二阶段的起点。依次类推。 显然，各阶段决策不同，所走的线路就不同；但后面各阶段的路线不受这点以前各段线路的影响。 选取最短线路的方法 ①枚举法：把A→G的所有可能线路的长度均计算出来，互相比较，找出最短线路。 共有2×3×2×2×2×1=48条线路， 最短长度为18，线路为:A→B1→C2→D1→E2→F2→G 枚举法可以找出最短线路，但计算繁琐。 ②动态规划方法 动态规划的基本概念 ①阶段: 表示某阶段的出发位置。通常一个阶段包含若干个状态。如第二阶段有2个状态：B1、B2；第五阶段有3个状态：E1、E2、E3。 因此第k阶段的状态集合就是第k阶段中所有支路的始点的集合，即某一阶段所有起点的集合构成这一阶段的状态集合。 某一阶段的状态被指定后，到下一阶段某状态的选择或指向，称为决策。描述决策的变量称为决策变量，用uk(xk)表示第k阶段处于xk时的决策变量。如第一阶段： u1(x1)= u1(A)=B1 在实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，以Dk(xk)表示xk的允许决策集合。 如第4阶段的状态集合为X4={D1,D2,D3,D4}，若从D2出发，其允许决策集合为D4(D2)={E2,E3}，若选取的决策为E2 ， 则u4(D2)=E2 因此，一条线路的某节点一方面是在其始点做决策所取得的值；另一方面又往往是下一个阶段的一个状态。也就是说， uk(xk)所取的值一方面是状态变量xk作决策uk取得的一个值，另一方面它往往又是下一个阶段的一个状态。 ④策略： 由第1阶段起点开始到终点为止的过程称为问题的全过程。 由每阶段的决策ui(xi)(i=1,2,…,n)组成的决策函数序列称为全过程策略，简称策略，记为P1,n： P1,n={u1(x1),u2(x2),…,un(xn)} 例如第1阶段决策为B1，第2阶段决策为C3，第3阶段决策为D2，第4阶段决策为E2，第5阶段决策为F1，第6阶段决策为G，则从起点A到终点G的一个决策为： {u1(A)=B1,u2(B1)=C3,u3(C3)=D2,u4(D2)=E2,u5(E2)=F1,u6(F