管理运筹学课件第9章动态规划.ppt

第9章 动态规划,课件,2,2023/11/4,教学目标与要求,【教学目标】1.理解下列基本概念：状态变量，决策变量，策略，状态转移方程，指标函数和最优值函数2.理解动态规划的基本方程和最优化原理3.理解动态规划模型建立过程5.掌握顺序算法与逆序算法解题方法【知识结构】,课件,3,2023/11/4,引例 马车驿站问题,E,E,D1D2,D1D2,D1D2,D1D2,C2C3C4,C1C2C3,1,D1E,1,D2E,2,C4D1 C4D2,2,C3D1 C3D2,2,C2D1 C2D2,2,C1D1C1D2,3,B2C2B2C3B2C4,3,B1C1B1C2B1C3,B1B2,2,AB1AB2,A,一共有2321=12条不同的路线,f(E)=0,f(D1)=2,f(D2)=1,f(C1)=8,f(C2)=5,f(C3)=4,f(C1)=5,f(B1)=8,f(B2)=11,f(A)=13,回顾分析过程:1.将分析对象划分成4阶段;2.每阶段始点状态与终点状态有关,而不考虑始终点状态如何形成(无记忆性);3.每阶段各始点状态为终点状态与始点至终点距离之和的最小值(状态转移)这种最优化方法称为动态规划,由美国数学家贝尔曼等人于20世纪50年代创立.,课件,4,2023/11/4,本章主要内容,9.1 动态规划的概念和原理9.1.1 动态规划的基本概念9.1.2 动态规划的最优化原理9.2 动态规划的模型和求解9.2.1 动态规划模型的建立9.2.2 动态规划问题的解法9.3 应用举例案例1 资源分配问题案例2 设备负荷问题案例3 生产库存问题案例4 背包问题本章小结,课件,5,2023/11/4,9.1.1 动态规划的基本概念,1.阶段:把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。描述阶段的变量称为阶段变量，常用k表示。导入案例中k=1,2,3,4,2.状态变量:每个阶段开始所处的自然状况或客观条件(用点集表示).如引例:第1阶段的状态就是起点A,记为s1=A;第2阶段有2个状态B1,B2,记为s2=B1,B2;第3阶段有4个状态C1,C2,C3,C4,记为s3=C1,C2,C3,C4;第4阶段有2个状态D1,D2,记为s4=D1,D2;,3.决策变量:在某一阶段的某个状态时的不同选择,如引例中B1状态下有3种选择:B1C1,B1C2,B1C3这3种选择构成了允许决策的集合。不同状态下允许决策的集合也不同，故决策变量是状态变量的函数，即xk(sk)D(sk),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，D2E,5.状态转移方程确定过程是由一个状态到另一个状态的演变过程。第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)=8,6.指标函数用来衡量所实现过程优劣的一种数量指标。其基本方程有加法和乘法两种形式，通常加法形式用的较多，其公式为：,7.边界条件起始或终止条件。,课件,6,2023/11/4,5.1.2 动态规划的基本原理,最优化原理(Optimality principle):最优策略具备这样的性质:无论初始状态与初始决策如何,以后诸决策对以第一个决策所形成的状态作为初始状态的过程而言,必然构成最优策策略.通俗地说:最优策略的子策略也是最优的.例如，在导入案例中，最优策略是AB1C2D1E,最短距离为13,其子策略:B1C2D1E,C2D1E,D1E也是最优的。依据这一原理，从后往前推各阶段最优子过程，从而得到全程最优过程。,设f(i)表示从点i到终点E的最短距离,d(i,j)表示点i,j之间的距离.显然f(E)=0,为该问题的边界条件.,k=4,决策：D1E,k=3,决策：D2E,决策：C1D1,决策：C2D1,k=2,决策：C3D2,决策：C4D2,决策：B1C2,决策：B2C3,k=1,决策：AB1,最短路线:AB1C2D1E最短路长:13,课件,7,2023/11/4,5.1.2 动态规划的最优化原理,课件,8,2023/11/4,9.2.1 动态规划模型的建立,解 把生产第k种产品看成是第k阶段，划分为n个阶段.设 sk表示第k阶段初资源可用量（状态变量）xk表示分配给第k阶段资源的数量（决策变量），显然有：允许决策集合 sk+1=sk-xk（状态转移方程）s1=a（边界条件）指标函数：若fk(sk)表示数量为sk资源分配给第k种产品时，从第k阶段到第n阶段总收益，则有：,课件,9,2023/11/4,9.2.1 动态规划模型的建立,指标函数通常有两种形式：加法形式和乘法形式。,课件,10,2023/11/4,9.2.2 动态规划问题的解法:逆序法,最优值函数f(k):从k阶段到E的最短距离；阶段指标函数,即该阶段选择不同路线的距离。从后向前推。,S1=AS2=B1,B2S3=C1,C2,C3,C4S4=D1,D2S5=E,f5(E)=0同理 f4(D1)=2,f4(D2)=1同理 f3(C2)=5,f3(C3)=4,f3(c4)=5同理 f2(B2)=11,课件,11,2023/11/4,9.2.2 动态规划问题的解法:顺序法,最优值函数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)=13,课件,12,2023/11/4,案例1 资源分配问题,5台设备分配给3个工厂，盈利表如下，如何分配可使获利最大？,分析 3个工厂看成3个阶段.阶段变量 k(k=1,2,3)；状态变量 sk表示为分配给第k个工厂至第n个工厂的设备台数；决策变量xk 表示分配给第k个工厂的设备台数；则有sk+1=sk-xk；Pk(xk)表示为xk 台设备分配到第k个工厂所得赢利值；fk(sk)表示为 台设备分配给第k个工厂至第n个工厂所得到的最大赢利值。则有:,k=3,k=2,k=1,方案一:1,2,2,方案二:2,1,2,方案三:2,2,1,方案四:3,2,0,课件,14,2023/11/4,案例2 设备负荷问题,某种机器可在高低两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为g=9x，其中x为投入生产的机器数量，季度完好率为a=0.65，在低负荷下生产的产量函数为h=4y，其中y为投入生产的机器数量，季度完好率为b=0.95。设资源拥有量100.解 4季度看成4阶段sk第k季初拥有完好机器数xk第k季分配给高负荷机器数,则低负荷分配数sk-xk下季度初完好机器数sk+1=0.65xk+0.95(sk-xk)第k季产量vk=6xk+4(sk-xk),课件,15,2023/11/4,k=4,f4 是x4 的增函数,故最大值解为 x4*=s4,相应地有 f4(s4)=9s4,k=3,f3 是x3 的增函数,故最大值解为 x3*=s3,相应地有 f3(s3)=14.85s3,课件,16,2023/11/4,k=2,f2 是x2 的增函数,故最大值解为 x2*=s2,相应地有 f2(s2)=18.6525s2,k=1,f1 是x1 的减函数,故最大值解为 x1*=0,相应地有 f1(s1)=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。,课件,17,2023/11/4,Lingo程序,model:sets:JD/1.4/:s,x,v;!定义状态变量、决策变量和指标函数;ZB/1.5/:f;!定义最优值函数;endsetsf(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);!目标;end,课件,18,2023/11/4,案例3 生产库存问题,课件,19,2023/11/4,案例3 生产库存问题,课件,20,2023/11/4,案例3 生产库存问题,课件,21,2023/11/4,案例3 生产库存问题,逆推:f5=26.5,s5=0,x5*=0 或 3,s4=3,x4*=6,s4=0,x4*=0,s3=1,s3=4,x3*=0 或 3,x3*=6,s2=3,s2=0,s2=0,x2*=6,x2*=0,x2*=0,s1=0,x1*=2,s1=3,x1*=5,s1=3,x1*=5,课件,22,2023/11/4,案例4 背包问题,课件,23,2023/11/4,案例4 背包问题,课件,24,2023/11/4,案例4 背包问题,最优方案:依次装2,1,0个最大价值:13,课件,25,2023/11/4,本章小结,本章介绍了动态规划的基本概念、基本原理和几种典型的应用问题。要求1）理解动态规划的核心概念状态与状态变量、决策与决策变量、策略、状态转移方程、指标函数和最优值函数。2）理解动态规划的最优化原理：一个最优策略的子策略总是最优的。3）动态规划模型的建立和求解一般的，给一个实际问题建立动态规划模型时，必须做到下面五点。(1)将问题的过程划分成适当的阶段。(2)正确选择状态变量，使它既能描述过程的演变，又满足无后效性。(3)确定决策变量及每阶段的允许决策集合。(4)正确写出状态转移方程即。(5)正确写出指标函数的关系。动态规划模型的求解有两种方法：逆序解法和顺序解法。4）动态规划的应用掌握动态规划在最短路线问题、资源分配问题、生产库存问题、背包问题求法。,