第四章动态规划 4.1一般方法 1.多阶段决策问题 多阶段决策过程:问题的活动过程分为若干相互联系的阶段,任 阶段i以后的行为仅依赖于i阶段的过程状态,而与i阶段之前的过程如何 达到这种状态的方式无关。在每一个阶段都要做出决策,这决策过程称 为多阶段决策过程( multistep decision process) 最优化问题:问题的每一阶段可能有多种可供选择的决策,必须从 选揉二种决策;各阶段的决策构成一个决策序列。决策序列不同,所 问题的结果可 多阶段决策的最优化问题就是:求能够获得问题最优解的决策序 列—最优决策序列。 2021/2/20
2021/2/20 1 第四章 动态规划 4.1 一般方法 1. 多阶段决策问题 多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一 阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何 达到这种状态的方式无关。在每一个阶段都要做出决策，这决策过程称 为多阶段决策过程(multistep decision process) 。 最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从 中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所 导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策序 列——最优决策序列。 云图 V1 V2 云图 V ... 云图 N
2.多阶段决策过程的求解策略 1)枚举法 穷举可能的决策序列,从中选取可以获得最优解的决策序列 2)动态规划 20世纪50年代初美国数学家 REBellman等人在研究多阶段决策过 程的优化问题时,提出了著名的最优化原理( prIncip| e of optimality), 把多阶段过程转化为一系列单阶段问题,创立了解决这类过程优化问 题的新方法—动态规划。 动态规划( dynamic programming)是运筹学的一个分支,是求解决 策过程( ecision process)最优化的数学方法。 应用领域:动态规划问世以来,在经济管理、生产调度、工程技 术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、 资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它 方法求解更为方便 2021/2/20
2021/2/20 2 2. 多阶段决策过程的求解策略 1）枚举法 穷举可能的决策序列，从中选取可以获得最优解的决策序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过 程的优化问题时，提出了著名的最优化原理(principle of optimality)， 把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问 题的新方法——动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决 策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技 术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、 资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它 方法求解更为方便
3.最优性原理( Principle of optimalit!y) 过程的最优决策序列具有如下性质:无论过程的初始状 态和初始决策是什么,其余的决策都必须相对于初始决策所 产生的状态构成一个最优决策序列 利用动态规划求解问题的前提 1)证明问题满足最优性原理 如果对所求解问题证明满足最优性原理,则说明用动态 规划方法有可能解决该问题 2)获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键 2021/2/20
2021/2/20 3 3. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的初始状 态和初始决策是什么，其余的决策都必须相对于初始决策所 产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态 规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键
例41[多段图问题]多段图G=(V,E)是一个有向图,且具有特性 结点:结点集V被分成k≥2个不相交的集合V,1≤i≤k, 其中V1和V分别只有一个结点:s(源结点)和t(汇点) 段:每一集合V定义图中的一段—一共k段。 边:所有的边(u,v)均具有如下性质:若∈E,则 若u∈V;,则u∈Vi+1,即该边将是从某段i指向i+1段, 1≤i≤k-1。 成本:每条边(u,v)均附有成本c(u,v) s到t的路径:是一条从第1段的源点s出发,依次经过第2段的某 结点v2,,经第3段的某结点v3,、…、最后在第k 段的汇点t结束的路径。 该路径的成本是这条路径上边的成本和。 多段图问题:求由s到t的最小成本路径 2021/2/20
2021/2/20 4 例4.1 [多段图问题]多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k， 其中V1和Vk分别只有一个结点：s(源结点)和t(汇点)。 段： 每一集合Vi定义图中的一段——共k段。 边： 所有的边(u,v)均具有如下性质： 若∈E，则 若u∈Vi，则u∈Vi＋1,即该边将是从某段i指向i+1段， 1≤i≤k－1。 成本：每条边(u,v)均附有成本c(u,v)。 s到t的路径：是一条从第1段的源点s出发，依次经过第2段的某 结点v2,i，经第3段的某结点v3,j、…、最后在第k 段的汇点t结束的路径。 该路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径
V2 4 6 6 5 7 3 2 3 10 12 4 6 8)0→ 11 8 5段图 2021/2/20
2021/2/20 5 1 2345 678 9 10 11 12 9732 4 3 2 7 11 11 8 1 4 563 5 6 425 V 1 V2 V3 V4 V5 5段图
多段图问题的多阶段决策过程:生成从s到t的最小成本路径是 在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,第i次 决策决定Ⅵ1(1≤si≤k2)中的哪个结点在从s到t的最短路径上。 ★最优性原理对多段图问题成立 假设s,v,v3,…,1,t是一条由s到t的最短路径。 ●初始状态:s 即,是V2的3,,kt构成 ●初始决策:(Ss,V2),v2∈V2 从v2至t的最短路径 ●初始决策产生的状态:v2 则,其余的决策 相对于v2将构成一个最优决策序 列—最优性原理成立 反证:若不然,设V2,q3,…,qk1,t是一条由v2到t的更短的路径, 则s,V2,q3,…,qk1,将是比s,v,v3…,k1,埂更短的从s到t的路径。与 假设矛盾。 故,最优性原理成立 2021/2/20
2021/2/20 6 多段图问题的多阶段决策过程：生成从s到t的最小成本路径是 在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次 决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。 ★ 最优性原理对多段图问题成立 假设s,v2 ,v3 ,…,vk-1 ,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2 )， v2∈V2 ● 初始决策产生的状态：v2 则，其余的决策：v3 ,...,vk-1相对于v2将构成一个最优决策序 列——最优性原理成立。 反证：若不然，设v2 ,q3 ,…,qk-1 ,t是一条由v2到t的更短的路径， 则s, v2 ,q3 ,…,qk-1 ,t将是比s,v2 ,v3 ,…,vk-1 ,t更短的从s到t的路径。与 假设矛盾。 故，最优性原理成立 即，是v2 v3 ,...,vk-1 t构成 从v2至t的最短路径
例4.2[0/1背包问题]KNAP(1,X) 日标函数:∑Px 1≤i 约束条件 ∑mx≤X k0,11>0,1≤i≤j 0/1背包间题:KNAP(1,n,M) 2021/2/20
2021/2/20 7 ◼例4.2[0/1背包问题] KNAP(1,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) i j i i p x 1 x p w i j w x X i i i i j i i = 0 1, 0, 0,1 1 或
★最优性原理对01背包问题成立: 设y1,y2yn是x,x2,x的0/1值最优序列。 ●初始状态:KNAP(1n,M) ●初始决策:决定y等于1还是等于0 ★若y1=0,KNAP(2,n-1,M是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M)将构成一个最优序列。否则,y1y2…yn将不是 KNAP(1,n,M)的最优解 ★若y1=1,KNAP(2n-1,MW1)是初始决策产生的状态。则y2yn相 对于KNAP(2n-1,M-W)将构成一个最优序列 如若不然,设存在另一0序列z2,z3,…,z乙n,使得 且∑p,≥∑PB∑mE≤M-m 2≤i≤n 2<i<n 则序列y1,z2,,zn将是一个对于KNAP(1n,M)具有更大效益值得序列。 与假设矛盾 故,最优性原理成立 2021/2/20
2021/2/20 8 ★ 最优性原理对0/1背包问题成立： 设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 ●初始状态： KNAP(1,n,M) ●初始决策：决定y1等于1还是等于0 ★ 若y1＝0, KNAP(2,n-1,M)是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M)将构成一个最优序列。否则，y1 ,y2 ,…,yn将不是 KNAP(1,n,M)的最优解 ★若y1＝1, KNAP(2,n-1,M-w1 )是初始决策产生的状态。则y2 ,…,yn相 对于KNAP(2,n-1,M－w1 )将构成一个最优序列。 如若不然，设存在另一0/1序列z2 ,z3 ,…,zn ,使得 且 则序列y1 ,z2 ,…,zn将是一个对于KNAP(1,n,M)具有更大效益值得序列。 与假设矛盾。 故，最优性原理成立 − i n wi zi M w 2 1 i n i n i i i i p z p y 2 2
4.最优决策序列的表示 设 就一个特定的 ●S0:问题的初始状态 r1,n1而言 ●n次决策:问题需要做nη次决策 ●x:昕阶段的决策值,1≤i≤n 设X1=r1,r1,2,……,r,n}是x可选决策值的集合,S1,n是在选择 决策值r1,n之后所产生的状态——“初始决策”所产生的状态 设1,j1是相应于状态S1,j的最优决策序列。 则,相应于S0的最优决策序列就是{r1iT1,n1≤j1≤p1中最优的 序列,记为 OP7,11,}=I 1≤/1≤P1 2021/2/20
2021/2/20 9 4. 最优决策序列的表示 设 ● S0：问题的初始状态 ● n次决策：问题需要做n次决策 ● xi：i阶段的决策值，1≤i≤n。 设X1={r1,1,r1,2,…,r1,p1}是x1可选决策值的集合，S1,j1是在选择 决策值r1,j1之后所产生的状态——“初始决策”所产生的状态。 设Γ1,j1是相应于状态S1,j1的最优决策序列。 则，相应于S0的最优决策序列就是{r1,j1Γ1,j1|1≤j1≤p1}中最优的 序列，记为 1, 1, 1 1 1 { } 1 1 1 1 = OPT r r j j j p 就一个特定的 r1,j1而言
r 1,2 「 n 1J1 1p1 2021/2/20 10
2021/2/20 10 s0 r1,1 r1,2... r1,p1 sn Γ1,j1 Γ1,1 Γ1,2 Γ1p1