十动态规划的应用-生产与存储,设备更新问题

生产与存贮问题

生产周期分为n个阶段，已知最初库存量：x1

阶段市场的需求：dk

生产的固定成本：K单位产品的消耗费用：L

单位产品的阶段库存费用：h仓库容量：M

阶段生产能力为B

一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。

问如何安排各阶段产量，使计划周期内的费用总和最小。不能超过阶段k至阶段n的需求总量xkdk+dk+1++dn，k=1,2,,n阶段k的初始库存量，x1已知，xn+1=00xkmin{M，dk+dk+1++dn}，（k=1,2,,n）状态变量xk：不能超过库存容量M，决策变量uk：不超过生产能力阶段k

的产量uk

dk+dk+1++dn-xk不小于该阶段的需求和库存量之差，

不超过kn

阶段的总需求减去第k

阶段初的库存量，dk-xk

ukmin{B，dk+dk+1++dn-xk}

状态转移方程为阶段生产费用和库存费用之和，即阶段k的生产费用k阶段末的库存费用动态规划基本方程阶段效益fn+1（xn+1）=0，k=1,2,,ndk-xk

ukmin{B，dk+dk+1++dn-xk}例5

已知n=3，K=8，L=2，h=2，x1=1，M=4，x4=0，B=6，d1=3，d2=4，d3=3，求解生产与库存问题。解：递推方程f4(x4)=0，k=1,2,3当时=8+2(3-x3)=14-2x3仓库容量：4dk-xk

ukmin{B，dk+dk+1++dn-xk}若x3=0,

u*3(0)=3则f3(0)=14若x3=1,则f3(1)=12u*3(1)=2若x3=2,则f3(2)=10u*3(2)=1

若x3=3,则f3(3)=8u*3(0)=0f3(x3)=14-2x3u3=3-x3x3：0～3k=2容量44+3ukdk-xk4-x2

u2min{6,7-x2}

f2(x2)=min{8+2u2+2(x2+u2-4)+f3(x2+u2-4)}4-x2

u2min{B，d2+d3-x2}=min{6,7-x2}0

x2min{M，d2+d3}=min{4,7}=4u*2(0)=4x2=04-x2

u2min{6,7-x2}

x2=1u*2(1)=34-x2

u2min{6,7-x2}

x2=2u*2(2)=24-x2

u2min{6,7-x2}

x2=3u*2(3)=1x2=4u*2(4)=04-x2

u2min{6,7-x2}

结果见下表：k=1f2=302u16x2=x1+u1-d1=1+u1-3=u1-2u*1(1)=2x1=1f3=14最优决策为{1，0，0，0}x2=u1-2=0x3=x2+u2-d2=0+4-4=0最优路线为最优目标函数值为42。（状态变量）u*1(1)=2，u*2(0)=4，u*3(0)=3

设备更新问题提法如下（以一台机器为例）：

n为设备计划使用年数。

Ik(t)为第k年（阶段）机器役龄为t年的一台机器运行（在使用一年）所得的收入。

Ok(t)为第k年机器役龄为t年的一台机器运行（再使用一年）时所需运行的费用（或维修费用）。

Ck(t)为第k年机器役龄为t年的一台机器更新时所需的净费用（处理一台役龄为t的旧设备，买进一台新设备的更新净费用）。

设备更新问题为折扣因子，表示一年以后的收入是上一年的单位。要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？建立动态规划模型如下：

阶段k（k=1，2，…，n）表示计划使用该设备的年限数。

状态变量sk：第k年初，设备已使用过的年数，即役龄。

决策变量xk：是第k年初更新，还是保留使用旧设备，分别用R，K表示。

阶段效益为：

状态转移方程为：

最优指标函数fk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益。实际上例7：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设=1）

动态规划的基本方程为解：n=5状态变量s5可取1，2，3，4

役龄项目012345效益IK(t)54.543.7532.5运行费OK(t)0.511.522.53更新费CK(t)0.51.52.22.533.5单位：万元卖掉役龄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，查f5(1)得x*5=K