运筹学基础及应用第五 胡运权.pptx

《运筹学基础及应用第五 胡运权.pptx》由会员分享，可在线阅读，更多相关《运筹学基础及应用第五 胡运权.pptx（72页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1 理解动态规划基本概念、最优化原理和基本方程，逆序法和顺序解法，学习应用动态规划解决多阶段决策问题。重点:掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产与存贮等问题。学习要点：第1页/共72页2第一节 多阶段的决策问题第2页/共72页3动态规划（Dynamic Programming）R.Bellman50年代执教于普林斯顿和斯坦福大学，后进入兰德（Rand）研究所。1957年发表“Dynamic Programming”一书，标识动态规划的正式诞生。动态规划的基本概念和定义 动态规划的研究对象和引例 动态规划是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基

2、本方法之一。第3页/共72页4 动态规划：是解决多阶段决策过程最优化问题的一种方法，无特定的数学模型。可解决 与时间有关的动态问题 与时间无关的静态问题第4页/共72页5多阶段决策问题 1）动态决策将时间作为变量的决策问题称为动态决策。其基本特点是多次决策。2）多阶段决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态过程可以按照时间进程分为状态互相联系而又互相区别的各个阶段，而且在每个阶段都要进行决策，当每一个阶段的决策确定以后，就完全确定了一个过程的活动路线。第5页/共72页612345引例1 最短路线问题25375632455114633334C1C3D1AB1B3B2

3、D2EC2第6页/共72页7引例2 生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？引例3 投资决策问题某公司现有资金Q万元，在今后5年内考虑给A，B，C，D 4个项目投资？引例4 设备更新问题现企业要决定一台设备未来8年的更新计划，问应在哪些年更新设备可使总费用最小？第7页/共72页8 动态规划方法的特点优点：1）许多问题用动态规划求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学无用武之地，而动态规划成为得力工具。2）某些情况下，用动态规划处理不仅能作定性描述分析，且可利用计算机给出求其数值解的方法。第8页/共72页9动态规划方法的特点

4、缺点：1）没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要作用。2）“维数障碍”：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。第9页/共72页10第二节 最优化原理与动态规划的数学模型一 最短路线问题求解25375632455114633334C1C3D1AB1B3B2D2EC2f(E)=0第10页/共72页11考虑一个阶段的最优选择C1C3D1AB1B3B2D2EC2f(D1)=3f(E)=025375632455114633334第11页

5、/共72页12C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(D1)=325375632455114633334考虑一个阶段的最优选择第12页/共72页13C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C1)=4f(D1)=325375632455114633334考虑二个阶段的最优选择第13页/共72页14C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C2)=7f(D1)=3f(C1)=437563245511463332534考虑二个阶段的最优选择第14页/共72页15C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f

6、(C3)=6f(D1)=3f(C1)=4f(C2)=725375632455114633334考虑二个阶段的最优选择第15页/共72页16C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B1)=11f(C2)=7f(C1)=425375632455114633334考虑三个阶段的最优选择第16页/共72页17C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B2)=7f(C2)=7f(C1)=4f(B1)=1125375632455114633334考虑三个阶段的最优选择第17页/共72页18C1C3D1

7、AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(B1)=11f(B2)=725375632455114633334考虑三个阶段的最优选择第18页/共72页1910C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=1125375632455114633334四个阶段联合考虑从A点到E点的最优选择第19页/共72页206C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1

8、)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B3）B37532455125314633334第20页/共72页216C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B3）B3 （B3，C2）C27532455125314633334第21页/共72页226C1C3D1

9、AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B3）B3 （B3，C2）C2 （C2，D2）D2 7532455125314633334第22页/共72页236C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态

10、A （A，B3）B3 （B3，C2）C2 （C2，D2）D2 （D2，E）E7532455125314633334从A到E的最短路径为11，路线为AB3C2 D2 E第23页/共72页24通过上例的讨论，可以看到多级决策过程具有以下特点：（1）把整个过程看成（或认为地分成）n个具有递推关系的单级过程。（2）采取逐级分析的方法，一般由最后一级开始倒向进行。（3）在每一级决策时，不只考虑本级的性能指标的最优，而且同时考虑本级及以后的总性能指标最优，因此它是根据“全局”最优作出本级决策的。第24页/共72页25动态规划法较之穷举法的优点:(1)容易计算出结果；(2)动态规划的计算结果不仅得到了从起始

