第5章动态规划 ●●●● ●●。●● 2021/28
2021/2/8 第5章 动态规划
51一般方法 ●●●●● ●●●● 1.多阶段决策问题 ●●0 ●●● ●●●● 多阶段决策过程:问题的活动过程分为着千相互联 系的阶段,任一阶段以后的行为仅依赖于逊阶段的过程状 态,而与阶段之前的过程如何达到这种状态的方式无关。 在每一个阶段都要做出决策,这一系列的决策称为多阶 段决策过程( multistep decision process)。 最优化问题:问题的每一阶段可能有多种可供选择的 决策,必须从中选择二种决策。各阶段的决策构成一个 决策序列。决策序列不同,所导致的问题的结果可能不 多阶段决策的最优化问题就是:求能够获得问题最优 解决策序列——最优决策序列
2021/2/8 1. 多阶段决策问题 多阶段决策过程：问题的活动过程分为若干相互联 系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状 态，而与i阶段之前的过程如何达到这种状态的方式无关。 在每一个阶段都要做出决策，这一系列的决策称为多阶 段决策过程(multistep decision process) 。 最优化问题：问题的每一阶段可能有多种可供选择的 决策，必须从中选择一种决策。各阶段的决策构成一个 决策序列。决策序列不同，所导致的问题的结果可能不 同。 多阶段决策的最优化问题就是：求能够获得问题最优 解的决策序列——最优决策序列。 云图 V1 V2 云图 V ... 云图 N 5.1 一般方法
2.多阶段决策过程的求解策略 ●●●●● ●●●● ●●0 1)枚举法:穷举可能的决策序列,从中选取可以获得最优解的决策。 序列 2)动态规划 20世纪50年代初美国数学家 RBEllman等人在研究多阶段决策过 程的优化问题时,提出了著名的最优化原理( principle of optimality), 把多阶段过程转化为一系列单阶段问题,创立了解决这类过程优化问 题的新方法—动态规划。 动态规划( dynamic programming)是运筹学的一个分支,是求解 决策过程( decision process)最优化的数学方法。 应用领域:动态规划问世以来,在经济管理、生产调度、工程技术 和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资 源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方 法求解更为方便。 2021/2/8
2021/2/8 2. 多阶段决策过程的求解策略 1）枚举法：穷举可能的决策序列，从中选取可以获得最优解的决策 序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过 程的优化问题时，提出了著名的最优化原理(principle of optimality)， 把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问 题的新方法——动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解 决策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技术 和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资 源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方 法求解更为方便
●●●●● 3.最优性原理 Principle of Optimality) ●●● 过程的最优决策序列具有如下性质:无论过程的。 初始状态和初始决策是什么,其余的决策都必须相对 于初始决策所产生的状态构成一个最优决策序列 利用动态规划求解问题的前提 1)证明问题满足最优性原理 如果对所求解问题证明满足最优性原理,则说明用 动态规划方法有可能解决该问题 2)获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键, 2021/28
2021/2/8 3. 最优性原理(Principle of Optimality) 过程的最优决策序列具有如下性质：无论过程的 初始状态和初始决策是什么，其余的决策都必须相对 于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用 动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键
例51[多段图问题]多段图G=(vE是一个有向图,且具有特:°° 性 ●●0 ●●●● 结点:结点集V被分成k≥2个不相交的集合V 1≤i≤k 其中V1和V分别只有一个结点s(源点)和t(汇点) 每一集合V定义图中的一段。 边:所有的边(u,V)均具有如下性质:若∈E 则该边将是从某段指向+1段,即若u∈V1,则v∈V1+y ≤i≤k-1 每条边(u,v)均附有成本c(u,v)。 s到t的路径:从第1段开始,至第2段、第3段、…、最后 在第k段终止。路径的成本是这条路径上边的成本和。 多段图问题:求由s到t的最小成本路径
2021/2/8 例5.1 [多段图问题]多段图G=(V,E)是一个有向图，且具有特 性: 结点：结点集V被分成k≥2个不相交的集合Vi， 1≤i≤k， 其中V1和Vk分别只有一个结点s(源点)和t(汇点) · 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若∈E， 则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1, 1≤i≤k－1。 · 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段、…、最后 在第k段终止。路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径
●●●●● ●●●● ●●0 ●●● ●●● 2 5 (2 6 9 3 7 3 2 3 7 10 12 611 5 5段图 2021/28
2021/2/8 1 2345 678 9 10 11 12 9732 4 2 2 7 11 11 8 1 4 563 5 6 425 V 1 V 2 V 3 V 4 V 5 5段图
●●● 多段图问题的多阶段决策过程:生成从s到t的最小成本路8。 径是在k-2个阶段(除s和t外)进行某种决策的过程:从s开始,·。。 第i次决策决定V(1sisk-2)中的哪个结点在从s到t的最短路径 上。 最优性原理对多段图问题成立 假设s,v2V3,k1,t是一条由s到t的最短路径。 ●初始状态:s ●初始决策:(s,v2),v2∈V2 ●初始决策产生的状态:V2 则,其余的决策: 35·k1 相对于v2将构成一个最优决策 序列——最优性原理成立 反证:若不然,设v2q3,…,q1t是一条由v2到t的更短的路 径,则s,v2q3,qk1t将是比s,V2V3y,vk1t更短的从s到t的 路径。与假设矛盾。 故,最优性原理成立
2021/2/8 多段图问题的多阶段决策过程：生成从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的 路径。与假设矛盾。 故，最优性原理成立
●●●●● ●●●● 例52[01背包问题]KNAP(jX) ●●0 ●●● ●●●● 目标函数:∑Px I0.1>01≤1≤j 0/1背包问题:KNAP(1,n,M) 2021/2/8
2021/2/8 ⚫例5.2[0/1背包问题] KNAP(l,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 或
最优性原理对0M背包问题成立: ●●●●● ●●●● ●●0 设y1y2;yn是x12x2…,xn的0/值最优序列。 ●●● ●●●● 若y1=0,KNAP(2n,M是初始决策产生的状态。则y2,yn 相对于KNAP(2n,M)将构成一个最优序列。否则,y1y2,yn将 不是KNAP(1,n,M)的最优解 若y1=1,KNAP(2n,M-w是初始决策产生的状态。则 y2,yn相对于KNAP(2,n,MW1)将构成一个最优序列。 否则,设存在另一01序列z1z2…,zn,使得 2;≤M-W 且 11y < 2≤i<1 则序列y1z2…,zn将是一个对于KNAP(1n,M)具有更大效益 值的序列,与假设矛盾 故,最优性原理成立 2021/28
2021/2/8 最优性原理对0/1背包问题成立： 设y1 ,y2 ,…,yn是x1 ,x2 ,…,xn的0/1值最优序列。 若y1＝0, KNAP(2,n,M)是初始决策产生的状态。则y2 ,…,yn 相对于KNAP(2,n,M)将构成一个最优序列。否则，y1 ,y2 ,…,yn将 不是KNAP(1,n,M)的最优解 若y1＝1, KNAP(2,n,M－w1 )是初始决策产生的状态。则 y2 ,…,yn相对于KNAP(2,n,M－w1 )将构成一个最优序列。 否则，设存在另一0/1序列z1 ,z2 ,…,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.动态规划模型的基本要素 ● 0● 个多阶段决策过程最优化问题的动态规划模型通常包含以下 要素: 1阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序 或空间特征来划分阶段,以便按阶段的次序解优化问题。阶段 变量一般用k=1,2,,n表示。 2021/28
2021/2/8 4. 动态规划模型的基本要素 一个多阶段决策过程最优化问题的动态规划模型通常包含以下 要素： 1) 阶段 阶段(step)是对整个过程的自然划分。通常根据时间顺序 或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段 变量一般用k=1,2,..,n表示