动态规划的基本概念.ppt

运 筹 学,动态规划,第五章 动态规划,动态规划是运筹学的一个重要分支，它是从1951年开始，由美国人贝尔曼（R.Belman）为首的一个学派发展起来的。动态规划在经济、管理、军事、工程技术等方面都有广泛的应用。动态规划是解决多阶段决策过程的最优化问题的一种方法。所谓多阶段决策过程是指这样一类决策过程：它可以把一个复杂问题按时间（或空间）分成若干个阶段，每个阶段都需要作出决策，以便得到过程的最优结局。由于在每个阶段采取的决策是与时间有关的而且前一阶段采取的决策如何，不但与该阶段的经济效果有关，还影响以后各阶段的经济效果，可见这类多阶段决策问题是一个动态的问题，因此，处理的方法称为动态规划方法。然而，动态规划也可以处理一些本来与时间没有关系的静态模型，这只要在静态模型中人为地引入“时间”因素，分成时段，就可以把它看作是多阶段的动态模型，用动态规划方法去处理。动态规划对于解决多阶段决策问题的效果是明显的，但也有一定的局限性。首先，它没有统一的处理方法，必须根据问题的各种性质并结合一定的技巧来处理；另外当变量的维数增大时，总的计算量及存贮量急剧增大。由于计算机的存贮量及计算速度的限制，目前的计算机仍不能用动态规划方法来解决较大规模的问题，这就是所谓“维数障碍”。,需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。,1 动态规划的基本概念,1.1 多阶段决策问题 在研究社会经济、经营管理和工程技术领域内的有关问题中，有一类特殊形式的动态决策问题多阶段决策问题。在多阶段决策过程中，系统的动态过程可以按照时间进程分为相互联系而又相互区别的各个阶段，在每个阶段都要进行决策。系统在每个阶段存在许多不同的状态，在某个时点的状态往往要依某种形式受到过去某些决策的影响，而系统的当前状态和决策又会影响系统过程今后的发展。因而在寻求多阶段决策问题的最优解时，重要的是不能仅仅从眼前的局部利益出发进行决策，而需要从系统所经过的整个期间的总效应出发，有预见性地进行动态决策，找到不同时点的最优决策及整个过程的最优策略。下面举例说明什么是多阶段决策问题。,例1（最短路线问题）在线路网络图1中，从A至E有一批货物需要调运。图上所标数字为各节点之间的运输距离，为使总运费最少，必须找出一条由A至E总里程最短的路线。,A,B1,B2,E,B3,C2,C3,C1,D2,D3,D1,4,5,3,4,4,4,3,1,6,5,8,8,7,7,10,2,9,6,为了找到由A至E的最短线路，可以将该问题分成ABCDE 4个阶段，在每个阶段都需要作出决策，即在A点需决策下一步到B1还是到B2或B3；同样，若到达第二阶段某个状态，比如B1，需决定走向C1还是C2；依次类推，可以看出：各个阶段的决策不同，由A至E的路线就不同，当从某个阶段的某个状态出发作出一个决策，则这个决策不仅影响到下一个阶段的距离，而且直接影响后面各阶段的行进线路。所以这类问题要求在各个阶段选择一个恰当的决策，使这些决策序列所决定的一条路线对应的总路程最短。,图1,例2（带回收的资源分配问题）某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所代替。此机车如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得的利润最大？本问题具有时间上的次序性，在五年计划的每一年都要作出关于这些机床生产负荷的决策，并且一旦作出决策，不仅影响到本年利润的多少，而且影响到下一年初完好机床数，从而影响以后各年的利润。所以在每年初作决策时，必须将当年的利润和以后各年利润结合起来，统筹考虑。与上面例1、例2类似的多阶段决策问题还有资源分配、生产存贮、可靠性、背包、设备更新问题等等。,1.2 动态规划的基本概念 1.阶段 动态规划问题通常都具有时间或空间上的次序性，因此求解这类问题时，首先要将问题按一定的次序划分成若干相互联系的阶段，以便能按一定次序去求解。如例1，可以按空间次序划分为ABCDE 4个阶段，而例2，按照时间次序可分成5个阶段。2.状态 在多阶段决策过程中，每阶段都需要作出决策，而决策是根据系统所处情况决定的。状态是描述系统情况所必需的信息。如例1中每阶段的出发点位置就是状态，例2中每年初拥有的完好机床数是作出机床负荷安排的根据，所以年初完好机床数是状态。一般地，状态可以用一个变量来描述，称为状态变量。记第k 阶段的状态变量为xk，k=1,2,n.,3.决策:多阶段决策过程的发展是用各阶段的状态演变来描述的，阶段决策就是决策者从本阶段某状态出发对下一阶段状态所作出的选择。描述决策的变量称为决策变量，当第k 阶段的状态确定之后，可能作出的决策要受到这一状态的影响。这就是说决策变量uk还是状态变量xk 的函数，因此，又可将第k阶段xk状态下的决策变量记为uk(xk)。在实际问题中，决策变量的取值往往限制在某一范围之内，此范围称为允许决策变量集合，记作Dk(uk)。如例2中取高负荷运行的机床数uk为决策变量，则0ukxk（xk是k阶段初完好机床数）为允许决策变量集合。4.状态转移方程:在多阶段决策过程中，如果给定了k 阶段的状态变量xk和决策变量uk，则第k+1阶段的状态变量xk+1也会随之而确定。也就是说xk+1是xk和uk函数，这种关系可记为 xk+1=T(xk,uk)称之为状态转移方程。,5.策略:在一个多阶段决策过程中，如果各个阶段的决策变量uk(xk)（k=1，2，n）都已确定，则整个过程也就完全确定。称决策序列u1(x1),u2(x2),un(xn)为该过程的一个策略，从阶段k到阶段n的决策序列称为子策略，表示成uk(xk),uk+1(xk+1),un(xn)。如例1中，选取一路线AB1C2D2E 就是一个策略：u1(A)=B1,u2(B1)=C2,u3(C2)=D2,u4(D2)=E 由于每一阶段都有若干个可能的状态和多种不同的决策，因而一个多阶段决策的实际问题存在许多策略可供选择，称其中能够满足预期目标的策略为最优策略。例1中存在12条不同路线，其中AB2C1D2E是最短线路。6.指标函数:用来衡量过程优劣的数量指标，称为指标函数。在阶段k的xk状态下执行决策uk，不仅带来系统状态的转移，而且也必然对目标函数给予影响，阶段效应就是执行阶段决策时给目标函数的影响。,多阶段决策过程关于目标函数的总效应是各阶段的阶段效应累积形成的。常见的全过程目标函数有以下两种形式：（1）全过程的目标函数等于各阶段目标函数的和，即：R=r1(x1,u1)+r2(x2,u2)+rn(xn,un)（2）全过程的目标函数等于各阶段目标函数的积，即：R=r1(x1,u1)r2(x2,u2)rn(xn,un)指标函数的最优值，称为最优函数值。一般，f1（x1）表示从第1阶段x1状态出发至第n阶段（最后阶段）的最优指标函数，fk（xk）表示从第k阶段xk状态出发至第n阶段的最优指标函数(k=1，2，n）。,2 动态规划的最优性原理,多阶段决策过程的特点是每个阶段都要进行决策，具有n个阶段的决策过程的策略是由n个相继进行的阶段决策构成的决策序列。由于前阶段的终止状态又是后一阶段的初始状态，因此确定阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。就是说，阶段k的最优决策不应只是本阶段的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个后部子过程的最优决策。对此，贝尔曼在深入研究的基础上，针对具有无后效性的多阶段决策过程的特点，提出了著名的多阶段决策的最优性原理：“整个过程的最优策略具有这样的性质：即无论过程过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。”简而言之，最优性原理的含意就是：最优策略的任何一部分子策略也必须是最优的。,如例1，AB2C1D2E是由A到E的最短路线，我们在该路线上任取一点C1，按照最优性原理C1D2E应该是C1到E的最短路。很容易用反证法证明这一结论的正确性，从而说明最优性原理的正确性。按最优性原理，可以将例1分成ABCDE 4个阶段，由后向前逐步求出各点到E的最短线路，直至求出A至E的最短线路。,K=4时，出发点有D1，D2，D3，记f4（Di）（i=1,2,3）为Di到E的最短距离；u4(Di)表示从状态Di出发采取的决策。显然：f4（D1）=7，u4(D1)=E f4（D2）=8，u4(D2)=E f4（D3）=6，u4(D3)=EK=3时，出发点有C1，C2，C3,f3（C1）=mind（C1D1）+f4（D1）,d（C1D2）+f4（D2）=min4+7,2+8=10,u3(C1)=D2f3（C2）=mind（C2D2）+f4（D2）,d（C2D3）+f4（D3）=min5+8,7+6=13,u3(C2)=D2或D3f3（C3）=mind（C3D2）+f4（D2）,d（C3D3）+f4（D3）=min10+8,9+6=15,u3(C3)=D3,K=2时，出发点有B1，B2，B3f2（B1）=mind（B1C1）+f3（C1）,d（B1C2）+f3（C2）=min6+10,4+13=16,u2(B1)=C1f2（B2）=mind（B2C1）+f3（C1）,d（B2C3）+f3（C3）=min3+10,1+15=13,u2(B2)=C1f2（B3）=mind（B3C2）+f3（C2）,d（B3C3）+f3（C3）=min8+13,4+15=19,u2(B3)=C3 K=1时，出发点只有A d（AB1）+f2（B1）4+16 f1（A）=min d（AB2）+f2（B2）=5+13=18,d（AB3）+f2（B3）3+19 u1(A)=B2 由f1（A）=18，可知从起点A到终点E的最短距离为18。,为了找出最短线路，再按计算顺序反推回去，可求出最优决策序列，即由 u1(A)=B2，u2(B2)=C1，u3(C1)=D2，u4(D2)=E组成最优策略，也就是最短线路为：AB2C1D2E,从上面的例子不难看出，对于最短线路问题，有如下的递推关系（函数方程）：fk（xk）=mind（xk,uk(xk)）+fk+1（T(xk,uk)）fn+1（xn+1）=0 k=n,n-1,1,一般情况下，多阶段决策问题存在下面的递推关系：fk（xk）=opt rk(xk,uk(xk)fk+1（T(xk,uk)）uk Dk(uk)fn+1（xn+1）=C k=n,n-1,1 这里rk(xk,uk(xk)是第阶段采用uk(xk)决策产生的阶段效应；fn+1（xn+1）=C是边界条件；“”号大多数情况下是“+”号，也可能是“”号。称上述递推关系为动态规划的基本方程，这个方程是最优化原理的具体表达形式。,在基本方程中，rk(xk,uk)，xk+1=T(xk,uk)都是已知函数，最优子策略fk（xk）与fk+1（xk+1）之间是递推关系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。,另一方面，由于k+1阶段的状态xk+1=T(xk,uk)是由前面的状态和决策所形成的，在计算fk+1（xk+1）时还不能具体确定xk+1的，这就要求必须就k+1阶段的各个可能状态计算fk+1（xk+1），因此动态规划不但能求出整个问题的最优策略和最优目标值，而且还能求出决策过程中所有可能状态的最优策略及最优目标值。,3 建立动态规划数学模型的步骤,“最优化原理”是动态规划的核心,所有动态规划问题的递推关系都是根据这个原理建立起来的,并且根据递推关系依次计算,最终可求得动态规划问题的解。一般来说，利用动态规划求解实际问题需先建立问题的动态模型，具体步骤如下：将问题按时间或空间次序划分成若干阶段。有些问题不具有时空次序，也可以人为地引进时空次序，划分阶段。正确选择状态变量xk。这一步是形成动态模型的关键，状态变量是动态规划模型中最重要的参数。一般来说，状态变量应具有以下三个特性：要能够用来描述决策过程的演变特征。要满足无后效性。即如果某阶段状态已给定后，则以后过程的进展不受以前各状态的影响，也就是说，过去的历史只通过当前的状态去影响未来的发展。递推性。即由k阶段的状态变量xk及决策变量uk可以计算出k+1阶段的状态变量xk+1。,确定决策变量uk及允许决策变量集合Dk(uk)。根据状态变量之间的递推关系，写出状态转移方程：xk+1=T(xk,uk(xk)建立指标函数。一般用rk(xk,uk)描写阶段效应，fk（xk）表示kn阶段的最优子策略函数。建立动态规划基本方程：fk（xk）=opt rk(xk,uk(xk)fk+1（xk+1）uk Dk(uk)fn+1（xn+1）=C k=n,n-1,1 以上是建立动态规划模型的过程，这个过程是正确求解动态规划的基础。在动态规划基本方程中，rk(xk,uk)，xk+1=T(xk,uk)都是已知函数，最优子策略fk（xk）与fk+1（xk+1）之间是递推关系，要求出fk（xk）及uk(xk)，需要先求出fk+1（xk+1），这就决定了应用动态规划基本方程求最优策略总是逆着阶段的顺序进行的。由后向前逐步计算，最终可以算出全过程的最优策略函数值及最优策略。,另一方面，由于k+1阶段的状态xk+1=T(xk,uk)是由前面的状态xk和决策uk所形成的，在计算fk+1（xk+1）时还不能具体确定xk+1的值，所以，这就要求必须就k+1阶段的各个可能状态计算fk+1（xk+1），因此动态规划方法不但能求出整个问题的最优策略和最优目标值，而且还能求出决策过程中所有可能状态的最优策略及最优目标值。,下面就按上述步骤求解例2。,例2（带回收的资源分配问题）某厂新购某种机床125台。据估计，这种设备5年后将被其它设备所代替。此机床如在高负荷状态下工作，年损坏率为1/2，年利润为10万元；如在低负荷状态下工作，年损坏率为1/5，年利润为6万元。问应如何安排这些机床的生产负荷，才能使5年内获得的利润最大？,解：以年为阶段，k=1，2，3，4，5 取k年初完好的机床数为状态变量xk 以k年初投入高负荷运行的机床数为决策变量uk，则低负荷运行机床数是xk-uk，于是状态转移方程为：xk+1=1/2uk+4/5（xk-uk）=0.8xk-0.3uk 以利润为目标函数，则k年利润为：10uk+6（xk-uk）=4uk+6xk 记fk（xk）为k年至5年末最大总利润，则动态规划基本方程为：fk（xk）=max 4uk+6xk+fk+1（0.8xk-0.3uk）0ukxk f6（x6）=0 k=5,4,3,2,1,以上是建立动态模型的过程，下面具体求解。注意动态规划基本方程为：,fk（xk）=max 4uk+6xk+fk+1（0.8xk-0.3uk）0ukxk,所以，当k=5时，有f5（x5）=max 4u5+6x5+f6（x6）=10 x5 u5=x5 0u5x5当k=4时f4（x4）=max 4u4+6x4+f5（0.8x4-0.3u4）0u4x4=max 4u4+6x4+10（0.8x4-0.3u4）0u4x4=max u4+14x4=15x4 u4=x4 0u4x4当k=3时f3（x3）=max 4u3+6x3+f4（0.8x3-0.3u3）0u3x3=max 4u3+6x3+15（0.8x3-0.3u3）0u3x3=max-0.5u3+18x3=18x3 u3=0 0u3x3,动态规划基本方程为：fk（xk）=max 4uk+6xk+fk+1（0.8xk-0.3uk）0ukxk,当k=2时f2（x2）=max 4u2+6x2+f3（0.8x2-0.3u2）0u2x2=max 4u2+6x2+18（0.8x2-0.3u2）0u2x2=max-1.4u2+20.4x2=20.4x2 u2=0 0u2x2 当k=1时f1（x1）=max 4u1+6x1+f2（0.8x1-0.3u1）0u1x1=max 4u1+6x1+20.4（0.8x1-0.3u1）0u1x1=max-2.12u1+22.32x1=22.32x1 u1=0 0u1x1=22.32125=2790（万元）,至此已算得最大总利润2790万元，再按与计算过程相反的顺序推回去，可得最优计划如下表所示：,