江西财经大学:《运筹学》课程教学资源(PPT课件)第五章 动态规划 Dynamic programming

CPOSIS AND 邮电大生 管理与人文学院忻展红 1999,4 第五章动态规划 不要过河拆桥
©管理与人文学院 忻展红 1999,4 第五章 动态规划 不要过河拆桥

动态规划 Dynamic programming 五十年代贝尔曼(B.E. Bellman)为代表的研究成果 属于现代控制理论的一部分 以长远利益为目标的一系列决策 最优化原理,可归结为一个递推公式 51动态规划的最优化原理及其算法23 511求解多阶段决策过程的方法 例5.1.1最短路问题
2 动态规划 Dynamic programming • 五十年代贝尔曼(B. E. Bellman)为代表的研究成果 • 属于现代控制理论的一部分 • 以长远利益为目标的一系列决策 • 最优化原理,可归结为一个递推公式 5.1 动态规划的最优化原理及其算法 5.1.1 求解多阶段决策过程的方法 例5.1.1 最短路问题 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2

决策树法 可以枚举出20条路径,其中最短的路径长度为16
3 决策树法 A C E H I I F J I F D G J J K 可以枚举出20条路径,其中最短的路径长度为16

例5.1.1最短路题 表现为明显的阶段性 一条从A到B的最短路径 中的任何一段都是最短的 3 10 设S表示由点到B点的最短路 径的长度 则有S4=min dac +sc AD+S 8 因此我们可以从B向回搜索最短路 标记法 6 °如何找出最短路径 最优性原理 最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关6⊥54⊥3121阶 而与如何达到这一状态无关
4 例5.1.1 最短路问题 • 表现为明显的阶段性 • 一条从A 到B 的最短路径 中的任何一段都是最短的 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 H L O B I E C A F D J G K N P M 4 3 5 2 3 5 2 3 4 4 7 7 1 1 3 4 2 2 2 5 4 8 1 2 1 6 1 2 1 4 0 2 1 4 5 7 1 0 8 6 7 1 1 8 9 6 5 4 3 2 1 阶 段 最优性原理 “最优策略的一部分也是最优的” 每步的决策只与相邻阶段状态有关, 而与如何达到这一状态无关 + + = AD D AC C A i d S d S S S i B 则有 min 径的长度 设 表示由 点到 点的最短路 •因此我们可以从B向回搜索最短路 •标记法 •如何找出最短路径

512动态规划的基本概念及递推公式 状态(每阶段初始的出发点) 最短路问题中,各个节点就是状态 生产库存问题中,库存量是状态 物资分配问题中,剩余的物资量是状态 控制变量(决策变量) 最短路问题中,走哪条路 生产库存问题中,各阶段的产品生产量 物资分配问题中,分配给每个地区的物资量 阶段的编号与递推的方向 一般采用反向递推,所以阶段的编号也是逆向的 当然也可以正向递推
5 5.1.2 动态规划的基本概念及递推公式 • 状态(每阶段初始的出发点) – 最短路问题中,各个节点就是状态 – 生产库存问题中,库存量是状态 – 物资分配问题中,剩余的物资量是状态 • 控制变量(决策变量) – 最短路问题中,走哪条路 – 生产库存问题中,各阶段的产品生产量 – 物资分配问题中,分配给每个地区的物资量 • 阶段的编号与递推的方向 – 一般采用反向递推,所以阶段的编号也是逆向的 – 当然也可以正向递推

动态规划的步骤 1、确定问颕的阶段和编号 2、确定状态变量 用Sk表示第k阶段的状态变量及其值 3、确定决策变量 用xk表示第k阶段的决策变量,并以xk°表示该阶段的最优 决策 4、状态转移方程 sk1=g(Sx)反向编号s+1=g(S,x)正向编号 5、直接效果 直接一步转移的效果dA(S,x) 6、总效果函数 指某阶段某状态下到终端状态的总效果,它是一个递推公式 fK(Sk,xk)=h(dk(sk,xk),fk-sk-ixk-)
6 动态规划的步骤 1、确定问题的阶段和编号 2、确定状态变量 – 用 Sk 表示第 k 阶段的状态变量及其值 3、确定决策变量 – 用 xk 表示第 k 阶段的决策变量,并以 xk *表示该阶段的最优 决策 4、状态转移方程 sk-1= g(sk , xk ) 反向编号 sk+1= g(sk , xk ) 正向编号 5、直接效果 – 直接一步转移的效果 dk (sk , xk ) 6、总效果函数 – 指某阶段某状态下到终端状态的总效果,它是一个递推公式 ( , ) ( ( , ), ( , )) 1 1 1 k k k = k k k k k− k− k− f s x h d s x f s x

