CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第五章动态规划 不要过河拆桥
©管理与人文学院 忻展红 1999，4 第五章 动态规划 不要过河拆桥
动态规划 Dynamic programming 五十年代贝尔曼(B.E. Bellman)为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理,可归结为一个递推公式 51动态规划的最优化原理及其算法23 511求解多阶段决策过程的方法 例5.1.1最短路问题
2 动态规划 Dynamic programming • 五十年代贝尔曼(B. E. Bellman)为代表的研究成果 • 属于现代控制理论的一部分 • 以长远利益为目标的一系列决策 • 最优化原理，可归结为一个递推公式 5.1 动态规划的最优化原理及其算法 5.1.1 求解多阶段决策过程的方法 例5.1.1 最短路问题 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2
决策树法 可以枚举出20条路径,其中最短的路径长度为16
3 决策树法 A C E H I I F J I F D G J J K 可以枚举出20条路径，其中最短的路径长度为16
例5.1.1最短路题 表现为明显的阶段性 一条从A到B的最短路径 中的任何一段都是最短的 3 10 设S表示由点到B点的最短路 径的长度 则有S4=min dac +sc AD+S 8 因此我们可以从B向回搜索最短路 标记法 6 °如何找出最短路径 最优性原理 最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关6⊥54⊥3121阶 而与如何达到这一状态无关
4 例5.1.1 最短路问题 • 表现为明显的阶段性 • 一条从A 到B 的最短路径 中的任何一段都是最短的 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 最优性原理 “最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关， 而与如何达到这一状态无关 + + = AD D AC C A i d S d S S S i B 则有 min 径的长度 设 表示由 点到 点的最短路 •因此我们可以从B向回搜索最短路 •标记法 •如何找出最短路径
512动态规划的基本概念及递推公式 状态(每阶段初始的出发点) 最短路问题中,各个节点就是状态 生产库存问题中,库存量是状态 物资分配问题中,剩余的物资量是状态 控制变量(决策变量) 最短路问题中,走哪条路 生产库存问题中,各阶段的产品生产量 物资分配问题中,分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推,所以阶段的编号也是逆向的 当然也可以正向递推
5 5.1.2 动态规划的基本概念及递推公式 • 状态(每阶段初始的出发点) – 最短路问题中，各个节点就是状态 – 生产库存问题中，库存量是状态 – 物资分配问题中，剩余的物资量是状态 • 控制变量(决策变量) – 最短路问题中，走哪条路 – 生产库存问题中，各阶段的产品生产量 – 物资分配问题中，分配给每个地区的物资量 • 阶段的编号与递推的方向 – 一般采用反向递推，所以阶段的编号也是逆向的 – 当然也可以正向递推
动态规划的步骤 1、确定问颕的阶段和编号 2、确定状态变量 用Sk表示第k阶段的状态变量及其值 3、确定决策变量 用xk表示第k阶段的决策变量,并以xk°表示该阶段的最优 决策 4、状态转移方程 sk1=g(Sx)反向编号s+1=g(S,x)正向编号 5、直接效果 直接一步转移的效果dA(S,x) 6、总效果函数 指某阶段某状态下到终端状态的总效果,它是一个递推公式 fK(Sk,xk)=h(dk(sk,xk),fk-sk-ixk-)
6 动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量 – 用 Sk 表示第 k 阶段的状态变量及其值 3、确定决策变量 – 用 xk 表示第 k 阶段的决策变量，并以 xk *表示该阶段的最优 决策 4、状态转移方程 sk-1= g(sk , xk ) 反向编号 sk+1= g(sk , xk ) 正向编号 5、直接效果 – 直接一步转移的效果 dk (sk , xk ) 6、总效果函数 – 指某阶段某状态下到终端状态的总效果，它是一个递推公式 ( , ) ( ( , ), ( , )) 1 1 1 k k k = k k k k k− k− k− f s x h d s x f s x
动态规划的步骤 hk是一般表达形式,求当前阶段当前状态下的阶段最优 总效果 (1)如最短路问题,是累加飛式,此时有 fE(SE, *i)=mind (Sk, *R)+R&(Sk1, *RDI dk(sk, xk)+fr(g(sk, xk),xki 终端的边际效果一般为f(S0,x)=0 (2)如串联系统可靠性问题,是连乘形式,此时有 fE(k, *R)=max, (Sk,*k).fR(SkI, *gl fri(a(sk,xk),xki 终端的边际效果一般为f6(s0x0)=1 从第1阶段开始,利用边际效果和边界条件,可以递推到最后 阶段
7 动态规划的步骤 – hk 是一般表达形式，求当前阶段当前状态下的阶段最优 总效果 (1) 如最短路问题，是累加形式，此时有 终端的边际效果一般为 f0 (s0 , x0 )=0 (2)如串联系统可靠性问题，是连乘形式，此时有 终端的边际效果一般为 f0 (s0 ,x0 )=1 从第1阶段开始，利用边际效果和边界条件，可以递推到最后 阶段
52动态规划模型举例 521产品生产计划安排问题 例1某工厂生产某种产品的月生产能力为10件,已知今后四个月 的产品成本及销售量如表所示。如果本月产量超过销售量时,可 以存储起来备以后各月销售,一件产品的月存储费为2元,试安排 月生产计划并做到: 1、保证满足每月的销售量,并规定计划期初和期末库存为零 2、在生产能力允许范围内,安排每月生产量计划使产品总成本 (即生产费用加存储费)最低。 月份阶段产品成本月销售量月初库存月末库存 ck/件 Jk k-1 4 70 6 S4=0 2 3 72 7 3 2 80 12 76 6 S=0
8 5.2 动态规划模型举例 5.2.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件，已知今后四个月 的产品成本及销售量如表所示。如果本月产量超过销售量时，可 以存储起来备以后各月销售，一件产品的月存储费为2元，试安排 月生产计划并做到： 1、保证满足每月的销售量，并规定计划期初和期末库存为零； 2、在生产能力允许范围内，安排每月生产量计划使产品总成本 (即生产费用加存储费)最低
例1产品生产计划安排 设x为第k阶段生产量,则有直接成本 dk(sk, xk=CKxk+2Sk 状态转移公式为 Str 总成本递推公式 (s,x)=mn(,x)+1(1,x1 第一阶段:(即第4月份) 由边界条件和状态转移方程s0=s1+x1-y1=s1+x1-6=0得 s1+x=6或x1=6-s120 估计第一阶段,即第4月份初库存的可能状态: 0≤s1≤30-6-7-12=5,所以,s1∈[0,5
9 例1 产品生产计划安排 • 设xk为第k阶段生产量，则有直接成本 dk (sk , xk )= ck xk+2sk • 状态转移公式为 sk-1= sk+ xk - yk • 总成本递推公式 第一阶段：(即第4月份) 由边界条件和状态转移方程 s0=s1+x1−y1= s1+x1−6=0 得 s1+x1= 6 或 x1= 6−s10 估计第一阶段，即第4月份初库存的可能状态： 0 s1 30−6−7−12=5，所以， s1 [0,5]
第一阶段最优决策表 第二阶段:最大可能库存量7件 f1(S1,x1) 由状态转移方程:s1=2+x2-1220及 s—012345 6 456 382 x2≤10,可知s2∈[12,7],minx2=5 5432 308 白阶段效果递推公式有: 234 f2(2,10)=d2(2,10)+f12(0,6) 160 =2×2+80×10+456=1260 86 得第二阶段最优决策表,如下 5 6 8 910|x2*|f2(S2yx2) 1260*101260 23456 18211891182 110411011681104 1026510321038^104471026 948×9549609669726948 78708768828888949005 870 s1=0s1=1s1=2s1=3s1=4s1
10 第一阶段最优决策表 s1 x1 f1 (s1 , x1 ) 0 6 456 1 5 382 2 4 308 3 3 234 4 2 160 5 1 8 6 第二阶段：最大可能库存量 7 件 由状态转移方程： s1=s2+x2−120 及 x210，可知 s2[2,7]，min x2=5 由阶段效果递推公式有： f2 (2,10)=d2 (2,10)+f1*(0,6) =22+8010+456=1260 得第二阶段最优决策表，如下 s2 x2 5 6 7 8 9 1 0 x2 * f2 (s2 ,x2 * ) 2 1260* 1 0 1260 3 1182* 1188 9 1182 4 1104* 1110 1116 8 1104 5 1026* 1032 1038 1044 7 1026 6 948* 954 960 966 972 6 948 7 870* 876 882 888 894 900 5 870 s1 = 0 s1 = 1 s1 = 2 s1 = 3 s1 = 4 s1 = 5