管理运筹学--动态规划讲解.ppt

第8章 动态规划 Dynamic Programming 华国伟 北京交通大学物流管理系 内容提要 动态规划产生于20世纪50年代, 美国数学家贝尔曼(R. Bellman)等人提出. 动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种算法.必须对具体问题进行具体分析,运用动态规划的原理和方法,划分阶段,建立相应的模型,然后再去求解. 动态规划是用来解决多阶段决策过程最优化的一种数量方法.其特点在于,它可以把一个多阶段决策问题变换为几个相互联系的同类型单阶段最优化问题,从而一个一个地去解决. 1. 多阶段决策过程及实例 多阶段决策过程（序贯决策过程） 动态规划的基本概念 1. 阶段 2. 状态 3. 决策 4. 策略 5. 状态转移方程 6. 指标函数和最优值函数 练习 动态规划(逆序法)小结: 1.将问题的过程划分成恰当的阶段;对于静态问题要人为地赋予“时间”概念, 以便划分阶段. 2.选择状态变量 sk , 既能描述过程的变化又满足无后效性; 3.确定决策变量 uk 及每一阶段的允许决策集合Dk( sk ); 4.正确写出状态转移方程; 状态转移方程应当具有递推关系. 5.正确写出阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k 阶段的收益，最优指标函数是 指从第k 阶段状态出发到第n 阶段末所获得收益的最 优值，最后写出动态规划基本方程。 逆序解法的基本方程 (1)指标函数为“和”的形式 求解时从边界条件开始,逆（或顺）过程行进方向,逐段递推寻优. 每段决策的选取都是从全局考虑的,与该段的最优选择答案一般是不同的. 在求整个问题的最优策略时,由于初始状态是已知的,每段的决策都是该段状态的函数,故最优策略所经过的各段状态便可逐次变换得到,从而确定了最优路线. 动态规划和静态规划的关系 二者都属于数学规划的范围，本质上都是求极值的问题。都是用迭代法逐步求解。 静态规划（如线性规划）研究的问题是与时间无关的，每步迭代是整体改进。 动态规划是用来解决多阶段决策过程最优化的一种数量方法。把问题的整体，恰当地分为若干个相互联系的阶段，按一定的次序去求解单阶段决策问题。每步迭代是由当前阶段到“下”个阶段。 对于某些静态的问题可以人为的引入时间因素，把它看作按阶段进行的一个动态规划问题，从而把一个n 维决策问题变换为几个一维最优化问题，一个一个地去解决。 1.动态规划的四大要素 ①决策变量及其允许集合 uk?Uk ②状态变量及其可能集合 sk?Sk ③状态转移方程 xk+1=Tk (sk,uk) ④阶段指标 vk (sk,uk) 练习1 P212 8.5 (1) 练习2 资源分配问题 资源平行分配问题—只合理分配资源, 不考虑回收 决策变量为离散值. 销售点分配问题；投资分配问题；货物分配问题 资源连续分配问题—考虑资源回收利用 决策变量为连续值 资源连续分配问题 练习 1 生产与存储问题 设某公司对某种产品要制订一项n个阶段的生产(或购买)计划.已知它的初始库存量为0,每阶段生产(或购买)该产品的数量有上限的限制;每阶段对该产品的需求量是已知的,公司保证供应;在n阶段末的终结库存量为0.问该公司如何制订每个阶段的生产(或采购)计划,从而使总成本最小. 按4个时期将问题分为4个阶段。 第k个时期内的生产成本为： 生产与存储问题的特征 考研试题 1. 下列关于动态规划问题的说法不正确的是（ ）。 A．应用推理或逆推法可能会得出不同的最优解 B．状态变量应具有无后效性 C．动态规划模型中，阶段是按时间或空间划分的 D．问题的阶段数等于问题中的子问题的数目 2. 用动态规划方法求解多阶段问题时，指标函数应满足（ ）。 A．定义在全过程和后部子过程上的数量函数 B．具有可分离性，满足递推关系 C．严格单调 D．以上A、B、C都是 3. 下述的( )不能设为动态规划中的状态变量. A．生产企业某种产品的每月月初库存 B．某种设备每年年末的可利用量 C．送货车辆行驶过的路程 D．送货车辆行驶时的速度 实际上 例7：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设?=1） 动态规划的基本方程为 解：n=5 状态变量s5可取1，2，3，4 3.5 3 2.5 5 3 2.5 3 4 2.5 2.2 1.5 0.5 更新费CK(t) 2 1.5 1 0.5 运行费OK(t) 3.75 4 4.5 5 效益IK(t) 3 2 1 0 役龄 项目 单位：万元 卖掉役龄2年的设备，买入新设备的更新费