运筹与决策5动态规划

《运筹与决策5动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章动态规划不要过河拆桥动态规划Dynamicprogramming五十年代贝尔曼(B.E.Bellman)为代表的研究成果属于现代控制理论的一部分以长远利益为目标的一系列决策最优化原理，可归结为一个递推公式5.1动态规划的最优化原理及其算法5.1.1求解多阶段决策过程的方法例5.1.1最短路问题决策树法可以枚举出20条路径，其中最短的路径长度为16例5.1.1最短路问题表现为明显的阶段性一条从A到B的最短路径中的任何一段都是最短的最优性原理“最优策略的一部分也是最优的”每步的决策只与相邻阶段状态有关，而与如何达

2、到这一状态无关因此我们可以从B向回搜索最短路标记法如何找出最短路径5.1.2动态规划的基本概念及递推公式状态(每阶段初始的出发点)最短路问题中，各个节点就是状态生产库存问题中，库存量是状态物资分配问题中，剩余的物资量是状态控制变量(决策变量)最短路问题中，走哪条路生产库存问题中，各阶段的产品生产量物资分配问题中，分配给每个地区的物资量阶段的编号与递推的方向一般采用反向递推，所以阶段的编号也是逆向的当然也可以正向递推动态规划的步骤1、确定问题的阶段和编号2、确定状态变量用Sk表示第k阶段的状态变量及其值3、确定决策变

3、量用xk表示第k阶段的决策变量，并以xk*表示该阶段的最优决策4、状态转移方程sk-1=g(sk,xk)反向编号sk+1=g(sk,xk)正向编号5、直接效果直接一步转移的效果dk(sk,xk)6、总效果函数指某阶段某状态下到终端状态的总效果，它是一个递推公式动态规划的步骤hk是一般表达形式，求当前阶段当前状态下的阶段最优总效果(1)如最短路问题，是累加形式，此时有终端的边际效果一般为f0(s0,x0)=0(2)如串联系统可靠性问题，是连乘形式，此时有终端的边际效果一般为f0(s0,x0)=1从第1阶段开始，利用边

4、际效果和边界条件，可以递推到最后阶段5.2动态规划模型举例5.2.1产品生产计划安排问题例1某工厂生产某种产品的月生产能力为10件，已知今后四个月的产品成本及销售量如表所示。如果本月产量超过销售量时，可以存储起来备以后各月销售，一件产品的月存储费为2元，试安排月生产计划并做到：1、保证满足每月的销售量，并规定计划期初和期末库存为零；2、在生产能力允许范围内，安排每月生产量计划使产品总成本(即生产费用加存储费)最低。例1产品生产计划安排设xk为第k阶段生产量，则有直接成本dk(sk,xk)=ckxk+2sk状态转移公

5、式为sk-1=sk+xk-yk总成本递推公式第一阶段：(即第4月份)由边界条件和状态转移方程s0=s1+x1y1=s1+x16=0得s1+x1=6或x1=6s10估计第一阶段，即第4月份初库存的可能状态：0s1306712=5，所以，s1[0,5]第一阶段最优决策表第二阶段：最大可能库存量7件由状态转移方程：s1=s2+x2120及x210，可知s2[2,7]，minx2=5由阶段效果递推公式有：f2(2,10)=d2(2,10)+f1*(0,6)=22+8010+456=1260得

6、第二阶段最优决策表，如下第二阶段最优决策表第三阶段：最大可能库存量4件由状态转移方程：s2=s3+x372及x310，可知s3[0,4]，minx3=5由阶段效果递推公式有：f3(1,10)=d3(1,10)+f2*(4,8)=21+7210+1104=1826得第三阶段最优决策表，如下第三阶段最优决策表第四阶段：初始库存量s4=0由状态转移方程：s3=s4+x460可知x46，由阶段效果递推公式有：f4(0,6)=d4(0,6)+f3*(0,10)=706+1902=2322得第四阶段最优决策

7、表，如下回溯得此表例2生产–库存管理问题(连续变量)设某厂计划全年生产某种产品A。其四个季度的订货量分别为600公斤，700公斤，500公斤和1200公斤。已知生产产品A的生产费用与产品的平方成正比，系数为0.005。厂内有仓库可存放产品，存储费为每公斤每季度1元。求最佳的生产安排使年总成本最小。解：四个季度为四个阶段，采用阶段编号与季度顺序一致。设sk为第k季初的库存量，则边界条件为s1=s5=0设xk为第k季的生产量，设yk为第k季的订货量；sk，xk，yk都取实数，状态转移方程为sk+1=sk+xk-yk仍采

8、用反向递推，但注意阶段编号是正向的目标函数为例2生产–库存管理问题(连续变量)第一步：(第四季度)总效果f4(s4,x4)=0.005x42+s4由边界条件有：s5=s4+x4–y4=0，解得：x4*=1200–s4将x4*代入f4(s4,x4)得：f4*(s4)=0.005(1200–s4)2+s4=7200–11s4+0.005s42第二步：(第三、四季