第1讲 最优化技术基础-2

1.多阶段决策过程的最优化(1)多阶段决策问题▲动态规划的研究对象是多阶段决策问题。▲多阶段决策问题:根据问题本身的特点，可以将其求解的全过程划分为若干个相互联系的阶段(即子问题)，在它的每一阶段都需要作出决策，并且在一个阶段的决策确定以后再转移到下一个阶段。▲多阶段决策过程:前一个阶段的决策要影响到后一个阶段的决策，从而影响整个过程。各个阶段所确定的决策就构成了一个决策序列，称为一个策略。一般来说，每一阶段可供选择的决策往往不止一个，因此，整个过程会有许多可供选择的策略。第四节动态规划▲最优策略：对应于一个策略，可以由一个量化的指标来确定这个策略对应的效果，不同的策略有各自的效果。在所有可供选择的策略中，对应效果最好的策略称为最优策略。多阶段决策过程最优化的目标是要达到整个活动过程的总体效果最优。由于各段决策间有机地联系着，本段决策的执行将影响到下一段的决策，以至于影响总体效果，所以决策者在每段决策时不应仅考虑本阶段最优，还应考虑对最终目标的影响，从而作出对全局来讲是最优的决策。动态规划就是符合这种要求的一种决策方法。应指出，动态规划不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。(2)多阶段决策问题举例a)工厂生产过程:为了取得全年最佳经济效益，在全年的生产过程中，根据市场需求，逐月或者逐季度地根据库存和需求情况决定生产计划安排。b)设备更新问题:需要综合权衡决定设备的使用年限，使总的经济效益最好c)连续生产过程的控制问题:一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。以上问题的发展过程都与时间因素有关，因此阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就是“动态”的含义，所以把处理这类问题的方法称为动态规划方法。d）资源分配问题:某工业部门拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题与时间因素无关，不属动态决策，但我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题。e）运输网络问题:运输网络连线上的数字表示两地距离(也可以是运费、时间等)，要求从A至E的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为几个阶段，而作为多阶段决策问题来研究。(3)动态规划求解的多阶段决策问题的特点通常多阶段决策过程的发展是通过状态的一系列变换来实现的。一般情况下，系统在某个阶段的状态转移除与本阶段的状态和决策有关外，还可能与系统过去经历的状态和决策有关。因此，问题的求解就比较困难复杂。适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”(马尔柯夫性)的多阶段决策过程。所谓无后效性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。多阶段决策过程特点:状态x1阶段1T1决策u1状态x2决策u2阶段2T2状态x3...状态xk决策uk阶段kTk状态xk+1...状态xn决策un阶段nTn状态xn+1(4)动态规划方法导引例1：为了说明动态规划的基本方法和特点，以上面运输网络图为例,讨论求最短路问题的方法。第一种方法枚举法.它的基本思想是列举出所有可能发生的方案和结果，再一一比较，求出最优方案。这里从A到E的路程可以分为5个阶段。各阶段走法:第1段有3种，第2段各有3种，第3段各有2种，第4段各1种，因此共有3×3×2×1＝18条可能的路线，分别算出各条路线的距离进行比较，可知最优路线是AB2C1D1E,最短距离是19．显然，如果组成网络的节点很多时，用穷举法求最优路线的计算量将会十分庞大，其中包含许多重复计算．枚举法虽可找出最优方案，但不是个好算法第二种方法:“局部最优路径”法.说某人从某站出发，他选择“逢近便走”的决策，以为只要“局部最优”,就会达到”“整体最优”，所取决策必是AB3C3D1E,但全程长度是25；显然，这种方法的结果常是错误的．局部最优法则是错误方法.第三种方法动态规划方法.首先将问题划分为5个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。动态规划方法总是从过程的最后阶段开始考虑，然后逆着实际过程发展的顺序，逐段向前递推计算直至始点。动态规划方法属较科学有效的算法，计算过程中，系统地删去了所有中间非最优的方案组合，从而使计算量比枚举法大为减少。2.动态规划的基本概念使用动态规划方法解决多阶段决策问题，首先要将实际问题写成动态规划模型，需要对动态规划的一些基本术语加以说明和定义：1.阶段为了便于求解和表示决策及过程的发展顺序，而把所给问题恰当地划分为若干个相互联系又有区别的子问题，称之为多段决策问题的阶段。一个阶段，就是需要作出一个决策的子问题，通常，阶段是按决策进行的时间或空间上先后顺序划分的。2.状态和状态变量用以描述系统在某特定的时间与空间域中所处位置及运动特征的量，称为状态。每个阶段的状态可分为初始状态和终止状态，阶段k的初始状态记作sk，终止状态记为sk+1。但通常定义阶段的状态即指其初始状态，故阶段k的终止状态sk+1为阶段k+1的初始状态。描述过程k的状态变量称为状态变量sk，其取值范围称为可能状态集Sk,即sk∈Sk。3.决策和决策变量决策是状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。描述决策变化的量称之决策变量，和状态变量一样，决策变量可以用一个数或一向量来描述，也可以是状态变量的函数，记以uk=uk(sk)，表示阶段k状态sk时的决策变量。决策变量的取值也有一定的允许范围，称之允许决策集合Uk(sk),uk(sk)∈Uk(sk)。4.策略全过程策略(Policy)是依次进行的全部n个阶段决策构成的决策序列，表示为p1,n{u1,u2,…,un};从k阶段到第n阶段，依次构成的决策序列称为k部子策略,表示为pk,n{uk,uk+1,…,un}，显然当k=1时的k部子策略就是全过程策略。在实际问题中，由于在各个阶段可供选择的决策有许多个，因此，它们的不同组合就构成了许多可供选择的决策序列(策略)，它们组成”允许策略集”，记作P1,n，从中找出具有最优效果的策略称为最优策略。5.状态转移方程系统在阶段k处于状态sk，执行决策uk(sk)的结果是系统状态的转移，即系统由阶段k的初始状态sk转移到终止状态sk+1，或者说由k阶段的状态sk转移到了k+1阶段的状态sk+1。对于具有无后效性的多阶段决策过程,系统由阶段k到阶段k+1的状态转移完全由阶段k的状态sk和决策uk(sk)所确定，与系统过去的状态s1,s2,…,sk-1及其决策u1(s1),u2(s2)…uk-1(sk-1)无关。系统状态的这种转移，用数学公式描述即有：(1)))(,(1kkkkksusTs式(1)称为多阶段决策过程的状态转移方程。有些问题的状态转移方程不一定存在数学表达式，但是它们的状态转移，还是有一定规律可循的。6.指标函数和最优解指标函数是用来衡量策略效果的某种数量指标。对不同问题，指标函数可以是诸如费用、成本、产值、利润、产量、耗量、距离、时间、效用等等。(1)阶段指标函数:用gk(sk,uk)表示第k段处于sk状态且所作决策为uk(sk)时的指标，它就是第k段指标函数，简记为gk。(2)过程指标函数（也称目标函数）:用Rk(sk,uk)表示第k子过程的指标函数。如运输网络图的Rk(sk,uk)表示处于第k段sk状态且所作决策为uk时，从sk点到终点E的距离。由此可见，Rk(sk,uk)不仅跟当前状态sk有关，还跟该子过程策略pk(sk)有关，因此它是sk和pk(sk)的函数，应表示为:))(,(kkkkspsR用fk(sk)表示第k子过程指标函数在状态sk下的最优值,即与它相应的子策略称为sk状态下的最优子策略，简记为:特别当k=1且s1取值唯一时，f1(s1)就是问题的最优值，而p1*就是最优策略。我们把最优策略和最优值统称为问题的最优解。nkspsRoptsfkkkksPpkkkKk,,2,1))},(,({)()(nkuuupnkkk,,2,1},,,,{1))(,(kkkkspsR},,),({)(211111nuususspnkuuupnkkk,,2,1},,,,{17.多阶段决策问题的数学模型综上所述，适于应用动态规划方法求解的一类多阶段决策问题，亦即具有无后效性的多阶段决策问题的数学模型呈以下形式:（5）nkUuSsusTstsusususRRoptfkkkkkkkknnuun,,2,1),(..),,,,,,(12211~1模型说明对于给定的多阶段决策过程，求取一个最优策略(决策序列)，使之既满足全部约束条件，又使目标函数取得极值，同时，执行该最优策略时，过程状态演变序列即最优路线,按上述定义，所谓最优决策是指它们在全过程上整体最优},,,{21nuuu},,,,{121nnssss8.最优化原理（贝尔曼最优化原理）作为一个全过程的最优策略具有这样的性质：对于最优策略过程中的任意状态而言，无论其过去的状态和决策如何，余下的诸决策必构成一个最优子策略。该原理的具体解释是，若某一全过程最优策略为：则对上述策略中所隐含的任一状态而言，第k子过程上对应于该状态的最优策略必然包含在上述全过程最优策略p1*中，即为)}(,),(),({)(11nnkkkkkksusususp)}(),(,),(),({)(221111nnkksususususp贝尔曼最优化原理概念:如图,如果已经给出从点A到点C的最优轨迹，那么从任一中间点B到点C的部分轨迹必须是从B到C的最优轨迹。设给出路线Ⅰ-Ⅱ是从A到C的最优路线，根据贝尔曼原理，则路线Ⅱ是从B到C的最优路线。[证]:用反证法,假设某条其它路线，例如Ⅱ’是从B到C的最优路线，那么，路线I-Ⅱ’比路线I-Ⅱ有更小的费用。但这与I-Ⅱ是从A到C最优路线的前提相矛盾，因此Ⅱ必是从B到C的最优路线贝尔曼阐述:“一个最优策略有这样的特性，不论初始状态和初始决策如何，相对于第一个决策所形成的状态来说，余下的决策必定构成一个最优策略”。(1)应将实际问题恰当地分割成n个子问题(n个阶段)。通常是根据时间或空间而划分的。(2)正确地定义状态变量sk，使它既能正确地描述过程的状态，又能满足无后效性．动态规划中的状态变量必须具备以下三个特征：a)要能够正确地描述受控过程的变化特征。b)要满足无后效性。即如果在某个阶段状态已经给定，那么在该阶段以后，过程的发展不受前面各段状态的影响，如果所选的变量不具备无后效性，就不能作为状态变量来构造动态规划的模型。c)要满足可知性。即所规定的各段状态变量的值，可以直接或间接地测算得到。3.动态规划方法的基本步骤(3)正确地定义决策变量及各阶段的允许决策集合Uk(sk).根据经验，一般将问题中待求的量，选作动态规划模型中的决策变量。或者在把静态规划模型(如线性与非线性规划)转换为动态规划模型时，常取前者的变量xj为后者的决策变量uk。(4)能够正确地写出状态转移方程。如果给定第k阶段状态变量sk的值，则该段的决策变量uk一经确定，第k+1段的状态变量sk+1的值也就完全确定，即有sk+1=Tk(sk,uk)(5)正确地构造出目标函数.例如常见的指标函数是取各段指标和的形式其中表示第i阶段的指标，它显然满足递推关系：nkiiiikkusgsR),()(),(iiiusg),,(),(111nkkkkkkssRusgR求最短