动态规划模型及实验.doc

第七章 动态规划模型与实验一个系统依据某种方式分为许多个不同的阶段，这些阶段不仅有着次序推移性，而且相互间有着依赖和影响。这种能分成阶段推移的系统叫做动态系统。动态规划是解决多阶段决策过程最优化的一种数学方法。动态规划的一个显著特点在于具有明确的阶段性，整个系统按某种方式可分为若干个不同的阶段，在每个阶段由若干种不同的方案可供选择。这样，在多阶段决策过程中，每个阶段决策的选择，不仅要依据次序来考查某阶段的效果外，而且更要顾及此决策对以后各阶段决策的影响，特别是对以后各个阶段决策的影响。系统最优决策问题要求在系统每个阶段可供的多种方案 (决策) 中，选择一个合适的决策，使整个系统达到最优的效果。整个过程分为多阶段的决策过程。各个阶段所做的决策形成确定整个系统的决策序列，称这样的决策序列为系统的一个策略。对应某一确定的策略，整个系统依据某种数量指标衡量其优劣的决策。多阶段决策过程就是在所有允许策略集合中。确定一个达到最优指标的最优策略。这种衡量系统的指标一般取最大值或最小值的策略。因此，多阶段决策过程也是一个可以构成多个变量的最优化问题。一个系统能分为多阶段的决策过程，有时需要数学技巧和艺术来划分，动态规划就是解决此类多阶段决策过程的最优化方法。7.1动态规划的基本原理实际生活的问题，通过构造数学模型，具有特殊的动态系统过程，将基于某种方式把整个过程分成若干个互相联系的阶段，在其每个阶段都需要作出合适决策，从而使整个过程达到最佳效果。同时，各个阶段决策的选择依赖于该阶段的状态以及前或后阶段的变化。各个阶段决策确定后，组成一个决策序列，从而形成了整个过程具有前后关联的链状结构的多阶段决策过程，称为序贯决策过程。由此，动态规划求解首先关键在于如何将实际问题构造成能形成多阶段的系统，并且在各个阶段能作出序贯性的最佳决策，以使在序贯决策的状态推移进程中达到整个系统的最优决策。例7.1能分成阶段的最短路问题。图7.1是一个路线网络图，连线上的数字表示两点之间的距离（或费用），要求寻找一条由A到E的路线，使距离最短（或费用最省）。657999745105556811 B1 C1 D1 A B2 C2 E D28 B3 C3图7.1 对于这样一个比较简单的问题，可直接使用枚举法列举所有从A到E的路线，共14条，然后，根据每条路线的长度（或费用），确定出所应走的路线（费用）最短（少）。直观的思想，如果已找到由A到E的最短路线是AB1C2D2E（记作L），那么当寻求L中的任何一点（如C2）到E的最短路时，它必然是L中子路线C2D2E（记作L1）。否则若D2到E的最短路是另一条路线L2 ，则把AB1C2与L2连接起来，就会得到一条不同于L的从A到E的最短路。根据此特性，可以从最后一段开始，用逐步向前递推的方法，依次求出路段上各点到E的最短路，最后得到A到E的最短路。上述这种由系统的作后阶段逐段向初是始阶段求最优的过程称为动态规划的逆推解法。该过程揭示了动态规划的基础思想，为使动态规划的思想和方法数学上描述。下面先引入动态规划中基本概念与最优目标函数的建立。（1）分阶段 把所给的系统，适当地依据具体情况分成若干个相互联系的阶段，描述阶段的变量称为阶段变量，常用k表示，并将各个阶段按顺序或逆序加以编号，如例7.1可分为5个阶段来求解，k=1，2，3，4，5。（2）状态 状态表示系统在某一阶段所处的位置，自然状况或客观条件。一个阶段系统会存在若干个可能的状态。在例7.1中，状态就是某阶段的出发位置，它既是该阶段某之路的起点，又是前一阶段某之路的终点，一个阶段有若干个状态，第一阶段有一个状态就是初始位置A，第二阶段有三个状态，即使集合B1，B2，B3，一般第k阶段的状态就是第k阶段所有始点的集合。描述过程状态的变量称为状态变量，常用Sk表示第k阶段的所有可能状态变量的集合，其元素为sk可以是数，数组或向量。如例7.1中第三阶段有三个状态，则sk可能取三个值，即C1,C2,C3，并且S3=C1，C2，C3 称为第三阶段的可达状态集合。（3）决策 决策表示当系统处于某一阶段的某个状态时，可以作出不同的选择，确定下一阶段的状态，这种决定称为决策。描述决策的变量称为决策变量，常用dk(sk)表示第k阶段当状态处于sk时的决策变量，它是状态变量的函数。而用Dk (S k) 表示相应的决策变量的函数集，即有dk (sk)Dk (Sk)。如在例7.1第二阶段中，从状态B2出发，其允许决策集合为D2(B2)=C1，C2，C3，某一阶段的状态变量及决策变量的值取定之后，那么下一阶段的状态随之确定。例如选取的点为C2，则C2是状态B1在决策d2(B1)作用下的一个新的状态，记作d2(B1)= C2，下一阶段的状态类似地对上阶段的状态和决策变量的依赖关系可用状态转移方程表示：s k+1=T k (s k，d k (s k) ) (7.1)(4) 策略 由系统各阶段确定的决策所形成的决策序列称为策略。从初始状态s1出发由系统的所有n个阶段的决策所形成的策略成为全过程策略，记为：P1，n(s 1)=d 1(s 1)，d 2(s 2)，d n (s n ) (7.2)由系统的第k个阶段出发的后面n k +1个阶段的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略，记为P k，n(s k)=d k(s k)，d k+1(s k+1)，d n (s n ) (7.3)所有可供选择的策略集合称为策略集合，用P表示，从允许策略集合中找出达到最优效果的策略称为最优策略。（5）状态转移方程 状态转移方程是确定过程由一个状态到另一个状态的演变过程。若给定第k阶段状态的演变过程，并且若该阶段的决策变量dk一经确定，第k+1阶段的状态变量sk+1也就完全确定，这种对应关系为：sk+1=Tk (sk ，dk(s k )所描述了由第k个阶段到第k+1个阶段的状态转移规律，称为状态转移方程。Tk 称为第k阶段的状态转移系数。如例7.1中，状态转移方程为s k+1=d k (s k )(6) 阶段收益 系统某一阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统总收益的一部份。阶段效益是阶段状态和决策变量的函数，反映该阶段的价值与目标。对第k阶段的某一状态sk执行某一决策d k(s k )的阶段效益可用r k(s k ，d k(s k )来表示。在例7.1中的阶段效益为走完一段路程所花费的距离。(7) 指标函数和最优值函数 系统执行某一策略所产生效果的优劣可用数量指标来衡量，这样的数量指标是整个系统总效益的反映，它是各个阶段状态和决策的函数，称为指标函数。它是定义在全进程和所有子进程上确定的数量函数，记 F k，n(sk, p k，n )，i=n，n-1，1 (7.4)表示从阶段k的某一状态sk 出发的后部子进程上的指标函数，其中pk，n表示从状态sk出发的一个子策略，最优策略下指标函数的指标为最优策略指标，记为 (7.5)其中Pk, n表示由状态Sk出发的所有允许子策略集合，“opt”为英文Optimization（最优）的缩写，可以依题意取min或max。由上述指标函数的定义，可得指标函数（例7.1的指标函数注记r k(s k ，d k(s k )表示第k 阶段中点s k 到d k(s k )的距离）。 其中 (7.6)而最优策略指标为 (7.7)在例7.1中显然有 fn+1(sn+1) = 0 (7.8)称为边值条件，动态规划的求解对k=n, n-1,1由（7.7）式求最优策略指标的过程。一般地对多数指标函数的形式取（7.6）式，而最优策略指标取形如（7.7）式，以求和形式出现，另一种常用形式是的各阶段的指标函数为乘积，即 (7.9)其相应的最优策略指标为 (7.10)对更一般的系统来说，指标函数未必是求和或乘积形式，但应具有可分离性，并满足递推关系，一般具有形式 (7.11) (7.12)在第k阶段，指标函数最优策略指标，即最优值，称为最优值函数，即fk(sk)。根据上述确定的阶段编号、状态变量、决策变量、状态转移方程以及指标函数，确定例7.1的最短路线，计算步骤如下：根据最短路线特性，寻找最短路线的方法，将从最后一段开始，用由后向前逐步递推的方法，求出各点到E点的最短路线，最后求得由A点到E点的最短路线。所以，动态规划的方向是从各点逐段向始点方向寻找最短路线的一种方法，见图7.2显示行进方向1 2 3 4 5始点 终点动态规划寻优途径图7.2当k= 4时，由D1到终点E只有一条路线，故f4(D1) = 6，同理，f4(D2) = 5。当k= 3时，出发点有C1、C2、C3三个，若从C1出发，则有两个选择，一是至D1，一是至D2，则其相应的决策为d3(C1)=D1，表示由D1至终点E的最短距离为11，其最短路线是C1D1E。同理，从C2和C3出发，则有其相应的决策为d3(C2) = D2。且d3(C3) = D3。类似地，可计算当k=2时，有f 2（B1）= 18 d2（B1）= C2f 2（B2）= 19 d2（B2）= C2f 2（B3）= 15 d2（B3）= C2当k=1时，出发点只有一个A点，则且d1（A）= B1 ，于是获得从始点A至终点E的最短距离为15。为使找出最短路线，再接计算的顺序推之，可求出最优决策函数序列dk，即由d1（A）= B1 ，d2（B1）= C2 ，d3（C2）= D2 ，d4（D2）= E，组成一个最优策略。那么最短路线为AB1C2D2E。从上述例7.1的计算过程，可知动态规划的方法比枚举有以下优点：（1）减少计算量，使用枚举法，要对18条路线比较，即比较运算进行18次，逐阶段累计加法为64次。使用动态规划来计算，比较运算为7次，加法运算16次，可见，动态规划方法比穷举法减少了许多计算量，而且随着规模扩大，计算量将大大地减少。（2）丰富了计算结果，虽然枚举法执行了较多的运算，其结果只有从起点A到终点E的一个结果，用动态规划方法以较少的运算不仅得到从A至E的最优路线，而且还确定了各中间点到终点E的最优路线。7.2 LINGO软件计算动态规划 使用LINGO软件计算上述动态规划问题。设：A顶点（城市）1，B12，B23，B34，C15，C26，C37，D18，D29，E点（城市）10。本例使用LINGO程序的编制动态规划模型如下：MODEL:SETS: ! Dynamic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here is our primitive set of ten cities, where F( i) represents the shortest path distance from city i to the last city; CITIES /1.10/: F; ! The derived set ROADS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.); ROADS( CITIES, CITIES)/ 1,2 1,3 1,4 2,5 2,6 3,5 3,6 3,7 4,5 4,6 5,8 5,9 6,8 6,9 7,8 7,9 8,10 9,10/: D; ! D( i, j) is the distance from city i to j;ENDSETSDATA: ! Here are the distances that correspond to the above links; D = 5 7 9 9 8 11 7 4 5 10 5 7 6 5 8 11 6 5;ENDDATA! If you are already in City 10, then the cost to travel to City 10 is 0; F( SIZE( CITIES) = 0;! The following is the classic dynamic programming recursion. In words, the shortest distance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance from j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) );END程序第十行，集合CITES表示点，赋值F(i)表示从城市i到最后一个城市的最短距离。第十五行中集合ROADS(,)表示连接城市间的弧，而数据D()表示从城市到城市的距离。动态规划的目标函数，即为从城市到最后城市10的最短距离为所有从城市到城市可达到路加上从到城市10的最短距离的和的最小值。使用SOLVE求解得结果如下，其中F（i）表示第i个（城市）点至最后（城市）终点E的距离。从上述计算过程，可归纳k阶段与k+1 阶段之间的递推关系 (7.13)称为动态规划的基本方程，以及边值条件为：f n+1 (sn+1 )=0动态规划方法的基本思想归纳如下：（1） 归纳出基本的递推关系式和恰当的边值条件，即基本方程。（2） 在多阶段决策过程中，虽是独立的阶段，但又将当前阶段效益和未来效益阶段结合起来的一种最优化方法。（3） 在求解整个系统的最优策略时，由于初始状态是已知的，而每阶段的决策都有该阶段的函数，所以最优策略经过的各段状态，便可逐次变递推换得到，从而确定了最优的路线。 例如，在例7.1中，初始状态A已知，上述逐次变换如图7.3。 d1(A) d2(B1) d4(D2) （已知） A B1 C2 E图7.3从而可得最优策略为d1(A)，d2(B1)，d4(D2)，相应的最短路线为AB1C2D2E，计算过程，使用图7.4直观简明地表示，图中每节点处上方的方格内的数，表示该点到终点E的最短距离，用直线连接点表示该点到终点E的最短路线，未连线的点表示该点到终点E不是最短路线，（舍去），图中粗线表示由始点A到终点E的最短路线，这种由E点开始从后向前，即从终点至起点求优的过程叫做逆推解法，逆推法不仅求出A到E最优路线，而且确定了任意点到点E的最优路线，如果问题不仅要求确定从点A到点E的最优路线，并要求知道A到其它点的最优路线，可采用从始端逐步向终端求优的顺推解法。2318191611101465 B1 C1 D1 A B2 C2 E D2 B3 C3图7.47.3 顺推解法对例7.1来说，顺推解法以A为始端，逐阶段计算各中间点到A的最优路线，直至确定E到A的最优路线，用顺推法求解时，可以根据情况对阶段重新编号，确定各阶段的允许状态集合，各状态的允许决策集合，状态转移方程，阶段效益及指标函数，如果阶段编号，状态变量与决策变量取值保持不变，则第k阶段的状态变量应是sk+1，而不是sk。这由于在顺推算法时sk+1成为k阶段的“初始状态”，而sk成为采取某一决策后的“终止状态”。因此，相应的状态转移方程为 (7.14) 它应是逆推算法中状态转移方程的逆变换，其次从初始阶段向最后阶段过渡的指标函数与最优指标应满足 (7.15) (7.16)边值条件为 (7.17) 在例7.1中，若阶段编号，状态变量与决策变量的定值不变，则顺推解法的指标函数为最优指标为在图7.5中，表示顺推过程的图解，详细计算不再聱述，每个节点处上方方格内的数表示该点到A点的最短距离，用直线连接的点表示该点到始点A的最短路线，粗线表示A到E的最短路线。235791413111918 B1 C1 D1 A B2 C2 E D2 B3 C3图7.5注意A到D1有两条最短路，即AB1C1D1，或AB2C3D1。使用LINGO软件程序编制软件本例的顺推法，只要设E1点（城市），D12，D23，C14，C25，C36，B17，B28，B39，A10点（城市）。计算动态规划（顺推法）LINGO程序如下：MODEL:SETS: ! Dynamic programming illustration. We have a network of 10 cities. We want to find the length of the shortest route from city 1 to city 10.; ! Here is our primitive set of ten cities, where F( i) represents the shortest path distance from city i to the last city; CITIES /1.10/: F; ! The derived set ROADS lists the roads that exist between the cities (note: not all city pairs are directly linked by a road, and roads are assumed to be one way.); ROADS( CITIES, CITIES)/ 1,2 1,3 2,4 2,5 2,6 3,4 3,5 3,6 4,7 4,8 5,7 5,8 5,9 6,8 6,9 7,10 8,10 9,10/: D; ! D( i, j) is the distance from city i to j;ENDSETSDATA: ! Here are the distances that correspond to the above links; D = 6 5 5 6 8 7 5 11 9 11 8 7 5 4 10 5 7 9;ENDDATA! If you are already in City 10, then the cost to travel to City 10 is 0; F( SIZE( CITIES) = 0;! The following is the classic dynamic programming recursion. In words, the shortest distance from City i to City 10 is the minimum over all cities j reachable from i of the sum of the distance from i to j plus the minimal distance from j to City 10; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) );END 详细解释参见逆推法，使用SOLVE求解得结果如下，其中F(i）表示第i个点至起点A的距离。 归纳如下，使用动态规划解一个可分阶段的多阶段决策问题时，必须包含下面步骤。（1）将系统划分成恰当的阶段，并编号；（2）确定状态变量，状态变量集合；（3）确定决策变量，以及允许决策变量集合；（4）建立状态转移方程；（5）确定各阶段的阶段效益；（6）建立指标函数；（7）为边值条件，求最优指标并给出相应于最优指标的状态转移方程。（8）对k=1,2，n，从最优指标的状态转移方程求得最优决策。上述求解过程由图7.6所示，在选择状态变量时应能正确地反映