11-动态规划1.ppt

1、14:063:29，第1页，多阶段决策问题：一个动态系统可以分为几个阶段，这些阶段的状态是相互关联的，并且根据时间的不同而互不相同，每个阶段根据系统的不同状态进行决策，目的是在整个决策过程中达到最佳效果。动态规划是解决多阶段决策问题的有效方法。多阶段决策过程示意图：包含随时间变化的因素和变量的系统。第一节，多阶段决策过程和实例，动态系统：动态规划，14:06:29，第2页，用动态规划方法解决与“时间”密切相关的多阶段决策问题。随着时间进程的发展，每个阶段的决策都会产生一系列的决策，形成一个决策序列，这就意味着“动态”，然而动态规划方法也可以解决与时间无关的静态问题，只要在问题中人为引入“时间段

2、”因素，静态问题就可以转化为多阶段决策问题。本章将介绍这种处理方法。第1节多阶段决策过程和实例，14:06:29，第3页，多阶段决策问题的特点用动态规划解决，通常多阶段决策过程的发展是通过一系列的状态变换来实现的。一般来说，一个系统在某一阶段的状态转换不仅与该阶段的状态和决策有关，还与系统过去的状态和决策有关。只有一个特殊的多阶段决策问题，即没有“后效”的多阶段决策过程，才适合用动态规划方法来解决。第一节，多阶段决策过程及实例，14:06:29，第4页，无后效(也称马尔可夫)无后效(也称马尔可夫)是指系统从某一阶段发展到未来，这仅由该阶段的状态及其未来的决策决定，与系统的先前状态和决策(历史)

3、无关。第1节多阶段决策过程和实例，14:06:29，第5页，第1节多阶段决策过程和实例，动态规划方法指南为了说明动态规划的基本思想、方法和特点，下图是讨论寻找最短路径问题的方法的实例，14336006336029，第6页，9，(用反证的方法证明)，14:06:29，第7页，状态变量的值有一定的允许集或范围，这叫做允许状态集。1.阶段和阶段变量是一个动态系统，根据时间或空间的自然特征可以分为几个相互关联的阶段；描述阶段的变量称为阶段变量，通常用k表示；状态，状态变量，状态：每个阶段开始时的自然状态。通常一个阶段有几个状态。描述状态的变量称为状态变量，而sk通常用于表示第k级的状态。第2节，动态规

4、划的基本概念，14:06:29，第8页，决策变量的取值范围称为允许决策集。常用的Dk(sk)表示当状态处于第k阶段时允许的决策集。很明显，描述决策的变量被称为决策变量，它是状态变量的函数，常用的uk(sk)表示第k阶段状态为sk时的决策变量。决策，决策变量，在某个阶段的某个状态下，你可以做出不同的选择，这种选择叫做决策。uk(sk) Dk(sk)，14:06:29，第9、4页。状态转换方程：系统在阶段k处于状态sk，并且执行判决uk(sk)的结果是系统状态转换，即，系统从阶段k的初始状态sk转换到终止状态sk 1。对于无后效的多阶段决策过程，从阶段K到阶段k 1的状态转换完全由阶段K的状态sk

5、和决策uk(sk)决定，与系统过去的状态和决策无关。这种系统状态的转换可以用数学公式来描述：sk 1=Tk(sk，uk(sk)，通常称为多阶段决策过程的状态转换方程。14:06:29，第10页，子过程的决策序列称为子策略，它被记录为pk，n(sk)，也就是说，策略的值范围称为允许的策略集，用p表示。允许策略集中最佳效果的策略称为最佳策略。14:06:29，第11、6页。指数函数用来衡量一项战略或子战略或决策的效果的量化指数称为指数函数。它是在整个过程或子过程或阶段中定义的一个确定的数量函数。对于不同的问题，指标函数可以是成本、成本、产值、利润、产量、消耗、距离、时间、效用等。14:06:29，

6、第12页，阶段指数函数：用于测量从K阶段的sk状态做出决策uk的效果，用vk表示(sk，uk)；过程指标函数：用于衡量从第k阶段的sk状态开始到第n阶段的sk状态结束，采用策略pk，n(sk)获得的总效果，用vk，n，14:063:29表示，第13，10页。过程指数函数等于每个阶段的指数函数之和。20过程指数函数等于它包含的每个阶段的指数函数的乘积。也就是说，在过程索引函数和阶段索引函数之间有两个共同的关系：即，通过采用第14页上的从第k阶段到第n阶段状态sk的最优策略而获得的过程索引函数值。(kth子流程的)最优值函数：如第15页第14:06336029节所述，为了解决多阶段决策流程问题，要

7、求f1(s1)，s1是唯一的，第16页第14336006:29节：动态规划的基本思想和基本方程S5=E1，E2，E3，k=6，S6=F1，F2，f1gf6 (f1)=4f2g，F6 (F2)=3，目标函数，14:06:29，第22页，14336006:29，第23页，询问如何分配投资金额以实现总收益最大化。解决方案：静态规划问题的模型可以列举如下。例1一家公司有10万元的资本。如果项目投资金额(i=1，2，3)为xi，其收益分别为。考虑到效益函数的形式，sk表示K阶段的可用资金量。1.根据问题，投资可以分三个阶段进行，即K=1，2，3；2.确定状态变量sk，k=1，2，3；3。确定决策变量英国

8、：U1=X1，U2=X2，U3=X3。英国代表第K阶段的投资金额。通常，静态规划中的变量可以作为决策变量。第4节，静态规划的动态规划解决方案，14336006:29，第24页，第1、2、3、S4 X3=0，2x12，4x3，9x2，效益函数，k，决策xk，4。根据约束方程，建立状态转移方程：sk 1=sk-uk，14:06:29，第25页，过程索引函数，5。建立基本方程：当阶段k=6时。逆向求解，14:063:29，第26页，当阶段k=1时，有一个最优决策和一个最优值函数，所以最后我们可以得到：S3=S2-x * 2=S1-x * 1-x * 2，14:063:29 2。确定状态变量sk，k=

9、1，2，3；解决方案：3。确定决策变量英国：U1=X1，U2=X2，U3=X3。通常，静态规划中的变量可以作为决策变量，并串联三个组件，14336006:29，第28、4页。根据约束方程建立状态转移方程：14:06:06。当阶段k=3时，有，当阶段k=2时，有，最优决策，最优值函数，阶段指数函数，基本方程，6，逆序求解，14336006:29，第30页，当阶段k=1时，有，所以最终结果是：S3=S2-X。当阶段k=n时，可以获得最优决策xn=un(sn)和最优值fn(sn)。具体方法如下：f1(s1)=opt，14:06:29，第32页，当阶段k=n-1时，得到状态转移方程、最优决策xn-1=un-1(sn-1)和最优值fn-1(sn-1)。当阶段k=k时，包括状态转移方程，得到最优决策xk=uk(s