[理学]运筹学4章.ppt

目 录 第一章 线性规划基础 第二章 线性规划专题 第三章 整数规划 第四章 动态规划 第五章 图与网络分析第六章 存储论 第四章 动态规划 多阶段决策问题 动态决策的基本要领和基本方程 动态规划应用举例 走一步看一步的结果与最短结果的比较 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数和最优值函数 动态规划的基本概念 概念 阶段 状态 决策 策略 状态转移方程 指标函数 最优指标函数 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法求最短路径（A-E） 逆推法原理 建立动态规划模型步骤 将问题的过程划分成为恰当的阶段 正确选择状态变量sk。使它既能描述过程的演变，又要满足无后效性 确定决策变量uk和每阶段的允许决策集合Dk(sk) 正确写出指标函数Ｖkn的关系，它满足三个性质： 建立动态规划模型步骤 正确写出指标函数Ｖkn的关系，它满足三个性质： 它是定义在全过程及其所有后部子过程上的数量函数； 它要有可分离性，并满足递推关系 函数f()对变量Ｖkn严格单调 建立实际问题基本方程构造步骤步骤 确定阶段指标函数Vkn 确定状态转移方程Sk+1 确定动态规划方程 fk*=(sk) 求解动态规划的方法 逆推法 根据边界条件从k=n开始，由后向前逆推，从而逐步可求得各段的最优决策和相应的最优值，最后求得f1(s1),得到整个问题最优解。 求解动态规划的方法 顺推法 根据边界条件从k=1开始，由前向后推，从而逐步可求得各段的最优决策和相应的最优值，最后求得fn(sn+1),得到整个问题最优解。 顺推法求最短路径（A-E） 顺推法求最短路径（A-E） 顺推法求最短路径（A-E） 顺推法求最短路径（A-E） 顺推法求最短路径（A-E） 顺推法求最短路径（A-E） 顺推法原理 动态规划与静态规划的关系 动态规划与静态规划的关系 逆推解法 S1已知; fk(sk)表示sk状态从第k阶段到n阶段的最大收益 逆推法例 max Z=x1x22x3 x1+x2+x3=c (c0) xi≥0 i=1,2,3 逆推法例 max Z=X1X22X3 x1+x2+x3=c (c0) Xi≥0 i=1,2,3 逆推法例 max Z=X1X22X3 x1+x2+x3=c (c0) Xi≥0 i=1,2,3 逆推法例 max Z=X1X22X3 x1+x2+x3=c (c0) Xi≥0 i=1,2,3 顺推解法 Sn+1已知; fk(sk)表示sk状态从第1阶段到k阶段的最大收益 顺推法例 max Z=4x12-x22+x32+12 3x1+2x2+x3≤9 xi≥0 i=1,2,3 顺推法例 max Z=4x12-x22+x32+12 3x1+2x2+x3≤9 xi≥0 i=1,2,3 3.动态规划应用 资源分配问题 max Z=g1(x1)+g2(x2)+…+gn(xn) x1+x2+…+xn=a (a0) Xi≥0 i=1,2,…,n 资源分配问题例1 资源分配问题例2 第四章小结 学习内容 多阶段决策问题 动态决策的基本要领和基本方程 动态规划的应用举例 动态规划的求解步骤 根据实际问题划分阶段 确定决策变量和允许决策集合 选择状态变量 确定状态转移方程 确定指标函数 利用逆推法和顺推法求解 1月生产？ 2月生产？ 3月生产？ 4月生产？ 1月初库存0 2月库存？ 3月库存？ 4月底库存0 1月需求2 2月需求3 3月需求2 4月需求4 库存容量3 生产能力6 生产与存储问题例 分为4个阶段 状态变量sk表示第k月初的库存 决策变量uk表示第k月的生产量 ak表示第k阶段的需求量 sk+1=sk+uk-ak ak-sk≤uk≤min(6，∑al-sk，3+ak-sk) 单位库存费用 0.5(千元) 每批固定成本 3 (千元) 单位生产成本 1 (千元) sk=0，1，2，3 生产时费用: d(s,u)=3+uk