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

1第八章动态规划8.1多阶段决策问题8.2最优化原理与动态规划的数学模型8.3离散确定性动态规划模型的求解8.4离散随机性动态规划模型的求解8.5一般数学规划模型的动态规划解法2理解动态规划基本概念、最优化原理和基本方程，逆序法和顺序解法，学习应用动态规划解决多阶段决策问题。重点:掌握动态规划模型结构、逆序法算法原理、资源分配、设备更新、生产与存贮等问题。学习要点：3第一节多阶段的决策问题4动态规划（DynamicProgramming）R.Bellman50年代执教于普林斯顿和斯坦福大学，后进入兰德（Rand）研究所。1957年发表“DynamicProgramming”一书，标识动态规划的正式诞生。动态规划的基本概念和定义动态规划的研究对象和引例动态规划是解决复杂系统优化问题的一种方法。是解决动态系统多阶段决策过程的基本方法之一。5动态规划：是解决多阶段决策过程最优化问题的一种方法，无特定的数学模型。可解决与时间有关的动态问题与时间无关的静态问题6多阶段决策问题1）动态决策—将时间作为变量的决策问题称为动态决策。其基本特点是多次决策。2）多阶段决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态过程可以按照时间进程分为状态互相联系而又互相区别的各个阶段，而且在每个阶段都要进行决策，当每一个阶段的决策确定以后，就完全确定了一个过程的活动路线。712345引例1最短路线问题25375632455114633334C1C3D1AB1B3B2D2EC28引例2生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？引例3投资决策问题某公司现有资金Q万元，在今后5年内考虑给A，B，C，D4个项目投资？引例4设备更新问题现企业要决定一台设备未来8年的更新计划，问应在哪些年更新设备可使总费用最小？9动态规划方法的特点☻优点：1）许多问题用动态规划求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学无用武之地，而动态规划成为得力工具。2）某些情况下，用动态规划处理不仅能作定性描述分析，且可利用计算机给出求其数值解的方法。10动态规划方法的特点缺点：1）没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要作用。2）“维数障碍”：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方法求解。11第二节最优化原理与动态规划的数学模型一最短路线问题求解25375632455114633334C1C3D1AB1B3B2D2EC2f(E)=012考虑一个阶段的最优选择C1C3D1AB1B3B2D2EC2f(D1)=3f(E)=02537563245511463333413C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(D1)=325375632455114633334考虑一个阶段的最优选择14C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C1)=4f(D1)=325375632455114633334考虑二个阶段的最优选择15C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C2)=7f(D1)=3f(C1)=437563245511463332534考虑二个阶段的最优选择16C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(C1)=4f(C2)=725375632455114633334考虑二个阶段的最优选择17C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B1)=11f(C2)=7f(C1)=425375632455114633334考虑三个阶段的最优选择18C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B2)=7f(C2)=7f(C1)=4f(B1)=1125375632455114633334考虑三个阶段的最优选择19C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(B1)=11f(B2)=725375632455114633334考虑三个阶段的最优选择2010C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=1125375632455114633334四个阶段联合考虑从A点到E点的最优选择216C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=11状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B3）B37532455125314633334226C1C3D1AB1B3B2D2EC2f(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）C27532455125314633334236C1C3D1AB1B3B2D2EC2f(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）D27532455125314633334246C1C3D1AB1B3B2D2EC2f(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（D2，E）E7532455125314633334从A到E的最短路径为11，路线为A→B3→C2→D2→E25通过上例的讨论，可以看到多级决策过程具有以下特点：（1）把整个过程看成（或认为地分成）n个具有递推关系的单级过程。（2）采取逐级分析的方法，一般由最后一级开始倒向进行。（3）在每一级决策时，不只考虑本级的性能指标的最优，而且同时考虑本级及以后的总性能指标最优，因此它是根据“全局”最优作出本级决策的。26动态规划法较之穷举法的优点:(1)容易计算出结果；(2)动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线。27动态规划方法的基本思想：(1)将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数．从而把问题化成一族同类型的子问题，然后逐个求解。(2)求解时从边界条件开始，逆(或顺)过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。(3)动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。28二、基本概念和基本原理动态规划模型要用到的概念：(1)阶段;(2)状态;(3)决策和策略;(4)状态转移律;(5)指标函数。1、阶段：将所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母k表示阶段变量。292、状态：各阶段开始时的客观条件叫做状态。状态变量：描述各阶段状态的变量，用sk表示第k阶段的状态变量。状态集合：状态变量的取值集合，用Sk表示。一阶段：S1＝{A}二阶段：S2＝{B1,B2,B3}三阶段：S3＝{C1,C2,C3}四阶段：S4＝{D1,D2}一阶段：S1＝{A}二阶段：S2＝{B1,B2,B3}三阶段：S3＝{C1,C2,C3}四阶段：S4＝{D1,D2}二、基本概念和基本原理30二、基本概念和基本原理二、基本概念和基本原理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时选择C2，可表示为：x2(B1)=C231二、基本概念和基本原理4策略：各段决策确定后，整个问题的决策序列就构成一个策略，用p1,n{x1(s1),x2(s2),...xn(sn)}表示。允许策略集合：对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1,n，使整个问题达到最优效果的策略就是最优策略。32二、基本概念和基本原理5、状态转移方程：动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。第k段的状态sk，本阶段决策为xk(sk)，则第k+1段的状态sk+1也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,xk)336、指标函数：用于衡量所选定策略优劣的数量指标。它分为阶段指标函数和过程指标函数。阶段指标函数是指第k段，从状态sk出发，采取决策xk时的效益，用Vk(sk,uk)表示。过程指标函数记为fk(sk)：表示从第k段状态sk按预定指标到过程终止时的效益值。二、基本概念和基本原理34最简单的方法——穷举法。共有多少条路径，依次计算并比较。动态规划方法——本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起始点到终点的最短路线。三、最优化原理与动态规划的数学模型35最优化原理OptimizationPrinciple作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。若M是从A到B的最优路线上的一点，则从M到B的路线也是最优的。ABM36动态规划的基本方程（最优化原理的应用）根据最优化原理得到的计算动态规划问题的递（逆）推关系式：,(,)nkniiiiKVvsx当时，11()(){(,)()}kkkkkkkkkkxDsfsoptvsxfsn,ik(,)knkiiVvsx当时11()(){(,)()}kkkkkkkkkkxDsfsoptvsxfs边界条件：k=n时，fn+1(sn+1)=0边界条件：k=n时，fn+1(sn+1)=1Opt:optimization,maxorminvk:k阶段的指标函数fk+1:k+1阶段的最优指标函数值fk:k阶段的最优指标函数值37构成动态规划模型的条件-1根据时间或空间的自然特征，实际问题能恰当地划分为若干阶段，形成多阶段决策的过程38构成动态规划模型的条件-2正确的选择状态变量S动态规划的状态应具有三个特征：能够用来描述受控过程的演变特征；满足无后效性：如果某阶段状态给定，则在这阶段以后过程的发展只与当前的状态有关，而与过去的历史无关。或当前的状态是过去历史发展的一个总结，过程的过去历史只能通过当前的状态影响未来的发展。可知性：各阶段状态变量的值，直接或间接地都是可以知道的。39构成动态规划模型的条件-3确定决策变量sk的含义及每阶段的允许决策集合Dk(sK))()(kkkksDsx40构成动态规划模型的条件-4正确写出状态转移方程sk+1=T(sk,xk(sk))或