动态规划问题的基本要素和最优化原理PPT课件.ppt

第二第二节节 动态规动态规划划问题问题的基本要素的基本要素和最和最优优化原理化原理2.1 动态规动态规划的基本概念划的基本概念2.2 动态规动态规划的基本思想划的基本思想2.3 建立建立动态规动态规划模型的步划模型的步骤骤 精品课程运筹学.1、阶阶段：段：把一个把一个问题问题的的过过程，恰当地分程，恰当地分为为若干个相互若干个相互联联系系的的阶阶段段，以便于按一定的次序去求解。，以便于按一定的次序去求解。描述描述阶阶段的段的变变量称量称为为阶阶段段变变量量。阶阶段的划分，一段的划分，一般是根据般是根据时间时间和空和空间间的自然特征来的自然特征来进进行的，但要便行的，但要便于于问题转问题转化化为为多多阶阶段决策。段决策。2、状、状态态：表示每个：表示每个阶阶段开始所段开始所处处的的自然状况或客自然状况或客观观条件条件。通常一个。通常一个阶阶段有若干个状段有若干个状态态，描述，描述过过程状程状态态的的变变量称量称为为状状态变态变量量。年、月、年、月、路段路段一个数、一个数、一一组组数、数、一个向一个向量量 状状态变态变量的取量的取值值有一定的允有一定的允许许集合或范集合或范围围，此，此集合称集合称为为状状态态允允许许集合集合。2.1 动态规动态规划的基本概念划的基本概念精品课程运筹学.3、决策：表示当、决策：表示当过过程程处处于某一于某一阶阶段的某个状段的某个状态时态时，可以作出不同的决定，从而确定下一可以作出不同的决定，从而确定下一阶阶段的状段的状态态，这这种决定称种决定称为为决策决策。描述决策的描述决策的变变量，称量，称为为决策决策变变量量。决策。决策变变量是状量是状态态变变量的函数。可用一个数、一量的函数。可用一个数、一组组数或一向量（多数或一向量（多维维情情形）来描述。形）来描述。在在实际问题实际问题中决策中决策变变量的取量的取值值往往在某一范往往在某一范围围之内，之内，此范此范围围称称为为允允许许决策集合决策集合。系系统统在某一在某一阶阶段的状段的状态转态转移不但与系移不但与系统统的当前的状的当前的状态态和决策有关，而且和决策有关，而且还还与系与系统过统过去的去的历历史状史状态态和决策有和决策有关。关。4、多多阶阶段决策段决策过过程程 可以在各个可以在各个阶阶段段进进行决策，去控制行决策，去控制过过程程发发展的多段展的多段过过程；程；其其发发展是通展是通过过一系列的状一系列的状态转态转移来移来实现实现的；的；精品课程运筹学.图图示如下：示如下：状状态转态转移方程是确定移方程是确定过过程由一个状程由一个状态态到另到另一个状一个状态态的演的演变过变过程。程。如果第如果第k阶阶段状段状态变态变量量sk的的值值、该阶该阶段的决策段的决策变变量一量一经经确定，第确定，第k+1阶阶段状段状态变态变量量sk+1的的值值也就确定。也就确定。其状其状态转态转移方程如下（一般形式）移方程如下（一般形式）12ks1u1s2u2s3skuksk+1 能用能用动态规动态规划方法求解的多划方法求解的多阶阶段决策段决策过过程是一程是一类类特殊的多特殊的多阶阶段决策段决策过过程，即程，即具有无后效性具有无后效性的多的多阶阶段段决策决策过过程。程。精品课程运筹学.如果状如果状态变态变量不能量不能满满足无后效性的要求，足无后效性的要求，应应适当地改适当地改变变状状态态的定的定义义或或规规定方法。定方法。动态规动态规划中能划中能处处理的状理的状态转态转移移方程的形式方程的形式。状状态态具有无后效性的多具有无后效性的多阶阶段决策段决策过过程的状程的状态转态转移方程如下移方程如下无后效性无后效性(马马尔尔可夫性可夫性)如果某如果某阶阶段状段状态给态给定后，定后，则则在在这这个个阶阶段以后段以后过过程的程的发发展不受展不受这这个个阶阶段以前各段状段以前各段状态态的影响；的影响；过过程的程的过过去去历历史只能通史只能通过过当前的状当前的状态态去影响去影响它未来的它未来的发发展；展；构造构造动态规动态规划模型划模型时时，要充分注意是，要充分注意是否否满满足无后效性的要求；足无后效性的要求；状状态变态变量要量要满满足无后效性的要求足无后效性的要求；精品课程运筹学.5 5、策略：是一个按、策略：是一个按顺顺序排列的决策序排列的决策组组成的集合。在成的集合。在实际问题实际问题中，可供中，可供选择选择的策略有一定的范的策略有一定的范围围，称，称为为允允许许策略集合策略集合。从允。从允许许策略集合中找出达到最策略集合中找出达到最优优效果的效果的策略称策略称为为最最优优策略策略。6 6、状、状态转态转移方程：是确定移方程：是确定过过程由一个状程由一个状态态到另一个到另一个状状态态的演的演变过变过程，描述了状程，描述了状态转态转移移规规律。律。7 7、指、指标标函数和最函数和最优值优值函数：用来衡量所函数：用来衡量所实现过实现过程程优优劣的一种数量指劣的一种数量指标标，为为指指标标函数函数。指。指标标函数的最函数的最优值优值，称称为为最最优值优值函数函数。在不同的。在不同的问题问题中，指中，指标标函数的含函数的含义义是不同的，它可能是距离、利是不同的，它可能是距离、利润润、成本、成本、产产量或量或资资源源消耗等。消耗等。动态规动态规划模型的指划模型的指标标函数，函数，应应具有可分离性，并具有可分离性，并满满足足递递推推关系关系。精品课程运筹学.小小结结:方程方程:状状态转态转移方程移方程概念概念:阶阶段段变变量量k k状状态变态变量量s sk k决策决策变变量量u uk k;指指标标:动态规动态规划本划本质质上是多上是多阶阶段决策段决策过过程程;效益效益指指标标函数形式函数形式:和、和、积积无后效性无后效性可可递递推推精品课程运筹学.解多解多阶阶段决策段决策过过程程问题问题，求出，求出 最最优优策略策略，即最，即最优优决策序列决策序列f1(s1)最最优轨线优轨线，即即执执行最行最优优策略策略时时的的状状态态序列序列 最最优优目目标标函数函数值值从从 k 到到终终点最点最优优策略策略子策略的最子策略的最优优目目标标函数函数值值精品课程运筹学.1、动态规动态规划方法的关划方法的关键键在于正确地写出基本在于正确地写出基本的的递递推关系式和恰当的推关系式和恰当的边边界条件（界条件（简简称基本方称基本方程）。要做到程）。要做到这这一点，就必一点，就必须须将将问题问题的的过过程分程分成几个相互成几个相互联联系的系的阶阶段，恰当的段，恰当的选选取状取状态变态变量量和决策和决策变变量及定量及定义义最最优值优值函数，从而把一个大函数，从而把一个大问题转问题转化成一化成一组组同同类类型的子型的子问题问题，然后逐个求，然后逐个求解。即从解。即从边边界条件开始，逐段界条件开始，逐段递递推推寻优寻优，在每，在每一个子一个子问题问题的求解中，均利用了它前面的子的求解中，均利用了它前面的子问问题题的最的最优优化化结结果，依次果，依次进进行，最后一个子行，最后一个子问题问题所得的最所得的最优优解，就是整个解，就是整个问题问题的最的最优优解。解。2.2 动态规动态规划的基本思想划的基本思想精品课程运筹学.2、在多、在多阶阶段决策段决策过过程中，程中，动态规动态规划方法是既把当前一段划方法是既把当前一段和未来一段分开，又把当前效益和未来效益和未来一段分开，又把当前效益和未来效益结结合起来考合起来考虑虑的的一种最一种最优优化方法。因此，每段决策的化方法。因此，每段决策的选选取是从全局来考取是从全局来考虑虑的，的，与与该该段的最段的最优选择优选择答案一般是不同的答案一般是不同的.最最优优化原理：作化原理：作为为整个整个过过程的最程的最优优策略具有策略具有这样这样的性的性质质：无：无论过论过去的状去的状态态和决策如何，相和决策如何，相对对于前面于前面的决策所形成的状的决策所形成的状态态而言，余下的决策序列必然构而言，余下的决策序列必然构成最成最优优子策略。子策略。”也就是也就是说说，一个最，一个最优优策略的子策策略的子策略也是最略也是最优优的。的。3、在求整个、在求整个问题问题的最的最优优策略策略时时，由于初始状，由于初始状态态是已知的，是已知的，而每段的决策都是而每段的决策都是该该段状段状态态的函数，故最的函数，故最优优策略所策略所经过经过的各的各段状段状态态便可逐段便可逐段变换变换得到，从而确定了最得到，从而确定了最优优路路线线。精品课程运筹学.2.3 建立建立动态规动态规划模型的步划模型的步骤骤 1 1、划分、划分阶阶段段 划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题题要要人人为为地地赋赋予予“时间时间”概念，以便划分概念，以便划分阶阶段。段。2 2、正确、正确选择选择状状态变态变量量 选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选择选择是从是从过过程演程演变变的特点中的特点中寻寻找。找。3 3、确定决策、确定决策变变量及允量及允许许决策集合决策集合 通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要要给给出决策出决策变变量的取量的取值值范范围围，即确定允，即确定允许许决策集合。决策集合。精品课程运筹学.4 4、确定状、确定状态转态转移方程移方程 根据根据k k 阶阶段状段状态变态变量和决策量和决策变变量，写出量，写出k+1k+1阶阶段状段状态态变变量，状量，状态转态转移方程移方程应应当具有当具有递递推关系。推关系。5 5、确定、确定阶阶段指段指标标函数和最函数和最优优指指标标函数，建立函数，建立动动态规态规划基本方程划基本方程 阶阶段指段指标标函数是指第函数是指第k k 阶阶段的收益，最段的收益，最优优指指标标函数是指函数是指从第从第k k 阶阶段状段状态态出出发发到第到第n n 阶阶段末所段末所获获得收益的最得收益的最优值优值，最后写出最后写出动态规动态规划基本方程。划基本方程。以上五步是建立以上五步是建立动态规动态规划数学模型的一般步划数学模型的一般步骤骤。由于。由于动动态规态规划模型与划模型与线线性性规规划模型不同，划模型不同，动态规动态规划模型没有划模型没有统统一的一的模式，建模模式，建模时时必必须须根据具体根据具体问题问题具体分析，只有通具体分析，只有通过过不断不断实实践践总结总结，才能，才能较较好掌握建模方法与技巧。好掌握建模方法与技巧。精品课程运筹学.