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