管理运筹学动态规划ppt课件

1、第第9章章 动态规划动态规划教学目的与要求教学目的与要求n【教学目的】n1. 了解以下根本概念：形状变量，决策变量，战略，形状转移方程，目的函数和最优值函数n2. 了解动态规划的根本方程和最优化原理n3. 了解动态规划模型建立过程n5. 掌握顺序算法与逆序算法解题方法n【知识构造】 模型：最短路问题、一维资源分配问题、模型：最短路问题、一维资源分配问题、 设备负荷问题、生产存贮问题设备负荷问题、生产存贮问题 概念：基本概念、基本方程和最优化原理概念：基本概念、基本方程和最优化原理 算法：顺序算法、逆序算法算法：顺序算法、逆序算法 计算机解法（计算机解法（Lingo,WinQSB 或或 Exce

2、l） 知识知识目标目标 管理管理 问题问题 技能技能目标目标 引例引例 马车驿站问题马车驿站问题124833538667863235AB2B1D2D1C3C2C4C1EA B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段44个阶段个阶段EED1D2D1D2D1D2D1D2C2C3C4C1C2C3 1D1E1D2E2C4D1 C4D22C3D1 C3D22C2D1 C2D22C1D1C1D23B2C2B2C3B2C43B1C1B1C2B1C3B1B22AB1AB2AB2B1C4C3C2C1D1D24321终点道路数可选道路起点阶段一共有一共有2321=12条不同的道路条不同的道路f(E)=0

3、f(D1)=2f(D2)=1f(C1)=8f(C2)=5f(C3)=4f(C1)=5f(B1)=8f(B2)=11f(A)=13回想分析过程回想分析过程:1.将分析对象划分成将分析对象划分成4阶段阶段;2.每阶段始点形状与终点形状有关每阶段始点形状与终点形状有关,而而不思索一直点形状如何构成不思索一直点形状如何构成(无记忆性无记忆性);3.每阶段各始点形状为终点形状与始点每阶段各始点形状为终点形状与始点至终点间隔之和的最小值至终点间隔之和的最小值(形状转移形状转移)这种最优化方法称为动态规划这种最优化方法称为动态规划, 由美国由美国数学家贝尔曼等人于数学家贝尔曼等人于20世纪世纪50年代创年代

4、创建建.本章主要内容本章主要内容n9.1 动态规划的概念和原理动态规划的概念和原理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本章小结本章小结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

6、,C2,C3,C4;第第4阶段有阶段有2个形状个形状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

7、个阶段个阶段4.战略战略按顺序陈列的决策组成的集按顺序陈列的决策组成的集合，由过程的第合，由过程的第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.形状转移方程形状转移方程确定过程是由一个形状到另确定过程是由一个形状到另一个形状

8、的演化过程。第一个形状的演化过程。第k阶段形状变量值给定后，假阶段形状变量值给定后，假设确定决策变量，第设确定决策变量，第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.目的函数目的函数用来衡量所实现过程优劣的用来衡量所实现过程优劣的一种数量目的。其根本方程一种数量目的。其根本方程有加法和乘法两种方式，通有加法和乘法两种方式，通常加法

9、方式用的较多，其公常加法方式用的较多，其公式为：式为：,111( , ,.,)( , )nk nkkkniiiiVs x ssv s x7.边境条件边境条件起始或终止条件。起始或终止条件。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之间的间隔之间的

11、间隔.显然显然f(E)=0,为该问题的边境条件为该问题的边境条件.k=411()( )(,)022f Df Ed D E1()2f D决策：决策：D1E1111212()(,)()min()(,)26min81 8f Dd C Df Cf Dd C D22()( )(,)0 11f Df Ed D E k=32()1f D决策：决策：D2E1()8f C决策：决策：C1D12()5f C决策：决策：C2D11212222()(,)()min()(,)23min51 5f Dd CDf Cf Dd CD1313232()(,)()min()(,)23min41 3f Dd C Df Cf Dd

