第九讲 队氙态规划 .pptVIP

湖州师范学院 湖州师范学院商学院 运筹学（operational research, OR） 第九讲 动态规划 商学院电子商务系 v2 v3 v4 v7 v5 v9 v6 v8 v10 2 8 5 12 13 10 7 10 13 11 2 8 6 5 8 8 5 4 0 5 8 4 7 最短路径问题 下图表示从起点v1到终点v10之间各点的距离。求 v1到 v10的最短路径。 v1 第1阶段 第2阶段 第3阶段 第4阶段 阶段： 第5阶段 12 17 14 20 19 Min{2+5,8+8,6+4}=7 动态规划问题具有以下基本特征 1. 问题具有多阶段决策的特征。阶段可以按时间划分，也可以按空间划分。 2. 每一阶段都有相应的“ 状态”与之对应。 3. 每一阶段都面临一个决策，选择不同的决策将会导致下一阶段不同的状态，同时，不同的决策将会导致这一阶段不同的目标函数值。 4. 每一阶段的最优解问题可以递归地归结为下一阶段各个可能状态的最优解问题，各子问题与原问题具有完全相同的结构。能否构造这样的递推归结，是解决动态规划问题的关键。这种递推归结的过程，称为“ 不变嵌入”。 第九讲 动态规划 5 . 状态具有无后效性 当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。如下图所示： 9 A B1 B2 B3 D1 C1 C4 C3 D2 E 7 8 12 12 14 4 12 1 3 6 5 10 6 4 C2 9 0 第九讲 动态规划 动态规划基本原理是将一个问题的最优解转化为求子问题的最优解，研究的对象是决策过程的最优化，其变量是流动的时间或变动的状态，最后到达整个系统最优。 基本原理一方面说明原问题的最优解中包含了子问题的最优解，另一方面给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，分而治之，即分治法，是一种解决最优化问题的算法策略。 动态规划求解可分为三个步骤：分解、求解与合并。 第九讲 动态规划 （1）阶段(Stage)：表示决策顺序的时段序列，阶段可以按时间或空间划分，阶段数k可以是确定数、不定数或无限数 动态规划理论基本概念 （3）决策（Decision）xk：从某一状态向下一状态过度时所做的选择。决策变量记为xk，xk是所在状态sk的函数。在状态sk下，允许采取决策的全体称为决策允许集合，记为Dk(sk)。各阶段所有决策组成的集合称为决策集。 （2）状态（State）：描述决策过程当前特征并且具有无后效性的量。状态可以是数量，也可以是字符，数量状态可以是连续的，也可以是离散的。每一状态可以取不同值，状态变量记为sk。各阶段所有状态组成的集合称为状态集。 第九讲 动态规划 (4) 策略(Strategy)：从第1阶段开始到最后阶段全过程的决策构成的序列称为策略，第k阶段到最后阶段的决策序列称为子策略。 （5）状态转移方程(State transformation function)：某一状态以及该状态下的决策，与下一状态之间的函数关系，记为 sk+1=T(sk,xk) （6）指标函数或收益函数(Return function)：是衡量对决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为k阶段指标函数、k子过程指标函数及最优指标函数。 第九讲 动态规划 k阶段指标函数 从k阶段状态sk出发，选择决策xk所产生的第k阶段指标，称为k阶段指标函数,记为vk(sk,xk)。 从k阶段状态sk出发，选择决策xk,xk+1,…,xn所产生的过程指标，称为k子过程指标函数或简称过程指标函数，记为 Vk(sk,xk,xk+1,…,xn)或Vk，n为阶段数。 过程指标函数 最优指标函数 从k阶段状态sk出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为fk(sk)，通常取Vk的最大值或最小值。 （Opt＝optimization 表示“max”或“min” 第九讲 动态规划 动态规划要求过程指标满足递推关系 ，即 连和形式： 最优指标函数是 第九讲 动态规划 动态规划数学模型上式、边界条件及状态转移方程构成。如连和形式的数学模型 ： 连乘形式(vj≠0) ： 最优指标函数是 第九讲 动态规划 对于可加性指标函数，上式可以写为 上式中“ opt”表示“ max”或“ min”。对于可乘性指标函数，上式可以写为： 上式称为动态