运筹学16动态规划4

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

1、第二节生产与存贮问题所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为n个阶段，已知最初库存量为x1，阶段市场的需求为dk，生产的固定成本为K，单位产品的消耗费用为L，单位产品的阶段库存费用为h，仓库容量为M，阶段生产能力为B。问如何安排各阶段产量，使计划周期内的费用总和最小。状态变量xk选为阶段k的初始库存量，x1已知，x

2、n+1=0。阶段k的库存量即不能超过库存容量M，也不能超过阶段k至阶段n的需求总量，即决策变量uk选为阶段k的产量。阶段产量必须不超过生产能力和第k阶段到第n阶段的总需求减去第k阶段初的库存量，同时要大于该阶段的需求和库存量之差，即状态转移方程为阶段费用为阶段生产费用和库存费用之和，即阶段k的生产费用k阶段末的库存费用动态规划基本方程例已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0（计划周期末的库存量为0），B=6，d1=3，d2=4，d3=3，求解生产与库存问题。解：利用上述的递推方程得若若

3、若若则则则则当时x4=x3+u3-d3=0当时若若则则结果见下表：时是唯一确定的，因此最优决策为最优路线为{1，0，0，0}最优目标函数值为42。x2=u1-2=0x3=x2+u2-d2=0+4-4=0个人、单位等随时均有设备更新问题。随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。第三节：设备更新问题设备更新问题（以一台机器为例

4、）：n为设备的计划使用年数。Ik(t)为第k年（阶段）机器役龄为t年的一台机器运行（再使用一年）所得的收入。Ok(t)为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。Ck(t)为第k年机器役龄为t年的一台机器更新时所需要的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。为折扣因子，表示一年以后的收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？建立动态规划模型如下：阶段k（k=1，2，…，n）表示计划

5、使用该设备的年限数。状态变量sk：第k年初，设备已使用过的年数，即役龄。决策变量xk：是第k年初更新（Replacement），还是保留使用（Keep）旧设备，分别用K，R表示。状态转移方程为：阶段效益为：最优指标函数fk(sk)：表示第k年初，一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为实际上例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）（单位：万元）解：n=5状态变量s5可取1，2，3，4例：设某台新设备的年效益及年均

6、维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）卖掉役龄2年的设备，买入新设备的更新费用状态变量s4可取1，2，3此时s3可取1或2由于状态s2只能取1，所以有由于状态s1只能取0，所以有上述过程递推回去，当x*1(0)=K，由状态转移方程本例的最优策略是{K，R，R，R，K}，即第一年初购买的设备到第二、三、四年初各更换一次，用到第五年年末，总效益为17万元。s2=1，查f2(1)得x*2=Rs3=1，查f3(1)得x*3=Rs4=1，查f4(1)得x*4=Rs5=1，查f

7、5(1)得x*5=K