运筹学-动态规划.ppt

第四章动态规划DynamicProgramming 多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划方法的基本步骤动态规划方法应用举例 本章内容重点 动态规划是解决多阶段决策过程最优化问题的一种方法 由美国数学家贝尔曼 Bellman 等人在20世纪50年代提出 他们针对多阶段决策问题的特点 提出了解决这类问题的 最优化原理 并成功地解决了生产管理 工程技术等方面的许多实际问题 动态规划是现代企业管理中的一种重要决策方法 可用于最优路径问题 资源分配问题 生产计划和库存问题 投资问题 装载问题 排序问题及生产过程的最优控制等 动态规划的基本原理多阶段决策过程最优化多阶段决策过程是指这样一类特殊的活动过程 他们可以按时间顺序分解成若干相互联系的阶段 在每个阶段都要做出决策 全部过程的决策是一个决策序列 所以多阶段决策问题也称为序贯决策问题 例生产与存储问题某工厂每月需供应市场一定数量的产品 供应需求所剩余产品应存入仓库 一般地说 某月适当增加产量可降低生产成本 但超产部分存入仓库会增加库存费用 要确定一个每月的生产计划 在满足需求条件下 使一年的生产与存储费用之和最小 例投资决策问题某公司现有资金Q亿元 在今后5年内考虑给A B C D四个项目投资 这些项目的投资期限 回报率均不相同 问应如何确定这些项目每年的投资额 使到第五年末拥有资金的本利总额最大 例设备更新问题企业在使用设备时都要考虑设备的更新问题 因为设备越陈旧所需的维修费用越多 但购买新设备则要一次性支出较大的费用 多阶段决策过程特点 多阶段决策问题 Multi Stagedecisionprocess 例1 不定阶段最短路线问题 如图是一个五座城市的及其相连道路的交通图 线上的数字是对应的路长 问 应如何选择行驶路线 才能使从A B C D各城市到E城市的行驶路程最短 从图中可以看出 任意两座城市之间都有道路相通 我们把从一座城市直达另一座城市作为一个阶段 例从A城市到E城市的阶段数 少则一个 例从A城市直达E城市 多则无限 例从A城市通过其他B C D三城市循环到E城市 为避免循环 加上约束条件 每个城市至多经过一次 于是从A城市到达E城市的阶段数有下列四种情形 1 从A城市直达E城市 一个阶段 2 从A城市通过其他B C D三城市之一到E城市 二个阶段 3 从A城市通过其他B C D三城市之二到E城市 三个阶段 4 从A城市通过其他B C D三城市各一次到E城市 四个阶段 例2 一定阶段最短路问题 W先生每天驾车去公司上班 如图 W先生的住所位于A 公司位于F 图中的直线段代表公路 交叉点代表路口 直线段上的数字代表两路口之间的平均行驶时间 现在W先生的问题是要确定一条最省时的上班路线 动态规划的基本概念阶段 状态 决策和策略 状态转移 指标函数 1阶段 Stage 将所给问题的过程 按时间或空间特征分解成若干个相互联系的阶段 以便按次序去求每阶段的解 用以描述阶段的变量叫作阶段变量 一般以k表示阶段变量 2状态 State 各阶段开始时的客观条件叫做状态 描述各阶段状态的变量称为状态变量 常用sk表示第k阶段的状态变量 状态变量的取值集合称为状态集合 用Sk表示 状态集合可以是一离散取值的集合 也可以为一连续的取值区间 视具体问题而定 按照过程进行的先后 每个阶段的状态可分为初始状态和终止状态 或称输入状态和输出状态 阶段k的初始状态记作sk 终止状态记为sk 1 但为了清楚起见 通常定义阶段的状态即指其初始状态 动态规划中的状态具有如下性质 当某阶段状态给定以后 在这阶段以后的过程的发展不受这段以前各段状态的影响 即 过程的过去历史只能通过当前状态去影响它未来的发展 这称为无后效性 如果所选定的变量不具备无后效性 就不能作为状态变量来构造动态规划模型 3决策和策略 DecisionandPolicy 当各段的状态确定以后 就可以做出不同的决定 或选择 从而确定下一阶段的状态 这种决定称为决策 决策变量用xk Sk 表示 允许决策集合用Dk Sk 表示 各个阶段决策确定后 整个问题的决策序列就构成一个策略 用p1 n x1 x2 xn 表示 对每个实际问题 可供选择的策略有一定的范围 称为允许策略集合 用P表示 使整个问题达到最优效果的策略就是最优策略 4状态转移方程动态规划中本阶段的状态往往是上一阶段的决策结果 如果给定了第k段的状态Sk 本阶段决策为xk Sk 则第k 1段的状态Sk 1由公式 Sk 1 Tk Sk xk 确定 称为状态转移方程 5指标函数用于衡量所选定策略优劣的数量指标称为指标函数v Sk xk Sk 对不同问题 指标函数可以是诸如费用 利润 产量 距离 时间 效用等等 满足可分离 可递推 可加性或可乘性 k子过程指标函数Vk n最优指标函数fk Sk 动态规划的基本思想 从过程的最后一段开始 用逆序递推方法求解 逐步求出各段各点到终点E最短路线 最后求出A点到E点的最短路线 A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F A B1 B2 C1 C2 C3 D1 D2 D3 E1 E2 F 4 1 5 4 4 4 4 5 3 3 3 3 3 2 2 2 2 A B C D E F 动态规划的函数方程 DP 建立DP函数方程是指确定过程的阶段及阶段数 规定状态变量和决策变量的取法 给出各阶段的状态集合 允许决策集合 状态转移方程和指标函数等 在上面的计算过程中 利用了第k阶段与第k 1阶段的关系 fk Sk Mind Sk dk Sk fk 1 Sk 1 dk Sk k 1 2 3 4 5f6 S6 0这种递推关系称为动态规划的函数基本方程 贝尔曼 Ballman 最优化原理作为整个过程的最优策略具有这样的性质 即无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的诸决策必须构成最优策略 这就是说 不管引导到这个现时状态的头一个状态和决策是什么 所有的未来决策应是最优的 动态规划数学模型由最优指标函数递推表达式 边界条件及状态转移方程构成 建立动态规划模型的要点1 划分阶段 2 选择状态变量 3 确定决策变量和允许决策集合 4 写出状态转移函数 5 列出动态规划方程 动态规划的优点 可把一个N维优化问题化成N个一维优化问题求解 DP方程中附加某些约束条件 可使求解更加容易 求得最优解以后 可得所有子问题的最优解 动态规划的缺点 一个 问题 一个 模型 一个 求解方法 且求解技巧要求比较高 没有统一处理方法 状态变量维数不能太高 一般要求小于6 维数灾难 离散型动态规划连续型动态规划 确定型动态规划随机型动态规划 动态规划的分类 离散型动态规划应用举例 1 开店问题2 一维背包问题3 生产与存储问题4 资源平行分配问题5 非线性分配问题 动态规划应用举例例6一家著名的快餐店计划在某城市建立5个分店 这个城市分成三个区 分别用1 2 3表示 由于每个区的地理位置 交通状况及居民的构成等诸多因素的差异 将对各分店的经营状况产生直接的影响 经营者通过市场调查及咨询后 建立了下表 该表表明了各个区建立不同数目的分店时的利润估计 确定各区建店数目使总利润最大 解 阶段 每个区 共三个阶段 状态 Sk为第k阶段开始时 可供分配的店数 决策 dk为分配给区k的店数 状态转移方程 Sk 1 Sk dk效益 rk dk 为分配给区k dk个店时的利润 fk Sk 为当第k阶段初始状态为Sk时 从第k阶段到最后阶段所得最大利润 fk Sk Maxrk dk fk 1 Sk 1 dk Sk k 1 2 3f4 S4 0 k 3时 计算如下 k 2时 计算如下 S3 S2 d2 k 1时 计算如下 最优解 d 1 3 d 2 2 d 3 0即 在区1建3个分店 在区2建2个分店 而不在区3建立分店 最大总利润 22 建立动态规划模型的要点 分析题意 识别问题的多阶段性 按时间或空间的先后顺序适当地划分满足递推关系的若干阶段 对非时序的静态问题要人为地赋予 时段 的概念 建立动态规划模型的要点 正确地选择状态变量 使其具备两个必要特征 1 可知性 即过去演变过程的各阶段状态变量的取值 能直接或间接地确定 2 能够确切地描述过程的演变且满足无后效性 建立动态规划模型的要点 根据状态变量与决策变量的含义 正确写出状态转移方程或转移规则 根据题意明确指标函数 最优指标函数以及一段效益即阶段指标的含义 并正确列出最优指标函数的递推关系及边界条件 即DP基本方程 生产和存储问题 假设某厂生产的某种产品 以后四个月的订单如下表所示 合同规定在月底前交货 生产每批产品的固定成本为3千元 每批生产的产品的数量不限 每件产品的可变成本为1千元 每批产品的最大生产能力为5件 产品每件每月的存储费用为0 5千元 设1月初有库存1件 4月底不再留下产品 试在满足需要的前提下 如何组织生产才能使总的成本费用最低 n 4 状态变量sk k 1 2 3 4 为每月初的库存 则s1 1 s5 0 决策变量xk 每月生产的产量状态转移方程sk 1 sk xk bk阶段损益函数d sk xk 为各阶段产品的总成本 库存成本 生产成本 模型 K 4S4的取值范围X4的取值范围 K 3S3的取值范围X3的取值范围 K 2S2的取值范围X2的取值范围 K 1S1的取值范围X1的取值范围 最优解为x1 2 x2 5 x3 0 x4 4 f1 s1 21 5 资源平行分配问题 假设有某种原材料数量为a 这种材料可以用来生产n种产品 已知生产每种产品所获的收益与所使用的原材料的数量关系为Vi gi xi 其中xi表示用于生产第i种产品的原材料的数量 目标 总收益最大 满足的条件 背包问题 一维 背包 问题例8 有一辆最大货运量为10吨的卡车 用于装载三种货物 每种货物的单位重量及相应单位价值如下 应如何装载可使总价值最大 解 设第i种货物装载的件数为xi i 1 2 3 则问题可表示为 maxZ 4x1 5x2 6x33x1 4x2 5x3 10 xi 0且为整数 i 1 2 3 阶段k 第k次装载第k种物品 k 1 2 n 状态变量Sk 假设Sk为第k阶段可分配的重量的额度 决策变量dk 第k次装载第k种物品的件数决策允许集合 Dk sk dk 0 xk sk wk xk为整数 状态转移方程 Sk 1 Sk wkxk阶段指标 rk ckxk K 3时S3的取值范围X3的取值范围 s3 K 2时S2的取值范围X2的取值范围 x2 s2 K 1时S1的取值范围X1的取值范围 s1 可推得全部策略为 x1 2 x2 1 x3 0 最大价值为13 非线性函数的资源分配问题 应用动态规划求解问题 D3 s3 0 1 2 sk 4 0 1 2 3 x1 0 s