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

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

2、策问题题4动态规划动态规划（Dynamic Programming） R. Bellman50年代执教于普林斯顿和斯坦福大学，年代执教于普林斯顿和斯坦福大学，后进入兰德（后进入兰德（Rand）研究所。）研究所。1957年发表年发表“Dynamic Programming”一书，标识动态规划的正式诞生。一书，标识动态规划的正式诞生。 动态规划的基本概念和定义动态规划的基本概念和定义 动态规划的研究对象和引例动态规划的研究对象和引例 动态规划是解决复杂系统优化问题的一种方法。动态规划是解决复杂系统优化问题的一种方法。是解决是解决动态系统多阶段决策动态系统多阶段决策过程的基本方法之一过程的基本方法之

3、一。5 动态规划：动态规划：是解决是解决多阶段决策多阶段决策过程过程最优最优化问题的一种方法，无特定的数学模型。化问题的一种方法，无特定的数学模型。可解决可解决 与时间有关的动态问题与时间有关的动态问题 与时间无关的静态问题与时间无关的静态问题6多阶段决策问题n 1）动态决策动态决策将将时间作为变量时间作为变量的决策问题称的决策问题称为动态决策。其基本特点是多次决策。为动态决策。其基本特点是多次决策。n 2）多阶段多阶段决策问题是一类特殊形式的动态决决策问题是一类特殊形式的动态决策问题。是指这样一类活动过程：系统的动态策问题。是指这样一类活动过程：系统的动态过程可以按照时间进程分为状态过程可以

4、按照时间进程分为状态互相联系而又互相联系而又互相区别互相区别的各个阶段，而且在每个阶段都要进的各个阶段，而且在每个阶段都要进行决策，当每一个阶段的决策确定以后，就完行决策，当每一个阶段的决策确定以后，就完全确定了一个过程的活动路线。全确定了一个过程的活动路线。712345引例引例1 最短路线问题最短路线问题25375632455114633334C1C3D1AB1B3B2D2EC28引例引例2 生产与存贮问题生产与存贮问题要求确定一个逐月的生产计划，在满足需求条件下，要求确定一个逐月的生产计划，在满足需求条件下，使一年的生产与存贮费用之和最小？使一年的生产与存贮费用之和最小？ 引例引例3 投资

5、决策问题投资决策问题某公司现有资金某公司现有资金Q万元，在今后万元，在今后5年内考虑给年内考虑给A，B，C，D 4个项目投资？个项目投资？引例引例4 设备更新问题设备更新问题现企业要决定一台设备未来现企业要决定一台设备未来8年的更新计划，问应在年的更新计划，问应在哪些年更新设备可使总费用最小？哪些年更新设备可使总费用最小？ 9 动态规划方法的特点n 优点：1）许多问题用动态规划求解比线性规划、非线许多问题用动态规划求解比线性规划、非线性规划更有效，特别是离散性问题，解析数学性规划更有效，特别是离散性问题，解析数学无用武之地，而动态规划成为得力工具。无用武之地，而动态规划成为得力工具。2）某些情

6、况下，用动态规划处理不仅能作定性某些情况下，用动态规划处理不仅能作定性描述分析，且可利用计算机给出求其数值解的描述分析，且可利用计算机给出求其数值解的方法。方法。10动态规划方法的特点缺点：缺点：n1）没有统一的处理方法，求解时要根据问题）没有统一的处理方法，求解时要根据问题的性质，结合多种数学技巧。因此，实践经验的性质，结合多种数学技巧。因此，实践经验及创造性思维将起重要作用。及创造性思维将起重要作用。n2）“维数障碍维数障碍”：当变量个数太多时，由于：当变量个数太多时，由于计算机内存和速度的限制导致问题无法解决。计算机内存和速度的限制导致问题无法解决。有些问题由于涉及的函数没有理想的性质使

