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

《运筹学》1第四节离散随机性动态规划模型求解◆掌握离散随机性动态规划模型的求解《运筹学》2一、随机性动态规划基本结构《运筹学》3二、基本方程11,maxkkkksDxkksfxsvEsfkkk(8.14)其中E{·}表示括弧内数量的期望值。《运筹学》4例6：某公司承担一种新产品试制任务，合同要求三个月内交出一台合格的样品，否则将负担1500元的赔偿费。据有经验的技术人员估计，试制时每投产一台合格概率为1/3，投产一批的准备结束费用为250元，每台试制费用为100元。若投产一批后全部不合格，可再投一批试制，但每投一批周期需一个月。要求确定每批投产多少台，使总试制费用(包括可能发生的赔偿损失)的期望值最小。《运筹学》5解：(1)合同期为三个月，投产一批的周期为一个月，作为一个阶段。故可将整个合同期划分为三个阶段。(2)状态变量sk。假定尚没一台合格品时sk=1，已得到一台以上合格品时sk=0。故签订合同时只有一种情况s1=1。(3)决策变量xk为每个阶段的投产试制台数Dk(sk)={1,2,…,N}(当sk=1时)Dk(sk)={0}(当sk=0时)。《运筹学》6(4)状态转移律为：(8.14)000100250kkkkxxxxc(5)第k阶段的费用支出为c(uk)，有(8.15)《运筹学》7(6)设fk(sk)为从状态sk、决策xk出发的k阶段以后的最小期望费用。因有fk(0)=0，故有132min0321132min1111kxksDxkxkxksDxkfxcffxcfkkkkkkkkk(8.16)《运筹学》8的意义为第四个月初仍未得到一件合格产品，因按合同需要赔偿1500元，故有。当k=3时，,0)1(3f)1(32)(min)1(43)(3333fxcfxxDx)1(4f1500)1(4f《运筹学》9当k=3时，表8-8x3s3c(x3)+(2/3)x3×1500f3(s3)x3*012345010150013501117994946948094604《运筹学》10当k=2时，x2s2c(x2)+(2/3)x2×946f2(s2)x2*01234010946981870830837083003当k=2时，表8-9《运筹学》11x1s1c(x1)+(2/3)x1×830f1(s1)x1*0123418309038197968147963当k=1时，表8-10◆该公司的最优决策为第一批投产3台；如果无合格品，第二批再投产3台；如果仍全部不合格，第三批投产4台。这样使总的期望研制费用(包括三批均不合格时的赔偿费)为最小，共计796元。