离散随机性动态规划模型求解

,2010,年,5,月,管理工程学院,运筹学,*,第四节 离散随机性动态规划模型求解,掌握离散随机性动态规划模型的求解,1,一、随机性动态规划基本结构,2,二、基本方程,(8.14),其中,E,表示括弧内数量的期望值。,3,例,5,：,某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担,1500,元的赔偿费。据有经验的技术人员估计，试制时每投产一台合格概率为,1/3,，投产一批的准备结束费用为,250,元，每台试制费用为,100,元。若投产一批后全部不合格，可再投一批试制，但每投一批周期需一个月。要求确定每批投产多少台，使总试制费用,(,包括,可能发生的赔偿损失,),的期望值最小。,4,解：,(1),合同期为三个月，投产一批的周期为一个月，故可将整个合同期划分为三个阶段。,(2),状态变量,s,k,。假定尚没一台合格品时,s,k,=1,，已得到一台以上合格品时,s,k,=0,。故签订合同时只有一种情况,s,1,=1,。,(3),决策变量,x,k,为每个阶段的投产试制台数,D,k,(,s,k,)=1,2,N,(,当,s,k,=1,时,),D,k,(,s,k,)=0 (,当,s,k,=0,时,),。,5,(4),状态转移律为：,(8.15),(5),第,k,阶段的费用支出为,c,(,u,k,),，有,6,(6),设,f,k,(,s,k,),为从状态,s,k,、决策,x,k,出发的,k,阶段以后的最小期望费用。因有,f,k,(0)=0,，故有,(8.16),7,当,k,=3,时，,表,8-10,x,3,s,3,c,(,x,3,)+(2/3) 1500,f,3,(,s,3,),x,3,*,0,1,2,3,4,5,0,1,0,1500,1350,1117,994,946,948,0,946,0,4,8,当,k,=2,时，,表,8-11,x,2,s,2,c,(,x,2,)+(2/3) 946,f,2,(,s,2,),x,2,*,0,1,2,3,4,0,1,0,946,981,870,830,837,0,830,0,3,当,k,=2,时，,表,8-11,9,x,1,s,1,c,(,x,1,)+(2/3) 830,f,1,(,s,1,),x,1,*,0,1,2,3,4,1,830,903,819,796,814,796,3,当,k,=1,时，,表,8-12,该公司的最优决策为第一批投产,3,台；如果无合格品，第二批再投产,3,台；如果仍全部不合格，第三批投产,4,台。这样使总的期望研制费用,(,包括三批均不合格时的赔偿费,),为最小，共计,796,元。,10,