7、问有些问题由于涉及的函数没有理想的性质使问题只能用动态规划描述，而不能用动态规划方题只能用动态规划描述，而不能用动态规划方法求解。法求解。11第二节第二节 最优化原理与动态规划的数学模型最优化原理与动态规划的数学模型一一 最短路线问题求解最短路线问题求解25375632455114633334C1C3D1AB1B3B2D2EC2f(E)=012考虑一个阶段的最优选择考虑一个阶段的最优选择C1C3D1AB1B3B2D2EC2f(D1)=3f(E)=02537563245511463333413C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(D1)=325375632455114

8、633334考虑一个阶段的最优选择考虑一个阶段的最优选择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考虑二个阶段

9、的最优选择考虑二个阶段的最优选择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)

10、=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(B

11、2)=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 ） C275324551253146333342

12、36C1C3D1AB1B3B2D2EC2f(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 7532455125314633334246C1C3D1AB1B3B2D2EC2f(D2)=4f(E)=0f(C3)=6f(D1)=3f(B3)=8f(C2)=7f(C1)=4f(A)=11f(B2)=7f(B1)=1

13、1状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态A （ A，B3） B3 （ B3， C2 ） C2 （ C2， D2 ） D2 （ D2， E） E7532455125314633334从从A到到E的最短路径为的最短路径为11，路线为，路线为AB3C2 D2 E25通过上例的讨论，可以看到多级决策过程具有以下特点：（1）把整个过程看成（或认为地分成）把整个过程看成（或认为地分成）n个具有个具有递推关系的单级过程。递推关系的单级过程。（2）采取逐级分析的方法，一般由最后一级开）采取逐级分析的方法，一般由最后一级开始倒向进

14、行。始倒向进行。（3）在每一级决策时，不只考虑本级的性能指）在每一级决策时，不只考虑本级的性能指标的最优，而且同时考虑本级及以后的总性能标的最优，而且同时考虑本级及以后的总性能指标最优，因此它是根据指标最优，因此它是根据“全局全局”最优作出本最优作出本级决策的。级决策的。26动态规划法较之穷举法的优点动态规划法较之穷举法的优点:(1) 容易计算出结果；容易计算出结果；(2) 动态规划的计算结果不仅得到了从起始点动态规划的计算结果不仅得到了从起始点到最终点的最短路线，而且得到了中间段任一到最终点的最短路线，而且得到了中间段任一点到最终点的最短路线点到最终点的最短路线 。27动态规划方法的基本思想

15、：动态规划方法的基本思想： (1)将多阶段决策过程划分阶段，恰当地选取状态变将多阶段决策过程划分阶段，恰当地选取状态变量、决策变量及定义最优指标函数从而把问题化成一量、决策变量及定义最优指标函数从而把问题化成一族同类型的子问题，然后逐个求解。族同类型的子问题，然后逐个求解。 (2)求解时从边界条件开始，逆求解时从边界条件开始，逆(或顺或顺)过程行进方向，过程行进方向，逐段递推寻优。在每一个子问题求解时，都要使用它前逐段递推寻优。在每一个子问题求解时，都要使用它前面已求出的子问题的最优结果，最后一个子问题的最优面已求出的子问题的最优结果，最后一个子问题的最优解，就是整个问题的最优解。解，就是整个

16、问题的最优解。 (3)动态规划方法是既把当前一段与未来各段分开，动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方又把当前效益和未来效益结合起来考虑的一种最优化方法，因此每段的最优决策选取是从全局考虑的，与该段法，因此每段的最优决策选取是从全局考虑的，与该段的最优选择一般是不同的。的最优选择一般是不同的。28二、基本概念和基本原理二、基本概念和基本原理动态规划模型要用到的概念：动态规划模型要用到的概念：n (1)阶段阶段; (2)状态状态; (3)决策和策略决策和策略; (4)状态状态转移律转移律; (5)指标函数。指标函数。1、阶段：、阶段：将将所给问

17、题的过程，按时间或空间特征分解所给问题的过程，按时间或空间特征分解成若干互相联系的阶段，以便按次序去求每阶段的解，常用成若干互相联系的阶段，以便按次序去求每阶段的解，常用字母字母k表示阶段变量。表示阶段变量。292、状态：、状态：各阶段开始时的客观条件叫做状态。各阶段开始时的客观条件叫做状态。状态变量状态变量：描述各阶段状态的变量，用描述各阶段状态的变量，用sk表示第表示第k阶段阶段的状态变量。的状态变量。状态集合：状态集合：状态变量的取值集合，用状态变量的取值集合，用Sk表示。表示。一阶段：S1A二阶段：S2B1,B2,B3三阶段：S3C1,C2,C3四阶段：S4D1,D2一阶段：一阶段：S

18、1A二阶段：二阶段：S2B1,B2,B3三阶段：三阶段：S3C1,C2,C3四阶段：四阶段：S4D1,D2二、基本概念和基本原理二、基本概念和基本原理30二、基本概念和基本原理二、基本概念和基本原理二、基本概念和基本原理二、基本概念和基本原理3、决策：、决策：当各段的状态取定以后，就可以作出不同当各段的状态取定以后，就可以作出不同的决定（或选择），从而确定下一阶段的状态，这种决的决定（或选择），从而确定下一阶段的状态，这种决定称为决策。定称为决策。决策变量：决策变量：表示决策的变量，称为决策变量，常用表示决策的变量，称为决策变量，常用xk(sk)表示第表示第k阶段当状态为阶段当状态为sk时的决

19、策变量。时的决策变量。允许决策集合：允许决策集合：决策变量的取值往往限制在一定范围决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合，用内，我们称此范围为允许决策集合，用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 策略：策略：各段决策确定后

20、，整个问题的决策序列就构成各段决策确定后，整个问题的决策序列就构成一个策略，用一个策略，用p1,nx1(s1),x2(s2),.xn(sn)表示。表示。允许策略集合：允许策略集合：对每个实际问题，可供选择的策略有一对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作定范围，称为允许策略集合，记作P1,n，使整个问题达到最，使整个问题达到最优效果的策略就是最优策略。优效果的策略就是最优策略。32二、基本概念和基本原理二、基本概念和基本原理 5、状态转移方程、状态转移方程：动态规划中本阶段的状态往往是上一阶动态规划中本阶段的状态往往是上一阶段状态和上一阶段的决策结果。段状态和上一阶段的

21、决策结果。第第k段的状态段的状态sk，本阶段决策为，本阶段决策为xk(sk)，则第，则第k+1段的状态段的状态sk+1也就完全确定，它们的关系可用公式表示：也就完全确定，它们的关系可用公式表示：sk+1=Tk(sk,xk)33 6、指标函数：、指标函数：用于衡量所选定策略优劣的数量指标。用于衡量所选定策略优劣的数量指标。 它分为它分为阶段指标函数阶段指标函数和和过程指标函数过程指标函数。 阶段指标函数阶段指标函数是指第是指第k段，从状态段，从状态sk出发，采取决策出发，采取决策xk时的效益，用时的效益，用Vk(sk,uk)表示。表示。 过程指标函数过程指标函数记为记为fk(sk)：表示从第：表

22、示从第k段状态段状态sk按预定指按预定指标到过程终止时的效益值。标到过程终止时的效益值。二、基本概念和基本原理二、基本概念和基本原理34最简单的方法最简单的方法穷举法。共有多少条穷举法。共有多少条路径，依次计算并比较。路径，依次计算并比较。动态规划方法动态规划方法本方法是从过程的最本方法是从过程的最后一段开始，用逆序递推方法求解，逐步求后一段开始，用逆序递推方法求解，逐步求出各段各点到终点的最短路线，最后求得起出各段各点到终点的最短路线，最后求得起始点到终点的最短路线始点到终点的最短路线。三、三、最优化原理与动态规划的数学模型最优化原理与动态规划的数学模型35最优化原理Optimization

23、 Principle 作为整个过程的最优策略具有这样的性质：n无论过去的状态和决策如何，对先前决策所形成的状态而言，余下的诸决策必构成最优策略。 若若M是从是从A到到B的最优路线上的一点，则的最优路线上的一点，则从从M到到B的路线也是最优的的路线也是最优的。ABM36动态规划的基本方程（最优化原理的应用）n根据最优化原理得到的计算动态规划问题的递（逆）推关系式：, ( ,) nk niiii KVv s x当时，11()() ( ,)()kkkkkkkkkkxDsf soptv s xfsn,i k ( ,) k nkiiVv s x当时11()( ) ( ,)()kkkkkkkkkkxDsf

24、 soptv s xfs边界条件：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阶段的最优指标函数值37构成动态规划模型的条件构成动态规划模型的条件-1n根据时间或空间的自然特征，实际问题能恰根据时间或空间的自然特征，实际问题能恰当地划分为当地划分为若干阶段若干阶段，形成，形成多阶段决策多阶段决策的过的过程程38构成动态规划模型的条件构成动态规划模型的条件-2 -2n正确的选择状态变量正确的选择状态变量S 动态规划的状态应具有三

25、个特征：动态规划的状态应具有三个特征： 能够用来描述受控过程的能够用来描述受控过程的演变特征演变特征；n满足无后效性：满足无后效性：如果某阶段状态给定，则在这阶如果某阶段状态给定，则在这阶段以后过程的发展只与当前的状态有关，而与过去的段以后过程的发展只与当前的状态有关，而与过去的历史无关。或当前的状态是过去历史发展的一个总结，历史无关。或当前的状态是过去历史发展的一个总结，过程的过去历史只能通过当前的状态影响未来的发展。过程的过去历史只能通过当前的状态影响未来的发展。n可知性：可知性：各阶段状态变量的值，直接或间各阶段状态变量的值，直接或间接地都是可以知道的。接地都是可以知道的。39构成动态规

26、划模型的条件构成动态规划模型的条件 - - 3n确定决策变量确定决策变量sk的含义及每阶段的的含义及每阶段的允许决策集合允许决策集合Dk(sK)()(kkkksDsx40构成动态规划模型的条件构成动态规划模型的条件-4 -4正确写出状态转移方程正确写出状态转移方程 sk+1=T(sk,xk(sk) 或或 sk+1=T(sk,xk) 41构成动态规划模型的条件构成动态规划模型的条件-5 -5明确指标函数明确指标函数Vk,n的关系的关系一般有两种形式一般有两种形式n和式n积式11()() ( ,)()kkkkkkkkkkxDsf soptv s xfs11()( ) ( ,)()kkkkkkkkk

27、kxDsf soptv s xfs42四四 逆序解法与顺序解法逆序解法与顺序解法如果寻优的方向与多阶段决策过程的实际行进方如果寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得全过程向相反，从最后一段开始计算逐段前推，求得全过程的最优策略，称为逆序解法。的最优策略，称为逆序解法。顺序解法的寻优方向同于过程的行进方向，计算顺序解法的寻优方向同于过程的行进方向，计算时从第一段开始逐段向后递推，计算后一阶段要用到时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，最后一段计算的结果就是全过前一阶段的求优结果，最后一段计算的结果就是全过程的最优结果。程的最优结

28、果。43第一步：k=0状态：s1Af0(A)0求解步骤求解步骤顺序解法求解顺序解法求解44第二步：k=1 状态：B1 B2 x1*(B1)=Ax1*(B2)=Af1(B1)4f1(B2)5(4)(5)45第三步：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)=B146(4)(5)(6)(7)(10)(12)第四步：k=3 状态：D1 D2 D3x3*(D1)=C1或C2x3*(D2)=C2x3*(D3)=C3f

29、3(D1)11f3(D2)12f3(D3)14(11)(12)(14)47第五步：k=4 状态：E1 E2 x4*(E1)=D1x4*(E2)=D2f4(E1)14f4(E2)14(4)(5)(6)(7)(10)(12)(11)(12)(14)(14)(14)48第六步：k=5 状态：F u5*(F)=E2f5(F)17(6)(4)(5)(7)(10)(12)(11)(12)(14)(14)(14)(17)即从A到F的最短距离为17。最优路线为：AB1C2D2E2F49逆序解法与顺序解法建模的不同点逆序解法与顺序解法建模的不同点1状态转移方式不同状态转移方式不同sk+1=Tk(sk,xk) s

30、k=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+1502指标函数的定义不同指标函数的定义不同 逆序解法中，我们定义最优指标函数逆序解法中，我们定义最优指标函数fk(sk)表示第表示第k段从状态段从状态sk出发，到终点后部子过程最优效益值，出发，到终点后部子过程最优效益值，f1(s1)是整体最优函数值。是整体最优函数值。 顺序解法中，定义最优指标函数顺序解法中，定义最优指标函数fk

31、(sk+1)表示第表示第k段段时从起点到状态时从起点到状态sk+1的前部子过程最优效益值。的前部子过程最优效益值。fn(sn+1)是是整体最优函数值。整体最优函数值。513. 基本方程形式不同基本方程形式不同(1)当指标函数为阶段指标和形式逆序解法则基本方程为：则基本方程为：顺序解法, (,)nk njjjjkVvsx=1,11 (,)kkjjjjVv sx+=1111()(,)(),1,.,2,1()0kkkkkkkkkuDnnfsopt v sxfskn nfs+=+=-= 11101()(,)()1,2,.,( )0kkkkkkkkkuDfsopt v sxfsknfs+-=+= 52(

32、2)当指标函数为阶段指标积形式当指标函数为阶段指标积形式逆序解法逆序解法基本方程为：基本方程为：基本方程为：基本方程为：顺序解法顺序解法nkjjjjnkusvV),( ,kjjjjkusvV11, 1),( 1111()(,)(),1,.,2,1()1kkkkkkkkkuDnnfsopt v s ufskn nfs1)(,.,2 , 1)(),()(10111sfnksfusvoptsfkkkkkDukkkk53第第3 3节节 离散确定型动态规划 模型求解Solution of Discrete Certain DP Model54例4n某一警卫部门共有某一警卫部门共有12支巡逻队，负责支巡逻

33、队，负责4个要害个要害部位部位A、B、C、D的警卫巡逻。的警卫巡逻。n对每个部位可分别派出对每个部位可分别派出2-4支巡逻队，并且由支巡逻队，并且由于派出巡逻队数的不同，各部位预期在一段于派出巡逻队数的不同，各部位预期在一段时期内可能造成的损失有差别，具体数字见时期内可能造成的损失有差别，具体数字见表表8-1。n问该警卫部门应往各部位分别派多少支巡逻问该警卫部门应往各部位分别派多少支巡逻队，使总的预期损失为最小队，使总的预期损失为最小。 ABCD218382434314352231410312125巡逻队数巡逻部位预期损失55解-1n阶段变量阶段变量k ：把12支巡逻队往4个部位派遣看成依次分

34、四个阶段(k=1，2，3，4)。n状态变量状态变量sk：表示每个阶段初拥有的可派遣的巡逻队数是前面阶段决策的结果，也是本阶段决策的依据n决策变量决策变量xk：表示各阶段对各部位派出的巡逻队数，n各阶段允许的决策集合决策集合Dk(sk)为：nDk(sk)=xk|2xk4| (k=1,2,3,4)56解解-2n状态转移方程：状态转移方程：sk+1=sk-xk (k=1,2,3,4)n每阶段初拥有可派遣的巡逻队数量等于上阶段初拥有的数量减去上阶段派出的数量n过程函数为阶段指标函数之和：过程函数为阶段指标函数之和：n阶段指标函数阶段指标函数vk(xk)表示表示k阶段派出的巡逻队数阶段派出的巡逻队数为为

35、xk时，该阶段的部位的预期损失值时，该阶段的部位的预期损失值44,41,41( )()( )()kiikkiikkki ki kVv xv xv xv xV 57解-3nfk(sk)：表示从：表示从k阶段状态为阶段状态为sk出发，采用最优出发，采用最优子策略到过程结束时的预期损失值，有子策略到过程结束时的预期损失值，有n先考虑给先考虑给D部位派巡逻队，即部位派巡逻队，即k=4，上式可写，上式可写为为 n边界条件边界条件f5(s5)=0 ，所以，所以 11()()min ()()kkkkkkkkkxDsfsv xfs444444455()()min ()( )xDsf sv xf s444444

36、4()( )min ()xDsf sv x58解-4 x4s4v4(x4)f4(s4)x4*23423434233431313434312525453431252546343125254因因D4（s4）=2，3，4，又，又s4的可能值是的可能值是2s46，故，故由表由表8-1的数据，可得下表的结果的数据，可得下表的结果 4444444()()min ()xDsf sv x总共总共12支巡逻队，每部位支巡逻队，每部位24支巡逻队。支巡逻队。59解-5n联合考虑对联合考虑对C、D两个部位派巡逻队，两个部位派巡逻队，k=3，有：，有：n因因D3(s3)=2,3,4，4s38，可得如下结果，可得如下结

37、果333333344()( )min ()( )xDsf sv xf s x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+3122+34552624+2522+3121+34492724+2522+2521+31473824+2522+2521+2546460解-6n考虑对考虑对B、C、D三个部位派巡逻队，三个部位派巡逻队，k=2，有，有由由D2(s2)=2,3,4，8s210，可得如下结果可得如下结果 222222233()()min ()( )xDsf sv xf s x2s2v2(x2)+f3(s2-x2)f2(s2)x2*234838+4935

38、+5531+58872938+4735+4931+558431038+4635+4731+4980461解-7n考虑对考虑对A、B、C、D四个部队派巡逻队，即四个部队派巡逻队，即k=1时，有时，有n因因s1=12, D1(s1)=2,3,4,可得如下结果可得如下结果 111111122()( )min ( )( )xDsf sv xf s x1s1v1(x1)+f2(s1-x1)f1(s1)x1*2341218+8014+8410+8797462解-8 x3s3v3(x3)+f4(s3-x3)f3(s3)x3*234424+34582524+31 22+34552624+25 22+3121+

39、34492724+25 22+2521+31473824+25 22+2521+25464x4s4v4(x4)f4(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)

40、f1(s1)x1*2341218+80 14+84 10+8797463第四节第四节 离散随机型动态规划离散随机型动态规划 模型求解模型求解Solution of Discrete Stochastic DP Model64随机型的动态规划n指状态的转移律是不确定的，即对给定的状态和决策，下一阶段的到达状态是具有确定概率分布的随机变量，这个概率分布由本阶段的状态和决策完全确定第第k+1阶段可阶段可能的状态数能的状态数给定状态给定状态xk和决策和决策uk的情况下，下一个可的情况下，下一个可能到达的状态的概率能到达的状态的概率从从k阶段状态阶段状态sk转移到转移到k+1阶段阶段状态为状态为i时的指时的指标函数值标函数值 随机性动态规划的基本结构图skxkSk+165指标函数为和函数的转换方程n在随机性的动态规划问题下，由于下一阶段到达的状态和阶段的效益值不确定，只能根据各阶段的期望效益值进行优化。n因此随机性的动态规划问题中，当指标函数值为各阶段效益和的情况下，基本方程应写为 )(),(max)(11)(kkkksDxkksfxsgEsfkkk期望值期望值66665 5一般数学规划模型的动态规划解法一般数学规划模型的动态规划解法用动态规划的方法求解一般数学规划模型思想：用动态规划的方法求解一般数学规划模型思想：将取定每个变量的值作为一个阶段，则有将取定每个变量的值作