《管理运筹学课件第9章-动态规划优秀PPT.ppt》由会员分享，可在线阅读，更多相关《管理运筹学课件第9章-动态规划优秀PPT.ppt（25页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第9章章 动态规划动态规划4/14/20231管理运筹学课件教学目标与要求教学目标与要求n【教学目标】【教学目标】n1.理解下列基本概念：状态变量，决策变量，策略，状态转移方程，指标函数和最优理解下列基本概念：状态变量，决策变量，策略，状态转移方程，指标函数和最优值函数值函数n2.理解动态规划的基本方程和最优化原理理解动态规划的基本方程和最优化原理n3.理解动态规划模型建立过程理解动态规划模型建立过程n5.驾驭依次算法与逆序算法解题方法驾驭依次算法与逆序算法解题方法n【学问结构】【学问结构】4/14/20232管理运筹学课件引例引例 马车驿站问题马车驿站问题12483353866786323
2、5AB2B1D2D1C3C2C4C1EA B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段44个阶段个阶段EED1D2D1D2D1D2D1D2C2C3C4C1C2C3 1D1E1D2E2C4D1 C4D22C3D1 C3D22C2D1 C2D22C1D1C1D23B2C2B2C3B2C43B1C1B1C2B1C3B1B22AB1AB2AB2B1C4C3C2C1D1D24321终点终点路线数路线数可选路线可选路线起点起点阶段阶段一共有一共有2321=12条不同的路途条不同的路途f(E)=0f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B
3、2)=11f(A)=13回顾分析过程回顾分析过程:1.将分析对象划分成将分析对象划分成4阶段阶段;2.每阶段始点状态与终点状态有关每阶段始点状态与终点状态有关,而而不考虑始终点状态如何形成不考虑始终点状态如何形成(无记忆性无记忆性);3.每阶段各始点状态为终点状态与始点每阶段各始点状态为终点状态与始点至终点距离之和的最小值至终点距离之和的最小值(状态转移状态转移)这种最优化方法称为动态规划这种最优化方法称为动态规划,由美国由美国数学家贝尔曼等人于数学家贝尔曼等人于20世纪世纪50年头创年头创立立.4/14/20233管理运筹学课件本章主要内容本章主要内容n9.1 动态规划的概念和原理动态规划的
4、概念和原理n9.1.1 动态规划的基本概念动态规划的基本概念n9.1.2 动态规划的最优化原理动态规划的最优化原理n9.2 动态规划的模型和求解动态规划的模型和求解n9.2.1 动态规划模型的建立动态规划模型的建立n9.2.2 动态规划问题的解法动态规划问题的解法n9.3 应用举例应用举例n案例案例1 资源安排问题资源安排问题n案例案例2 设备负荷问题设备负荷问题n案例案例3 生产库存问题生产库存问题n案例案例4 背包问题背包问题n本章小结本章小结4/14/20234管理运筹学课件9.1.1 动态规划的基本概念动态规划的基本概念1.阶段阶段:把所给问题的过程，把所给问题的过程，恰当地分为若干个
5、相恰当地分为若干个相互联系的阶段，以便互联系的阶段，以便能按确定的次序去求能按确定的次序去求解。描述阶段的变量解。描述阶段的变量称为阶段变量，常用称为阶段变量，常用k表示。表示。导入案例导入案例中中k=1,2,3,42.状态变量状态变量:每个阶段起先所处的自然状每个阶段起先所处的自然状况或客观条件况或客观条件(用点集表示用点集表示).如引例如引例:第第1阶段的状态就是起点阶段的状态就是起点A,记记为为s1=A;第第2阶段有阶段有2个状态个状态B1,B2,记为记为s2=B1,B2;第第3阶段有阶段有4个状态个状态C1,C2,C3,C4,记为记为s3=C1,C2,C3,C4;第第4阶段有阶段有2个
6、状态个状态D1,D2,记为记为s4=D1,D2;3.决策变量决策变量:在某一阶段的某个状态时的在某一阶段的某个状态时的不同选择不同选择,如引例中如引例中B1状态状态下有下有3种选择种选择:B1C1,B1C2,B1C3这这3种选择构成了允许决策种选择构成了允许决策的集合。不同状态下允许决的集合。不同状态下允许决策的集合也不同，故决策变策的集合也不同，故决策变量是状态变量的函数，即量是状态变量的函数，即xk(sk)D(sk)124833538667863235AB2B1D2D1C3C2C4C1E A B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段44个阶段个阶段4.策略策略按依次排列的决策组
7、成的集按依次排列的决策组成的集合，由过程的第合，由过程的第k阶段起先到阶段起先到终止状态为止的过程终止状态为止的过程(或或k子子过程过程),k子过程的策略称子策子过程的策略称子策略，记为略，记为Pk,n(sk),即即 Pk,n(sk)=xk(sk),xk+1(sk+1),xn(sn)当当k=1时，即为全过程的一时，即为全过程的一个策略。如引例中：个策略。如引例中：DE，即即4到到5过程起始有过程起始有2个状态，个状态，D1和和D2，因此有，因此有P4,5=D1E，D2E5.状态转移方程状态转移方程确定过程是由一个状态到另确定过程是由一个状态到另一个状态的演化过程。第一个状态的演化过程。第k阶阶
8、段状态变量值给定后，假如段状态变量值给定后，假如确定决策变量，第确定决策变量，第k+1阶段阶段状态变量值就完全确定。即：状态变量值就完全确定。即：sk+1=T(sk,xk)如引例中：若对如引例中：若对AB1,AB2选择了选择了AB1,则则s2=5,B1到到C有有3种选择种选择:B1C1、B1C2、B1C3，若选择，若选择了了B1C2,则则s3=s2+d(B1,C2)=86.指标函数指标函数用来衡量所实现过程优劣的用来衡量所实现过程优劣的一种数量指标。其基本方程一种数量指标。其基本方程有加法和乘法两种形式，通有加法和乘法两种形式，通常加法形式用的较多，其公常加法形式用的较多，其公式为：式为：7.
9、边界条件边界条件起始或终止条件。起始或终止条件。4/14/20235管理运筹学课件5.1.2 动态规划的基本原理动态规划的基本原理124833538667863235AB2B1D2D1C3C2C4C1EA B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段44个阶段个阶段最优化原理最优化原理(Optimality principle):最优策略具备这样的性质最优策略具备这样的性质:无论初无论初始状态与初始决策如何始状态与初始决策如何,以后诸决以后诸决策对以第一个决策所形成的状态作策对以第一个决策所形成的状态作为初始状态的过程而言为初始状态的过程而言,必定构成必定构成最优策策略最优策策略.通俗
10、地说通俗地说:最优策略的最优策略的子策略也是最优的子策略也是最优的.例如，在导入案例中，最优策略是例如，在导入案例中，最优策略是AB1C2D1E,最短距离为最短距离为13,其子策略其子策略:B1C2D1E,C2D1E,D1E也是最优的。也是最优的。依据这一原理，从后往前推各阶段依据这一原理，从后往前推各阶段最优子过程，从而得到全程最优过最优子过程，从而得到全程最优过程。程。设设f(i)表示从点表示从点i到终点到终点E的最短距的最短距离离,d(i,j)表示点表示点i,j之间的距离之间的距离.明显明显f(E)=0,为该问题的边界条件为该问题的边界条件.k=4决策：决策：D1Ek=3决策：决策：D2
11、E决策：决策：C1D1决策：决策：C2D1k=2决策：决策：C3D2决策：决策：C4D2决策：决策：B1C2决策：决策：B2C3k=1决策：决策：AB1最短路途最短路途:AB1C2D1E最短路长最短路长:134/14/20236管理运筹学课件5.1.2 动态规划的最优化原理动态规划的最优化原理4/14/20237管理运筹学课件9.2.1 动态规划模型的建立动态规划模型的建立解解 把生产第把生产第k种产品看成是第种产品看成是第k阶段，划分为阶段，划分为n个阶段个阶段.设设 sk表示第表示第k阶段初资源可用量（状态变量）阶段初资源可用量（状态变量）xk表示分配给第表示分配给第k阶段资源的数量（决策
12、变量），显然有：阶段资源的数量（决策变量），显然有：允许决策集合允许决策集合 sk+1=sk-xk （状态转移方程）（状态转移方程）s1=a （边界条件）（边界条件）指标函数：指标函数：若若fk(sk)表示数量为表示数量为sk资源分配给第资源分配给第k种产品时，从第种产品时，从第k阶段到第阶段到第n阶段总阶段总收益，则有：收益，则有：4/14/20238管理运筹学课件9.2.1 动态规划模型的建立动态规划模型的建立指标函数通常有两种形式：加法形式和乘法形式。指标函数通常有两种形式：加法形式和乘法形式。4/14/20239管理运筹学课件9.2.2 动态规划问题的解法动态规划问题的解法:逆序法逆序
13、法最优值函数最优值函数f(k):从从k阶段到阶段到E的最短距离；阶段指标函数的最短距离；阶段指标函数,即该阶段选择即该阶段选择不同路途的距离。从后向前推。不同路途的距离。从后向前推。S1=AS2=B1,B2S3=C1,C2,C3,C4S4=D1,D2S5=Ef5(E)=0同理 f4(D1)=2,f4(D2)=1同理 f3(C2)=5,f3(C3)=4,f3(c4)=5同理 f2(B2)=11124833538667863235AB2B1D2D1C3C2C4C1E A B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段44/14/202310管理运筹学课件9.2.2 动态规划问题的解法动态规划
14、问题的解法:依次法依次法124833538667863235AB2B1D2D1C3C2C4C1E A B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段4最优值函数最优值函数f(k):从从A到到k阶段的最短距离；阶段指标函数阶段的最短距离；阶段指标函数,即该阶段选择即该阶段选择不同路途的距离。从前向后推。不同路途的距离。从前向后推。S0=AS1=B1,B2S2=C1,C2,C3,C4S3=D1,D2S4=E最优值函数最优值函数:f0(A)=0f1(B1)=5,f2(B2)=3f2(C1)=7,f3(C2)=8,f3(C3)=10,f3(c4)=9f3(D1)=11,f4(D2)=134/14
15、/202311管理运筹学课件案例案例1 资源安排问题资源安排问题5台设备安排给台设备安排给3个工厂，盈利表如下，如何安排可使获利最大？个工厂，盈利表如下，如何安排可使获利最大？台数台数工厂工厂012345甲甲乙乙丙丙00045389711119111211111212分析分析 3个工厂看成个工厂看成3个阶段个阶段.阶段变量阶段变量 k(k=1,2,3)；状态变量状态变量 sk表示为分配给第表示为分配给第k个工厂至第个工厂至第n个工厂的设备台数；个工厂的设备台数；决策变量决策变量xk 表示分配给第表示分配给第k个工厂的设备台数；个工厂的设备台数；则有则有sk+1=sk-xk；Pk(xk)表示为表
16、示为xk 台设备分配到第台设备分配到第k个工厂所得赢利值；个工厂所得赢利值；fk(sk)表示为表示为 台设备分配给第台设备分配给第k个工厂至第个工厂至第n个工厂所得到的最大赢利值。个工厂所得到的最大赢利值。则有则有:4/14/202312管理运筹学课件k=3 x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2 x2s2P2(x2)+f3(s2-x2)f2(s2)x2*01234501234500+30+70+90+110+12 5+05+35+75+95+11 9+09+39+79+9 11+011+311+7 12+012+312
17、+0059121618 0121，222，3 k=1 x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211+911+511+0201，2，3012345甲甲乙乙丙丙00045389711119111211111212方案一方案一:1,2,2:1,2,2方案二方案二:2,1,2:2,1,2方案三方案三:2,2,1:2,2,1方案四方案四:3,2,0:3,2,04/14/202313管理运筹学课件案例案例2 设备负荷问题设备负荷问题n某种机器可在凹凸两种不同的负荷下进行生产，设机器在某种机器可在凹凸两种不同的负荷下进行生产，设机器在高负荷下生产的产量
18、函数为高负荷下生产的产量函数为g=9x，其中，其中x为投入生产的机为投入生产的机器数量，季度完好率为器数量，季度完好率为a=0.65，在低负荷下生产的产量函，在低负荷下生产的产量函数为数为h=4y，其中，其中y为投入生产的机器数量，季度完好率为为投入生产的机器数量，季度完好率为b=0.95。设资源拥有量。设资源拥有量100.n解解 4季度看成季度看成4阶段阶段sk第第k季初拥有完好机器数季初拥有完好机器数xk第第k季安排给高负荷机器数季安排给高负荷机器数,则低负荷安排数则低负荷安排数sk-xk下季度初完好机器数下季度初完好机器数sk+1=0.65xk+0.95(sk-xk)第第k季产量季产量v
19、k=6xk+4(sk-xk)4/14/202314管理运筹学课件k=4=4f4 是是x4 的增函数的增函数,故最大故最大值值解解为为 x4*=s4,相相应应地有地有 f4(s4)=9s4k=3=3f3 是是x3 的增函数的增函数,故最大故最大值值解解为为 x3*=s3,相相应应地有地有 f3(s3)=14.85s34/14/202315管理运筹学课件k=2=2f2 是是x2 的增函数的增函数,故最大故最大值值解解为为 x2*=s2,相相应应地有地有 f2(s2)=18.6525s2k=1 1f1 是是x1 的减函数的减函数,故最大故最大值值解解为为 x1*=0,相相应应地有地有 f1(s1)=
20、21.719875s1=2172反向推算，由s1=100，x1=0，知s2=95，x2=95，s3=61.75，x3=61.75，s4=40.14，x4=40.14，s5=26.09。即第1季度设备100%全部安排给低负荷第2季度初完好设备为95%，全部安排给高负荷第3季度完好设备为61.75%，全部安排给高负荷第4季度完好设备为40.14%，全部安排给高负荷。全年结束后，设备完好率为26.09%.最大产量2172。4/14/202316管理运筹学课件Lingo程序model:sets:JD/1.4/:s,x,v;!定义状态变量、决策变量和指标函数;ZB/1.5/:f;!定义最优值函数;end
21、setsf(5)=0;!初始化最优值函数;s(1)=100;!初始化状态变量;for(jd:x=s);!决策变量取值限制;for(jd(k)|k#lt#4:s(k+1)=0.65*x(k)+0.95*(s(k)-x(k););!状态转移方程;for(jd(k):v(k)=9*x(k)+4*(s(k)-x(k);!指标函数表达式;for(zb(k)|k#lt#5:f(k)=v(k)+f(k+1););!基本方程;max=f(1);!目标;end4/14/202317管理运筹学课件案例案例3 生产库存问题生产库存问题4/14/202318管理运筹学课件案例案例3 生产库存问题生产库存问题4/14/
22、202319管理运筹学课件案例案例3 生产库存问题生产库存问题4/14/202320管理运筹学课件案例案例3 生产库存问题生产库存问题阶段阶段12345需求需求/dk23243逆推逆推:f5=26.5,s5=0,x5*=0 或或 3s4=3 x4*=6s4=0 x4*=0s3=1 s3=4 x3*=0 或或 3x3*=6s2=3 s2=0 s2=0 x2*=6 x2*=0 x2*=0s1=0 x1*=2s1=3 x1*=5s1=3 x1*=54/14/202321管理运筹学课件案例案例4 背包问题背包问题4/14/202322管理运筹学课件案例案例4 背包问题背包问题4/14/202323管理
23、运筹学课件案例案例4 背包问题背包问题背包重背包重345价值价值456最最优优方案方案:依次装依次装2,1,0个个最大价最大价值值:134/14/202324管理运筹学课件本章小结本章小结n本本章章介介绍绍了了动动态态规规划划的的基基本本概概念念、基基本本原原理理和和几几种种典典型型的的应应用用问问题题。要求要求n1 1）理解动态规划的核心概念）理解动态规划的核心概念n状状态态与与状状态态变变量量、决决策策与与决决策策变变量量、策策略略、状状态态转转移移方方程程、指指标标函函数数和最优值函数。和最优值函数。n2 2）理解动态规划的最优化原理：一个最优策略的子策略总是最优的。）理解动态规划的最优
24、化原理：一个最优策略的子策略总是最优的。n3 3）动态规划模型的建立和求解）动态规划模型的建立和求解n一般的，给一个实际问题建立动态规划模型时，必需做到下面五点。一般的，给一个实际问题建立动态规划模型时，必需做到下面五点。n(1)(1)将问题的过程划分成适当的阶段。将问题的过程划分成适当的阶段。n(2)(2)正确选择状态变量，使它既能描述过程的演化，又满足无后效性。正确选择状态变量，使它既能描述过程的演化，又满足无后效性。n(3)(3)确定决策变量及每阶段的允许决策集合。确定决策变量及每阶段的允许决策集合。n(4)(4)正确写出状态转移方程即。正确写出状态转移方程即。n(5)(5)正确写出指标函数的关系。正确写出指标函数的关系。n动态规划模型的求解有两种方法：逆序解法和依次解法。动态规划模型的求解有两种方法：逆序解法和依次解法。n4 4）动态规划的应用）动态规划的应用n驾驾驭驭动动态态规规划划在在最最短短路路途途问问题题、资资源源安安排排问问题题、生生产产库库存存问问题题、背背包包问题求法。问题求法。4/14/202325管理运筹学课件