第六章动态规划.ppt

引言 动态规划 DynamicProgramming动态规划是运筹学的一个分支 是解决多阶段决策过程最优化的一种数学方法 1951年 美国数学家贝尔曼等人提出了 最优性原理 即根据一类多阶段决策问题的特点 把多阶段决策问题变换为一系列相互联系的单阶段决策问题 然后分阶段逐个加以解决 从而创建了解决最优化问题的一种新的方法 动态规划 引言 动态规划是解决某一类问题的一种方法 是分析问题的一种途径 而不是一种特殊算法 如线性规划是一种算法 因此 在学习动态规划时 除了对基本概念和方法正确地理解外 应以丰富的想象力去建立模型 用创造性的技巧去求解 引言 本部分我们主要研究离散决策过程 介绍动态规划的基本概念 理论和方法 通过一些典型的应用问题来说明它的应用 多阶段决策过程及实例 多阶段决策过程 Multi Stagedecisionprocess 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段 每一阶段都需作出决策 全部过程的决策是一个决策序列 多阶段决策过程最优化的目标 达到整个活动过程的总体效果最优 而非各单个阶段最优的简单总和 多阶段决策过程及实例 多阶段决策问题的典型例子 多阶段决策问题的典型例子 1 生产决策问题 企业在生产过程中 由于需求是随时间变化的 因此企业为了获得全年的最佳生产效益 就要在整个生产过程中逐月或逐季度地根据库存和需求决定生产计划 2 机器负荷分配问题 某种机器可以在高低两种不同的负荷下进行生产 在高负荷下进行生产时 产品的年产量g和投入生产的机器数量u1的关系为g g u1 多阶段决策问题的典型例子 3 航天飞机飞行控制问题 由于航天飞机的运动的环境是不断变化的 因此就要根据航天飞机飞行在不同环境中的情况 不断地决定航天飞机的飞行方向和速度 状态 使之能最省燃料和实现目的 如软着落问题 4 线性规划 非线性规划等静态的规划问题也可以通过适当地引入阶段的概念 应用动态规划方法加以解决 多阶段决策过程及实例 请看如下典例 最短路线问题 多阶段决策过程及实例 贪心算法每一步都走最短的线路 A B2 C4 D3 E2 F2 G 长度为21 不是最优 最短的线路 A B1 C2 D1 E2 F2 G 长度为18 枚举法 列出每条可能的路线 然后算出每条路的长度 从中选择最优路线 缺点是线路太多 随点数增加很快 标号法 标号法 只适用于这类最优路线问题的特殊解法 标号法是借助网络图通过分段标号来求出最优路线的一种简便 直观的方法 通常标号法采取 逆序求解 的方法来寻找问题的最优解 即从最后阶段开始 逐次向阶段数小的方向推算 最终求得全局最优解 多阶段决策过程及实例 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 该点到G点的最短距离 从G到A的解法称为逆序解法 从A到G的解法称为顺序解法 最短路问题 该方法比枚举法简单 计算的路远少于枚举法计算过程分了六个阶段 每个阶段都是一个子问题 有出发点和选择 并有不同的获得 后一阶段的出发点由前阶段的出发点和选择确定前一阶段的获得不仅与本阶段的选择有关还与后一阶段的获得有关 这类问题称之为多阶段决策问题 动态规划的基本概念和基本原理 1 阶段 stage 把所给问题恰当地划分为若干个相互联系又有区别的子问题 通常根据时间顺序或空间特征来划分 以便按阶段的次序逐段解决整个过程的优化问题 描述阶段的变量叫作阶段变量 阶段变量通常用k表示 k 1 2 3 n 动态规划的基本概念和基本原理 2 状态 state 用以描述事物 或系统 在某特定的时间与空间域中所处位置及运动特征的量 称为状态 它应能描述过程的特征并具有 无后效性 又称马尔柯夫性 是指系统从某个阶段往后的发展 仅由本阶段所处的状态及其往后的决策所决定 与系统以前经历的状态和决策 历史 无关 状态变量 sk statevariable 状态集合 Sk setofadmissiblestates 动态规划的基本概念和基本原理 3 决策 decision 决策 确定系统过程发展的方案 决策的实质是关于状态的选择 是决策者从给定阶段状态出发对下一阶段状态作出的选择 决策变量 uk sk decisionvariable 决策集合 Dk sk setofadmissibledecision 动态规划的基本概念和基本原理 4 策略 policy 策略也叫决策序列 一组有序的决策序列构成一个策略 从第k阶段至第n阶段的一个策略称为后部子策略 动态规划的基本概念和基本原理 5 状态转移方程 equationofstatetransition 系统在阶段k处于状态sk 执行决策uk sk 的结果是系统状态的转移 即系统由k阶段的状态sk转移到了k 1阶段的状态sk 1 对于具有无后效性的多阶段决策过程 系统由阶段k到阶段k 1的状态转移完全由阶段k的状态sk和决策uk sk 所确定 与系统过去的状态及其决策无关 系统状态的这种转移 用数学公式描述即有 sk 1 Tk sk uk k 1 2 n 动态规划的基本概念和基本原理 6 指标函数 objectivefunction 用来衡量策略或决策的效果的某种数量指标 就称为指标函数 对不同问题 指标函数可以是诸如费用 成本 产值 利润 产量 耗量 距离 时间 效用 等等 通常表示为vk sk uk 多阶段决策过程及实例 从A点铺设一条煤气管道到E点 由于距离过长 必须经过三次加压才能保证终端用户的压力 经过前期调查确定每个加压站的三个备选位置 由于地理条件限制某些地点之间不适合建管道 可选地及其管线连接关系如下图 贪心算法 每一步都走最短的线路 A B1 C3 D1 E 长度为14 不是最优 最优 A B2 C1 D1 E 长度为11 枚举法 列出每条可能的路线共21条 然后算出每条路的长度 从中选择最优路线 缺点是线路太多 随点数增加很快 最短路问题 确定三个加压站本质上是选择一条从A到E的路使总长度最短 从A到E的任一条路都必然是先从A到B1 B2 B3中某一个点 然后从该点到E点 假设从A到E最短路是从A先到B1 然后从B1到E 那么到达B1后必然沿着从B1到E的最短路走 如果分别求出B1 B2 B3到E点的最短路 就可以求出A到E的最短路 以f i 表示点i到点E的最短路的长度 则有 最短路问题求解思路 最短路问题 为了求出B1 B2 B3到E点的最短路 就需要求出C1 C2 C3到E点的最短路 最短路问题 为了求出C1 C2 C3到E点的最短路 就需要求出D1 D2 D3到E点的最短路 最短路问题 由于D1 D2 D3到E点只有一条路 所以 最短路问题 由f D1 f D2 f D3 可计算出f C1 f C2 f C3 最短路问题 由f C1 f C2 f C3 可计算出f B1 f B2 f B3 最短路问题 由f B1 f B2 f B3 可计算出f A 标号法 0 3 5 4 4 8 6 11 7 8 11 从E到A的解法称为逆序解法 从A到E的解法称为顺序解法 最短路径问题举例 下图表示从起点A到终点E之间各点的距离 求A到E的最短路径 最短路问题 从上面的计算过程中可以看出 在求解的各个阶段 我们利用了K阶段与K 1阶段之间的递推关系 动态规划的基本方程 动态规划的基本思想 基本思想总结 例 最短路线问题1 划分阶段 2 求解从边界条件开始 逆向逐段递推 3 每段的最优是从全局考虑的 并非仅考虑本阶段 动态规划的最优性原理和最优性定理 基本思想 动态规划方法的关键 正确地写出基本方程 1 将问题的过程划分为多个相互联系的多阶段决策过程 恰当地选取状态变量和决策变量及定义最优指标函数 把问题转化成一组同类型的子问题 2 从边界条件开始 逆过程行进方向 逐段递推寻优 3 在每个子问题求解时 均利用它前面已求出的子问题的最优化结果依次进行 最后一个子问题所得的最优解 就是整个问题的最优解 动态规划的最优性原理和最优性定理 在多阶段决策过程中 动态规划方法是既把当前的一段和未来的各段分开 又把当前效益和未来效益结合起来考虑的一种最优化方法 因此 每阶段决策的选取是从全局来考虑 与该段的最优选择一般是不同的 动态规划方法的基本思想体现了多阶段性 无后效性 递归性 总体优化性 动态规划的最优性原理和最优性定理 Bellman最优化原理 一个过程的最优策略具有这样的性质 即无论开始的状态及决策如何 对先前的决策所形成的状态而言 余下的诸决策必构成最优策略 简言之 一个最优策略的子策略总是最优的 动态规划求解方法 逆推解法 BackwardInductionMethod 将寻优过程看做连续递推的过程 从最终阶段开始 逆着实际决策过程的进展方向逐段求解 在每一段求解中都要利用刚刚求解完那段的结果 直到初始阶段求出结果回到始点为止 顺推解法 ForwardInductionMethod 从初始阶段向前递推 直到最终阶段为止 一般地 当过程的终点给定时 用顺推法比较方便 基本方程 递推关系式 假定过程的总效益 指标函数 与各阶段效益的关系为 基本方程 递推关系式 由于初始状态s1已知 故可逐步确定出每阶段的决策及效益 基本方程 递推关系式 假定过程的总效益 指标函数 与各阶段效益的关系为 例3用逆推解法求解问题 例3用逆推解法求解问题 例3用逆推解法求解问题 用逆推解法 从后先前依次有 例3用逆推解法求解问题 例3用逆推解法求解问题 例3用逆推解法求解问题 利用微分法易知 已知s1 c 可得各阶段的最优决策和最优值 即 例3用逆推解法求解问题 例3用逆推解法求解问题 建立动态规划模型 建立动态规划模型的步骤 1 正确 明确地划分阶段k k 1 2 3 n 依据决策过程的时间和空间的顺序关系 2 正确选择并确定状态变量sk及状态集合Sk 状态变量的确定有时并非显而易见 要确定它 通常可对问题作如下分析而帮助确定状态变量a 什么关系将各个阶段联系在一起 b 为了决定今后的最优 子 策略 需要事件现状的哪些信息 建立动态规划模型 3 确定决策变量uk及决策集合Dk sk 4 写出状态转移方程sk 1 Tk sk uk 5 定义阶段指标值 函数 vk sk uk 6 定义第k至n阶段 后部子过程 的最优指标 目标 函数fk sk 7 作出动态规划结构图 建立动态规划模型 8 建立动态规划基本方程 逆序递推方程 9 逆序递推求解动态规划基本方程 求出最优决策序列u n u n 1 u 2 u 110 顺序确定最优策略 p 1n u 1 u 2 u n 例分配投资问题 某公司有资金10万元 若投资于项目k k 1 2 3 的投资额为xk时 其收益分别为g1 x1 4x1 g2 x2 9x2 g3 x3 2x32 问应该如何分配投资数额才能使总收益最大 该问题表面上看与时间无明显关系 其静态模型 Maxz 4x1 9x2 2x32x1 x2 x3 10 xi 0 i 1 2 3 建立动态规划模型与求解 建立DP模型与求解阶段k 1 2 3 分别表示项目1 2 3状态变量sk 第k段初拥有的资金总量 分配给第k至第3个项目的资金数量 决策变量xk 第k段的投资量 分配给第k个项目的资金数量 决策集合Dk sk xk 0 xk sk 建立动态规划模型与求解 4 状态转移方程sk 1 sk xk 建立动态规划模型与求解 5 阶段指标值 函数 vk sk xk gk xk 所以指标函数为 6 fk sk 第k段初拥有的资金总量为sk时 第k至第3段按最优投资策略所获得的第k至第3段的总收益 g1 x1 4x1g2 x2 9x2g3 x3 2x32 建立动态规划模型与求解 7 建立动态规划基本方程 逆序递推方程 8 逆序递推求解动态规划基本方程k 3 f3 s3 2s32x3 s3 建立动态规划模型与求解 可以证明极大值只可能在端点取得 即 1 s2 9 2时 f2 0 f2 s2 此时x2 s2f2 s2 9s22 s2 9 2时 f2 0 f2 s2 此时x2 0f2 0 2s22 建立动态规划模型与求解 k 1第一种情况 当f2 s2 9s2 f1 10 Max 4x1 f2 s2 Max 4x1 9s2 0 x1 10 Max 4x1 9 s1 x1 Max 9s1 5x1 9s1 x1 0 但此时s2 s1 x1 10 0 9 2与s2 9 2矛盾 故舍去 0 x1 10 建立动态规划模型与求解 k 1第二种情况 同样可以证明极大值只可能在端点取得 比较两个端点 x1 0时 f1 10 200 x1 10时 f1 10 40所以x1 0 建立动态规划模型与求解 10 顺序确定最优策略 最优投资方案为全部资金投资于第3个项目 可获最大收益200万元 资源分配问题 分配问题就是将一定数量的一种或者若干种资源 适当地分配给若干个使用者 而使目标函数为最优 设有某种原料 总数量为a 若分配数量xi用于生产i种产品 收益为gi xi 问应如何分配 才能使n种产品的总收入最大 资源分配问题 数学模型如下 可将它看作一个多阶段决策问题 用动态规划方法求解 资源分配问题 设 决策变量Xk 投资第k个项目的资金数状态变量sk 分配用于生产第k种产品至第n种产品的原料数量 状态转移方程 sk 1 sk xk 资源分配问题 最优值函数fk sk 投资第k至n项所得的最大收益数 动态规划基本方程 利用这个递推关系式进行逐段计算 最后求得f1 a 即为所求问题的最大总收入 资源分配问题 例6某工业部门根据国家计划的安排 拟将某种高效的设备5台分配给所属的甲 乙 丙三个工厂 各工厂若获得这种设备之后 可以为国家提供的盈利如表所示 问这5台设备如何分配给工厂才能使国家得到的盈利最大 盈利表 资源分配问题 解 将问题按工厂分3个阶段 Sk 分配给第k个工厂到第n个工厂的设备台数 Xk 分配给第k个工厂的设备台数 Sk 1 Sk xk 分配给第k 1个工厂到第n个工厂的设备台数 资源分配问题 Pk xk xk台设备分到第k个工厂所得的盈利值 fk Sk Sk台设备分配给第k个工厂到第n个工厂所得到的最大盈利值 因而可以写出递推关系式为 资源分配问题 逆序法 当k 3时 设将S3台设备 S3 0 1 2 3 4 5 全部分配给工厂丙时 则最大盈利值为 因为此时只有一个工厂 有多少设备就全部分配给丙工厂 故它的盈利值就是该段的最大盈利值 其数值计算如表6 2所示 资源分配问题 表6 2 资源分配问题 当k 2时 把x2台设备分配给工厂乙和工厂丙时 则对每个x2值 有一种最优的分配方案 使最大盈利值为 资源分配问题 表6 3 资源分配问题 当k 1时 设把S1 S1 5 台设备分配给工厂甲 工厂乙和工厂丙时 则最大盈利值为 资源分配问题 表6 4 资源分配问题 最优分配方案有两个 X1 0 根据S2 S1 x1 5 0 5 查表6 3知 x2 2 S3 S2 x2 5 2 3 查表6 2知x3 S3 3 即 甲工厂 0台 乙工厂 2台 丙工厂 3台 X1 2 根据S2 S1 x1 5 2 3 查表6 3知 x2 2 S3 S2 x2 3 2 1 查表6 2知x3 S3 1 即 甲工厂 2台 乙工厂 2台 丙工厂 1台 生产与存储问题 例10 某车间需要按月在月底供应一定数量的某种部件给总装车间 由于生产条件的变化 该车间在各月份中生产每单位这种部件所需耗费的工时不同 各月份的生产量与当月的月底前 全部要存入仓库以备后用 已知总装车间的各个月份的需求量以及在加工车间生产该部件每单位数量所需工时数如表6 7所示 生产与存储问题 设仓库容量限制为H 9 开始库存量为2 期终库存量为0 需要制定一个半年的逐月生产计划 即满足需要和库容量的限制 又使生产这种部件的总耗费工时数为最少 生产与存储问题 解 按月份划分阶段K 状态变量Sk 第k段开始时部件库存量 决策变量uk 第k段内的部件生产量 状态转移方程 允许决策集合Dk sk 生产与存储问题 最优值函数fk sk 在第k段开始的库存量为sk时 从第k段至第6段所生产部件的最小累计工时数 逆推关系式 生产与存储问题 因要求期终库存量为0 所以s7 0 因每月的生产是供应下月的需要 所以u6 0 f6 s6 0由 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 生产与存储问题 习题6 7 解 将问题按零售店分为4个阶段 状态变量sk 分配给第k至第4个零售店的货物箱数 决策变量xk 分配给第k个零售店的货物箱数 状态转移方程 sk 1 sk xk阶段指标pk xk 将xk箱货物分配给第k个零售店的盈利 最优值函数fk sk 将sk箱货物分配给第k至第4个零售店的最大盈利 习题6 7 习题6 7 习题6 7 习题6 7 习题6 7 习题6 8 解 将问题按粮田数分为4个阶段 状态变量sk 分配给第k至第4块粮田的肥料重量 决策变量xk 分配给第k块粮田的肥料重量 状态转移方程 sk 1 sk xk阶段指标pk xk 将xk单位肥料分配给第k个粮田增产粮食的数量 最优值函数fk sk 将sk单位肥料分配给第k至第4块粮田的最大数量 习题6 8 做题步骤与方法与习题6 7相同 习题6 9 解 将问题按营业区分为3个阶段 状态变量sk 第k至第3个区增设的店数 决策变量xk 第k个区增设的店数 状态转移方程 sk 1 sk xk阶段指标pk xk 第k个区增设xk店所取得的利润 最优值函数fk sk 从第k至第3个区增设sk店所取得的最大利润 习题6 9 做题步骤与方法与习题6 7相同 习题6 10 解 将问题按周期分为4个阶段 状态变量sk 第四年初完好的机器数 决策变量xk 第k年度用于第一种任务的机器数 sk xk 表示该年度用于第二种任务的机器数 状态转移方程 sk 1 1 1 3 xk 1 1 10 sk xk 2 3xk 9 10 sk xk 习题6 10 最优值函数fk sk 第k至第4个周期的总收益的最大值 习题6 10 习题6 12 解 设3种产品其运输重量分别为x1 x2 x3 由题意得模型为 最大利润为260 运输方案有两个 0 2 0 或 1 0 1 WinQSB软件解题 生产准备成本 生产和存储成本 WinQSB软件解题 阶段初库存量 各阶段生产量 阶段末库存量 各阶段生产库存费用 各阶段总费用 本章结束 生产与存储问题 例8 某工厂要对一种产品制定今后四年的生产计划 根据估计在今后四年内 市场对该产品的需求量如表6 5所示 表6 5 生产与存储问题 假定该厂生产每批产品的固定成本为3 千元 若不生产即为0 每单位产品成本为1 千元 每个时期生产能力所允许的最大生产批量不超过6个单位 每个时期未售出的产品 每个单位需付存贮费0 5 千元 假定在第一个时期的初始库存量为0 第四个时期末的库存量也为0 试问该厂应如何安排各个时期的生产与库存 才