动态规划的步骤 hk是一般表达形式,求当前阶段当前状态下的阶段最优 总效果 (1)如最短路问题,是累加飛式,此时有 fE(SE, *i)=mind (Sk, *R)+R&(Sk1, *RDI dk(sk, xk)+fr(g(sk, xk),xki 终端的边际效果一般为f(S0,x)=0 (2)如串联系统可靠性问题,是连乘形式,此时有 fE(k, *R)=max, (Sk,*k).fR(SkI, *gl fri(a(sk,xk),xki 终端的边际效果一般为f6(s0x0)=1 从第1阶段开始,利用边际效果和边界条件,可以递推到最后 阶段
7 动态规划的步骤 – hk 是一般表达形式,求当前阶段当前状态下的阶段最优 总效果 (1) 如最短路问题,是累加形式,此时有 终端的边际效果一般为 f0 (s0 , x0 )=0 (2)如串联系统可靠性问题,是连乘形式,此时有 终端的边际效果一般为 f0 (s0 ,x0 )=1 从第1阶段开始,利用边际效果和边界条件,可以递推到最后 阶段

52动态规划模型举例 521产品生产计划安排问题 例1某工厂生产某种产品的月生产能力为10件,已知今后四个月 的产品成本及销售量如表所示。如果本月产量超过销售量时,可 以存储起来备以后各月销售,一件产品的月存储费为2元,试安排 月生产计划并做到: 1、保证满足每月的销售量,并规定计划期初和期末库存为零 2、在生产能力允许范围内,安排每月生产量计划使产品总成本 (即生产费用加存储费)最低。 月份阶段产品成本月销售量月初库存月末库存 ck/件 Jk k-1 4 70 6 S4=0 2 3 72 7 3 2 80 12 76 6 S=0
8 5.2 动态规划模型举例 5.2.1 产品生产计划安排问题 例1 某工厂生产某种产品的月生产能力为10件,已知今后四个月 的产品成本及销售量如表所示。如果本月产量超过销售量时,可 以存储起来备以后各月销售,一件产品的月存储费为2元,试安排 月生产计划并做到: 1、保证满足每月的销售量,并规定计划期初和期末库存为零; 2、在生产能力允许范围内,安排每月生产量计划使产品总成本 (即生产费用加存储费)最低

例1产品生产计划安排 设x为第k阶段生产量,则有直接成本 dk(sk, xk=CKxk+2Sk 状态转移公式为 Str 总成本递推公式 (s,x)=mn(,x)+1(1,x1 第一阶段:(即第4月份) 由边界条件和状态转移方程s0=s1+x1-y1=s1+x1-6=0得 s1+x=6或x1=6-s120 估计第一阶段,即第4月份初库存的可能状态: 0≤s1≤30-6-7-12=5,所以,s1∈[0,5
9 例1 产品生产计划安排 • 设xk为第k阶段生产量,则有直接成本 dk (sk , xk )= ck xk+2sk • 状态转移公式为 sk-1= sk+ xk - yk • 总成本递推公式 第一阶段:(即第4月份) 由边界条件和状态转移方程 s0=s1+x1−y1= s1+x1−6=0 得 s1+x1= 6 或 x1= 6−s10 估计第一阶段,即第4月份初库存的可能状态: 0 s1 30−6−7−12=5,所以, s1 [0,5]

第一阶段最优决策表 第二阶段:最大可能库存量7件 f1(S1,x1) 由状态转移方程:s1=2+x2-1220及 s—012345 6 456 382 x2≤10,可知s2∈[12,7],minx2=5 5432 308 白阶段效果递推公式有: 234 f2(2,10)=d2(2,10)+f12(0,6) 160 =2×2+80×10+456=1260 86 得第二阶段最优决策表,如下 5 6 8 910|x2*|f2(S2yx2) 1260*101260 23456 18211891182 110411011681104 1026510321038^104471026 948×9549609669726948 78708768828888949005 870 s1=0s1=1s1=2s1=3s1=4s1
10 第一阶段最优决策表 s1 x1 f1 (s1 , x1 ) 0 6 456 1 5 382 2 4 308 3 3 234 4 2 160 5 1 8 6 第二阶段:最大可能库存量 7 件 由状态转移方程: s1=s2+x2−120 及 x210,可知 s2[2,7],min x2=5 由阶段效果递推公式有: f2 (2,10)=d2 (2,10)+f1*(0,6) =22+8010+456=1260 得第二阶段最优决策表,如下 s2 x2 5 6 7 8 9 1 0 x2 * f2 (s2 ,x2 * ) 2 1260* 1 0 1260 3 1182* 1188 9 1182 4 1104* 1110 1116 8 1104 5 1026* 1032 1038 1044 7 1026 6 948* 954 960 966 972 6 948 7 870* 876 882 888 894 900 5 870 s1 = 0 s1 = 1 s1 = 2 s1 = 3 s1 = 4 s1 = 5
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第九章 特殊随机服务系统.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第三章 运输问题——数学模型及其解法.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.4)随机变量函数的分布.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.3)连续型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.2)离散型随机变量.ppt
- 湖南商学院:《概率论》课程教学资源(PPT课件)第二章 随机变量及其分布(2.1)随机变量的定义.ppt
- 《数学史》数学物理.ppt
- 《数学史》世界数学点点.ppt
- 浙江大学:《数学史》廿一世纪的数学展望.ppt
- 香港中文大学:《数学史》几何三十载.ppt
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——目录.pdf
- 《数理统计和质量保证》教学资源(参考书籍)PDF电子版——正文(共十章).pdf
- 《线性代数智能CAI》电子教案:线性方程组的解.ppt
- 西南交通大学数学系:《数学模型与LINGO软件》.pdf
- 《统计分布》教学资源(书籍文献)目录.doc
- 《统计分布》教学资源(书籍文献)目录.pdf
- 《统计分布》教学资源(书籍文献)正文(共六章).pdf
- 河海大学:《概率论与数理统计》课程教学资源(PPT课件讲稿,共五章,主讲:印凡成).ppt
- 河海大学:《概率论》概率论与数理统计综合练习2004.doc
- 河海大学:《概率论》习题20解答(或答案).doc
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第八章 标准服务系统(M/M/n系统).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(2/2).ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析(1/2).ppt
- 江西财经大学:《运筹学》课程教学资源_作业题集.doc
- 江西财经大学:《运筹学》课程教学资源_教学大纲.doc
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(2/2)2.4 线性规划的灵敏度分析 2.5 参数线性规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第十章 存储理论 Inventory Theory.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第四章 整数规划.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第二章 线性规划的对偶理论及其应用(1/2)2.1 线性规划的对偶理论 2.2 线性规划的对偶定理 2.3 对偶单纯型算法.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第六章 图与网路分析 6.1 图与网路的基本概念 6.2 树图与最小生成树 6.3 最短路问题 6.4 网路的最大流和最小截 6.5 欧拉回路和中国邮递员问题 6.6 哈密尔顿回路及旅行推销员问题 6.7 选址问题.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)第七章 随机服务理论概述.ppt
- 江西财经大学:《运筹学》课程教学资源(PPT课件)绪论(忻展红).ppt
- 江西财经大学:《运筹学》课程教学资源(案例)DEC 的短期制造问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)SYTECH 公司的生产优化问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)里尤尼亚的外购问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)投资基金最佳使用计划.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)项目选择问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)跨国投资问题.pdf
- 江西财经大学:《运筹学》课程教学资源(案例)两辆铁路平板车的装货问题.pdf