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

1、1,第八章 动态规划,8.1 多阶段决策问题 8.2 最优化原理与动态规划的数学模型 8.3 离散确定性动态规划模型的求解 8.4 离散随机性动态规划模型的求解 8.5 一般数学规划模型的动态规划解法,2,理解动态规划基本概念、最优化原理和基本方程，逆序法和顺序解法，学习应用动态规划解决多阶段决策问题。 重点 :掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产与存贮等问题。,学习要点：,3,第一节 多阶段的决策问题,4,动态规划（Dynamic Programming）,动态规划是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。,5,动态规划：是解决多

2、阶段决策过程最优化问题的一种方法，无特定的数学模型。,可解决 与时间有关的动态问题 与时间无关的静态问题,6,多阶段决策问题 1）动态决策将时间作为变量的决策问题称为动态决策。其基本特点是多次决策。 2）多阶段决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态过程可以按照时间进程分为状态互相联系而又互相区别的各个阶段，而且在每个阶段都要进行决策，当每一个阶段的决策确定以后，就完全确定了一个过程的活动路线。,7,引例1 最短路线问题,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,C1,C3,D1,A,B1,B3,B2,D2,E,C2,8,引例

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

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

5、6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,13,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑一个阶段的最优选择,14,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C1)=4,f(D1)=3,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑二个阶段的最优选择,15,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C2

6、)=7,f(D1)=3,f(C1)=4,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,2,5,3,4,考虑二个阶段的最优选择,16,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(C1)=4,f(C2)=7,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑二个阶段的最优选择,17,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B1)=11,f(C2)=7,f(C1)=4,2,5,3,7,5,6

7、,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑三个阶段的最优选择,18,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f (D2)=4,f (E)=0,f(C3)=6,f (D1)=3,f(B2)=7,f(C2)=7,f(C1)=4,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑三个阶段的最优选择,19,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(B1)=11,f(B2)=7,2,5,3,

8、7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,考虑三个阶段的最优选择,20,10,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,2,5,3,7,5,6,3,2,4,5,5,1,1,4,6,3,3,3,3,4,四个阶段联合考虑从A点到E点的最优选择,21,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,

9、f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B3） B3,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,22,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B3） B3 （ B3， C2 ） C2,7,5,3,

10、2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,23,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,24,6,C1,C3,D1,A,B1,B3,B2,D2,E,C2,f(D2)=4,

11、f(E)=0,f(C3)=6,f(D1)=3,f(B3)=8,f(C2)=7,f(C1)=4,f(A)=11,f(B2)=7,f(B1)=11,状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态,A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2 （ D2， E） E,7,5,3,2,4,5,5,1,2,5,3,1,4,6,3,3,3,3,4,从A到E的最短路径为11，路线为AB3C2 D2 E,25,通过上例的讨论，可以看到多级决策过程具有以下特点：,（1）把整个过程看成（或认为地分成）n个具有递推关系的单级过程。 （2）采取逐级分析的方法，一

