运筹学第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}。所以,在这里,状态变量的取值实际上是给定集合 的一个元素。
合,用 Dk ( sk )表示第 k 阶段从状态 sk 出发时的允许决策集合 ,显然
有U k ( sk )∈ Dk ( sk )。
在例 5.1 中第二阶段如决定从 B1 出发,即 s2=B1 ,可选择走 C1 或 C2,C3,即其允许的决策变量集合 D2(B1)={C1,C2,C3} 。如果我们选择 从 C2 走,则此时的决策变量可表示为 U2(B1)=C2 。所以, 在这里决策变 量的取值实际上也是给定集合的一个元素。
所以, 所谓动态规划, 就是解决多阶段决策和过程最优化问题的一 种数学规划方法。显然, 由于它所解决问题的多阶段性, 因此它必然与 时间有着密切的关系, 随着时间的推移或过程的发展而决定各阶段的决 策, 从而, 产生了一个决策序列, 这就是动态的意思。然而它也可处理与 时间无关的静态问题, 只要在问题中人为地引入“时间”因素, 将问题 看成一个多阶段的决策过本程课即件的可所。有权属于熊义杰
5.1.2 动态规划的基本概念
一、阶段(stage)
将所给问题的过程,按时间或空间特征分解成若干相互 联系的段落以便按次序求解就形成了阶段,阶段变量常用字母 k来表示。
如例5.1若有四个阶段,k就等于1,2,3,4。第一阶段共有3 条路线即(A,B1), (A,B2)和(A,B3),第二阶段有9条路线,第3 阶段有6条路线,第4 阶段有2 条路线。
在动态规划中,状态必须具有如下性质:即当某阶段状 态给定以后,在这阶段以后过程的发展不受这段以前各状态 的影响 , 这称作无后效性。如果所选定的变量不具备无后效性, 就不能作为状态变量来构造动态规划模型。如在例5.1中,当 某阶段的状态变量确定以后,假定s3=C2,因而在确定第3 阶段 的货运路线时,就只与C2 这个城市有关,而与货物由哪个城 市到达此地无关,所以满足状态的无后效性
型、连续确定型和连续随机型四种类型,其中离散确定型是最基本的
例5.1 设A地的某一企业要把一批货物由A地运到E城销售, 其间要经过 八个城市,各城市间的交通路线及距离如图5.1所示, 问应选择什么路线 才能使总的距离最短?
图5.1 例5.1路线图(共18条路线,3×3×2×1=18)
这是一个最短路径问题的动态规划,QSB中也叫车马驿站问 题。由图5.1 不难看出, 本例是一个四阶段的决策问题, 因此, 无疑 可以用动态规划方法求解。
本课件的所有权属于熊义杰
三、 决策和策略(Decision and Policy)
当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确 定下一阶段的状态,这种决定就是决策 。表示决策的变量称为决策变量,
常用U k ( sk )表示第 k 阶段当状态为 sk 时的决策变量 ,在实际问题中 ,
决策变量的取值是被限制在一定的范围内,我们称此范围为允许的决策集
多阶段决策的目标是要达到整个活动过程的总体效果最优, 所以多 阶段决策又叫做过程最优化。也正是因为如此, 多阶段决策并非各阶段 决策的简单总和, 由于各阶段决策之间的有机联系, 某一段决策的执行 必将影响到下一段的决策,以至于影响到总体效果, 所以决策者在每一 段决策中不仅应考虑本段最优, 还应考虑对最终目标的影响, 从而做出 对全局来说最优的决策。动态规划就是符合这种要求的一种决策方法。
本课件的所有权属于熊义杰
四、状态转移方程 在动态规划中,本阶段的状态往往是上阶段决策的结果。所以如果给
定了第 k 阶段的状态 sk 和该阶段的决策 U k ( sk ),则第 k+1 段的状态 sk+1
由于 k 阶段决策的完成也就完全确定了 ,它们之间的关系可用如下公式表示:
sk +1 = Tk ( sk ,U k ) 其中, Tk 表示从状态 sk 出发经过 U k 向下一阶段的转移 (Transfer),换 言之,即 sk+1 是从状态 sk 出发经过决策 U k 转移的结果。
动态规划是现代管理中一种重要的决策方法,它可以广泛地用于解 决最短路径问题、资源分配问题、生产计划与库存问题、投资问题、 装载问题、排序问题及生产过程的最优控制等。由于它具有独特的 解题思路因此在处理某些优化, 问题时常比线性规划等方法更为有效。
动态规划模型一般根据决策过程的时间参数是离散的还是连续的 过程的演变是确定型的还是随机型的可以划分为离散确定型、离散随机
在各阶段决策确定以后, 整个问题的决策序列就构成了一个策略 ,用
P1,n (U1 ,U2,…,Un) 表示,如对于例 5.1, P1,n (A,B2,C1,D2,E) 就是一个策略。
对于每个实际问题 ,可供选择的策略有一定范围 ,称为允许策略集合,用 P 表示,使整个问题达到最优效果的策略就是最优策略。如对于例 5.1 总共 可有 18 个策略,但最优策略只有一个。
由于上式表示了由 k 段到第 k+1 段的状态转移规律,所以就称为状态
转移方程。在例 5.1 中,状态转移方程即 sk+1 =U k 。
第五章 动态规划
§5.1 动态规划的基本概念和方法 §5.2 动态规划的基本原理﹑模型和解法 §5.3 前向动态规划法 §5.4 动态规划的应用 §5.5 运用QSB解动态规划问题
本课件的所有权属于熊义杰
§5.1 动态规划的基本概念和方法 5.1.1 多阶段决策及过程最优化
多阶段决策是指这样一类特殊的活动过程, 它们可以按时间顺序分 解成若干相互联系的阶段, 每个阶段都要作出决策, 全部过程的决策是 一个决策序列, 所以多阶段