运筹学课件--动态规划.ppt

2020 2 22 运筹学课件 动态规划 8 1多阶段决策问题与动态规划8 2动态规划的基本概念8 3动态规划的步骤8 4动态规划的应用1求解静态规划问题2资源分配问题3不确定性采购问题4排序问题 2020 2 22 运筹学课件 动态规划所研究的对象是多阶段决策问题 所谓多阶段决策问题是指一类活动过程 它可以分为若干个相互联系的阶段 在每个阶段都需要作出决策 这个决策不仅决定这一阶段的效益 而且决定下一阶段的初始状态 每个阶段的决策确定以后 就得到一个决策序列 称为策略 多阶段决策问题就是求一个策略 使各阶段的效益的总和达到最优 8 1多阶段决策问题与动态规划 2020 2 22 运筹学课件 安全过河问题 古代有3位商人各自带了一个仆人外出来到了一个渡口 渡口只有一条小船每次只能乘2人 仆人私下约定只要岸上的仆人人数超过商人人数 就可杀人越货 但是过河的决策由商人制定 问商人如何安全的渡过河去 2020 2 22 运筹学课件 2020 2 22 运筹学课件 一 多阶段决策问题1 时间阶段的例子 机器负荷问题 某厂有1000台机器 现需作一个五年计划 以决定每年安排多少台机器投入高负荷生产 产量大但损耗也大 可使五年的总产量最大 8 1多阶段决策问题与动态规划 2020 2 22 运筹学课件 2 空间阶段的例子 最短路问题 如图为一线路网络 现要从A点铺设一条管道到E点 图中两点间连线上数字表示两点间距离 现需选一条由A到E的铺管线路 使总距离最短 2020 2 22 运筹学课件 动态规划 解决问题的基本特征 1 动态规划一般解决最值 最优 最大 最小 最长 问题 2 动态规划解决的问题一般是离散的 可以分解 划分阶段 的 3 动态规划解决的问题必须包含最优子结构 即可以由 n 1 的最优推导出n的最优 2020 2 22 运筹学课件 动态规划模型的分类 以 时间 角度可分成 离散型和连续型 从信息确定与否可分成 确定型和随机型 从目标函数的个数可分成 单目标型和多目标型 2020 2 22 运筹学课件 1 基本概念 阶段 Stage 分步求解的过程 用阶段变量k表示 k 1 n 状态 State 每阶段初可能的情形或位置 用状态变量Sk表示 按状态的取值是离散或连续 将动态规划问题分为离散型和连续型 决策 Decision 每阶段状态确定后的抉择 即从该状态演变到下阶段某状态的选择 用决策变量xk表示 状态转移 由Sk转变为Sk 1的规律 记Sk 1 T Sk xk 策略 Policy 由各阶段决策组成的序列 记P1n x1 xn 称Pkn xk xn 为阶段k至n的后部子策略 8 2基本概念与方程 2020 2 22 运筹学课件 当前状态 以前状态 决策 显然 从上图可以看出 当前状态通过决策 回到了以前状态 可见决策其实就是状态之间的桥梁 而以前状态也就决定了当前状态的情况 K Sk Sk 1 Xk Vk 2020 2 22 运筹学课件 过河 决策向量xk I J 初始状态s1是T 3 3 结束状态sn是T 0 0 可达状态有哪些 3 J 2 2 1 1 0 J 0 3 2 1 1 2 3 A J I I表示留在左岸的商人人数J表示留在左岸的仆人人数 2020 2 22 运筹学课件 阶段指标 每阶段选定决策xk后所产生的效益 记vk vk Sk xk 指标函数 各阶段的总效益 记相应于Pkn的指标函数为vkn vkn Sk Pkn 其中最优的称最优指标函数 记fk fk Sk optvkn 问题 动态规划的最优解和最优值各是什么 最优解 最优策略P1n 最优值 最优指标f1 2020 2 22 运筹学课件 多阶段决策过程 2020 2 22 运筹学课件 2 基本原理与基本方程 1 基本原理 以最短路为例说明 2020 2 22 运筹学课件 2 基本方程 根据最优性原理 可建立从后向前逆推求解的递推公式 基本方程 通常动态规划问题的最优值函数满足递推关系式 边界条件 2020 2 22 运筹学课件 动态规划求解的一般步骤 确定过程的分段 构造状态变量 设置决策变量 写出状态转移 列出阶段指标和指标函数 写出基本方程 由此逐段递推求解 K Sk Sk 1 Xk Vk 8 3动态规划的求解方法 2020 2 22 运筹学课件 例1用动态规划方法求解前面的最短路问题 1 离散型 求解方法 2020 2 22 运筹学课件 标号法求解在每个节点上标出从该节点到终点的最短距离 始端 终端 0 5 2 8 7 12 20 14 19 19 1 2 3 4 逆序解法 2020 2 22 运筹学课件 请在每个节点上标出从该节点到始点的最短距离 顺序解法 2020 2 22 运筹学课件 解 设阶段k 1 2 3 4依次表示4个阶段选路的过程 状态sk表示k阶段初可能处的位置 决策xk表示k阶段初可能选择的路 阶段指标vk表示k阶段与所选择的路段相应的路长 指标函数vk4 表示k至4阶段的总路长 用表格方式求解 逆推 2020 2 22 运筹学课件 4 3 8 7 12 C1D1E C2D2E C3D2E 2020 2 22 运筹学课件 2 2020 2 22 运筹学课件 1 A 19 AB2C1D1E f1 19 最短路 最短距 2020 2 22 运筹学课件 作业 用表格方式法求解8 2 并给出阶段 状态变量 决策变量 状态转移方程和指标函数 最优值函数 2020 2 22 运筹学课件 2020 2 22 运筹学课件 2 连续型 用公式递推求解 例2用动态规划方法求解前面的机器负荷问题 某种机器可以在高 低两种负荷下进行生产 高负荷年产量8 年完好率0 7 低负荷年产量5 年完好率0 9 现有完好机器1000台 需制定一个5年计划 以决定每年安排多少台机器投入高 低负荷生产 使5年的总产量最大 2020 2 22 运筹学课件 阶段指标vk 8xk 5 sk xk 表示第k年的产量 指标函数vkn 表示第k至5年的总产量 解 设阶段k 1 5表示第k年安排机器的过程 状态sk表示第k年初的完好机器台数 决策xk表示第k年投入高负荷的机器台数 则投入低负荷的台数为sk xk 状态转移sk 1 0 7xk 0 9 sk xk 2020 2 22 运筹学课件 f5 S5 是关于x5的单调增函数 x5 S5 f5 S5 8S5 2020 2 22 运筹学课件 5年的最大总产量为23 72 1000 23720 2020 2 22 运筹学课件 逆推解法的特点 始端已知 终端边界值取0或1 1 已知初始状态s12 最优值函数fk sk 表示第k阶段的初始状态为sk 从k阶段到n阶段的最优值 该问题的最优值f1 s1 3 边界条件是fn 1 0或者14 递推关系是fk sk opt vk fk 1 2020 2 22 运筹学课件 第四节动态规划应用举例本节将通过动态规划的四种应用类型 静态规划问题的动态规划求解 资源分配问题 复合系统可靠性问题 设备更新问题 进一步介绍动态规划的特点和处理方法 2020 2 22 运筹学课件 三阶段决策问题 状态变量Sk s1 s2 s3 s4决策变量为xi x1 x2 x3 例子 一 静态规划问题的动态规划求解 2020 2 22 运筹学课件 4 假定s1 4 用逆推法可分析每个阶段的状态转移 第3阶段 s3 x3第2阶段 s2 x2 s3第1阶段 s1 x1 s2 递推方程 每个阶段上决策变量的取值范围 2020 2 22 运筹学课件 2020 2 22 运筹学课件 2020 2 22 运筹学课件 2020 2 22 运筹学课件 4 假定s4 4 用顺推法可分析每个阶段的状态转移 第1阶段 s2 x1第2阶段 s3 x2 s2第3阶段 s4 x3 s3 递推方程 每个阶段上决策变量的取值范围 已知终止状态sn 1怎么求解动态规划 2020 2 22 运筹学课件 2020 2 22 运筹学课件 二 资源分配问题 1 问题的一般提法设有某种资源 总数量为a 用于生产n种产品 若分配数量xi用于生产第i种产品 其收益为gi xi 问应如何分配 可使总收益最大 2 数学规划模型 模型的特点 变量分离 2020 2 22 运筹学课件 3 用动态规划方法求解 阶段k状态sk决策xk 1 n表示把资源分配给第k种产品的过程 表示在给第k种产品分配之前还剩有的资源量 表示分配给第k种产品的资源量 状态转移sk 1 sk xk 阶段指标vk指标函数vkn 2020 2 22 运筹学课件 例3某公司拟将某种高效设备5台分配给所属甲 乙 丙3厂 各厂获此设备后可产生的效益如下表 问应如何分配 可使所产生的总效益最大 2020 2 22 运筹学课件 解 阶段k状态sk决策xk 1 2 3依次表示把设备分配给甲 乙 丙厂的过程 表示在第k阶段初还剩有的可分台数 表示第k阶段分配的设备台数 状态转移sk 1 sk xk 阶段指标vk指标函数vk3 问题 本问题是属于离散型还是属于连续型 怎样解 离散型 用表格的方式求解 2020 2 22 运筹学课件 3 012345 012345 046111212 0 04 06 011 012 012 0 046111212 012345 2020 2 22 运筹学课件 2 000 000 0 000 4155 0 51 0 000 6155 421010 0 102 0 000 11155 621010 431111 0 142 1 000 12155 1121010 631111 441111 0 161 32 2 000 12155 1221010 1131111 641111 451111 0 212 3 2020 2 22 运筹学课件 1 5 210 2 32 2 1 最优策略 P 13为0 2 3或2 2 1 即分给甲厂0台 分给乙厂2台 分给丙厂3台 或分给甲厂2台 分给乙厂2台 分给丙厂1台 最优值 f1 21 可见 最优解可以是不唯一的 但最优值是唯一的 2020 2 22 运筹学课件 资源分配问题的应用很广泛 例如 1 某学生正在备考4门功课 还剩7天时间 每门功课至少复习1天 若他已估计出各门功课的复习天数与能提高的分数之间的关系 问他应怎样安排复习时间可使总的分数提高最多 2 背包问题 旅行者携带的背包中能装的物品重量为a 现他要从n种物品中挑选若干数量装入背包 问他应如何挑选可使所带的物品总价值最大 2020 2 22 运筹学课件 其中 ci xi 表示携带数量为xi的价值函数 Wi表示第i种物品的单件重量 2020 2 22 运筹学课件 三 复合系统工作可靠性问题 1 问题的一般提法设某工作系统由n个部件串接而成 为提高系统的可靠性 在每个部件上装有备用件 已知部件i上装有xi个备用件时 其正常工作的概率为pi xi 每个部件i的备用件重量为wi 系统要求总重量不超过W 问应如何安排备用件可使系统可靠性最高 串接 2020 2 22 运筹学课件 2 数学规划模型 模型的特点 变量分离 3 用动态规划方法求解 2020 2 22 运筹学课件 阶段k状态sk决策xk 1 n表示安排第k个部件备用件的过程 表示在给第k个部件安排之前还剩有的容许重量 表示第k个部件上安排的备用件数量 状态转移sk 1 sk wkxk 阶段指标vk指标函数vkn 2020 2 22 运筹学课件 可靠性问题的应用很广泛 例如 1 某重要的科研攻关项目正在由3个课题组以3种不同的方式进行 各组已估计出失败的概率 为减少失败的概率 选派了2名高级专家去充实科研力量 若可估计出各组增加专家后的失败概率 问应如何分派专家可使总的失败概率最小 2 已知x1 x2 xn c 求z x1x2 xn的最大值 2020 2 22 运筹学课件 四 设备更新问题 例4某运输公司购进一批卡车投入运营 公司每年初需对卡车作出更新或继续使用的决定 假设第k年中 rk tk 表示车龄为tk的车使用一年的收入 uk tk 表示车龄为tk的车使用一年的维修费用 ck tk 表示车龄为tk的车更新成新车的费用 现公司需制定一个10年计划 以决定如何安排使10年的总收入最大 问题 状态和决策怎样设置 决策是更新与否 可用0 1变量表示 状态可设为车龄 2020 2 22 运筹学课件 阶段k状态sk决策xk 1 10表示第k年的决策过程 tk表示第k年的车龄 状态转移tk 1 tk 1 1 xk 阶段指标vk指标函数vkn rk tk uk tk ck tk xk 2020 2 22 运筹学课件 四 其他 随机型问题举例 例5某瓷厂接受订制一个瓷瓶的任务 瓷瓶用电炉烧制 据技术分析估计 每个瓷瓶出炉后的合格率为0 5 各瓶合格与否相互独立 即一炉如装有n个瓷瓶 那么出炉后都不合的概率为0 5n 制造一个瓷瓶的原料费为100元 烧一炉的费用为300元 现因厂中条件限制最多只能烧3炉 每炉最多装4个瓷瓶 若3炉的瓷瓶无1个合格 则因不能履行合同而被罚款1600元 试用动态规划方法确定一种生产方案 即每炉该装几个瓷瓶 使总的期望成本为最小 2020 2 22 运筹学课件 作业 9 19 11 2020 2 22 运筹学课件 采购与销售 某商店在未来的4个月里 准备用它的一个仓库来专门经销某种商品 仓库最大容量能贮存这种商品1000单位 假定该商店每月只能出卖仓库现有的货 当商店在某月购货时 下月初才能到货 预测该商品未来四个月的买卖价格如表7 12所示