12、般由最后一级开始倒向进行。 （3）在每一级决策时，不只考虑本级的性能指标的最优，而且同时考虑本级及以后的总性能指标最优，因此它是根据“全局”最优作出本级决策的。,26,动态规划法较之穷举法的优点: (1) 容易计算出结果； (2) 动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线 。,27,动态规划方法的基本思想： (1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数从而把问题化成一族同类型的子问题，然后逐个求解。 (2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求

13、出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。 (3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。,28,二、基本概念和基本原理,动态规划模型要用到的概念： (1)阶段; (2)状态; (3)决策和策略; (4)状态转移律; (5)指标函数。,1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。,29,2、状态：各阶段开始时的客观条件叫做状态。 状态变量：描述各阶段状态的变量，用sk表示第

14、k阶段的状态变量。 状态集合：状态变量的取值集合，用Sk表示。,一阶段：S1A 二阶段：S2B1,B2,B3 三阶段：S3C1,C2,C3 四阶段：S4D1,D2,一阶段：S1A 二阶段：S2B1,B2,B3 三阶段：S3C1,C2,C3 四阶段：S4D1,D2,二、基本概念和基本原理,30,二、基本概念和基本原理,二、基本概念和基本原理,3、决策：当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。 决策变量：表示决策的变量，称为决策变量，常用xk(sk)表示第k阶段当状态为sk时的决策变量。 允许决策集合：决策变量的取值往往限制在一定范围内，我们

15、称此范围为允许决策集合，用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。,D2( B1)=C1,C2 D2( B2)=C1,C2,C3 如状态为B1时选择C2，可表示为：u2(B1)=C2,D2( B1)=C1,C2 D2( B2)=C1,C2,C3 如状态为B1时选择C2，可表示为： x2(B1)=C2,31,二、基本概念和基本原理,4 策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。 允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。,3

16、2,二、基本概念和基本原理,5、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。 第k段的状态sk，本阶段决策为xk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,xk),33,6、指标函数：用于衡量所选定策略优劣的数量指标。 它分为阶段指标函数和过程指标函数。 阶段指标函数是指第k段，从状态sk出发，采取决策xk时的效益，用Vk(sk,uk)表示。 过程指标函数记为fk(sk)：表示从第k段状态sk按预定指标到过程终止时的效益值。,二、基本概念和基本原理,34,最简单的方法穷举法。共有多少条路径，依次计算并比较。 动

17、态规划方法本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。,三、最优化原理与动态规划的数学模型,35,最优化原理Optimization Principle,作为整个过程的最优策略具有这样的性质： 无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。,若M是从A到B的最优路线上的一点，则从M到B的路线也是最优的。,36,动态规划的基本方程（最优化原理的应用）,根据最优化原理得到的计算动态规划问题的递（逆）推关系式：,边界条件： k=n时，fn+1(sn+1)=0,边界条件： k=n时， fn+1(

18、sn+1)=1,Opt: optimization, max or min vk: k阶段的指标函数 fk+1:k+1阶段的最优指标函数值 fk:k阶段的最优指标函数值,37,构成动态规划模型的条件-1,根据时间或空间的自然特征，实际问题能恰当地划分为若干阶段，形成多阶段决策的过程,38,构成动态规划模型的条件-2,正确的选择状态变量S 动态规划的状态应具有三个特征： 能够用来描述受控过程的演变特征； 满足无后效性：如果某阶段状态给定，则在这阶段以后过程的发展只与当前的状态有关，而与过去的历史无关。或当前的状态是过去历史发展的一个总结，过程的过去历史只能通过当前的状态影响未来的发展。 可知性：

19、各阶段状态变量的值，直接或间接地都是可以知道的。,39,构成动态规划模型的条件 - 3,确定决策变量sk的含义及每阶段的允许决策集合Dk(sK),40,构成动态规划模型的条件-4,正确写出状态转移方程 sk+1=T(sk,xk(sk) 或 sk+1=T(sk,xk),41,构成动态规划模型的条件-5,明确指标函数Vk,n的关系 一般有两种形式 和式 积式,42,四 逆序解法与顺序解法 如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。 顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段

20、的求优结果，最后一段计算的结果就是全过程的最优结果。,43,第一步：k=0 状态：s1A,f0(A)0,求解步骤,顺序解法求解,44,第二步：k=1 状态：B1 B2,x1*(B1)=A,x1*(B2)=A,f1(B1)4,f1(B2)5,(4),(5),45,第三步：k=2 状态：C1 C2 C3 C4,u2*(C1)=B1,x2*(C2)=B1,x2*(C3)=B1,f2(C1)6,f2(C2)7,f2(C3)10,x2*(C4)=B2,f2(C4)12,(6),(7),(10),(12),x2*(C1)=B1,46,第四步：k=3 状态：D1 D2 D3,x3*(D1)=C1或C2,x3

21、*(D2)=C2,x3*(D3)=C3,f3(D1)11,f3(D2)12,f3(D3)14,(11),(12),(14),47,第五步：k=4 状态：E1 E2,x4*(E1)=D1,x4*(E2)=D2,f4(E1)14,f4(E2)14,(14),(14),48,第六步：k=5 状态：F,u5*(F)=E2,f5(F)17,(17),即从A到F的最短距离为17。 最优路线为：AB1C2D2E2F,49,逆序解法与顺序解法建模的不同点,1状态转移方式不同 sk+1=Tk(sk,xk) sk=Tk(sk+1,xk),50,2指标函数的定义不同 逆序解法中，我们定义最优指标函数fk(sk)表示

22、第k段从状态sk出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值。 顺序解法中，定义最优指标函数fk(sk+1)表示第k段时从起点到状态sk+1的前部子过程最优效益值。fn(sn+1)是整体最优函数值。,51,3. 基本方程形式不同 (1)当指标函数为阶段指标和形式 逆序解法,则基本方程为：,则基本方程为：,顺序解法,52,(2)当指标函数为阶段指标积形式 逆序解法,基本方程为：,基本方程为：,顺序解法,53,第3节 离散确定型动态规划 模型求解,Solution of Discrete Certain DP Model,54,例4,某一警卫部门共有12支巡逻队，负责4个要害部位

23、A、B、C、D的警卫巡逻。 对每个部位可分别派出2-4支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见表8-1。 问该警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小。,55,解-1,阶段变量k ：把12支巡逻队往4个部位派遣看成依次分四个阶段(k=1，2，3，4)。 状态变量sk：表示每个阶段初拥有的可派遣的巡逻队数是前面阶段决策的结果，也是本阶段决策的依据 决策变量xk：表示各阶段对各部位派出的巡逻队数， 各阶段允许的决策集合Dk(sk)为： Dk(sk)=xk|2xk4| (k=1,2,3,4),56,解-2,状态转移方程：sk+1=

24、sk-xk (k=1,2,3,4) 每阶段初拥有可派遣的巡逻队数量等于上阶段初拥有的数量减去上阶段派出的数量 过程函数为阶段指标函数之和： 阶段指标函数vk(xk)表示k阶段派出的巡逻队数为xk时，该阶段的部位的预期损失值,57,解-3,fk(sk)：表示从k阶段状态为sk出发，采用最优子策略到过程结束时的预期损失值，有 先考虑给D部位派巡逻队，即k=4，上式可写为 边界条件f5(s5)=0 ，所以,58,解-4,因D4（s4）=2，3，4，又s4的可能值是2s46，故由表8-1的数据，可得下表的结果,总共12支巡逻队，每部位24支巡逻队。,59,解-5,联合考虑对C、D两个部位派巡逻队，k=3，有： 因D3(s3)=2,3,4，4s38，可得如下结果,60,解-6,考虑对B、C、D三个部位派巡逻队，k=2，有 由D2(s2)=2,3,4，8s210，可得如下结果,61,解-7,考虑对A、B、C、D四个部队派巡逻队，即k=1时，有 因s1=12, D1(s1)=2,3,4,可得如下结果,62,解-8,最优策略