高等教育运筹学课程--动态规划2.pptVIP

动态规划（2） 应用举例 1、建立动态规划模型的一般步骤 1 划分阶段。即按时间和空间的先后顺序适当地划分为满足递推关系的若干个阶段。 2 正确选择状态变量。（可知性和无后效性） 3 根据状态变量和决策变量的含义，正确写出状态转移方程 Sk+1=Tk(sk,uk) 4 明确指标函数Vk.n、最优指标函数fk(sk)及k阶段指标Vk(sk,us)的含义。 5 正确列出最优指标函数的递推关系及边界条件。 2、资源分配问题 所谓分配问题，就是将数量一定的一种或若干种资源（例如原材料，资金，机器设备，劳力，食品等等），恰当地分配给若干个使用者，使效益函数为最优。 (1)资源离散分配问题 多元投资分配问题 设有某种原料，总数量为a，用于生产n种产品。若分配数量xi用于生产第i种产品，其收益为gi(xi),问应如何分配，才能使生产n种产品的总收入最大？ （2）资源连续分配问题 一般问题的提法是： 3、生产与存贮问题 所谓生产与库存问题就是一个生产部门，如何在已知生产成本、库存费用和各阶段市场需求条件下，决定各阶段产量，使计划内的费用总和为最小的问题。很多问题可以化成此类问题来解决。 4、设备更新问题 个人、单位等随时均有设备更新问题。自行车、彩电、设备随着使用年限的增加而设备陈旧，处理价格愈低，因此需要维修和更新的费用增加。处于各种阶段的设备总是面临保留还是更新问题。保留还是更新，应该从整个计划期间的总回收额来考虑，而不能从局部的某个阶段的回收额来考虑，是一个多阶段的决策问题。 5、动态规划总结 一、动态规划基本概念： 1 阶段：将所给问题的过程，按时间或空间特征分 解成若干互相联系的阶段，用k表示， 2 状态：各阶段开始时的客观条件。 状态变量用sk表示。 状态变量集合用Sk表示。 状态性质：当某阶段状态给定以后，在这阶段以 后的过成的发展不受这段以前各状态 的影响。 当 时 当 时 依次类推可得， 相应的 相应的 相应的 因为S1=1000，所以f1(s1)=23700 因此最优策略为 即前两年应在年初把全部完好的机器投入低负荷生产，后三年应在年初把全部完好的机器投入高负荷生产。最高产量为23700（台）。 每年年初的机器状态：S1=1000 S2=0.7u1+0.9(s1-u1)=0.9s1=900 S3= 0.7u2+0.9(s2-u2)=0.9s2=810 S4= 0.7u3+0.9(s3-u3)=0.7s3=567 S5= 0.7u4+0.9(s4-u4)=0.7s4=397 S6= 0.7u5+0.9(s5-u5)=0.7s5=278 练习：每年年初的完好机器数。 作业：如规定在第五年结束时完好机器数为500台，该如何安排生产？ 生产与库存问题本身就是一个多阶段决策过程。设某一生产部门，生产周期分为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年的机器再使用一