ychx4运筹学4.ppt

运筹学 动态规划 动态规划的概念与模型 静态决策 一次性决策 多段决策过程 具有无后效性的多段决策过程 K后部子过程 动态规划模型 动态规划的建模 动态规划的建模 动态规划的建模 动态规划的建模 动态规划解的概念 动态规划最优性原理 动态规划最优性原理 动态规划最优性原理 贝尔曼函数 贝尔曼函数 贝尔曼函数 动态规划基本方程 动态规划基本方程 动态规划基本方程 动态规划方法基本原理 动态规划问题求解的一般步骤 动态规划问题求解的一般步骤 动态规划问题求解的一般步骤 动态规划问题求解的一般步骤 动态规划问题求解的一般步骤 动态规划问题求解的一般步骤 动态规划四大要素、一个方程 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----定步数问题 动态规划应用举例----不定步数问题 动态规划应用举例----不定步数问题 不定步数问题----函数迭代法 不定步数问题----函数迭代法 不定步数问题----函数迭代法 不定步数问题----函数迭代法 不定步数问题----策略迭代法 不定步数问题----策略迭代法 不定步数问题----策略迭代法 不定步数问题----策略迭代法 不定步数问题----策略迭代法 不定步数问题----策略迭代法 资源分配问题 资源分配问题 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多元分配 资源的多段分配 资源的多段分配 资源的多段分配 资源的多段分配 资源的多段分配 资源的多段分配 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 串联系统可靠性问题 生产－库存问题 生产计划周期分为n个阶段，即k=1~n； 已知最初库存量为x1； 阶段需求量为dk； 单位产品的消耗费用为Lk； 单位产品的阶段库存费用为hk； 仓库容量为Mk； 阶段生产能力为Bk； 生产的准备费用为： 生产－库存问题 生产－库存问题 生产－库存问题 生产－库存问题举例 例4－5 求解生产－库存问题。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计划周期末期的库存量为0），Bk＝6，d1=3，d2=4，d3=3。 生产－库存问题举例 例4－5 求解生产－库存问题。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计划周期末期的库存量为0），Bk＝6，d1=3，d2=4，d3=3。 生产－库存问题举例 例4－5 求解生产－库存问题。已知其n=3，ck=8，Lk=2，hk=1.5，x1=1，Mk=4，x4=0（计划周期末期的库存量为0），Bk＝6，d1=3，d2=4，d3=3。 生产－库存问题举例 生产－库存问题举例 生产－库存问题举例 生产－库存问题举例 二维背包问题 背包问题的特征类似于往旅行背包里面装用品的问题，要求在旅行袋容积和／或载重量的限制下，所装物品的总价值最大。这一类问题在海运、航运以及航天等领域都有应用。 若只考虑重量或体积限制，则称为一维背包问题，若同时考虑重量和体积限制，则称为二维背包问题。 考虑有N种物品需要装船。第i种物品单位的重量为ωi，单件体积为υi，而价值为pi。最大的装载重量为W，最大体积为V。现在要确定在不超过船的最大载重量和最大体积（不考虑货物形状）的条件下，使所载物品价值最大的装载方案。 二维背包问题 例4－6 已知货物的单位重量ωi，单位体积υi及价值pi如表所示，船的最大载重能力为W＝5，最大装载体积为V＝8，求最优装载方案。 二维背包问题 例4－6 W＝5，V＝8 二维背包问题 例4－6 W＝5，V＝8 二维背包问题 二维背包问题 二维背包问题 二维背包问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 设备更新问题 习题 65 3 2 3 80 4 3 2