运筹学15-动态规划III-11幻灯片课件.ppt

第15讲 动态规划III 本讲提纲 1. 可靠性问题 2. 设备更新问题 3. 随机采购问题 1. 可靠性问题 问题的一般提法： 某工作系统由n个部件串联而成，部件i(i=1,2,...,n)上装有xi个备用元件，其正常工作的概率为pi(xi);又设部件i上的一个备用元件的费用为ci，要求总费用不超过C。问应如何安排备用件使系统的可靠性最高？ 系统正常工作的概率(系统的可靠性)： 静态规划的模型为： 例：某厂设计一种电子设备，由三种元件D1，D2、D3组成。已知这三种元件的价格和可靠性如表所示，要求在设计中所使用元件的费用不超过105元。试问应如何设计使设备的可靠性达到最大。 元件 单位/元（Ck） 可靠性(Pk) D1 30 0.9 D2 15 0.8 D3 20 0.5 2. 设备更新问题 企业中经常会遇到一台设备应该使用多少年更新最合算的问题。一般来说，一台设备在比较新时，年运转量大，经济收入高，故障少，维修费用少，但随着使用年限的增加，年运转量减少因而收入减少，故障变多，维修费用增加。如果更新可提高年净收入，但是当年要支出一笔数额较大的购买费。 设备更新问题的一般提法： 已知一台役龄为t的设备，即该设备已使用过t年，该设备投入运行一年带来的收入额为r(t), 但同时须付出的维修费用为u(t)，若卖掉该役龄为t的设备，可获得的折价费为c(t)，购入一台新设备的费用为p。要求：在n年内每年年初做出决策，是使用旧设备还是更换一台新设备，使n年的总效益最大。 例：设某台设备的年收益、年维修费用、新设备购入费以及旧设备折价费如下表所示。试确定今后5年的最优更新策略，使总效益最大。 役龄 0 1 2 3 4 5 收益r(t) 5 4.5 4 3.75 3 2.5 维修费u(t) 0.5 1 1.5 2 2.5 3 新设备购入费p 10 10 10 10 10 10 折价费c(t) 9.5 8.5 7.8 7.5 7 6.5 3. 随机采购问题 某公司打算在5周内采购一批原料，未来5周内的原料的价格有三种，这些价格的出现概率可以估计，如下表。该部分由于生产需要，必须在5周内采购这批原料。如果第一周价格很高，可以等到第2周；同样的，第2周如果仍对价格不满意，可以等到第3周；类似地，未来几周都可能选择购买或者等待，但必须保证第5周时采购了该原料。试问该选择哪种采购方案，才能使得采购费用最小？ 价格 概率 500 0.3 600 0.3 700 0.4 解：建立动态规划模型 阶段：将采购期限5周依次分为5个阶段，k=1,2,3,4,5 状态变量：第k周原料的实际价格，sk 决策变量：xk表示第k周是否采购的0-1变量，若选择采购，则xk=1，若选择等待，则xk=0 SkE表示第k周决定等待，而在以后采取最优策略时采购价格的期望值(即第k周选择等待的代价)。 最优指标函数：fk(sk)表示第k周实际价格为sk时，从第k周至第5周采取最优策略所花费的最小期望价格。 k =5： 因为如果前4周都没有买，那第5周必须购买，因此有 f5(s5)=s5，即f5(500)=500；f5(600)=600；f5(700)=700。 k =4：