运筹学第八章动态规划.ppt

1、第八章动态规划，导论，动态规划是解决多阶段决策过程优化的一种方法。这种方法是由美国数学家贝尔曼在20世纪50年代初提出的。并成功地解决了生产管理和工程技术中的许多问题，从而建立了运筹学的一个新分支，即动态规划。贝尔曼在1957年出版了动态规划，这是动态规划领域的第一本书。动态规划与其他规划方法的区别在于，动态规划是解决某一类问题(多阶段决策问题)的方法，是研究问题的一种方式，而不是具体的算法。因此，与线性规划不同，它没有标准的数学表达式和一套明确定义的(算法)规则，但必须分析和管理具体问题。因此，在学习动态规划时，不仅要正确理解基本概念和方法，还要在积累一定经验的基础上，用丰富的想象力建立模型

2、，用创造性的技巧解决问题。提纲，1个动态规划的例子，2个动态规划的基本概念，3个动态规划的基本思想和原则，4个逆序解和顺序解，学习目标：1阐明什么是多阶段决策问题，并特别注意如何将没有明显时间背景的问题转化为多阶段决策问题。P156例1动态规划，P156例2机器负荷分配问题(时间阶段问题)有某种机器设备用来完成两种工作A和B.如果k开始时完整机器的数量是xk，如果uk的数量用于A，剩余的(xkuk)用于工作B，则该年的预期收入是g(uk) h(xkuk)。G(uk)和h(xkuk)是已知函数，g(0)=h(0)=0。此外，机器和设备在使用中会损坏。当机器用于工作A时，一年后可继续使用的完好机器