12、C Dk=23()4f C决策：决策：C3D21414242()(,)()min()(,)28min514f Dd CDf Cf Dd CD4()5f C决策：决策：C4D21111212313()(,)()min()(,)()(,)82min 53846f Cd B Cf Bf Cd B Cf Cd B C1()8f B决策：决策：B1C22122313414()(,)()min()(,)()(,)58min 471156f Cd B Cf Bf Cd B Cf Cd B C1122()( ,)( )min()( ,85min1311 3f Bd A Bf Af Bd A B2()11f B

13、决策：决策：B2C3k=1( )13f A 决策：决策：AB1最短道路最短道路:AB1C2D1E最短路长最短路长:135.1.2 动态规划的最优化原理动态规划的最优化原理9.2.1 动态规划模型的建立动态规划模型的建立解解 把消费第把消费第k种产品看成是第种产品看成是第k阶段，划分为阶段，划分为n个阶段个阶段.设设 sk表示第表示第k阶段初资源可用量形状变量阶段初资源可用量形状变量 xk表示分配给第表示分配给第k阶段资源的数量决策变量，显然有：阶段资源的数量决策变量，显然有： 允许决策集合允许决策集合 sk+1=sk-xk 形状转移方程形状转移方程 s1=a 边境条件边境条件 目的函数：目的函

14、数：假设假设fk(sk)表示数量为表示数量为sk资源分配给第资源分配给第k种产品时，从第种产品时，从第k阶段到第阶段到第n阶阶段总收益，那么有：段总收益，那么有：10()max()(),()max()kknnkkkkkkkxsnnnnxsfsgxfsxknfsgx()0kkkkkD sxxs,( )nk niii kVg x9.2.1 动态规划模型的建立动态规划模型的建立目的函数通常有两种方式：加法方式和乘法方式。目的函数通常有两种方式：加法方式和乘法方式。,( )nk niii kVg x( )nk,niii kVg x9.2.2 动态规划问题的解法动态规划问题的解法:逆序法逆序法最优值函数

15、最优值函数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)=114115()min(,)( )202fDd D EfE1141311141(,)()62()minmin8(,)()8 1d C DfDf Cd C DfD1211222( ,)()58( )minmin13( ,)(

16、)3 11d A BfBf Ad A BfB11312112321333(,)()28()min(,)()min 35864(,)()d B Cf CfBd B Cf Cd B Cf C124833538667863235AB2B1D2D1C3C2C4C1E A B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段49.2.2 动态规划问题的解法动态规划问题的解法:顺序法顺序法124833538667863235AB2B1D2D1C3C2C4C1E A B C D E阶段阶段1阶段阶段2阶段阶段3阶段阶段4最优值函数最优值函数f(k):从从A到到k阶段的最短间隔；阶段目的函数阶段的最短间隔；阶

17、段目的函数,即该阶段选择即该阶段选择不同道路的间隔。从前向后推。不同道路的间隔。从前向后推。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)=131110()min(, )( )505f Bd B AfA112121223131234124(,)()67(,)()38()minmin11(,)()3 1089(,)()d C Df Cd CDf CfDd C Df Cd CDf C1314232

18、(,)()2 11( )minmin13(,)()1 13d D EfDfEd D EfD211111()min(,)()min 257f Cd B Cf B案例案例1 资源分配问题资源分配问题5台设备分配给台设备分配给3个工厂，盈利表如下，如何分配可使获利最大？个工厂，盈利表如下，如何分配可使获利最大？ 台数台数工厂工厂012345甲甲乙乙丙丙00045389711119111211111212分析分析 3个工厂看成个工厂看成3个阶段个阶段.阶段变量阶段变量 k(k=1,2,3)；形状变量形状变量 sk表示为分配给第表示为分配给第k个工厂至第个工厂至第n个工厂的设备台数；个工厂的设备台数；决

