第八章动态规划.ppt

概述 基本概念 基本思想 基本要求 基本解法 主要应用 一维资源分配 二维资源分配 生产计划与存储 授课内容 背包问题 不确定性采购 可靠性 设备更新 货郎担问题 排序 2020 3 22 20世纪50年代 美国数学家贝尔曼 解决多阶段决策过程的最优化的一种方法 多阶段决策过程 可以按时间顺序分解成若干个相互联系的阶段 每阶段有若干个方案供选择 一种动态的决策过程 最终目标是达到整体最优 概述 2020 3 22 主要的应用 最优路径问题 资源分配问题 排序问题 投资问题 装载问题 生产计划与库存问题 生产过程的最优控制等 动态规划种类划分 离散确定型 离散随机型 连续确定型 连续随机型 2020 3 22 例 设从甘肃要铺一条煤气管道到北京 途中须经过陕西 山西 河北 每省设一个中间站 各省建站可供选择的地点及各段距离如下图 现要求选择一条铺管线路 使总距离最短 2020 3 22 2020 3 22 阶段k 指对整个过程的自然划分 根据时间顺序或空间特征来划分阶段 目的是为了按照时间等次序来解决优化问题 状态指各个阶段开始时候所处的自然状况或者客观条件 描述过程状态的变量为状态变量 可以用一个数 一组数或一向量 状态的设定需要满足无后效性要求 基本概念 2020 3 22 sk 第k阶段的状态变量 Sk sk 为第k阶段的状态集合 决策表示当过程处于某一阶段的某个状态时候 可做出不同的决定 从而确定下个阶段的状态 2020 3 22 策略按照顺序排列的各个阶段决策组成的序列 P 允许策略集合最优策略 使整个问题达到最优效果的策略 2020 3 22 状态转移方程确定一个过程状态到另一个状态的演变过程 指标函数衡量所选定的策略优劣的数量指标 2020 3 22 最优策略 最优指标函数 2020 3 22 k 4开始 k 3 2020 3 22 k 2 k 1 2020 3 22 在多阶段决策中 将前一段与未来分开 又将当前效益和未来效益结合起来综合考虑 在求整个问题的最优策略时 由于初始状态已知 各段决策都是其状态的函数 因此可以得到每段状态 形成最优解 最关键的是写出递推关系式和恰当的边界条件 基本思想 2020 3 22 动态规划的优点 减少了计算工作量 丰富了计算结果 建立动态规划模型 将问题的过程划分成恰当的阶段 正确选择状态变量和决策变量 写出状态转移方程 正确写出指标函数 数量函数 具有可分离性 严格单调 2020 3 22 问题必须能够分成几个相互联系的阶段 而且在每一个阶段都具有需要进行决策的问题 每一阶段都必须有若干与该阶段相关的状态 建模时总是从与决策有关的条件中 或是从问题的约束条件中去选择状态变量 基本要求 2020 3 22 状态的选取必须 在问题的各阶段 能直接或间接确定状态变量值 通过现阶段的决策 当前状态转移成下阶段状态 状态的无后效性 具有明确的指标函数 且阶段指标值可以计算 能正确列出最优值函数的递推公式和边界条件 2020 3 22 2020 3 22 在图上直接作业的方法为标号法 逆序解法 规定行进方向10 1 从最终点向初始点进行计算的解法1 10 顺序解法 规定行进方向1 10 从最终点向初始点进行计算的解法10 1 上述两种方法仅仅表示行进方向不同 或对始端和终端看法的颠倒 但是规定行进方向后 均是按照这个方向的逆方向进行求解 基本解法 2020 3 22 动态规划的最优性原理 作为整个过程的最优策略具有以下性质 无论过去的状态和决策如何 对前面的决策所形成的状态而言 余下的决策必须构成最优的策略 即一个最优策略的子策略也是最优的 2020 3 22 动态规划模型的求解 解法 离散型 分段穷举法 连续型 利用解析方法或线性规划方法 没有固定的方法 具体模型具体分析 要求 经验 技巧 灵活 2020 3 22 2020 3 22 某公司有某种原料总数量为a 用于n种产品 已知对第i个产品分配数量xi 收益为gi xi 问应如何分配使总收入最大 一维资源分配 阶段 k 1 2 n 状态变量sk 第k阶段用于第k到第n个产品的数量 决策变量uk 第k个产品的数量 2020 3 22 状态转移方程 指标函数Vk n 第k阶段可分配的数量为sk时 第k至第n个产品的最大总收入 建立递推公式 边界条件 2020 3 22 在三个不同的地区设置4个销售点 在不同地区设置不同数量的销售点 每月得到的利润如下 问在各个地区如何设置销售点 使得每月获得的利润最大 2020 3 22 某有色金属公司拟拨出50万元对所属三家冶炼厂进行技术改造 若以十万元为最少分割单位 各厂收益与投资的关系如下表 如何投资使收益最大 2020 3 22 连续资源的分配问题设有数量为y的某种资源 将它分别投入两种生产方式A和B 已知收益函数分别是g x 和h x x为资源投入量 设这种资源用于生产后还可以回收一部分用于生产 A B的回收率分别为a和b 对总数量为y的资源进行n个阶段的生产 应如何分配每个阶段投入A B的资源数量 才能使总收益最大 2020 3 22 机器负荷问题 某机器可以在不同的负荷下生产 在高负荷下产量为机器数量的10倍 机器完好率为0 7 低负荷下为产量的5倍 机器完好率为0 9 假设工厂开始有机器为1000台 每年如何安排机器在高低负荷下生产 使得5年内生产的产品总量最高 2020 3 22 某公司有两种原料 数量分别为a b 需要分配用于n种产品 如何两种原料分别以xi和yi为单位 收益为gi xi yi 问应如何分配这两种原料 使总收入最大 二维资源的分配 2020 3 22 拉格朗日乘数法 逐次逼近法 2020 3 22 粗格子点法 采用离散式方式 2020 3 22 某商店在四个月用一个仓库经销商品 最大容量为1000单位 每月只能卖出仓库现货 在某月购货时 下月初才到货 未来四个月的买卖价格如下 假定在1月初仓库贮有500单位 如何制定四个月的订购与销售计划 获利最大 不计库存费 生产计划与存储问题 2020 3 22 状态变量sk xk 第k月卖出的货物数量 yk 第k月订购的货物数量 0 xk sk 0 yk 1000 sk xk 决策变量 第k个月的库存量 含上月的定货 2020 3 22 2020 3 22 2020 3 22 依据上述计算 可以得到 第一月 卖出500 订购0个 第二月 卖出0个 订购1000个 第三月 卖出1000个 订购1000个 第四月 卖出1000个 订购0个 2020 3 22 某工厂其交货任务如表 表中的数字为月底交货量 月最大生产能力为6单位 每单位货物生产费用为1000元 生产月份需要经常费3000元 仓库保管费用为每单位每月500元 开始与交货末存货为0 每月生产多少 才能满足任务又能使总费用最小 2020 3 22 2020 3 22 2020 3 22 2020 3 22 某工厂其交货任务如表 表中的数字为月底交货量 月最大生产能力为400件 存货能力为300件 每100件货物生产费用为10000元 生产月份需要经常费4000元 仓库保管费用为每百件每月1000元 开始与交货末存货为0 每月生产多少 才能满足任务又能使总费用最小 2020 3 22 再生产点 2020 3 22 2020 3 22 背包问题 某一个人背包上山 可以携带商品重量固定a 有n种物品可以装入 第i种商品的重量为wi 上山过程中的作用是携带数量的函数 问该人如何选择携带的物品 使得总价值最大 2020 3 22 2020 3 22 某厂生产三种产品 各种产品的重量与利润如表 现将三种产品运输到市场进行销售 运输能力不超过10吨 如何安排运输使得在那个利润最大 2020 3 22 不确定性采购 某部门欲采购一批原料 原料价格在五周内可能有所变动 分别为500 600 700 预测得每种价格的概率分别为0 3 0 3 0 4 试问该部门应在五周内采用什么采购方案 可使采购价格的均值最小 2020 3 22 某种机器的工作系统由n个部件串联组成 只要有一个部件失灵 整个系统就不能正常工作 为提高系统工作的可靠性 在每一个部件上均装有主要元件的备用件 备用元件越多 整个系统的可靠性越大 但备用元件增多也会导致系统的成本 重量相应增大 设部件i i 1 2 n 上装有xi个备用元件时 正常工作的概率为pi xi 设装一个i部件的设备元件费用为ci 重量为wi 要求整个系统所装备用元件的总费用不超过C 总重量不超过W 问如何选择个部件的备用元件数 使整个系统的工作可靠性最大 复合系统工作可靠性 2020 3 22 设A 整个系统正常工作 Ai 部件i正常工作 2020 3 22 决策变量uk 部件k上所装的备用元件数xk状态变量 sk 第k个到第n个部件可使用的总费用Yk 第k个到第n个部件容许的总重量状态转移方程 指标函数Vk n 2020 3 22 某种电子设备需要三种元件 三种元件的可靠性如表 设计元件费用不超过120元 如何设计使得设备的可靠性最大 2020 3 22 有n种工件分别在机床AB上加工 先A后B两道加工工序 用ai和bi分别表示在A和B上加工时间 问如何在两个机床上安排加工的顺序 使得在机床A上加工第一个工件开始到在机床B上将最后一个工件加工完为止 所用的加工总时间最少 排序 2020 3 22 2020 3 22 2020 3 22 已知一台设备已使用了t年 随着使用年限的逐渐增加 机器的使用效率降低 收入减少 维修费用增加 而且机器使用年限越长 本身的价值就越小 现要做一个n年的设备更新计划 每年年初做出决策 是继续使用旧机器还是更换一台新机器 使n年的总收益最大 设备更新问题 2020 3 22 2020 3 22 设某台新设备