运筹学7动态规划

主要内容:§7.1多阶段决策过程的最优化§7.2动态规划的基本概念和基本原理§7.3动态规划模型的建立与求解§7.4动态规划应用举例第七章动态规划教学要求：•1．掌握动态规划的基本概念：阶段、状态、决策、策略、状态转移方程、指标函数和最优值函数、最优策略、最优轨线•2．了解动态规划的基本理论：最优性定理和最优性原理•3．掌握动态规划基本思想和基本方程•4．牢固掌握动态规划的顺序解法和逆序解法。会处理动态与静态规划的关系•5．了解和掌握若干典型问题的动态规划模型及求解技巧：如最短路线、资源分配、生产计划、货物存储、设备更新与系统可靠性问题、背包问题、推销商问题等•6．了解多维动态规划降维方法和减少离散状态点数方法•7．了解随机性问题的动态规划求解方法•重点：动态规划顺序解法和逆序解法；若干典型问题动态规划模型及求解技巧；•难点：建立动态规划数学模型的状态转移方程。§7.1多阶段决策过程的最优化动态规划（DynamicProgramming）是运筹学的一个重要分支，它是解决多阶段决策过程最优化的一种方法。美国数学家贝尔曼（R.E.Bellman）等人在50年代初提出了解决多阶段决策问题的“最优性原理”（PrincipleofOptimality）。1957年贝尔曼出版了专著“动态规划”，该书是动态规划的第一本著作。目前动态规划已经用于解决最优路径问题、资源分配问题、生产调度问题、设备更新问题、复合系统可靠性问题及生产过程最优控制等，并且取得了显著的效果。回本章目录动态规划是求解问题的一种方法，而不是算法（线性规划是一种算法），因而没有标准的数学表达式，对于具体问题需要具体分析。一、多阶段决策问题在生产经营活动中，某些问题决策过程可以划分为若干相互联系的阶段，每个阶段需要做出决策，从而使整个过程取得最优。由于各个阶段不是孤立的，而是有机联系的，也就是说，本阶段的决策将影响过程下一阶段的发展，从而影响整个过程效果，所以决策者在进行决策时不能够仅考虑选择的决策方案使本阶段最优，还应该考虑本阶段决策对最终目标产生的影响，从而做出对全局来讲是最优的决策。当每个阶段的决策确定以后，全部过程的决策就是这些阶段决策所组成的一个决策序列，所以多阶段决策问题也称为序贯决策问题。多阶段决策问题中，各个阶段一般是按照时间来划分的，随着时间的发展而产生各个阶段的决策，从而形成决策序列，这就是动态的含义。在一些与时间无关的静态问题中（如非线性规划等），可以人为地赋予时间的概念，使其成为一个多阶段决策问题，再用动态规划方法处理。12n状态决策状态决策状态状态决策二、多阶段决策问题举例属于多阶段决策类的问题很多，例如：例1工厂生产过程：由于市场需求是一随着时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决定生产计划安排。例2设备更新问题：一般企业用于生产活动的设备，刚买来时故障少，经济效益高，即使进行转让，处理价值也高，随着使用年限的增加，就会逐渐变为故障多，维修费用增加，可正常使用的工时减少，加工质量下降，经济效益差，并且，使用的年限越长、处理价值也越低，自然，如果卖去旧的买新的，还需要付出更新费．因此就需要综合权衡决定设备的使用年限，使总的经济效益最好。例3连续生产过程的控制问题：一般化工生产过程中，常包含一系列完成生产过程的设备，前一工序设备的输出则是后一工序设备的输入，因此，应该如何根据各工序的运行工况，控制生产过程中各设备的输入和输出，以使总产量最大。以上所举问题的发展过程都与时间因素有关，因此在这类多阶段决策问题中，阶段的划分常取时间区段来表示，并且各个阶段上的决策往往也与时间因素有关，这就使它具有了“动态”的含义，所以把处理这类动态问题的方法称为动态规划方法。不过，实际中尚有许多不包含时间因素的一类“静态”决策问题，就其本质而言是一次决策问题，是非动态决策问题，但是也可以人为地引入阶段的概念当作多阶段决策问题，应用动态规划方法加以解决。例4资源分配问题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题)。例5运输网络问题：如图7-1所示的运输网络，点间连线上的数字表示两地距离(也可是运费、时间等)，要求从fk(sk)至v10的最短路线。这种运输网络问题也是静态决策问题。但是，按照网络中点的分布，可以把它分为4个阶段，而作为多阶段决策问题来研究。v255614109388778865611795v1v3v4v6v5v7v9v8v101234图7-1运输网络图示（10）（14）（16）（15）（17）（22）（22）（21）（27）特别注意：动态规划求解的多阶段决策问题的特点：适合于用动态规划方法求解的只是一类特殊的多阶段决策问题，即具有“无后效性”的多阶段决策过程。所谓无后效性，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。§7.2动态规划的基本概念和基本原理引言为了说明动态规划的基本思想方法和特点，以下面的例题来讨论求最短路问题的方法。回本章目录第一种方法称做全枚举法或穷举法。它的基本思想是列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从A到G的路程可以分为6个阶段。第一段的走法有2种，第二、三、四、五、六段的走法各6、8、6、6、2，因此共有2×3×2×2×2＝48条可能的路线，分别算出各条路线的距离，最后进行比较求优。AB1B2C1C2C3C4D1D2D3E1E2E3F1F2G531368763685338422213335256643最优路径长度＝18第二种方法即所谓“局部最优路径”法，是说某人从k阶段出发，他并不顾及全线是否最短，只是选择当前最短途径，“逢近便走”，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是下图所示，全程长度是25；显然，这种方法的结果常是错误的．AB1B2C1C2C3D1D2D3E1E2E3F1F2G531368763685338422213335256643C4第三种方法是动态规划方法。动态规划方法寻求该最短路问题的基本思想是，首先将问题划分为6个阶段，每次的选择总是综合后继过程的一并最优进行考虑，在各段所有可能状态的最优后继过程都已求得的情况下，全程的最优路线便也随之得到。一、动态规划的基本概念运用动态规划求解多阶段决策问题，首先要将该问题写成动态规划模型，再进行求解，动态规划模型中用到的概念及符号如下：12n状态决策状态决策状态状态决策12ks1u1s2u2s3skuksk+1例6最短路问题如图7-2所示，要从A地到E地铺设管线，中间需要经过三个中间站，两点之间的连线上的数字表示距离，问应该选择什么路线，使总距离最短？35256321737562254321B1AB2B3C1C2C3C4ED2D11.阶段（stage）根据所需解决问题的特点，按照时间或空间顺序把整个过程划分为若干相互联系的阶段，以便按照一定次序求解。描述阶段的变量称为阶段变量，通常用字母k表示阶段变量。例如例6中，从A到E可以划分为四个阶段，第一阶段k=1，从A到B（B有三种选择，B1，B2，B3）；第二阶段k=2，从B到C（C有四种选择，C1，C2，C3，C4）；第三阶段k=3，从C到D（D有两种选择，D1，D2）；第四阶段k=4，从D到E。•例6可以分为四个阶段来求解，k=1，2，3，4。上海A伊犁EB1B245C1C2C3425D1D356753D243654546第一阶段第二阶段第三阶段第四阶段2.状态（state）状态表示各阶段开始所处的自然状况或客观条件，它既是某阶段过程演变的起点，又是前一阶段某种决策的结果。描述状态的变量称为状态变量，常用sk表示第k阶段的状态变量。状态变量sk的取值集合称为状态集合，第k阶段的状态集合记为Sk，例如例6中，第一阶段状态为A，第二阶段有三个状态：B1，B2，B3；第三阶段有四个状态：C1，C2，C3，C4；第四阶段有两个状态：D1，D2；各阶段状态集合分别为：•S1=｛A｝•S2=｛B1，B2，B3｝•S3=｛C1，C2，C3，C4｝•S4=｛D1，D2｝上海A伊犁EB1B245C1C2C3425D1D356753D243654546第一阶段第二阶段第三阶段第四阶段S1={A}S2={B1,B2}S3={C1,C2,C3}…….n个阶段的决策过程有n+1个状态变量这里状态的选取应当满足无后效性：系统从某个阶段往后的发展演变，完全由系统本阶段所处的状态及决策所决定，与系统以前的状态及决策无关。也就是说，过去的历史只能通过当前的状态去影响未来的发展，当前的状态是过去历史的一个完整总结。只有具有无后效性的多阶段决策过程才适合于用动态规划方法求解。例6中，当某个阶段已经选定某个点时，这个点以后的管线铺设只与该点有关，而与该点以前的管线铺设无关，所以满足无后效性。3.决策（decision）当各阶段的状态选定以后，可以做出不同的决定（或选择）从而确定下一个阶段的状态，这种决定（或选择）称为决策。表述决策的变量称为决策变量，常用uk（sk）表示第k阶段当状态为sk时的决策变量。实际问题中，决策变量的取值往往限制在某一范围内，此范围称为允许决策集合，常用Dk（sk）表示第k阶段从状态sk出发的允许决策集合，显然uk（sk）∈Dk（sk）。例如例6中，第二阶段若从B2出发，可以选择C1，C2，C3，C4，即允许决策集合为：D2（B2）=｛C1，C2，C3，C4｝当决定选择C3时，可以表示为：u2（B2）=C3上海A伊犁EB1B245C1C2C3425D1D356753D243654546第一阶段S1={A}u1(A)=B1或u1(A)=B2,D1(A)={B1,B2}4.策略（policy）当各个阶段的决策确定以后，各阶段的决策形成一个决策序列，称此决策序列为一个策略。使系统达到最优效果的策略称为最优策略。在n阶段决策过程中，从第k阶段到终止状态的过程，称为k后部子过程（或称为k子过程），k后部子过程相应的决策序列称为k后部子过程策略，简称子策略，记为pk，n（sk），即：Pk，n（sk）=｛uk（sk），uk+1（sk+1），…，un（sn）｝当k=1时，即由第一阶段某个状态出发做出的决策序列称为全过程策略，简称策略，记为p1，n（s1），即：p1，n（s1）=｛u1（s1），u2（s2），…，un（sn）｝上海A伊犁EB1B245C1C2C3425D1D356753D243654546P1,5(A)={A,B1,C2,D2,E}P1,5(A)={A,B2,C3,D3,E}P2,5(A)={B2,C2,D1,E}5.状态转移方程（statetransferequation）•动态规划中，本阶段的状态往往是上一个阶段状态和上一个阶段决策作用的结果。设第k阶段状态为sk，做出的决策为uk（sk），则第k+1阶段的状态sk+1随之确定，他们之间的关系可以表示为：•sk+1=Tk（sk，uk）•这种表示从第k阶段到第k+1阶段状态转移规律的方程称为状态转移方程，它反映了系统状态转移的递推规律。例如例6中，上一阶段的决策就是下一阶段的状态，所以状态转移方程为：•sk+1=uk（sk）•状态转移方程是建立动态规划数学模型的难点之一。),(),(),(122231112kkkkusTsusTsusTs12ks1u1s2u2s3skuksk+1一旦某阶段的状态和决策为已知，下阶段的状态便完全确定——无后效性。6.指标函数和最优指标函数•衡量所选策略优劣的数量指标称为指标函数。它定义在全过程和所有后部子过程，常用Vk，n表示，即：•Vk，n=Vk，n（sk，uk，s