动态规划的步骤 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