11、点到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线。第25页/共72页26动态规划方法的基本思想：(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数从而把问题化成一族同类型的子问题，然后逐个求解。(2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。第26页/共72页27

12、二、基本概念和基本原理动态规划模型要用到的概念：n(1)阶段;(2)状态;(3)决策和策略;(4)状态转移律;(5)指标函数。1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。第27页/共72页282、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。状态集合：状态变量的取值集合，用Sk表示。一阶段：S1A二阶段：S2B1,B2,B3三阶段：S3C1,C2,C3四阶段：S4D1,D2一阶段：S1A二阶段：S2B1,B2,B3三阶段：S3C1,C2,C3四阶段：S4D1,D2二

13、、基本概念和基本原理第28页/共72页29二、基本概念和基本原理二、基本概念和基本原理3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。决策变量：表示决策的变量，称为决策变量，常用xk(sk)表示第k阶段当状态为sk时的决策变量。允许决策集合：决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。D2(B1)=C1,C2 D2(B2)=C1,C2,C3如状态为B1时选择C2，可表示为：u2(B1)=C2D2(B1)=C1,C2 D2(B2)=C1,C2,C3如状态为B1时选

14、择C2，可表示为：x2(B1)=C2第29页/共72页30二、基本概念和基本原理4 策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。第30页/共72页31二、基本概念和基本原理 5、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为xk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,xk)第31页/

15、共72页32 6、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策xk时的效益，用Vk(sk,uk)表示。过程指标函数记为fk(sk)：表示从第k段状态sk按预定指标到过程终止时的效益值。二、基本概念和基本原理第32页/共72页33最简单的方法穷举法。共有多少条路径，依次计算并比较。动态规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。三、最优化原理与动态规划的数学模型第33页/共72页34最优化原理Optimization Principle

16、 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。若M是从A到B的最优路线上的一点，则从M到B的路线也是最优的。ABM第34页/共72页35动态规划的基本方程（最优化原理的应用）根据最优化原理得到的计算动态规划问题的递（逆）推关系式：边界条件：k=n时，fn+1(sn+1)=0边界条件：k=n时，fn+1(sn+1)=1Opt:optimization,max or min vk:k阶段的指标函数 fk+1:k+1阶段的最优指标函数值 fk:k阶段的最优指标函数值第35页/共72页36构成动态规划模型的条件-1根据时间或空

17、间的自然特征，实际问题能恰当地划分为若干阶段，形成多阶段决策的过程第36页/共72页37构成动态规划模型的条件构成动态规划模型的条件-2-2正确的选择状态变量S 动态规划的状态应具有三个特征：能够用来描述受控过程的演变特征；满足无后效性：如果某阶段状态给定，则在这阶段以后过程的发展只与当前的状态有关，而与过去的历史无关。或当前的状态是过去历史发展的一个总结，过程的过去历史只能通过当前的状态影响未来的发展。可知性：各阶段状态变量的值，直接或间接地都是可以知道的。第37页/共72页38构成动态规划模型的条件构成动态规划模型的条件 -3确定决策变量sk的含义及每阶段的允许决策集合Dk(sK)第38页

18、/共72页39构成动态规划模型的条件构成动态规划模型的条件-4-4正确写出状态转移方程 sk+1=T(sk,xk(sk)或 sk+1=T(sk,xk)第39页/共72页40构成动态规划模型的条件构成动态规划模型的条件-5-5明确指标函数Vk,n的关系一般有两种形式和式积式第40页/共72页41四 逆序解法与顺序解法如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。第41页/共72页42

19、第一步：k=0状态：s1Af0(A)0求解步骤顺序解法求解第42页/共72页43第二步：k=1 状态：B1 B2 x1*(B1)=Ax1*(B2)=Af1(B1)4f1(B2)5(4)(5)第43页/共72页44第三步：k=2 状态：C1 C2 C3 C4u2*(C1)=B1x2*(C2)=B1x2*(C3)=B1f2(C1)6f2(C2)7f2(C3)10 x2*(C4)=B2f2(C4)12(4)(5)(6)(7)(10)(12)x2*(C1)=B1第44页/共72页45(4)(5)(6)(7)(10)(12)第四步：k=3 状态：D1 D2 D3x3*(D1)=C1或C2x3*(D2)=

20、C2x3*(D3)=C3f3(D1)11f3(D2)12f3(D3)14(11)(12)(14)第45页/共72页46第五步：k=4 状态：E1 E2 x4*(E1)=D1x4*(E2)=D2f4(E1)14f4(E2)14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)第46页/共72页47第六步：k=5 状态：F u5*(F)=E2f5(F)17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即从A到F的最短距离为17。最优路线为：AB1C2D2E2F第47页/共72页48逆序解法与顺序解法建模的不同点1状态转移方式不

21、同sk+1=Tk(sk,xk)sk=Tk(sk+1,xk)1状态s1决策x1效益v1(s1,x1)s2kskxkvk(sk,xk)Sk+1nsnxnvn(sn,xn)Sn+11状态s1决策x1效益v1(s2,x1)s2kskxkvk(sk+1,xk)Sk+1nsnxnvn(sn+1,xn)Sn+1第48页/共72页492指标函数的定义不同 逆序解法中，我们定义最优指标函数fk(sk)表示第k段从状态sk出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值。顺序解法中，定义最优指标函数fk(sk+1)表示第k段时从起点到状态sk+1的前部子过程最优效益值。fn(sn+1)是整体最优函数

22、值。第49页/共72页503.基本方程形式不同(1)当指标函数为阶段指标和形式逆序解法则基本方程为：则基本方程为：顺序解法第50页/共72页51(2)当指标函数为阶段指标积形式逆序解法基本方程为：基本方程为：顺序解法第51页/共72页52第3节 离散确定型动态规划 模型求解Solution of Discrete Certain DP Model第52页/共72页53例4某一警卫部门共有12支巡逻队，负责4个要害部位A、B、C、D的警卫巡逻。对每个部位可分别派出2-4支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8-1。问该警卫部门应往各部位分别

23、派多少支巡逻队，使总的预期损失为最小。ABCD218382434314352231410312125巡逻队数巡逻部位预期损失第53页/共72页54 解解-1-1阶段变量k：把12支巡逻队往4个部位派遣看成依次分四个阶段(k=1，2，3，4)。状态变量sk：表示每个阶段初拥有的可派遣的巡逻队数是前面阶段决策的结果，也是本阶段决策的依据决策变量xk：表示各阶段对各部位派出的巡逻队数，各阶段允许的决策集合Dk(sk)为：Dk(sk)=xk|2xk4|(k=1,2,3,4)第54页/共72页55解-2状态转移方程：sk+1=sk-xk (k=1,2,3,4)每阶段初拥有可派遣的巡逻队数量等于上阶段初拥

24、有的数量减去上阶段派出的数量过程函数为阶段指标函数之和：阶段指标函数vk(xk)表示k阶段派出的巡逻队数为xk时，该阶段的部位的预期损失值第55页/共72页56解-3fk(sk)：表示从k阶段状态为sk出发，采用最优子策略到过程结束时的预期损失值，有先考虑给D部位派巡逻队，即k=4，上式可写为 边界条件f5(s5)=0，所以 第56页/共72页57解-4 x4s4v4(x4)f4(s4)x4*23423434233431313434312525453431252546343125254因D4（s4）=2，3，4，又s4的可能值是2s46，故由表8-1的数据，可得下表的结果 总共12支巡逻队，每

25、部位24支巡逻队。第57页/共72页58解-5联合考虑对C、D两个部位派巡逻队，k=3，有：因D3(s3)=2,3,4，4s38，可得如下结果 x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+3122+34552624+2522+3121+34492724+2522+2521+31473824+2522+2521+25464第58页/共72页59解-6考虑对B、C、D三个部位派巡逻队，k=2，有由D2(s2)=2,3,4，8s210，可得如下结果 x2s2v2(x2)+f3(s2-x2)f2(s2)x2*234838+4935+5531+5887293

26、8+4735+4931+558431038+4635+4731+49804第59页/共72页60解-7考虑对A、B、C、D四个部队派巡逻队，即k=1时，有因s1=12,D1(s1)=2,3,4,可得如下结果 x1s1v1(x1)+f2(s1-x1)f1(s1)x1*2341218+8014+8410+87974第60页/共72页61解-8 x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+31 22+34552624+25 22+3121+34492724+25 22+2521+31473824+25 22+2521+25464x4s4v4(x4)f4(

27、s4)x4*23423434233431313434312525453431252546343125254 x2s2v2(x2)+f3(s2-x2)f2(s2)x2*234838+49 35+55 31+58872938+47 35+49 31+558431038+46 35+47 31+49804l最优策略为：lA部位4支，B部位2支，C部位2支，D部位4支，总预期损失为97单位。x1s1v1(x1)+f2(s1-x1)f1(s1)x1*2341218+80 14+84 10+87974第61页/共72页62第四节第四节 离散随离散随机型动态规划机型动态规划 模型求模型求解解Solution

28、 of Discrete Stochastic DP Model第62页/共72页63随机型的动态规划随机型的动态规划指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定第k+1阶段可能的状态数给定状态xk和决策uk的情况下，下一个可能到达的状态的概率从k阶段状态sk转移到k+1阶段状态为i时的指标函数值 随机性动态规划的基本结构图skxkSk+1第63页/共72页64指标函数为和函数的转换方程指标函数为和函数的转换方程在随机性的动态规划问题下，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效

29、益值进行优化。因此随机性的动态规划问题中，当指标函数值为各阶段效益和的情况下，基本方程应写为 期望值第64页/共72页65655一般数学规划模型的动态规划解法用动态规划的方法求解一般数学规划模型思想：将取定每个变量的值作为一个阶段，则有n个变量的数学规划问题，可看作是有n 个阶段的多阶段决策问题。右端向量可看成资源数，用状态变量表示约束的个数决定决策变量的维数用动态规划的方法求解一般数学规划模型的条件：1.目标函数可以分解为单变量函数的和或积即f(x1,x2,xn)=f1(x1)+f2(x2)+fn(xn)或f(x1,x2,xn)=f1(x1)f2(x2)fn(xn)2.约束为线性不等式，变量可以是连续变量或整数变量第65页/共72页6666例7,用动态规划方法求解非线性规划问题。第66页/共72页6767解：设将确定变量 的值作为两个阶段，K=1，2。决策变量 表示第K个变量的取值。状态变量 表示第K个阶段初约束条件右端项的剩余值。状态转移方程：阶段指标函数：确定 取值对目标函数值的贡献；最优指标函数：具体的 边界条件 第67页/共72页6868当K=2时，第二个变量的取值为 令 ，求其最大值 22第68页/共72页6969当K=1时，第一个变量的取值为 于是第69页/共72页702023/2/2470第70页/共72页71第71页/共72页72感谢您的观看！第72页/共72页