[高等教育]运筹学3.pptVIP

1 * 第二节 生产与存贮问题 所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。 生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为n个阶段， 已知最初库存量为x1， 阶段市场的需求为dk， 生产的固定成本为K， 单位产品的消耗费用为L， 单位产品的阶段库存费用为h， 仓库容量为M， 阶段最大生产能力为B。 问如何安排各阶段产量，使计划周期内的费用总和最小。 状态变量xk选为阶段k的初始库存量，x1已知，xn+1=0。 阶段k的库存量即不能超过库存容量M，也不能超过阶段k至阶段n的需求总量(因为n+1阶段的库存量为0），即 决策变量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，求解生产与库存问题。 解：利用上述的递推方程得 若 若 若 若 则 则 则 则 当 时 x4=x3+u3-d3=0 当 时 若 若 则 则 结果见下表： 时 是唯一确定的，因此 最优决策为 最优路线为 {1，0，0，0} 最优目标函数值为42。 x2=u1-2=0 x3=x2+u2-d2=0+4-4=0 第三节：设备更新问题 个人、单位等随时均有设备更新问题。自行车、彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。 设备更新问题提法如下（以一台机器为例）： n为计划设备使用年数。 Ik(t) 为第k年（阶段）已经使用过t年的机器再使用一年所得的收入。 Ok(t) 为第k年已经使用过t年的机器再使用一年的维修费用 。 Ck(t) 为第k年卖掉一台已经使用过t年的机器，买进一台新设备的更新净费用。 建立动态规划模型如下： 阶段k（k=1，2，…，n）表示计划使用该设备的年限数。 状态变量sk：第k年初，设备已使用过的年数。 决策变量xk：是第k年初更新（Replacement），还是保留使用（Keep）旧设备，分别用K，R表示。 状态转移方程为： 阶段效益为： ?为折扣因子，表示一年以后的收入是上一年的?单位。 要求在n年内的每年年初作出决策，是继续使用旧设备还是更换一台新的，使n年内总效益最大？ 最优指标函数fk(sk)：表示第k年初，使用一台已用了sk年的设备，到第n年末的最大收益，动态规划的基本方程为 实际上 例：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设?=1） （单位：万元） 解：n=5 状态变量s5可取1，2，3，4 卖掉役龄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=R s3=1，查f3(1)得x*3=R s4=1，查f4(1)得x*4=R s5=1，查f5(1)得x*5=K 动态规划总结 一、动态规划基本概念： 1 阶段：将所给问题的过程，按时间或空间特征分解成若干互 相联系的阶段，用k表示， 2 状态：各阶段开始时的客观条件。 状态变量用sk表示。 状态变量集合用Sk表示。 性质：当某阶段状态给定以后，在这阶段以后的过 成的发展不受这段以前各状态的影响。 3 决策：当各阶段的状态确定以后，可以作出不同的选择，从 而确定下一阶段的状态。这个选择称为决策。