运筹学 动态规划.ppt

第四章 动态规划 动态规划是运筹学的一个重要分支，是解决多阶段决策过程最优化问题的一种非常有效的方法。1951年，美国数学家贝尔曼（R.Bellman）等人，根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。 动态规划是分析某一类问题的一种途径。它不像LP那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 4.1 多阶段决策过程的最优化 一、多阶段决策过程 某厂有1000台机器，现需作一个五年计划，以决定每年安排多少台机器投入高负荷生产（产量大但损耗也大）可使五年的总产量最大，如图4-1所示。 4.2 动态规划的基本概念和基本原理 二、最优化原理 三、动态规划基本思路 1、将问题划分多个阶段。恰当选择状态变量、决策变量 及定义最优指标函数 2、从边界条件开始，逆向或正向逐段递推求解。 3、各个阶段的最优决策是从全局考虑的，并非仅考虑本阶段。 建立动态规划的模型，就是分析问题并建立问题的动态规划基本方程，成功地应用动态规划方法的关键，在于识别问题本身的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题。而正确建立基本递推关系方程的关键又在于正确选择状态变量。 一、DP模型的建立 1、正确、明确地划分阶段 k， k =1，2，3，…，n。 2、正确选择并确定状态变量 sk 及状态集合 Sk 。 例4-3 分配投资问题 问题的一般描述如下：设有某种资源，总数量为a，用于生产n种产品；若分配数量 xi 用于生产第i种产品，其收益为gi(xi)。问应如何分配，使得使总收益最大？ 该类问题可用动态规划进行求解： 例如： 某公司有资金10万元，若投资于项目 k (k = 1,2,3)的投资额为 xk 时，收益分别为 g1(x1) = 4x1， g2(x2) = 9x2， g3(x3) = 2x32 ，问应该如何分配投资数额才能使总收益最大？ 该问题表面上看与时间无明显关系，其静态模型： 现人为地给它赋予“时段”的概念，将投资项目排序，首先考虑项目1的投资，然后考虑项目2的投资……，问题分为3个阶段，每个阶段只决定一个项目的投资金额。 例4-4 采购与销售问题 P103 例2 某商店在未来四个月里，利用一个仓库经销某种商品。仓库最大容量H = 1000件，每月中旬订购商品并于下月初到货。估计未来四个月该商品的购价pk及售价qk如表4-1所示。假定商店在1月初库存500件，每月的需求不限，问应如何计划每月的订购及销售数量，使总利润最大（不考虑库存费用）。 课堂练习 某公司拟将某种高效设备5台分配给所属甲、乙、丙3厂。各厂获此设备后可产生的效益如表4-2所示。问应如何分配，可使所产生的总效益最大？ 解： 阶段k =1,2,3依次表示把设备分配给甲、乙、丙厂的过程； 状态sk表示在第k阶段初还剩有的可分台数； 决策xk表示第k阶段分配的设备台数； 状态转移sk+1 = sk - xk ； 阶段指标vk 表示第k阶段分配后产生的效益； 指标函数： 基本方程： 逆序递推法 将寻优过程看做连续递推的过程，从最终阶段开始，逆着实际决策过程的进展方向逐段求解，在每一段求解中都要利用刚刚求解完那段的结果，直到初始阶段求出结果回到始点为止。 顺序递推法 从初始阶段向前递推，直到最终阶段为止。 表格求解： 当问题划分的阶段和可供选择的状态较多时，动态规划可采用表格形式进行求解。 某厂每月交货量及生产相应费用如表4-3、表4-4所示 某厂生产三种产品，其重量及利润关系表4-5所示。现将三种产品运往市场出售，运输总重量不超过6吨。问如何安排运输使总利润最大？ 例4-8 资源分配问题 某公司新引进6台生产设备，用于4种产品的生产，投入的设备数量不同利润也不同(见表4-6)。问应如何分配设备，使总利润最大？ k = 4 时，S4 = { 0，1，2，3，4，5，6 } 方案1 方案2 方案3 方案4 产品1 0台 1台 2台 2台 产品2 2台 1台 1台 2台 产品3 3台 3台 2台 0台 产品4 1台 1台 1台 2台 最大总利润（万元） 134 134 134 134 即 垦食溉倦蠕侮脆恼锅惫碱恳痹侄程眨井柴七宠音虞窒邵寺萄系沧串多庐坍运筹学 动态规划运筹学 动态规划 0 20 42 60 75 85 90 0 25 45 57 65 70 73