1、管 理 运 筹 学第十章 动态规划1 动态规划的基本概念与基本思路2 多阶段决策过程最优化问题举例3 动态规划的应用 (1)4 动态规划的应用 (2)1管 理 运 筹 学 动态规划是一种研究 多阶段决策 问题的理论和方法，在决策中将问题分成若干阶段，对不同阶段采取不同的决策， 使全过程达到整体最优 。 所谓多阶段决策问题是指这样一类决策过程，当每个阶段的决策选定以后，过程也就随之确定。把各个阶段的决策综合起来，构成一个决策序列，称为一个 策略 。显然由于各个阶段选取的决策不同，对应整个过程就可以有一系列不同的策略。当对过程采取某一策略时，可以得到一个 确定的（或期望的）效果 ，采取不同的策略，
2、就会得到不同的效果。 多阶段的决策问题，就是要在所有可能采取的策略中间选取一个 最优的策略 ，使在预定的标准下得到最好的效果。2管 理 运 筹 学 与线性规划相比，动态规划问题 没有一个标准的数学模型。然而，动态规划是 一类很普遍的问题解决方法 ，需要建立特定的方程以适应各种情况。 在多阶段决策问题中 , 各个阶段采取的决策 , 一般来说是与时间 有关的 , 决策依赖于当前的状态 , 又随即引起状态的转移 , 一个决策序列就是在变化的状态中产生出来的 , 故有 “ 动态 ”的含义。因此 , 把处理它的方法称为动态规划方法。但是 , 一些与时间没有关系的静态规划 (如线性规划、非线性规划等 )问
3、题 , 只要人为地引进 “时间 ”因素 , 也可把它视为多阶段决策问题 , 用动态规划方法去处理。 动态规划问题的复杂性在于 各阶段决策之间的相互联系。根据实际问题构造动态规划模型往往需要掌握更多的技巧。3管 理 运 筹 学 4管 理 运 筹 学 最短路径问题：引例。 如图 , 给定一个线路网络 , 两点之间连线上的数字表示两点间的距离 ( 或费用 ) ,试求一条由 A 到 G 的铺管线路, 使总距离为最短 (或总费用最小 )。1 动态规划的基本概念5管 理 运 筹 学 由图可知 , 从 A 点到 G 点可以分为 6 个 阶段。从 A 到 B 为第一阶段 , 从 B 到 C为第二阶段 从 F
4、到 G 为第六阶段。 在第一阶段 , A 为起点 , 终点有 B1 、 B2 两个 , 因而这时走的路线有两个选择 , 一是走到 B1 ; 一是走到 B2 , 若选择走到 B2 的决策 , 则 B2 就是第一阶段在我们决策之下的结果。它既是第一阶段路线的终点 , 又是第二阶段路线的始点。 在第二阶段 , 再从 B2 点出发 , 对应于 B2 点就有一个可供选择的终点集合 C2 , C3 , C4 ; 若选择由 B2 走至 C2 为第二阶段的决策 , 则 C2 就是第二阶段的终点 , 同时又是第三阶段的始点。 同理递推下去 , 可看到 : 各个阶段的决策不同 , 铺管路线就不同。很明显 , 当某
5、阶段的始点给定时 , 它直接影响着后面各阶段的行进路线和整个路线的长短 , 而后面各阶段的路线的发展不受这点以前各阶段路线的影响 。 故此问题的要求是 : 在各个阶段选取一个恰当的决策 , 使由这些决策组成的一个决策序列所决定的一条路线 , 其总路程最短。6管 理 运 筹 学1、动态规划的基本概念 1. 阶段 把所给问题的过程 , 恰当地分为若干个相互联系的阶段 , 以便能按一定的次序去求解。描述阶段的变量称为阶段变量 , 常用 k 表示。阶段的划分 , 一般是根据 时间和空间的自然特征 来划分 , 但要便于把问题的过程能转化为多阶段决策的过程。如引例可分为 6个阶段来求解 , k 分别等于
6、1、 2、 3、 4、 5、 6。7管 理 运 筹 学 2. 状态 状态表示 每个阶段开始所处的自然状况或客观条件 , 它 描述了研究问题过程的状况 ,又称不可控因素。 在引例中 , 状态就是某阶段的出发位置。它既是该阶段某支路的起点 ,又是前一阶段某支路的终点。 通常一个阶段有若干个状态 , 第一阶段有一个状态就是点 A, 第二阶段有两个状态 , 即点集合 B1 , B2 , 一般第 k 阶段的状态就是第 k 阶段所有始点的集合。8管 理 运 筹 学 描述过程状态的变量称为状态变量 。常用 sk 表示第 k 阶段的状态变量。如在引例中第三阶段有四个状态 , 则状态变量 sk 可取四个值 ,
7、即 C1 、 C2 、 C3 、 C4 。点集合 C1 , C2 , C3 , C4 就称为第三阶段的可达状态集合。记为 S3 = C1 , C2 , C3 , C4 。有时为了方便起见 , 将该阶段的状态编上号码 1 , 2 这时也可记 S3 = 1 , 2 , 3 , 4。第 k 阶段的可达状态集合就记为 S k 。9管 理 运 筹 学 这里所说的状态应具有下面的性质 : 如果某阶段状态给定后 , 则在这阶段以后过程的发展不受这阶段以前各段状态的影响。换句话说 , 过程的过去历史只能通过当前的状态去影响它未来的发展 , 当前的状态是以往历史的一个总结。这个性质称为无后效性 ( 即马尔科夫性 )。 如果状态仅仅描述过程的具体特征 , 则并不是任何实际过程都能满足无后效性的要求。所以 , 在构造决策过程的动态规划模型时 , 不能仅由描述过程的具体特征这点着眼去规定状态变量 , 而 要充分注意是否满足无后效性的要求 。10