3、数量占年初投入的70%；如果在作业B中使用，一年后可以继续使用的完整机器数量占年初输入的90%。明年年初，可继续用于A和B的设备数量为xk 1=0.7uk 0.9(xk uk)。让第一年年初的完好机器总数为1000台，并询问连续五年每年A和B的机器数量如何分配，以使五年的总收入最大化。1动态规划的例子，相应的问题称为多阶段决策问题。这是一个多阶段的决策过程。这个过程可以分为几个相互关联的阶段，每个阶段都需要做出一个决定，从而在整个过程中形成一个决定。第一年，u1，x2=0.7u10.9 (x1-u1)，U2，x3=0.7u20.9 (x2-U2)，u3，第四年，u4，x5=0.7u4 0.9(

4、x4-u4)，u5，P156例1最短路线问题(空间从A到E有很多路线可供选择，且各点之间的距离如图所示。问旅行者选择哪条路线，这样从A到E的总距离是最短的。1，2，3，4，决策1，决策2，决策3，决策4可以看作是一个四阶段决策问题。从以上两个例子中，我们可以知道，所谓的多阶段决策问题就是指这样一个决策问题：这个过程可以分为相互关联的阶段，每个阶段对应一组备选决策，而每个决策的选择取决于当前的状态并影响未来的整体结果。当每个阶段的决策被选定时，它就构成了一个决策序列，称为策略，它对应于某个效果。多阶段决策问题是寻找最佳策略。多阶段决策过程的特点1。每个阶段的决策都是相互关联的。多阶段决策过程优化

5、的目的是实现整个活动过程的最佳整体效果，而不是某一阶段的最佳“局部”效果。因此，每个阶段的决策选择不是任意的。前一个决策的选择决定了当前的状态，从而影响到决策后下一阶段的状态和决策，从而影响整体效果。因此，在每个阶段做出决策时，决策者不仅要考虑这一阶段的最佳方案，还要考虑对最终目标的影响，从而做出总体上最佳的决策。动态规划是满足这一要求的优化方法。2.每个阶段的决策通常与“时间”相关。动态规划方法与“时间”密切相关。随着时间进程的发展，每个阶段的决策都是决定的，从而产生一个决策序列，这就是“动态”的含义。但是，一些与时间无关的静态问题，只要人为地将“时间”因素引入到问题中，也可以被视为多阶段决

6、策问题，可以用动态规划方法来处理。学习目标：1 .准确、熟练掌握动态规划的基本概念，尤其是状态变量、决策变量、状态转移规律、指标函数和基本方程。2.动态规划的基本概念是，为了解决和表达决策和过程的发展顺序，把给定的问题分成几个相互关联的不同的子问题，称为多阶段决策问题阶段。阶段是需要做出决定的子问题。通常，根据决策的时间或空间顺序来划分阶段。描述一个阶段的变量称为阶段变量，通常记录为k，k=1，2和n。例如，解可以根据空间分为四个阶段，k=1，2，3，4。(1)阶段、状态：每个阶段开始时的客观条件。描述每个阶段状态的变量称为状态变量，而xk通常用来表示第k阶段的状态。(2)状态。在示例1中，状

7、态是某个阶段的起始位置。根据状态变量的值是连续的还是离散的，动态规划问题可以分为离散型和连续型。动态规划中的状态应满足无后效性(Markov属性):所谓无后效性是指系统达到某一状态之前的过程决策不会影响到该状态之后的决策。它是指系统从某一阶段到未来的发展，它只由这一阶段的状态及其未来的决策所决定，而与系统以前的状态和决策(历史)无关。该过程的过去历史只能通过当前状态影响其未来发展。在示例1中，当在某个阶段的状态中选择了某个点时，该点之后的路线仅与该点相关，并且不受该点之前的路线的影响，因此该状态没有后效。状态集：状态变量xk的值集称为状态集，它实际上是一个关于状态的约束条件。通常，Sk用来表示

8、状态集xkSk。第一阶段S1=a；第二阶段有三个国家B1，B2和B3，所以S2=B1，B2和B3。(3)决策，当过程在某一阶段处于某一状态时，可以作出不同的决策来确定下一阶段的状态，这叫做决策。描述决策的变量称为决策变量，当状态为xk时，uk(xk)通常用于表示k阶段的决策变量，xk是状态变量的函数。在示例1中，从第二阶段的状态B1，可以选择下一阶段的C1、C2和C3。如果我们决定选择C1，它可以表示为u2(B1)=C1。B1，C1，C2，C3，决策集：当状态为xk时，决策变量uk(xk)的值范数称为决策集，通常用Dk(xk)表示。在示例1中，从第二阶段的状态B1，可以选择下一阶段的C1、C2

9、和C3。也就是说，D2(B1)=C1、C2和C3；B1、C1、C2、C3，决策集实际上是决策的约束条件，uk(xk) Dk(xk)。总结阶段k、状态xk、状态集Sk、决策集uk(xk)和决策集Dk(xk)。(4)状态转移定律(方程):从某个状态值xk开始，当确定了决策变量uk(xk)的值时，也就确定了下一阶段状态变量xk 1的值。描述从xk到xk 1转变的定律称为状态转变定律(方程式)。从第二阶段的状态B1开始，如果我们明确选择C2(即确认下一阶段的状态)。在上面的例子中，u2(B1)=C2的状态转移定律是：xk 1=uk(xk)。一般来说，下一阶段状态变量xk 1的值是前一阶段的某个状态变量

10、xk和前一阶段的决策变量uk(xk)的函数，表示为xk 1=Tk(xk，uk(xk)，(5)策略：由N个决策阶段组成的决策序列依次构成一个策略，由P1U1 (x1)、U2 (x2)和UN (xn)表示。在本例中，p14u1 (a)=B1，U2 (B1)=C2，u3 (C2)=D1，U4 (D1)=e代表策略之一，其总距离为2 5 6 3=16。策略集：在实际问题中，由于每个阶段都有许多可供选择的决策，它们的不同组合构成了许多可供选择的决策序列(策略)，由它们组成的集合称为策略集，被记录为P1n。从策略集合来看，效果最好的策略称为最优策略。子策略：从K阶段到N阶段，由依次做出的阶段决策组成的决策

11、序列称为K子策略，表示为PKN=英国(XK)、英国1 (XK 1)、联合国(XN)，例如，从第三阶段C2状态开始的子策略可以表示为P34=U3 (C2)，它是在整个过程或子过程或阶段中定义的一个确定的数量函数。对于不同的问题，指标函数可以是成本、成本、产值、利润、产量、消耗、距离、时间、效用等。阶段指数函数、过程指数函数、阶段指数函数：是指在K阶段从状态xk进行决策uk时产生的收益，用vk(xk，uk)表示。在示例1中，索引函数是距离。例如，v2(B1，C2)表示从B1开始，采用从判定点到C2的两点之间的距离，即v2(B1，C2)=5。过程指数函数：是指在第K阶段从某个状态xk取子策略pkn时

12、所获得的收益，在例1中记录为Vkn(xk，uk，xk 1，uk 1，xn)，如V34 (C2，U3 (C2)=D1，D1，U4 (D1)=E，E)。过程指数函数Vkn通常是描述整个过程或后K子过程的优劣的量化指标，它是由阶段指数函数vk(1)累加而成的(1)可分性：适用于动态规划求解问题的过程指标函数(即目标函数)必须具有关于阶段指标的可分形式，即后子过程的指标函数可以表示为：vkn (xk，uk，xk1，uk 1，xn)=vk (xk，uk) vk1 (xk1，uk 1) VN在多阶段决策问题中，一种常见的目标函数形式是每个阶段的效果之和，即对于某些问题， 例如系统可靠性，目标函数是每个阶段

13、的效果的产物，例如，简而言之，特定问题的目标函数的表达形式需要依赖于特定问题。 (2)递归：过程指标函数Vkn应满足递归关系，即递归，VKN (xk，uk，xk1，uk 1，xn)，kxk，uk，v (k 1) n (xk1，uk 1，xn)，vk (xk，uk) vk1 Uk)，V(k 1)n(xk 1，uk 1，xn)，最优指标函数：它表示当kth阶段的状态为xk至终止时，采用最优策略pkn*的最优收益值写为fk(xk)。Fk (xk)=vkn (xk，pkn *)=optvkn (xk，pkn)，例如1，f3(C2)=3 4=7。其中opt可以根据具体情况采用最大值或最小值。，C2，动态

14、规划的目标是什么？最优解：最优策略p1n最优值：最优指标f1(A)，多阶段决策问题的数学模型综上所述，一类适用于动态规划方法的多阶段决策问题的数学模型是如下形式： f1=opt V1n(x1，p1n)最优指标函数xk 1=Tk(xk，Uk(xk)状态转移方程ukDk决策变量xkSk状态变量k=1，2，n，阶段变量，St，上述数学模型表明，对于给定的多得到一个(或多个)最优策略或最优决策序列u1、u2、un，它不仅满足左表达式给出的所有约束，而且使左表达式所示的目标函数得到极值。summary :index function form : sum，product，no aftereffect，r

15、ecursion，fk (xk)=vkn (xk，pkn *)=optvkn (xk，pkn)，vkn (xk，uk，xk1，uk 1，xn)，kxk，Xn)，解决多阶段决策过程的问题，找出，u1*、u2*、un*、x1*、x2*、xn*、1。划分阶段，2。正确选择状态变量，3。确定决策变量和允许的决策集，4。确定状态转移方程，5。确定阶段指标函数和最优指标函数，建立静态问题应人工给出“时间”的概念，以便划分阶段。在建立动态规划模型的步骤中，状态变量的选择不仅要准确描述过程的演化，而且要满足无后效的要求，并且每个阶段的状态变量的值都是可以确定的。通常选择待解决问题的关键变量作为决策变量，并给出决策变量的取值范围，即确定允许的决策集。根据k阶段状态变量和决策变量，编写了k-1阶段状态变量，状态转移方程应该具有递归关系。阶段指数函数指的是第k阶段的收入，最优指数函数指的是从第k阶段到第n阶段结束所获得的收入的最优值。最后，写出了动态规划的基本方程。以上五个步骤是建立动态规划数学模型的一般步骤。由于动态规划模型不同于线性规划模型，在