第五章动态规划 §51动态规划的基本概念和方法 §52动态规划的基本原理、模型和解法 §53前向动态规划法 §5.4动态规划的应用 §5.5运用QSB解动态规划问题 2021/2/24
2021/2/24 1 第五章 动态规划 §5.1 动态规划的基本概念和方法 §5.2 动态规划的基本原理﹑模型和解法 §5.3 前向动态规划法 §5.4 动态规划的应用 §5.5 运用QSB解动态规划问题
§51动态规划的基本概念和方法 51.1多阶段决策及过程最优化 多阶段决策是指这样一类特殊的活动过程,它们可以按时间顺序分 解成若干相互联系的阶段,每个阶段都要作出决策,全部过程的决策是 个决策序列,所以多阶段决策问题又称为序贯决策问题。 多阶段决策的目标是要达到整个活动过程的总体效果最优,所以多 阶段决策又叫做过程最优化。也正是因为如此,多阶段决策并非各阶段 决策的简单总和,由于各阶段决策之间的有机联系,某一段决策的执行 必将影响到下一段的决策,以至手影响到总体效果。所以决策者在每 段决策中不仅应考虑本段最优,还应考虑对最终目标的影响,从而做出 对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。 所以,所谓动态规划,就是解决多阶段决策和过程最优化问题的一 种数学规划方法。显然,由于它所解决问题的多阶段性,因此它必然与 时间有着密切的关系,随着时间的推移或过程的发展而决定各阶段的决 策,从而,产生了一个决策序列,这就是动态的意思。然而它也可处理与 时间无关的静态问题,只要在问题中人为地引入“时间”因素,将问题 看成个多阶段的决策过程即可
2021/2/24 2 5.1.1 多阶段决策及过程最优化 多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分 解成若干相互联系的阶段, 每个阶段都要作出决策, 全部过程的决策是 一个决策序列, 所以多阶段决策问题又称为序贯决策问题。 多阶段决策的目标是要达到整个活动过程的总体效果最优, 所以多 阶段决策又叫做过程最优化。也正是因为如此, 多阶段决策并非各阶段 决策的简单总和, 由于各阶段决策之间的有机联系, 某一段决策的执行 必将影响到下一段的决策，以至于影响到总体效果, 所以决策者在每一 段决策中不仅应考虑本段最优, 还应考虑对最终目标的影响, 从而做出 对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。 所以, 所谓动态规划, 就是解决多阶段决策和过程最优化问题的一 种数学规划方法。显然, 由于它所解决问题的多阶段性, 因此它必然与 时间有着密切的关系, 随着时间的推移或过程的发展而决定各阶段的决 策, 从而, 产生了一个决策序列, 这就是动态的意思。然而它也可处理与 时间无关的静态问题, 只要在问题中人为地引入“时间”因素, 将问题 看成一个多阶段的决策过程即可。 §5.1 动态规划的基本概念和方法
动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解 决最短路径问题、资源分配问题、生产计划与库存问题、投资问题、 装载问题、排序问题及生产过程的最优控制等。由于它具有独特的 解题思路因此在处理某些优化问题时常比线性规划等方法更为有效 动态规划模型一般根据决策过程的时间参数是离散的还是连续的 过程的演变是确定型的还是随机型的可以划分为离散确定型、离散随机 型、连续确定型和连续随机型四种类型,其中离散确定型是最基本的 例5.1设A地的某一企业要把一批货物由A地运到E城销售,其间要经过 八个城市,各城市间的交通路线及距离如图5.所示,问应选择什么路线 才能使总的距离最短? B1 6 4 C1 8 5 ①14 2)XC2 1D2f3 B3 9 3)3 2021/2/24 图51例5.1路线图(共18条路线,3×3×2×1=18)
2021/2/24 3 动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解 决最短路径问题、资源分配问题、生产计划与库存问题、投资问题、 装载问题、排序问题及生产过程的最优控制等。由于它具有独特的 解题思路因此在处理某些优化问题时常比线性规划等方法更为有效。 , 动态规划模型一般根据决策过程的时间参数是离散的还是连续的 过程的演变是确定型的还是随机型的可以划分为离散确定型、离散随机 型、连续确定型和连续随机型四种类型，其中离散确定型是最基本的 例5.1 设A地的某一企业要把一批货物由A地运到E城销售, 其间要经过 八个城市,各城市间的交通路线及距离如图5.1所示, 问应选择什么路线 才能使总的距离最短? 图5.1 例5.1路线图(共18条路线,3×3×2×1=18)
这是一个最短路径问题的动态规划,QSB中也叫车马驿 站问题。由图5.1不难看出,本例是一个四阶段的决策问题, 因此,无疑可以用动态规划方法求解。 52动态规划的基本概念 阶段tage) 将所给问题的过程,按时间或空间特征分解成若干相互 联系的段落以便按次序求解就形成了阶段,阶段变量常用字母 k来表示 如例51若有四个阶段,k就等于1234。第一阶段共有3 条路线即(AB1),(AB2)和(A,B3),第二阶段有9条路线,第3 阶段有6条路线,第4阶段有2条路线。 2021/2/24
2021/2/24 4 这是一个最短路径问题的动态规划，QSB中也叫车马驿 站问题。由图5.1 不难看出, 本例是一个四阶段的决策问题, 因此, 无疑可以用动态规划方法求解。 5.1.2 动态规划的基本概念 一、阶段(stage) 将所给问题的过程，按时间或空间特征分解成若干相互 联系的段落以便按次序求解就形成了阶段,阶段变量常用字母 k来表示。 如例5.1若有四个阶段，k就等于1,2,3,4。第一阶段共有3 条路线即(A,B1), (A,B2)和(A,B3),第二阶段有9条路线，第3 阶段有6条路线,第4 阶段有2 条路线
二、状态( state) 各阶段开始时的客观条件或出发点称作状态,描述各阶 段状态的变最称作状态变量,用s表示。状态变量的取值集合 称为状态集合,用S表示。在例5.1中,第一阶段的状态为A 第二阶段的状态为城市B1,B2和B3。所以状态变量s1的集合 S={A}s2的集合是S2={B1B2B3},依次有S3={(C1,C2C S={D1,D2}。所以,在这里状态变量的取值实际上是给定集 的一个元素。 在动态规划中,状态必须具有如下性质:即当某阶段状 态给定以后,在这阶段以后过程的发展不受这段以前各状态 的影响,这称作无后效性。如果所选定的变量不具备无后效性 就不能作为状态变量来构造动态规划模型。如在例5.中,当 某阶段的状态变量确定以后,假定s3=C2,因而在确定第3阶段 的货运路线时,就只与C2这个城市有关,而与货物由哪个城 市到达此地无关,所以满足状态的无后效性 2021/2/24
2021/2/24 5 二、状态(state) 各阶段开始时的客观条件或出发点称作状态，描述各阶 段状态的变最称作状态变量, 用s表示。状态变量的取值集合 称为状态集合, 用S表示。在例5.1中，第一阶段的状态为A， 第二阶段的状态为城市B1，B2和B3。所以状态变量s1的集合 S1={A},s2 的集合是 S2={B1 ,B2 ,B3}, 依 次 有 S3={C1 ,C2 ,C3}, S4={D1 ,D2}。所以,在这里,状态变量的取值实际上是给定集合 的一个元素。 在动态规划中，状态必须具有如下性质：即当某阶段状 态给定以后，在这阶段以后过程的发展不受这段以前各状态 的影响 , 这称作无后效性。如果所选定的变量不具备无后效性， 就不能作为状态变量来构造动态规划模型。如在例5.1中，当 某阶段的状态变量确定以后，假定s3=C2,因而在确定第3 阶段 的货运路线时，就只与C2 这个城市有关，而与货物由哪个城 市到达此地无关，所以满足状态的无后效性