动态规划(理论部分).

第四章动态规划动态规划动态规划是解决多阶段决策过程最优化问题的一种方法。在二十世纪五十年代由美国数学家理查德.贝尔曼(Richard．Ba11man)首先提出的。它可以把一个n维最优化问题转化为n个一维最优化问题来求解。一个决策问题，往往可以分解成若干个相互联系，又相对独立的阶段，对于每一个阶段，存在着很多方案可供选择，我们要对每个阶段作出一个决策。而各阶段之间又有密切的联系，某一个阶段的不同决策，将会对其它阶段的决策产生重大的影响，某个阶段局部的较优方案，未必是整个问题的最好方案，某个阶段局部的不好方案，也未必是整个问题的不好方案。我们要寻找的是整个问题，也就是所有阶段总体的一个最优方案，这就是动态规划所要讨论的问题。一、多阶段决策问题所谓多阶段决策问题是有这样一类决策过程，它可以划分为若干个相互联系的阶段，在任一阶段都有若干种方案可供选择，选择哪一种方案需要作出决策，这样就形成一个决策序列，通常称为一种策略。不同的策略就产生不同的效果，在所有可能的策略当中，选择一个效果最好的最优策略，就是解决多阶段决策问题的主要目的。下面举几个例子来说明。例1：（最短路程问题）设从A地到E地要铺设一条管道，其中要经过若干个中间点(如图)。图中两点之间连线上的数字表示两地间的距离。现在要选择一条铺设管道的路线，使总长度最短。2511214106104131112396581052C1C3D1AB1B3B2D2EC2在这个问题中，从A到B1，B2，B3中的哪一个点要作出一项决策，从B1，B2，B3某点到C1，C2，C3中的哪一个点又要作出一项决策等等。所以总共要作出四个决策。因此，我们可以把整个路程分为A，B(包括B1，B2，B3)，C(包括C1，C2，C3，)，D(包括D1和D2)，E五个阶段。这就是一个多阶段的决策问题。二、动态规划的基本思想用动态规划求解多阶段决策问题，是把整个问题划分为若干阶段后，依次地为每一个阶段作出最优决策，而每个阶段的最优决策应该是包含本阶段和所有以前各阶段在内的最优决策，也就是到本阶段为止，包含以前各阶段在内的最优总决策。因此，在确定了最后一个阶段的决策之后，整个问题的最优决策序列也就随之产生。这就是用动态规划解多阶段决策问题的基本思想。以上面的例1来说明动态规划解决问题的思想。设：Sk----第k阶段的起点（状态变量）dk(x,y)-----第k阶段的顶点x到顶点y的“距离”；fk(Sk)------第k阶段从顶点Sk到终点的最短“路”长。最短路线的重要特性就是：如果最短路线在第K站通过点Pk。则由点Pk出发到达终点的这条路线，对于从点Pk出发到达终点的所有可能选择的不同路经来说，必定也是最短路线。例如，在最短路线问题中，如果找到了A到E的最短路：121ABCDE则应该是由C2出发到E点的所有可能不同线路中的最短路线21CDE最短路线这一特性，启发我们找最短路线的方法：那就是从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点的最短路线。所以，动态规划的常用的方法是从终点逐段向始点方向寻找“最短路线”。如图所示：行进方向起点终点动态规划寻优途径下面按上述思想，将例1从最后一段开始计算，由后向前逐步推移至A点。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0设想有k＝5时，f5(E)＝0。2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=04115()(,)()505fDdDEfEK=4时：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=54225()(,)()202fDdDEfE2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5311242114111()min(,)()minmin8最优决策9(,)()358211fCCDfDfDCDCDK=3时：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8222422141223DC7711min2556min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7232423141333DC121213min21058min)D(f)D,C()D(f)D,C(min)C(f最优决策2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=81131211232133311(,)()12820()min(,)()min147min2120(,)()101222最优决策:BCfCfBBCfCBCfCBCK=2时：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=212222322333212131()min(,)()min107min1714(,)((,)()41216最优决策:)6814BCffBBCfCBCfCCBC2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=143131233232333332(,)()13821()min(,)()min127min1919(,)()111223最优决策:BCfCfBBCfCBCfCBC2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=2112113232222(,)()22123()minminmin19(,)()11920最优决(,)()514策9:1ABfBfAABfBABfBABK=1时：2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态AB2C1D1E（A，B2）（B2，C1）（C1,D1）（D1,E）2511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态最优决策状态最优决策状态最优决策状态最优决策状态A（A，B2）B2（B2，C1）C1（C1，D1）D1（D1，E）E从A到E的最短路径为19，路线为A→B2→C1→D1→E三、动态规划的基本概念(1)阶段（stage）把所研究的决策问题，按先后顺序划分为若（2）状态（state）状态表示每个阶段开始时所处的自然状况或(3)决策（decision）决策表示在某一阶段处于某种状态时，决策者在若干种方案中作出的选择决定。描述决策的变量称决策变量，第k阶段的决策变量常用uk表示。决策变量的取值会受到状态变量的制约，被限制在某一范围之内。干相互联系的决策步骤，以便按一定的次序进行求解。描述阶段的变量称阶段变量，常用k表示。客观条件，它描述了影响决策的因素随决策进程的变化情况，它既是前面阶段所作决策的结果又是本阶段作出决策的出发点和依据。描述状态的变量称为状态变量，第k阶段的状态变量常用sk表示。通常，在第一阶段状态变量s1是确定的，称初始状态。T1S1S2V1u1T2S3V2u2TkSkSk+1VkukTnSnSn+1Vnun……多阶段决策过程如下：n个决策子问题k称为阶段变量Sk描述k阶段初的状态，即状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量Vk为k阶段从状况Sk出发,做出决策uk之后的后果，(4)策略（policy）把从第一阶段开始到最后阶段终止的整个决策过程，称为问题的全过程；而把从第k阶段开始到最后阶段终止的决策过程，或称为k子过程。在全过程上，各阶段的决策按顺序排列组成的决策序列p1,n＝{u1,u2,……,un}称为全过程策略，简称策略；而在k子过程上的决策序列pk,n＝{uk,uk+1,……,un}称为k子过程策略，也简称子策略。(5)状态转移方程(6)指标函数（准则函数）,目标函数和最优值函数指标函数分为阶段指标函数和过程指标函数。阶段指标函数是对某一阶段的状态和决策产生的效益值的度量用Vk(sk,uk)表示。从第k阶段到最终阶段的过程称为k--后部子过程，简称为：k--子过程。若第k阶段的状态变量值为sk，当决策变量uk的取值决定后，下一阶段状态变量Sk+1的值也就完全确定。即Sk+1的值对应于Sk和uk的值。这种对应关系记为:sk+1＝Tk(sk,uk)，称为状态转移方程。状态转移方程描述了由一个阶段的状态到下一阶段的状态的演变规律。过程指标函数是指从第k阶段至第n阶段所包含的各阶段的状态和决策所产生的总的效益值，记为:Vk,n＝Vk,n(Sk,uk,Sk+1,uk+1,……,Sn,un)TkSkSk+!Vk(Sk,uk)uk(Sk)TnSnSn+1……Vn(Sn,un)un(Sn)K－子过程定义在全过程上的准则函数相当于目标函数，一般记为:V1,n＝V1,n(S1,u1,…Sk,uk,…,Sn,un)，或简记为V1,n,11,,()(,,,,,)knkkknkkkknnuufSoptVSuSuSu()kkfS把过程指标函数Vk,n对k子过程策略pk,n求最优，得到一个关于状态Sk的函数，称为最优值函数或贝尔曼函数，记为:。即①各阶段指标函数的和:,(,)nknjjjjkVVSu,(,)nknjjjjkVVSu②各阶段指标函数的积:动态规划所要求的过程指标函数应具有可分离性，即可表达为它所包含的各阶段指标函数的函数形式。常见的两种过程指标函数形式是：也就是说在阶段k从初始状态Sk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的最优目标函数取值。式中的“opt”（optimization）可根据具体问题的实际意而取min或max。,,()(,)knnkkjjjuujkfSoptVSu,,()(,)knnkkjjj