运筹学动态规划.ppt

第五章动态规划 一 最短路问题 问题从点A到点E要建造一条石油管道 由于线路 过长 在中间点B C D要设立加压站 在点B分别有B1 B2 和B3三处可建 同样在点C D处也有三点可建 各 点之间的距离如下图所表示 使从A到E 点的距离 为最短 问应如何铺设管道 才能 分析要求从A到点E的最短距离 一种方法是列出从 为此将整个问题分成若干个阶段 即若干个节点 起点到终点的所有可能的路线 并计算每一条路线的路 长 但当问题较大 节点较多时 这样的计算是相当烦 琐的 考虑各节点到终点的最短距离 联合起来就得到起点到 终点的最短距离 解 从上各点到到的最短距离分别为 从上各点到到的最短距离分别为 即从到的最短路线为 最段距离为10 同理 即有 即有 即 最短路线为18 最佳路线为 例2求最短路问题 解仿上例 同样有 即有 即有 即 最短路线为15 最佳路线为 二 动态规划的数学模型 1 基本概念和符号 阶段和阶段变量 所谓阶段是按时间或空间将问题分成若干个进程的部 在前面2例中 问题按空间分成4个阶段 为便于描述各个阶段 引入量来刻划问题中的阶段 该量即称为阶段变量 一般用来表示 分 状态和状态变量 状态表示在某一阶段可能出现的情况 在多阶段规划 在某个阶段 相应的状态可能有多个取值 一般可表 中 每个阶段的初始状态又是前一阶段的终止情况 相 应地 将描述过程状态的变量称为状态变量 一般用 来表示 示为 集合称为阶段的状态集 例如在前面的例1中 有 决策 所谓决策 即是从当前阶段演变到下一阶段所作出的 由于当前状态和下一阶段的状态都可能存在多个元 选择 素 因而从当前状态到下一阶段的选择方案可能有多个 由此形成决策的集合 以表示在第个阶段在 在一个多阶段决策问题中 当从第一个阶段到最后阶 时的决策 而以表示在第个阶段状态是的容 许的决策的集合 例如在例1中 有 段的每一个阶段的决策确定后 由这些决策构成一个决 策序列 该序列称为规划中的策略 例如在例1中 决策序列 为一个策略 若节点已经确定 则称从该节点到终点 状态转移函数 在多阶段决策过程中 把某一阶段中的某一状态转移 的策略序列为从该节点出发的子策略 到下一阶段中的某一状态的变化过程称为状态的转移 显然过程的转移既与当前状态又与当前状态下的决策有 关 所以状态间的转移用表达式 或 来反映 前者称为顺序关系 后者称为逆序关系 这两种 均称为状态转移函数 阶段损益函数 在状态间的转移过程中 从当前状态转移到下一阶段 或支出即称为阶段间的损益 若当前状态为下一阶 表示 在前两例中 阶段损益值即为两地间的距离 的某一状态 必然会有所收益或有所支出 这样的收益 段的状态为则相应的损益值以 在一个多阶段的动态规划中 若 是一个策略 则量 称为策略的指标函数值 在所有决策中 使指标函数值 达到最优的策略即称为最优策略 相应的指标函数记为 即 2 最优化原理及规划方程 在前面的例子中可以发现 当知道从当前状态的每一 个节点到终点的最短路线和最短距离 那么前一阶段的 每一个节点到终点的最短距离仅与从上一阶段到本阶段 的阶段损益函数及本阶段的最优值有关 而与下一阶段 无关 该特征即为动态规划的基本特征 动态规划原理 在动态规划中 从当前阶段到终点的最短距离仅与本 动态规划原理可用相应的数学关系式来表示 阶段到下一阶段的阶段损益函数及下一阶段到终点的最 短距离有关 动态规划问题求解 将问题分成若干个阶段 正确选择状态变量 确定每个阶段的决策及容许的决策集合 列出状态转移函数 或 确定当前阶段的每一个节点的最优值 当时 即得到问题的最优解 列出阶段损益函数 三 动态规划在管理决策中的应用 1 投资分配问题 资金的运作 就是对投资对象的选择 从中进行一个 最佳的组合 以获得最大的收益 例3某公司拟出资5百万元对下属三个工厂进行技术改 求最佳投资分配方案及最佳收益 造 改造完成后所增加的收益如下 解可以将对三个工厂的投资视为三个阶段 对第一个工厂的投资及收益情况如下 该表中的数据可看作为第一阶段中的各个节点到终点 的最短距离 对前2个工厂的投资及收益 当总投资额为一万元时 相应的收益为 而当总投资额为2万元时 平行地可以计算其它情形 由此得到下表 表2对前2个工厂的投资及收益分配表 注表中两项和数据的意义是 第一项表示对第一个工 投资以万元为单位 厂的投资收益 而第二项的数据是对第二个工厂投资的 收益 注意表中数据的结构 表3对3个工厂的投资及收益分配表 注表中两项和数据的意义是 第一项表示对前两个工 分配方案中的第一列表示的是对前两个工厂的联合投 由此得到最佳投资方案和最佳收益分别为 方案 收益 厂的联合投资收益 而第二项的数据是对第三个工厂的 投资收益 资额 例4某公司拟用一部分现金 在三个地区建立若五个 销售点 由于环境的不同 在各地区设立不同个数的销 售点所带来的收益也有所不同 收益有下表表示 试确定建立销售点的方案 使收益达到最大 解仿上例 有 表1在前两地区建立销售点及收益分配表 表2在3个地区建立销售点及收益分配表 最佳方案为最佳收益为10 2 出产和存储问题 问题的提出 一个工厂的产品 在一定的时间内 增加生产批量 能 够降低产品的单位成本 但如果产品的产量超过市场的 需求 就会形成产品的积压 从而增加存储费用 因此如 何根据市场需要及生产的实际情况 合理地制定相应的 生产计划 使得在一个生产周期中 生产和存储费用达 到最低 例5设某厂生产一种产品 以后4个月的订单为 合同规定 产品在每月的月底交货 生产每批产品的 固定成本为3千元 每批出产的件数不限 每件产品的可 变成本为1千元 每批产品的最大生产能力为5件 产品 每件每月的存储费为0 5千元 设一月初有一件库存 四 月底不再有库存 试在满足需要的前提下 如何组织生 产 才能使总的费用为最小 解将问题分成4个阶段 状态变量表示第月的库 而是每月的订货量 则状态转移函数为 阶段损益函数为 存 决策变量为第月的产量 由题意得 用逆序法求解 1 此时的最小取值为0 而最大可能取值为 由此得下表 2 此时的最小取值为0 而最大可能取值为 由此得下表 上表中的最后一列数据表示的是时对应于的各 个取值时的指标函数的最优取值 3 此时的最小取值为0 而最大可能取值为 由此得下表 4 此时此时有 由此得到最优解 总成本 注最优解的确定方法 由最后表知 此时再查前表中当 时的对应取值 得相应的再 查前一表 得最后得 例6某建筑公司拟建造甲 乙 丙三类住房以供出售 甲类住房每栋成本100万元 售价200万元 乙类住房每 栋成本60万元 售价110万元 丙类住房每栋成本30万元 售价70万元 市政局规定每栋类住房最多建造3栋 该公 司现有资金350万元 问如何安排生产可使得收益为最 大 分析将建造三类住房分成3个阶段 状态表示在该 约束条件为 阶段所拥有的资金额 决策变量表示第阶段所建住房 数 则收益函数为 解1 2 则有下表 即 问题的最优解为最大利润为370万元 3 背包问题 背包问题是动态规划中一个有趣而又十分有用的数学 模型 问题设某人上山 可携带的物品的重量限制为公 斤 并设有几种物品可供选择装入包中 已知第种物品 的函数问如何选择使所起的作用为最大 的每件重量为公斤 在上山过程中的作用是携带数量 分析设为第种物品的携带数量 则相应问题的数学 为整数 模型为 解法 其中 是装入第一至第种物品的总重量 则容许 将问题分成若干个阶段 在第个阶段 以表 示用于装载第一种至第种物品的总重量 决策变量 表示装载第种物品的件数 则相应的状态转移方程为 决策的集合为 最优值函数是总重量不超过公斤 背包中能 放入第一种物品到第种物品的最大使用价值 即 例7求解背包问题 为整数 解设状态变量为第阶段能装载的总重量 决策变 由此得 量为装载第种物品的件数 则 由此得 由此得 所以最佳决策是最大效益为 由此得表 即 最优解为最大价值为 例8某厂新购进某种器具125件 这种器具5年后将被其 分析将125件新器具看作资源 年终后 一部分资源 它新器具所取代 此种器具在高负荷下工作 年损坏率为 0 5 年利润为10万元 在低负荷下工作 年损坏率为0 2 年利润为6万元 问如何安排这些器具的生产负荷 才能 使5年内总利润为最大 损坏后报废 另一部分仍能继续使用 可将这部分资源 看作回收资源 对问题按时间分为5个阶段 因此得动态规划方程 表示第阶段初完好的器具数 表示在高负荷下工作的器具数 则在低负荷下工作的器 具数为 则阶段损益函数为 设状态变量 状态转移函数为 解 此处 令再由 取 取 取 取 即 上述计算过程中的结果可用下表表示 5年总的收益为2790 万元 在上面的问题中 所牵涉到的决策变量均为离散型的 而在某些问题中 决策变量可能是连续型的或则是混合 型的 下面的几个例子说明对该类问题应该如何解决 四 决策变量连续的动态规划问题 例9设某厂生产两种产品 由于该厂仓库及其它 设备条件的限制 对于两种产品的日产量相应 又知这两种产品的售价分别为10 千元 百件 和 的成本为 15 千元 百件 工时定额消耗均为1百件 小时 如果 每天总生产时间不超过8小时 产品应各生产多少 小时 才能使总利润达到最大 分析引入利润函数 约束条件是对工时的限制 即 由此得到问题的数学模型为 注意到为连续变量 解则 因此有 此为一元函数的极值问题 利用函数求极值的方法 为 此先求驻点 令 因函数是开口向下的抛物线 故有 事实上