多阶段决策过程(multistepdecisionpr

第6章动态规划本章基本要求1、理解多阶段决策问题的含义；2、掌握动态规划的基本概念，特别是状态变量、决策变量、状态转移方程、指标函数与最优值函数、边界条件、基本方程；3、掌握最优化原理的内容、动态规划的求解步骤及逆序递推法、顺序递推法；4、掌握求解动态规划的解析法与列表法；5、会判定动态规划问题的类型并求解.在生产、计划、管理中往往需要研究处理包含多个阶段决策过程的问题，这类问题能分解为若干阶段或若干个子问题，通过对每个子问题作出决策得到解决，动态规划就是研究这种多阶段决策问题的优化方法．它能为分析问题的全过程提供总的框架，在这个框架内又可用各种优化技术解决每一阶段上的具体问题. 根据决策过程是离散的还是连续的，是确定的还是随机的，动态规划大体可分为离散确定型、离散随机型、连续确定型和连续随机型等四种决策类型.本章首先介绍多阶段决策问题及动态规划的基本概念，然后介绍动态规划的基本原理、求解步骤和方法，最后介绍动态规划的一些应用.§6.1多阶段决策问题动态规划（Dynamic Programming）是运筹学的一个重要分支，是求解多阶段决策问题的一种最优化方法．20世纪50年代初R. E. Bellman等人在研究多阶段决策过程(Multistep Decision Process)的优化问题时，提出了著名的最优性原理（Principle of Optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类优化问题的新方法——动态规划．1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作．动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用．例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便．动态规划的成功之处在于，它可以把一个n 维决策问题变换为n 个一维最优化问题，一个一个地求解．这是经典极值方法所做不到的，它几乎超越了所有现存的计算方法，特别是经典优化方法．另外，动态规划能够求出全局极大或极小，这也是其它优化方法很难做到的．虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划等），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解．应该指出的是，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊的算法，它不像线性规划那样有统一的数学模型和算法（例如单纯形法），而必须对具体问题进行具体分析，针对不同的问题，运用动态规划的原理和方法，建立起相应的模型，然后再用动态规划方法去求解．因此，读者在学习时，除了要对动态规划的基本原理和方法正确理解外，还应以丰富的想象力去建立模型，用灵活的技巧去求解．多阶段决策问题很多，下面通过几个具体例子说明什么是多阶段决策问题.例6.1-1 最短路径问题设有一个旅行者从图7.1-1中的A 点出发途中需经B C D ，，等处，最后到达终点E ．从A 到E 有很多条路线可供选择，各点之间的距离如图所示，问旅行者应选择哪一条路线，使从A 到达E 的总路程最短?图6.1-1 A 经,,B C D 到E 的路径图从A 出发有三种方案可供选择：到12,B B 或3B ，如果仅考虑一段内最优，自然要选A 到1B ，但从整体上考虑，从A 到E 的最短路确经3B 而不经过1B ，因此，分段孤立地从本段最优考虑，总体不一定最优．如果把从A 到E 的所有可能路线一一列举出来，找出最短一条，这不仅费事，而且当阶段数多时就很难办到.实际上，这是一个多阶段决策问题．显然可以将全过程划分为4个阶段，每个阶段开始时要确定选择哪一条路径，而且上一个阶段的决策必然影响到下一个阶段选择路径时的状态．决策的目标是使总的路程最短．例6.1-2 生产计划问题工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3（千元），工厂每季度的最大生产能力为6（千件）．经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）．如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）．还规定年初和年末这种产品均无库存．试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少．这也是一个多阶段决策问题．显然可以将全过程划分为4个阶段（一个季度一个阶段），每个阶段开始时要确定该季度的产量，而且上一个阶段的决策必然影响到下一个阶段的生产状态．决策的目标是使一年的总费用（生产成本和存储费）最少．例6.1-3 机器负荷分配问题某种机器可以在高低两种不同的负荷下进行生产，在高负荷下生产时，产品的年产量g 和投入生产的机器数量x 的关系为()g g x =，这时的年完好率为a ，即如果年初完好机器数为x ，到年终时完好的机器数为(01)ax a <<，在低负荷下生产时，产品的年产量h 和投入生产的机器数量y 的关系为()h h y =，相应的完好率为(01)by b <<，且a b <．假定开始生产时完好的机器数量为1s ，要制定一个五年计划，确定每年投入高、低两种负荷生产的完好机器数量，使5年内产品的总产量达到最大．这同样是一个多阶段决策问题．显然可以将全过程划分为5个阶段（一年一个阶段），每个阶段开始时要确定投入高、低两种负荷下生产的完好机器数，而且上一个阶段的决策必然影响到下一个阶段的生产状态．决策的目标是使产品的总产量达到最大．例6.1-4 装载问题某运输公司要为某企业运送物资，现有n 种货物供其选择装运．这n 种货物的编号为1,2,...,n ．已知第j 种货物每件重j a 公斤，每件可收费j c 元，1,2,...,j n =．又知该公司的车辆所能承受的总重量不超过b 公斤．问该公司应如何选择这种货物的件数，使得收取的运费最多．设该公司选择第j 种货物的件数为(1,2,...,)j x j n =，则问题可归结为11max ..012nj jj n j j j jz c x a x b s t x j n === ≤ ≥= ∑∑L 且为整数（，，，） 这是一个整数规划问题，当然可以用整数规划的方法求解．然而，由于这一模型的特殊结构，我们可以把本来属于“静态规划”的各问题引进“时间”因素，分成若干个阶段，用动态规划的方法求解．以上几个问题虽然具体意义各不相同，但也有一些共同的特点，即都可以看成一个多阶段的决策问题，而且各个阶段决策的选取不是任意的，它依赖于当前面临的状态，又对以后的发展产生影响．当各个阶段的决策确定之后，就组成了一个决策序列，也就决定了整个过程的一条活动路线．这种把一个问题变成一个前后关系具有链状态结构的多阶段决策过程，也称为序贯决策过程，相应的问题就称为多阶段决策问题.下面以例7.1-1为例简单的介绍一下动态规划方法求解多阶段决策问题的基本思路与基本步骤．动态规划方法解题的基本思路是：将一个多阶段决策问题转化为依次求解多个单阶段决策问题，从而简化计算过程，这种转化的实现是从最后一个阶段出发进行反推，这种算法称为逆序算法．对于例7.1-1,具体求解步骤如下：(1)考虑一个阶段的最优选择．旅行者到达E 点前，上一站必然到达1D 或2D ．如果上一站为1D ，则本阶段最优决策为1D E →，距离1(,)3d D E =,其中(,)d I J 表示,I J 之间的距离,记1()3f D =，1()f D 表示某阶段初从1D 出发到终点E 的最短距离．同理，若上一站为2D ，则最优决策为2D E →,2()4f D =．(2)联合考虑两个阶段的最优选择．当旅行者离终点E 还剩两站时，他必然位于12,C C 或3C 的某一点，如果位于1C ，则从1C 到终点E 的路线可能有两条：11C D E →→或12C D E →→，旅行者从这两条路线中选取最短的一条，并且不管经过1D 或2D ，到达该点后，他应沿着从1D 或2D 到E 的最短路程继续走．故从1C 出发到E 的最短路程为111122(,)()13min min 4.(,)()44d C D f D d C D f D ++ == ++即，从1C 到E 的最短路线为11C D E →→，并记1() 4.f C =同理，从2C 出发到E 的最优选择为211222(,)()63min min 7.(,)()34d C D f D d C D f D ++ == ++即，从2C 到E 的最短路线为22C D E →→,并记2()7f C =．从3C 出发到E 的最优选择为311322(,)()33min min 6.(,)()34d C D f D d C D f D ++ == ++即，从3C 到E 的最短路线为31C D E →→，并记3()6f C =．(3)再考虑三个阶段联合起来的最优选择．当旅行者离终点E 还有三站时，他位于12,B B 或3B 中的某一点，如果位于1B ，则出发到E 的最优选择为111122133(,)()74min (,)()min 571166(,)()d B C f C d B C f C d B C f C ++ +=+= ++即，从1B 到E 的最短路线为111B C D E →→→，记1()11f B =.如果从2B 出发，到E 点的最优选择为211222233(,)()34min (,)()min 27746(,)()d B C f C d B C f C d B C f C ++ +=+= ++即，从2B 到E 的最短路线为211B C D E →→→，记2()7f B =，如果从3B 出发，到E 点的最优选择为311322333(,)()54min (,)()min 17856(,)()d B C f C d B C f C d B C f C ++ +=+= ++即：从3B 到E 的最短路线为322B C D E →→→，记3()8f B =．(4)四个阶段联合考虑.从A 到E 的最优选择为112233(,)()211min (,)()min 571138(,)()d A B f B d A B f B d A B f B ++ +=+= ++即,从A 到E 的最短路线为322A B C D E →→→→，距离长度为()11f A =．§6.2动态规划的基本概念用动态规划处理多阶段决策问题时，首先建立一些基本概念，通过这些概念定量描述这个多阶段决策问题，现结合例6.1-1解释这些概念.(1)阶段：指一个问题需要作出决策的步数．如例6.1-1中有4个阶段.描述问题阶段数的变量称为阶段变量，常用k 来表示，k 编号方法常用顺序编号法，即,初始阶段编号为1，以后随进程逐渐增大．通常将所给问题的过程按时间或空间特征分解为若干互相联系的阶段．(2)状态：对于多阶段决策问题，我们把每一阶段的起始“位置”叫做状态，它既是该阶段的某一起点，又是前一阶段的某一终点．例如在例6.1-1中第二阶段的状态有三个：12,B B 和3B ．我们把描述过程状态的变量叫做状态变量．它可以用一个数，一组数或一个向量来描述，通常用i k s 表示第k 阶段的第i 个状态．一般每一阶段都有若干个状态，故我们用k S = {}12,,,m k k k s s s L 表示第k 段的所有状态构成的状态集合．在最短路问题例6.1-1中 {}1,S A ={}{}{}{}212331234125,,,,,,,,S B B B S C C C S D D S E ====.应当指出，这里说的状态和常识中的状态不尽相同，它一般要满足：①要能描述问题的变化过程．②给定某一阶段的状态，以后各阶段的发展不受以前各阶段状态的影响，也就是说，当前的状态是过去历史的一个完整总结，过程的过去历史只能通过当前状态去影响它未来的发展，这个性质称为无后效性．③要能直接或间接地计算出来．(3)决策：指某阶段初从给定的状态出发，决策者从面临的若干种不同方案中做出的选择．决策变量()k k x s 表示第k 阶段状态为k s 时对方案的选择，决策变量的取值要受到一定的限制，用()k k D s 表示k 阶段状态为k s 时决策允许的取值范围，称为允许决策集合．故有()()k k k k x s D s ∈例如例6.1-1最短路径问题中{}21123(),,D B C C C =，而211()x B C =是可能的决策．(4)策略：当每一阶段的决策都确定以后，按先后顺序排列的决策组成的集合，称为一个全过程策略，简称策略，记为1,n p ，即{}1,1122(),(),,()n n n p x s x s x s =L如例7.1-1中选取122A B C D E →→→→就是一个策略．而,{(),,()}k n k k n n p x s x s =L ,称为后部子过程策略，如例6.1-1中选取从1B 到E 的一条路线121B C D E →→→就是一个后部子过程策略．对于多阶段决策问题，可供选择的策略很多，用1,1()n P s 及,()k n k P s 表示全体策略集合和后部子策略集合，显然有1,1,1,,(),().n n k n k n k p P s p P s ∈∈由于每一阶段都有若干个可能的状态和多种不同的决策，因而一个多阶段决策问题存在许多策略可供选择，称其中能够满足预期目标的策略为最优策略．如例6.1-1中路线3A B → 22C D E →→→为最优策略．(5)状态转移方程：从k s 的某一个状态出发，当决策变量()k k x s 的取值决定后，下一个阶段状态变量1k s +的取值也就随之确定.这种从上阶段的某一状态值到下阶段某一状态值得转移的规律称为状态转移律.显然下一阶段状态1k s +的取值是上阶段状态变量k s 和上阶段决策变量()k k x s 的函数，记为：1(,)k k k k s T s x +=状态转移律也叫状态转移方程．如例6.1-1中由于前一阶段的终点即为后一阶段的起点，故状态转移方程为1()k k k s x s +=(6)指标函数：用来衡量允许策略优劣的数量指标称为指标函数，它分为阶段指标函数与过程指标函数．阶段指标函数是指对应某一阶段状态k s 和从该状态出发的一个阶段的决策k x 的某种效益度量，用(,)k k k r s x 表示．过程的指标函数是指从状态k s 出发(k =1，2，…，n )至过程最终，当采取某种策略时，按预定标准得到的效益值，这个值既与k s 的状态值有关，又与k s 以后所选取的策略有关，它是两者的函数．记作,,11,,,,,,,.k n k n k k k k n n k n k k n V V s x s x s x V s p ++==L （,,）（）例如，在例6.1-1中，两点间距离(,)d A B １即为阶段的指标函数，而从1B 到终点E 的距离即为过程指标函数．常见指标函数的形式为：○1②(7)最优值函数：指标函数的最优值，称为最优值函数，记为()k k f s ，它表示从第k 个阶段的状态k s 出发到第n 个阶段的终止状态的过程，采取最优策略所得到的指标函数值，即,,,,()(,),k k k n k k n k n k n f s opt V s p p P =∈式中，opt 表示最优化，根据效益值的具体含义可以是求最大，或求最小.,11,(,)(,)(,)(,)n k n i i i i k n k k k i i i i k k k k k n V r s x r s x r s x r s x V ==++==+=+∑∑,11,(,)(,)(,)(,)n k n i i i i k n k k k i i i i k k k k k nV r s x r s x r s x r s x V ==++===∏∏．．§6.3动态规划的基本原理和建立动态规划模型的步骤6.3.1 最优化原理我们知道，最短路问题具有这样的特点：如果最短路线经过第k 阶段的状态k s ，那么从k s 出发到达终点的这条路线，对于从k s 出发到达终点的所有路线来说，也是最短路线．实际上具有上述特点的问题很多，贝尔曼正是研究这样一类所谓多阶段决策问题，发现它们都有这一共同特点，于是提出了解决这类问题的最优化原理．最优化原理 作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，对前面所形成的状态而言，余下的决策必然构成一个最优子策略．简言之：一个最优策略的子策略仍是最优的．例6.1-1正是根据这一原理求解的，从图6.1-1可以看出，无论从哪一段的某状态出发到终点E 的最短路线，只与此状态有关，而与这点以前的状态路线无关，即不受从A 点是如何到达这点的决策影响．而且从A 到E 的最短路线若经过i B ，则此路线由i B 到E 的后半部分应是由i B 到E 的最短路线．根据这个原理写出的计算动态规划问题的递推关系式称为动态规划方程．当,(,)nk n i i ii k V r s x ==∑时 ,,,,11()(,)(){(,)()}(())k k k n k k n k n k n k k k k k k k k f s opt V s p p P opt r s x f s x D s ++=∈=+∈ 当,(,)nk n i i ii k V r s x ==∏时 ,,,,11()(,)(){(,)()}(())k k k n k k n k n k n k k k k k k k k f s opt V s p p P opt r s x f s x D s ++=∈=∈6.3.2 建立动态规划模型的步骤用动态规划求解多阶段决策问题的基本思想是：利用最优化原理，建立动态规划方程，即建立动态规划的数学模型，最后再设法求其数值解．建立动态规划模型的步骤为：(1)将问题的过程恰当地分成若干个阶段，一般按问题所处的时间或空间进行划分，并确定阶段变量；(2)正确选取状态变量k s 使之满足无后效性等三个条件；(3)确定决策变量()k k x s 及每个阶段的允许决策集合()k k D s ；(4)写出状态转移方程 1(,)k k k k s T s x +=；(5)根据题意列出指标函数,k n V 、最优函数()k k f s 及阶段指标函数(,)k k k r s x ；(6)明确边界条件动态规划方程是递推关系，方程中含有11()k k f s ++，当k n =时，也即从最后一个阶段开始逆推时出现11()n n f s ++，这个项称为问题的边界条件．边界条件11()n n f s ++的值要根据问题的条件来决定，例如，当指标函数值是各阶段指标函数值的和时，可取11()n n f s ++=0，当指标函数值是各阶段指标函数值的积时，可取11()n n f s ++=1．(7)写出动态规划方程最后,根据最优化原理，结合所给的边界条件，可以写出如下的动态规划方程1111(){(,)()}()0(,1,,1)k k k k k k k n n f s opt r s x f s f s k n n ++++=+==− L (6.3-1) 或 1111(){(,).()}()1(,1,,1)k k k k k k k n n f s opt r s x f s f s k n n ++++= ==− L (6.3-2) 上面7步是构造动态规划模型的基础，是正确写出动态规划基本方程的基本要素，一个问题的动态规划模型构造得是否正确，又集中地反映在要恰当地定义最优值函数、正确地写出递推关系和边界条件，下面我们就来讨论这个问题．公式（6.3-1）和（6.3-2）称为动态规划的递推方程．由于是从k=n 开始向前逆序递推，又称为逆序递推方程．在递推过程中，将前面几个公式写在一起就构成对第一类指标函数式（加法形式）的一组基本方程：11111(){(,)()}()0(,),(,1,...,1)k k k k k k k n n k k k k f s opt r s x f s f s s T s x k n n +++++=+ = ==− (6.3-3)同理，对于第二类指标函数（乘法形式的），也可写出它的一组基本方程：11111(){(,).()}()1(,),(,1,...,1)k k k k k k k n n k k k k f s opt r s x f s f s s T s x k n n +++++= = ==− (6.3-4)于是得到求解动态规划的逆序方法的求解过程：运用公式（6.3-3）、（6.3-4）（或者公式(6.3-1) 、(6.3-2）)之一，从k=n 开始，由后向前逆推，逐步求得各阶段的最优决策和相应的最优值，求出11()f s ，就是全过程的最优值（将1s 的值代入计算即得），然后再由1s 和*1x ，利用状态转移方程计算出2s ，从而确定*2x ，．．．，依次类推，最后确定*n x ，于是得最优策略****1,12{,,...,}n n p x x x =. 后面的计算过程称为“回代”，又称为“反向追踪”．总之，动态规划的计算过程是由递推和回代两部分组成．逆序递推的过程如图6.3-1所示§6.4动态规划的求解方法本节主要讨论一维动态规划的求解法．所谓一维动态规划问题是指：在一个多阶段决策过程中，每一个阶段只用一个状态变量k s 就足以描述系统的状态演变，并且在每一个阶段，只需要选择一个决策变量k x 就够了．前面讨论的问题都属于这一类．若每个阶段需要两个或多个状态变量才能描述系统的演变，或者每个阶段需要选择两个或多个决策变量时，这类问题都属于多维动态规划问题，本书不做讨论．求解一维动态规划问题，基本上有两类方法：一类是解析法；一类是列表法（数值计算法）．所谓解析法，它需要用到指标函数的数学公式表示式，并且能用经典求极值的方法得到最优解，即用解析的方法求得最优解．所谓列表法，它在计算过程中不用或者很少用到指标函数的解析性质，而是通过列表的方式来逐步求得最优解，它可以解决解析法难于解决的问题．下面通过实例来分别介绍这两种方法．6.４.1 动态规划的解析法我们首先讨论仅有一个约束条件的数学规划问题)()()(max 2111n n x g x g x g Z +++=L=≥≤+++),,2,1(0..2211n j x b x a x a x a t s j n n L L 这里，当()j j g x ,j=1,2,…,n 均为线性函数时，则为线性规划问题；当()j j g x 不全为线性函数时，则为非线性规划问题；当j x 有整数要求时，则为整数规划问题．虽然这一类问题可在线性规划、非线性规划及整数规划中讨论．但是，用动态规划方法来解决这一类问题有其特殊的优点和方便之处．用动态规划求解这一类问题，有一个统一的模式．即把问题划分为n 个阶段，取k x 为第k 阶段的决策变量．第k 阶段的效益为()k k g x （k=1,2,…,n ）．过程指标函数为各阶段效益之和，即,()(1,2,...,)nk n jjj kV g xk n ===∑问题是如何选择状态变量k s ，正如线性规划问题中可以将约束条件看成资源限制一样，这里也可以这样理解，即将现有数量为b 个单位的某种资源用来生产n 种产品，问如何分配使总利润最大．假设工厂的决策者分几个阶段来考虑这个问题，如果是用逆序递推法，决策者首先考虑的是第n 种产品生产几件，消耗资源多少；然后考虑第1n −种和第n 种产品各生产多少，消耗资源多少，依次向前递推．在第k 阶段时，就要考虑第k 种、第1k +种，…，第n 种产品各生产多少，消耗资源多少．于是我们就可以这样来选择状态变量，即令k s 表示可供第k 种产品至第n 种产品消耗的资源数．显然由0k s ≥,且k s 满足无后效性，而第k 阶段的资源消耗为k k a x ，于是得状态转移方程为.1,,1,,1L −=−=+n n k x a s s k k k k再由0k s ≥及决策变量k x 的非负性，可得允许决策集合为≤≤=k k k k k k a s x x s D 0|)( 允许状态集合为{}b s s S k k k ≤≤=0|且S 1=｛b ｝.设最优函数()k k f s 表示从第k 阶段到第n 阶段指标函数的最优值，则逆序递推方程为+=≤≤224/05651max 22s x s x 2*225,44s s x ==当k=1时，状态转移方程2113s s x =−，故{})(4max )(2213/01111s f x s f s x +=≤≤−+=≤≤)3(454max 1113/011x s x s x+=≤≤113/04541max 11s x s x *1114,33s s x ==由于110s ≤及11()f s 关于1s 是单调增函数，故应取110s =．这时3401034)10(1=×=f这就是指标函数的最优值．再回代求最优决策：由于110s =,所以03103103,31031121*1=×−=−===x s s s x 00404,042232*2=×−=−===x s s s x 053*3==s x即线性规划问题的最优解为T X )0,0,310(*=最优值Z *=40/3．例6.4-2 用动态规划方法求解33221max x x x Z ==≥≤++)3,2,1(06..321j x x x x t s j解：这个问题可以理解为将一个数6（或某种资源数）分成三部分，使目标函数23123max z x x x =达到最大.取阶段变量k=1,2,3共分三个阶段0.决策变量k x 表示第k 阶段分配的数量，状态变量k s 表示从第k 阶段至第3阶段可供分配的总数量，则状态转移方程为k k k x s s −=+1允许决策集合 {}k k k k k s x x s D ≤≤=0|)(， 允许状态集合1{06},{6}k k k S s s S =≤≤=，递推方程为1144()max{(,).()}()1(3,2,1)k k k k k k k f s r s x f s f s k ++= ==当k=3时，有3333*3333330()max{},x s f s x s x s ≤≤===当k=2时，有{}{}32220332022)(max )(max )(2222x s x s f x s f s x s x −=⋅=≤≤≤≤令322222)()(x s x x −=ϕ，则)4()()(2222222x s x s x −−=′ϕ 再由22()0x ϕ′=得22x s =或224s x =，又由直接验证可知22(04s ϕ′′<，故224sx =为)(22x ϕ的极大值点．这时4*2222227(),2564s f s s x ==当k=1时，有令4112111)(25627)(x s x x −⋅=ϕ，则)62()(25627)(11311111x s x s x x −−=′ϕ再令 0)(11=′x ϕ 得3,,011111s x s x x === 又由直接验证可知11(03s ϕ′′<，故113sx =为11()x ϕ的极大值点．这时1122*11111102()max{8}2,2s x s f s x s x ≤≤===当k=2时，有{}{}2222201122022)(24max )(4max )(2222x s x s f x s f s x s x −+=+=≤≤≤≤令2222222)(24)(x s x x −+=ϕ，则)(48)(22222x s x x −−=′ϕ. 由0)(22=′x ϕ得223s x =．但由于012)(22>=′′x ϕ，所以223s x =为最小值点．故极大值点必在区间[0，2s ]的端点，计算两端点的函数值22222224)(,2)0(s s s ==ϕϕ并比较其大小可知极大值点为22x s =．这时22224)(s s f =当k=3时，有{})(max )(223310/03333s f s s f s x +=≤≤{}2333310/0)10(4max 33x s s s x −+=≤≤但320s ≤，所以取320s =，得{}233303)1020(4max )20(23x x f s x −+=≤≤由直接验证可知，30x =为极大值点．故0,1600)20(*33==x f又02,02020;20,20101*12212*2332===−=−====−=s x x s s s x x s s ，即，最优解为0,20,0*3*2*1===x x x目标函数最优值为1600．以上几个例子中，由于是将状态变量和决策变量都是作为连续变量看待的，且指标函数和状态转移方程都有确定的解析表达式，求极值时所用的方法是微积分中的方法，所以我们把这类问题的求解方法统称为动态规划的解析法．6.４.２ 动态规划的列表法在多阶段决策问题中，当指标函数没有明确的解析表达式（例如用数值表给出），或者对变量有整数要求时，则不能用解析法求解，只能用列表法（数值计算法）求解，下面举例说明．例6.4-4 (资源分配问题) 设有6810×元资金用于扩建三个工厂投资数均为整数(单位为610元)，每个工厂的利润增长额与投资数有关，详细数据见表6.4-1(单位：610元)．表6.4-1 投资与利润增长的关系问应如何确定这三个工厂的投资数，使总的利润增长额为最大?解 将问题分为三个阶段，即把向第k 个工厂进行投资作为第k 个阶段，k =3，2，1．第k 阶段初，选取可用于向第k 个工厂至第3个工厂进行的投资数，作为该阶段的状态变量，用k s 表示．选取用于第k 个工厂的投资数作为决策变量，用k x 表示，显然每个阶段的允许决策集合为(){|0}k k k k k D s x x s =≤≤，因每阶段初可用的投资数是上阶段初可用的投资数减去上阶段用去的投资数，故状态转移方程为1,(1,2,3)k k k s s x k +=−=.用()k k g x 表示给工厂k 分配资金k x 时得到的利润增长额，故指标函数可写为3,3i11,3()()()k k k ii k k k k V g x g x g x V =++=+=+∑设用()k k f s 表示从k 阶段状态k s 开始采用最优策略时的利润增长额，则有11()max{()()},()k k k k k k k k k f s g x f s x D s ++=+∈因问题中只有三个工厂，故假想的第4阶段初拥有的投资数已不可能促使这三个工厂利润额的增长，故边界条件44()0.f s = 动态规划递推方程为144()max{()()}()0,(3,2,1)k k k k k k k f s g x f s x f s k +=+−== (1)当3k =时，可用于投资的只有第3个工厂，投资额33(0,1,2,,8)s s =L 全部给第3个工厂，最大利润增长额为：3333333()max{()},()f s g x x D s =∈根据这个关系式，由表6.4-1中数据，得表7.4-2的结果表6.4-2 仅投资第三个工厂的情况 (单位：610元) 状态3s0 1 2 3 4 5 6 7 8 33()f s0 4 26 40 45 50 5l 52 53 对应决策*3x12345678(2)当2k =时，可用于投资的工厂为2和3．这时有222232222()max{()()}0f s g x f s x x s =+−≤≤2s 可能取得值为0,1,2,3,4,5,6,7,8具体计算步骤见表6.4-3．(3)当1k =时，可用于投资的工厂为1,2和3．这时有111121111()max{()()}0f s g s f s x x s =+−≤≤利用动态规划方程1s 分别求出不同值时的11()f s 及*11()x s ．计算步骤见表6.4-4．表6.4-3 投资2，3两工厂的情况表6.4-4 投资三个工厂的情况由表6.4-4可知，当1s 6810=×时，投资给第1个工厂的金额为4×610元，即1(8)4x =×610(元)；当62410s =×时，查表6.4-3知投资给第2个工厂的金额为4×610元，即62(4)410x =× (元)；当30s =时，查表6.4-2知，投资给第3个工厂的金额为0，即3(0)0x =； 即最优策略为，6410×元，6410×元，0元． 预期最大投资增长额为140×610元．。

动态规划多阶段决策过程（multistep decision process ）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。

动态规划（dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。

利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。

动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。

动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。

动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。

1 、最优子结构性质。

如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。

最优子结构性质为动态规划算法解决问题提供了重要线索。

2 、子问题重叠性质。

子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。

动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。

当我们已经确定待解决的问题需要用动态规划算法求解时，通常可以按照以下步骤设计动态规划算法：1 、分析问题的最优解，找出最优解的性质，并刻画其结构特征；2 、递归地定义最优值；3 、采用自底向上的方式计算问题的最优值；4 、根据计算最优值时得到的信息，构造最优解。

多阶段决策和序贯决策教材引言多阶段决策和序贯决策是决策理论中重要的概念和方法。

在很多实际应用中，决策问题往往不仅仅是一次性的选择，而是需要在不同阶段进行多次决策，每次决策都受之前决策的影响。

本教材将介绍多阶段决策和序贯决策的基本概念和方法，并提供案例来帮助读者理解和应用这些概念和方法。

多阶段决策多阶段决策是指决策问题中包含多个决策节点的情况。

在每个决策节点，决策者需要面临不同的选择，并根据选择的结果进行下一阶段的决策。

多阶段决策常见于实际生活中的许多问题，比如投资决策、项目管理等。

多阶段决策可以通过决策树来表示。

决策树是一种树状结构，其中每个节点表示一个决策点，每个边表示一个选择。

通过自顶向下的递归过程，从根节点到叶子节点，决策树可以表示整个多阶段决策的过程。

在每个决策节点，决策者根据一定的决策准则选择一个最优的方案。

常用的决策准则包括最大化效益、最小化风险等。

序贯决策序贯决策是多阶段决策的一种特殊形式，它是指在每个决策节点上，决策者只能看到当前状态的信息，并且只做当前状态下最优的决策，无法事先知道所有后续状态的信息。

序贯决策常见于动态环境下的问题，比如控制系统、机器人等。

序贯决策可以通过动态规划来求解。

动态规划是一种递推的算法，通过将问题划分为一系列子问题，并利用子问题的最优解来推导出整个问题的最优解。

在序贯决策中，我们可以定义一个价值函数来表示当前状态的价值，然后利用动态规划算法不断更新和求解价值函数，最终得到最优的决策序列。

案例分析为了帮助读者理解和应用多阶段决策和序贯决策的概念和方法，下面将给出一个案例分析。

假设你是一家餐厅的经理，现在面临一个供应商选择的问题。

你可以选择三个不同的供应商，每个供应商的价格和质量都不同。

此外，每个供应商的产品质量在未来可能会有变化。

你需要决策在当前时间选取哪个供应商，并在之后的时间里根据每个供应商的质量变化重新评估和选择供应商。

这个问题可以通过多阶段决策和序贯决策的方法来解决。