1、第 5章 动态规划*1. 多阶段决策问题多阶段决策过程 ：问题的活动过程分为若干相互联系的阶段，任一阶段 i以后的行为仅依赖于 i阶段的过程状态，而与 i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程 (multistep decision process) 。最优化问题 ：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。 多阶段决策的最优化问题 就是：求能够获得问题最优解的决策序列 最优决策序列。5.1 一般方法Date2. 多阶段决策过程的求解策略1）
2、 枚举法： 穷举 可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划20世纪 50年代初美国数学家 R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的 最优化原理 (principle of optimality)，把 多阶段 过程转化为一系列 单阶段 问题，创立了解决这类过程优化问题的新方法 动态规划 。动态规划 (dynamic programming)是 运筹学 的一个分支，是求解决策过程 (decision process)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理
3、、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。Date3. 最优性原理 (Principle of Optimality)过程的 最优决策序列 具有如下性质：无论过程的初始状态 和 初始决策 是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。Date例 5.1 多段图问题 多段图 G=(V,E)是一个有向图，且具有特性 :结点 ：结点集 V被分
4、成 k2 个不相交的集合 Vi， 1ik，其中 V1和 Vk分别只有一个结点 s(源点 )和 t(汇点 ) 每一集合 Vi定义图中的 一段 。边 ： 所有的边 (u,v)均具有如下性质： 若 E， 则该边将是从某段 i指向 i+1段，即若 uV i，则 vV i 1, 1ik 1。 每条边 (u,v)均附有成本 c(u,v)。s到 t的路径 ：从第 1段开始，至第 2段、第 3段、 、最后在第 k段终止。路径的 成本 是这条路径上边的成本和。多段图问题 ：求由 s到 t的 最小成本路径 。Date12345678910111297324227111181456356425V1 V2 V3 V4
5、 V55段图Date多段图问题的 多阶段决策过程： 生成从 s到 t的最小成本路径是在 k-2个阶段（除 s和 t外）进行某种决策的过程：从 s开始， 第 i次 决策决定 Vi+1(1ik-2)中的哪个结点在从 s到 t的最短路径上。 最优性原理对多段图问题成立假设 s,v2,v3,v k-1,t是一条由 s到 t的最短路径。 初始状态 ： s 初始决策： (s,v2)， v2V 2 初始决策产生的状态： v2则，其余的决策 ： v3,.,vk-1相对于 v2将构成一个最优决策序列 最优性原理成立。反证 ：若不然，设 v2,q3,q k-1,t是一条由 v2到 t的更短的路径，则 s, v2,
6、q3,q k-1,t将是比 s,v2,v3,v k-1,t更短的从 s到 t的路径。与假设矛盾。故，最优性原理成立Datel例 5.20/1背包问题 KNAP(l,j,X)目标函数：约束条件：0/1背包问题： KNAP(1,n,M)Date最优性原理对 0/1背包问题成立：设 y1,y2, yn是 x1,x2, xn的 0/1值最优序列。若 y1 0, KNAP(2,n,M)是初始决策产生的状态。则 y2, yn相对于 KNAP(2,n,M)将构成一个最优序列。否则 ， y1,y2, yn将不是 KNAP(1,n,M)的最优解若 y1 1, KNAP(2,n,M w1)是初始决策产生的状态。则y2, yn相对于 KNAP(2,n,M w1)将构成一个最优序列。否则，设存在另一 0/1序列 z1,z2, zn,使得 且则序列 y1,z2, zn将是一个对于 KNAP(1,n,M)具有更大效益值的序列 ,与假设矛盾故，最优性原理成立Date4. 动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：1) 阶段阶段 (step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用 k=1,2,.,n表示。Date