19、策变量决策变量xk 表示分配给第表示分配给第k个工厂的设备台数；个工厂的设备台数；那么有那么有sk+1=sk-xk；Pk(xk)表示为表示为xk 台设备分配到第台设备分配到第k个工厂所得赢利值；个工厂所得赢利值；fk(sk)表示为表示为 台设备分配给第台设备分配给第k个工厂至第个工厂至第n个工厂所得到的最大赢利个工厂所得到的最大赢利值。那么有值。那么有:1044()max ()()3,2,1( )0kkkkkkkkkxsfsP xfsxkf sk=3 x3s3P3(x3)f3(s3)x3*0123450123450379111203791112012345k=2 x2s2P2(x2)+f3(s

20、2-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+0059121618 0121，222，3 k=1 x1s1P1(x1)+f2(s1-x1)f1(s1)x1*01234550+184+168+1211+911+511+0201，2，3012345甲甲乙乙丙丙000453897111191112111112121044()max ()()3,2,1( )0kkkkkkkkkxsfsP xfsxkf s1kkkssx方案一方案一:1,2,2:1,2,

21、2方案二方案二:2,1,2:2,1,2方案三方案三:2,2,1:2,2,1方案四方案四:3,2,0:3,2,0案例案例2 设备负荷问题设备负荷问题n某种机器可在高低两种不同的负荷下进展消费，设机器在某种机器可在高低两种不同的负荷下进展消费，设机器在高负荷下消费的产量函数为高负荷下消费的产量函数为g=9x，其中，其中x为投入消费的机为投入消费的机器数量，季度完好率为器数量，季度完好率为a=0.65，在低负荷下消费的产量函，在低负荷下消费的产量函数为数为h=4y，其中，其中y为投入消费的机器数量，季度完好率为为投入消费的机器数量，季度完好率为b=0.95。设资源拥有量。设资源拥有量100.n解解

22、4季度看成季度看成4阶段阶段sk第第k季初拥有完好机器数季初拥有完好机器数xk第第k季分配给高负荷机器数季分配给高负荷机器数,那么低负荷分配数那么低负荷分配数sk-xk下季度初完好机器数下季度初完好机器数sk+1=0.65xk+0.95(sk-xk)第第k季产量季产量vk=6xk+4(sk-xk)11()55()max()1,2,3,4()0kkkkkkkkxDsfsvfskfs111()5564()0.650.95()(0)()max()(1,2,3,4)()0kkkkkkkkkkkkkkkkkkxDsvxsxsxsxxsfsvfskf s44444444444544404440440( )

23、max 94()0.650.95()max 94()max 54xsxsxsf sxsxfxsxxsxxs 33333333333433303333330330( )max 94()0.650.95()max 94()9 0.650.95()max 2.312.55xsxxsf sxsxfxsxxsxxsxxs sk=4f4 是x4 的增函数,故最大值解为 x4*=s4,相应地有 f4(s4)=9s4k=3f3 是x3 的增函数,故最大值解为 x3*=s3,相应地有 f3(s3)=14.85s322222222222322202222220220( )max 94()0.650.95()max

24、 94() 14.85(0.650.95()max 0.54518.1075xsxsxsf sxsxfxsxxsxxsxxs11111111411101111110110( )max94()0.650.95()max94() 18.6525 0.650.95()max0.5957521.719875xxxf sxsxfxsxxsxxsxxs 100 100 100k=2f2 是x2 的增函数,故最大值解为 x2*=s2,相应地有 f2(s2)=18.6525s2k=1f1 是x1 的减函数,故最大值解为 x1*=0,相应地有 f1(s1)=21.719875s1=2172反向推算，由s1=10

25、0，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。Lingo程序model:sets:JD/1.4/:s,x,v;!定义形状变量、决策变量和目的函数;ZB/1.5/:f;!定义最优值函数;endsetsf(5)=0;!初始化最优值函数;s(1)=100;!初始化形状变量;for(j

26、d: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);!目的;end案例案例3 消费库存问题消费库存问题案例案例3 消费库存问题消费库存问题案例案例3 消费库存问题消费库存问题案例案例3 消费库存问题消费库存问题阶段阶段12345需求需求/dk 23243逆推逆推: f5 =26.5, s5=0, x5*=0 或或 3s4=3 x4*=6s4