第五章动态规划 §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 这个城市有关，而与货物由哪个城 市到达此地无关，所以满足状态的无后效性
、决策和策略 Decision and Policy) 当各阶段的状态确定以后,就可以做出不同的决定或选择,从而确 定下一阶段的状态,这种决定就是决策。表示决策的变量称为决策变量, 常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量,在实际问题中, 决策变量的取值是被限制在一定的范围内,我们称此范围为允许的决策集 合,用Dk(Sk)表示第k阶段从状态Sk出发时的允许决策集合,显然 有Uk(S1)∈D(SA)。 在例51中第二阶段如决定从B1出发,即s2=B1,可选择走C1或 C2,C3,即其允许的决策变量集合D2(B1){C1C2,C3}。如果我们选择 从C2走,则此时的决策变量可表示为UB1)=C2。所以,在这里决策变 量的取值实际上也是给定集合的一个元素 在各阶段决策确定以后,整个问题的决策序列就构成了一个策略,用 (U1,2,U)表示如对于例51、Pn(AB2CD2E)就是一个策略。 对于每个实际问题,可供选择的策略有一定范围,称为允许策略集合,用P 表示,使整个问题达到最优效果的策略就是最优策略。如对于例5.1总共 可有18个策略,但最优策略只有一个。 2021/2/24
2021/2/24 6 三、 决策和策略(Decision and Policy) 当各阶段的状态确定以后，就可以做出不同的决定或选择，从而确 定下一阶段的状态，这种决定就是决策。表示决策的变量称为决策变量， 常用Uk （ k s ）表示第 k 阶段当状态为 k s 时的决策变量，在实际问题中, 决策变量的取值是被限制在一定的范围内，我们称此范围为允许的决策集 合，用 Dk （ k s ）表示第 k 阶段从状态 k s 出发时的允许决策集合，显然 有Uk （ k s ）∈ Dk （ k s ）。 在例 5.1 中第二阶段如决定从 B1 出发，即 s2=B1，可选择走 C1 或 C2，C3，即其允许的决策变量集合 D2 (B1)={C1,C2,C3} 。如果我们选择 从 C2 走，则此时的决策变量可表示为 U2 (B1)=C2 。所以, 在这里决策变 量的取值实际上也是给定集合的一个元素。 在各阶段决策确定以后， 整个问题的决策序列就构成了一个策略 ,用 P1,n (U1 ,U2 ,…,Un ) 表示,如对于例 5.1, P1,n (A,B2,C1,D2,E)就是一个策略。 对于每个实际问题,可供选择的策略有一定范围 ,称为允许策略集合，用 P 表示，使整个问题达到最优效果的策略就是最优策略。如对于例 5.1 总共 可有 18 个策略，但最优策略只有一个
四、状态转移方程 在动态规划中,本阶段的状态往往是上阶段决策的结果。所以如果给 定了第k阶段的状态Sk和该阶段的决策Uk(Sk),则第k+1段的状态Sk 由于k阶段决策的完成也就完全确定了,它们之间的关系可用如下公式表示: SkHI=TK (Sk, UK) 其中,Tk表示从状态Sk出发经过Uk向下一阶段的转移( Transfer),换 言之,即Sk+1是从状态Sk出发经过决策Uk转移的结果 由于上式表示了由k段到第k+1段的状态转移规律,所以就称为状态 转移方程。在例51中状态转移方程即Sk+1=U 五、指标函数 用于衡量所选定策略优劣的数量指标称作指标函数。一个n阶段的决策 过程,从1到n叫作问题的原过程,对于任意一个给定的k(1≡k≡n),从k 段到第n段称为原过程的一个后部子过程用Vn(S1,Bn)表示初始状态为 s1采用策略Pn时原过程的效益值用kn(SA,Pn)表示在第k阶段状态 2021/2/24
2021/2/24 7 四、状态转移方程 在动态规划中，本阶段的状态往往是上阶段决策的结果。所以如果给 定了第 k 阶段的状态 k s 和该阶段的决策Uk ( k s )，则第 k+1 段的状态 k+1 s 由于 k 阶段决策的完成也就完全确定了 ,它们之间的关系可用如下公式表示： k+1 s ＝Tk （ k s ，U k ） 其中，Tk 表示从状态 k s 出发经过Uk 向下一阶段的转移(Transfer) ，换 言之，即 k+1 s 是从状态 k s 出发经过决策U k 转移的结果。 由于上式表示了由 k 段到第 k+1 段的状态转移规律，所以就称为状态 转移方程。在例 5.1 中,状态转移方程即 k+1 s ＝U k 。 五、指标函数 用于衡量所选定策略优劣的数量指标称作指标函数。 一个 n 阶段的决策 过程, 从 1 到 n 叫作问题的原过程,对于任意一个给定的 k(1 ≦k≦n),从 k 段到第 n 段称为原过程的一个后部子过程.用V1,n (s1,P1,n )表示初始状态为 s1采用策略 P1,n 时原过程的效益值,用Vk ,n （ k s ， Pk ,n ）表示在第 k 阶段状态
为Sk采用策略Pn时的后部子过程的效益值。最优指标函数记为f(Sk) 它表示从第k阶段的状态Sk出发采用最优策略Pkn到过程终止时的最佳效 益值,于是有下面的关系式: fr(sk)=vkn(sk, pk.n)=opt Vkn(Sk, Pkn) 其中,opt全称 optimization即最优化,在最大化时用max,在最小化时用 min。fk(Sk)也称作k阶段从状态Sk出发时的后部子过程的最佳效益值 当k=1时,f1(S1)就是从初始状态S1到全过程结束的整体最优指标函数。 在例51中指标函数就是距离。如在第2阶段,状态为B2时,V2,4(B2) 就表示从B2到E的可能距离,f2(B2则表示从B2到E的最短距离。本问 题的总目标是求f1(A),即从A到E的最短距离 2021/2/24 8
2021/2/24 8 为 k s 采用策略 Pk ,n 时的后部子过程的效益值。最优指标函数记为 ( ) k k f s , 它表示从第 k 阶段的状态 k s 出发采用最优策略 * pk ,n 到过程终止时的最佳效 益值,于是有下面的关系式： k f （ k s ）＝Vk ,n （ k s ， * pk ,n ）＝optVk ,n ( k s , Pk ,n ) 其中,opt 全称 optimization 即最优化，在最大化时用 max,在最小化时用 min。 k f （ k s ）也称作 k 阶段从状态 k s 出发时的后部子过程的最佳效益值, 当 k=1 时, ( ) 1 1 f s 就是从初始状态 s1 到全过程结束的整体最优指标函数。 在例 5.1 中,指标函数就是距离。如在第 2 阶段,状态为 B2 时,V2，4(B2) 就表示从 B2 到 E 的可能距离，f2(B2)则表示从 B2 到 E 的最短距离。本问 题的总目标是求 f1(A),即从 A 到 E 的最短距离
5.1.3最短路径问题的动态规划 为了求出例5.1的最短路线,一个简单的方法是,可以求出 所有从A到E的可能走法的路长并加以比较。不难知道,从A到 E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要 求出最最短路线需做54次加法运算和17次比较运算,这叫做穷 举法。不难理解,当问题的段数很多,各段的状态也很多时这 种方法的计算量会大大增加,甚至使得寻优成为不可能。 下面应用动态规划方法求解例5.1。为了获得每一个后部 子过程的最佳效益值只能运用逆序递推方法求解即由最后 段到第一段逐步求出各点到终点的最短路线最后求出A点到E 点的最短路线。运用逆序递推方法的好处是可以始终盯住目 标不致脱离最终目标。例5.1是一个四阶段决策问题,一般可 分为四步: 第一步,从k-4开始状态变量S可取两种状态D1D2,它们到E点 的距离分别为4和3,这也就是由D和D2到终点E的最短距离 即f4(D1)=4,f(D2)=3 2021/2/24 9
2021/2/24 9 为了求出例5.1的最短路线,一个简单的方法是,可以求出 所有从A到E的可能走法的路长并加以比较。不难知道,从A到 E共有18条不同的路线,每条路线有四个阶段,要做3次加法,要 求出最最短路线需做54次加法运算和17次比较运算,这叫做穷 举法。不难理解,当问题的段数很多,各段的状态也很多时,这 种方法的计算量会大大增加,甚至使得寻优成为不可能。 下面应用动态规划方法求解例5.1。为了获得每一个后部 子过程的最佳效益值,只能运用逆序递推方法求解,即由最后一 段到第一段逐步求出各点到终点的最短路线,最后求出A点到E 点的最短路线。运用逆序递推方法的好处是可以始终盯住目 标,不致脱离最终目标。例5.1是一个四阶段决策问题,一般可 分为四步： 第一步,从k=4开始,状态变量s4可取两种状态D1 ,D2 ,它们到E点 的距离分别为4和3,这也就是由D1和D2到终点E 的最短距离 即 f4 (D1 )=4, f4 (D2 )=3。 5.1.3 最短路径问题的动态规划
第二步,k=3,状态变量s3可取3个值即C1,C2和C3,这是需经过一个 中间站才能到达终点E的二级决策间题为方便应用,规定用ds,U)表 示由状态Sk出发,采用决策Uk到达下一阶段Sk1时的两点距离。显然从C1 到E有两条路线需加以比较,取其中最短的,即: f 3(Cl)=min d(C1,D)+f(D)3+4 ld(ci d,)+f(d - min =7 5+3 这说明,由C1到E的最短距离为7,其路径为以C1→D1→E,相应的决策 为U3(C1)=D1 5,(C,)-min1 ∫d(C2,D)+f4(D)6+4 -min d(C2,D2)+f4(D2) 2+3 即从C2到E的最短距离为5,其路径为C2→D2→E,相应的决策为 U3(C2)=D 2021/2/24 10
2021/2/24 10 第二步,k=3, 状态变量 s3 可取 3 个值即 C1,C2 和 C3,这是需经过一个 中间站才能到达终点 E 的二级决策问题。为方便应用，规定用 d( k s ,Uk )表 示由状态 k s 出发,采用决策U k 到达下一阶段 k+1 s 时的两点距离。显然从 C1 到 E 有两条路线需加以比较,取其中最短的,即： 3 f （C1）＝min + + ( , ) ( ) ( , ) ( ) 1 2 4 2 1 1 4 1 d C D f D d C D f D =min + + 5 3 3 4 =7 这说明,由C1 到 E 的最短距离为 7,其路径为以C1 → D1 →E,相应的决策 为 * U3 （C1）= D1 3 f （C2 ）＝min + + ( , ) ( ) ( , ) ( ) 2 2 4 2 2 1 4 1 d C D f D d C D f D =min + + 2 3 6 4 =5 即从 C2 到 E 的最短距离为 5,其路径为C2 → D2 →E,相应的决策为 * U3 （C2 ）= D2
