[管理学]第六章 动态规划.ppt

Chapter 1 第六章 动态规划Dynamic Programming 多阶段决策过程最优化问题：有一些活动，它在时间或空间上可以分成若干个阶段，需要对每个阶段进行决策(有若干个方案可供选择)，使得活动的整体效果最好。 每个阶段的决策都不是可以任意确定的，它依赖于当前的状况，同时，它的决策结果又影响到以后的决策。组成了一个决策序列。 这样的决策过程是在变化的过程中产生的，故有动态的含义。处理它的方法称为动态规划的方法。 方法：多阶段问题转化成一系列互相联系的较容易的单阶段问题。 第一节 动态规划的基本思想和方法 一、多阶段决策过程最优化问题举例 P169 例4.3：最短路线问题（P176） 从A点到E点可分成4个阶段。以A为起点，终点有三个B1、B2、B3，有三个选择。若选择B2，则B2为第一阶段决策的结果。同时它又是第二阶段的开始状态。当每个阶段做出决策的结果，直接影响到后面的选择和决策的结果。 最短路线有一个重要特性： 如果从起点A经过C2点和D1点到达终点E是一条最短的路线，则由C2 点经过D1 点到达E点的这条子路线，是由C2 点出发到达E点所有路线中的最短路线。 寻找最短路线的方法，从最后一段开始，由后向前逐步推进，找出各点到E点的最短路线，最后就能确定一条从A点到E点的最短路线。 作业例1：如图给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)。试求一条从A到G的铺管线路，使总距离最短(或总费用最小)。 最短路线为A→B1→C2→D1→E2→F2→G 二、动态规划的最优性原理 作为整个过程的最优策略具有这样的性质：即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简言之，一个最优策略的子策略总是最优的。 但“最优性原理”仅仅是策略最优性的必要条件，非充分条件。 充分条件应是动态规划的基本方程。 三、动态规划的基本概念和基本方程 1、阶段 把所给问题的过程，分成若干个相互联系的阶段，以便按一定的次序去求解。 阶段变量常用K来表示。阶段的划分一般是按照时间和空间的自然特征来划分，但要便于将问题的过程转化为多阶段决策的过程。 K＝1，2，3，4，5，6 2、状态 每个阶段开始时所处的状况，同时又是前一阶段的终点。用Sk来表示第K阶段的状态。 如：S2={B1，B2}；S3={C1，C2，C3，C4}。 注意：要明确每个阶段状态的集合或者范围。 “状态”具有 “无后效性”（“马尔科夫性”）：如果某阶段的状态给定后，当前的状态是以往历史的总结，则在这阶段以后过程的发展不受这阶段以前各阶段的影响。 3、决策 决策表示当过程处于某一阶段的某个状态的选择，Uk(Sk)表示第k阶段处于Sk状态时的决策。 如：U2(B1)＝C2，表示处于第二阶段，以B1为始点选择C2作为第二阶段的终点。 Dk(Sk)表示第k阶段处于Sk状态时的允许决策集合。D2(B1)＝{ C1 ,C2 ,C3}。Uk(Sk)∈Dk(Sk)。 4、策略 由各个阶段的决策所组成的决策函数序列为全过程策略。 P1,n(S1)={ U1(S1), U2(S2),…, Un(Sn)} Pk,n(Sk)={ Uk(Sk), Uk+1(Sk+1),…, Un(Sn)}为k子过程的策略。 允许策略集合，用P来表示。从允许策略集合中找出达到最优效果的策略称为最优策略。 5、状态转移方程 第k+1阶段的状态是由第k阶段的状态和第k阶段的决策所决定的，用方程的形式表示这种关系为Sk+1=Tk(Sk,Uk),它反映了由第k阶段到第k+1阶段的状态转移规律，称为状态转移方程，状态转移函数。如：S3=T2(S2,U2) C2＝T2(B1，C2) 6、指标函数和最优值函数 用来衡量所实现过程优劣（全过程策略，或k子过程策略优劣）的一种数量指标，称为指标函数。常用Vk,n表示。 Vk,n＝Vk,n(Sk，Uk ，Sk＋1 ，…,Sn+1) k=1,2,…,n 对于要构成动态规划模型的指标函数，应具有可分离性，并满足递推关系，即Vk,n可表示为Sk，Uk ，Vk＋1,n的函数。 Vk,n(Sk,Uk ,Sk＋1 ,…,Sn+1)＝φk(Sk,Uk ,Vk＋1,n(Sk＋1,Uk＋1…,Sn+1)) 常见的指标函数有： 1)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的和。 Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝ Vk,n（Sk，Uk ，Sk＋1 ，…,Sn+1）＝vk(sk,uk)+ Vk+1,n（Sk+1，Uk+1 ，Sk＋2 ，…,Sn+1） 2)整个过程和它的任一子过程的指标函数是它所包含的各阶段的指标的乘积，即： Vk,n（Sk，Uk ，Sk＋1