动态规划(完整)学习课件.ppt

k = 1:s2 = s1 –c1 x1 因此得到： x1 = 1 ,s2=120-30=90, x2 = 2 ,s3=90-2*15=60 , x3 = 3 即：p={1，2，3} 可靠性为0.756 * 4、生产调度（生产与库存）问题 某厂根据市场预测，确认今后4个月该厂的一种主要产品每月的需求的量d为3，2，3，2万件。已知每月生产固定费用b为2千元，但若当月不生产则为0；产品成本c为1千元/件，贮存费用h为 0.2千元/万件/月。最大存贮能力w为4万件。若第1月初五库存产品，第4月末也不留库存，则该厂怎样安排生产，才能使今后4个月的总费用最少？ * 建立动态规划模型： 1、阶段与时间相联系, 阶段 k表示月份 2、状态变量 sk 表示 k 月初的库存量; 3、决策变量 xk 表示 k月的产量; 4、若dk为需求量，则状态转移方程: sk+1 = sk +xk-dk; 5、阶段函数: vk(sk,xk)为k月的生产费用 ， 过程函数： fk(sk)为从第一月到第k月的总生产费用 fk(sk)=max{ vk(sk,xk)+fk+1(sk+1)} 6. 基本状态方程 * k=4 这是最后一个月，需求为2，无库存s5=0。由状态方程知：s4=2-x4,x4?0,则s4只能是0，1，2 * k=3 这是第3个月，需求为3。由状态方程知：s4=s3+x3-3,又由于 2? s4 ? 0,即2? s3+x3-3 ? 0,s3 ≤ w=4则s3取值是0,1，2，3，4。X3={x3|3≤s3+x3≤5,s3=0,1,2,3,4} * k=2 这是第2个月，需求为2。第一个月无库存s1=0，s2 =s1+x1-3=x1-3，又因x1 ≤5，则s2取值是0，1，2。由状态方程知：s3=s2+x2-2,又由于 4? s3 ? 0,即4? s2+x2-2 ? 0; X2={x2|2≤s2+x2≤6且x2 ≤5,s2=0,1,2} * k=1 这是第1个月，需求为3。第一个月无库存s1=0，s2 =x1-3=x1-3，又因x1 ≤5，s2取值是0，1，2。X1={x1|3≤x1≤5} * 5 设备更新问题 设备在使用全过程中会遭受磨损, 使用一段时间后就要维修, 而且使用的时间越长, 维修费用越高, 设备使用多少时间在经济上最合算, 就是设备更新问题。 * 例: 某设备的年效益和年均维修费用如下表, 如何在未来的5年内进行更新决策。 使用年限 0 1 2 3 4 效益 r 5 4.5 4 3.75 3 维修费u 0.5 1 1.5 2 2.5 更新费c 0.5 1.5 2.2 2.5 3 * 分析： 阶段 k = 1, 2, 3, 4, 5; sk 表示 k 年初设备已使用的年限; xk 为 k 年初决定设备是继续使用还是更新的决策变量: xk = 1表示继续使用, xk = 0表示更新; 状态转移方程: sk+1 = sk + 1，xk=1; sk+1 = 1，xk=0 * 阶段函数: vk(sk) = r(skxk) - u(skxk) - c(sk)(1-xk ) r(0) - u(0) - c(sk) (xk= 0) vk(sk) = r(sk) - u(sk ) (xk= 1) 递推函数: fk(sk) = max{vk(sk) + fk+1(sk+1)} * k = 5 状态变量 s5 可取 1, 2, 3, 4 f5(1) = maxx1=0,1{r(0) - u(0) - c(1), r(1) - u(1)} = max {5-0.5-1.5, 4.5-1}= 3.5 (x5*=1) f5(2)=max{5-0.5-2.2, 4-1.5}= 2.5 (x5*=1) f5(3)=max{5-0.5-2.5, 3.75-2}= 2 (x5*=0) f5(4)=max{5-0.5-3, 3-2.5} = 1.5 (x5*=0) * k = 4 状态变量 s4 可取 1, 2, 3 f4(1) = max{r(0)-u(0)-c(1)+f5(1), r(1)-u(1)+ f5(2)}