实验项目五动态规划.doc

实验项目五动态规划实验学时：2 实验目的：动态规划（dynamic programming，DP）是解决多阶段决 策问题的一种有效的数量化方法，难度比较大，技巧性也很强。Lindo/lingo 是求解动态规划比较常用的软件之一，通过本实验，掌握动态规划模型在 Lindo/lingo 中的求解。 实验要求：1.掌握动态规划的建模步骤及方法； 2.掌握动态规划模型在 Lindo/lingo 转化及求解； 3.学会动态规划的执行结果分析 实验内容及步骤： 例：如图 5-1 所示，某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？ 图 5-1 下面简单说明动态规划的求解建模过程，有助于下一步在 Lindo/lingo中模型的表示，这是一个很重要的过程，建议读者不要跳过。动态规划方法求解时注意事项： （1）动态规划的三个基本要素：阶段、状态、决策。其中最关键的是状态的描述，最难的也是状态的设计，它关系到算法的时间、空间复杂度，也跟实现的复杂度息息相关。 （2）动态规划的两个条件：最优子结构、无后效性，其中后效性往往容易被忽视。（3）动态规划本质是用空间换时间，在有大量重叠子问题的时候其优势才能充分体现出来。 上例的求解过程如下：（1）阶段与阶段变量：先把问题从中间站 B，C，D，E 用空间位置分成 5 个阶段，阶段用阶段变量 k 来描述，k=1,表示第一阶段，k=2 表示 第二阶段，（2）状态与状态变量：每一阶段的左端点（初始条件）集合称为本 阶段的状态（即开始的客观条件，或称阶段初态）。如第三阶段有四个状 态 S3 =C1 ,C2，C3，C4, 第四阶段有三个状态 S4=D1, D2 , D3, 描述过程状态的变量称为状态变量：用小写 s1 ,s2 ,s3 表示第一， 第二，第三阶段的状态变量。当处在状态 C2 时，我们可记s3= C2 (3)决策与决策变量：如当处于 C2 状态时，下一步怎么走？如何选择 路线？即如何决策。是走向 D1，还是走向 D2？当过程处于某一阶段的某 一状态时，可以作出不同的决策（或选择），从而确定下一阶段的状态， 这种决定（或选择）叫决策。如选择 D2，记 u3（C2）= D2 即当处于 C2 状态时，下一步的决策为 D2。 其中uk(sk) 表示第 k 阶段当状态处于sk 时的决策变量。 一般地，用Dk(sk) 表示第 k 阶段从状态sk 出发的允许决策集合。如 D3(C2)=D1，D2显然，uk(sk) Dk(sk) 。 （4）策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列： u1(s1) ，u2(s2) ，u3(s3) ，u4(s4) ，u5(s5) 称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。 这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。 （5）状态转移方程：是描述由第 k 阶段到第 k+1 阶段状态转移规律 的关系式。 sk+1 =Tk(sk,uk)上例中状态转移方程为：sk+1=uk(sk)（6）指标函数与最优指标函数：用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段，从状态sk 出发，采用决策uk 时的效益，用dk(sk, uk) 表示。最优指标函数是指从第k阶段状态sk 采用最优策略到过程终止时的最佳效益值，用fk(sk) 表示。例如：d（C2, D1）是指由 C2 出发，下一阶段的决策是 D1 的两点间的距离。即 d（C2, D1）=4。f2(B1) 表示从 B1 到 F 的最短距离。整个问题即为f1(A) =？ 在这里我们选择逆序递推法求解：倒退着从F向A走，每倒退一步，思想上问自己：“从现在出发，退向何处？到F的距离最短？”我们分5步来解决问题： （1） k=5 时 求f5(s5)=？此时状态集 S5=E1，E2，故分情况讨论，由 E1 到终点 F 的最短距离为f5(E5)=5同理，f5(E2)=3。故最优决策为：u5(E1)=F，u5(E2)=Fk=4 时 下求f4(s4) =？由于 S4=D1,D2,D3下分四种情况进行讨论： （5）k=1 时， S1=A再按计算顺序的反推可得最优策略：u1(A) = B1. u2(B1) = C2. u3(C2) = D2. u4(D2) = E2. u5(E2) = F从而得最优路径：a58最短距离为：f1(A) =17。由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系：此递推关系称为动态规划的基本方程。式（7.2）称为边界条件。 每步的计算过程及最路径如图 5-2 所示。图 5-2 当然本题也可用顺序法求解，但与逆序法无本质的区别。一般来说，当初始状态给定时，用逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两种方法均可使用。 下面用 lingo 来求解动态规划问题 可以看出上面的求解过程是比较复杂的，用 lingo 来求解动态规划问题可以节省大量时间，但使用前要把问题进行一个转化，让 lingo 知道我们在用它做什么。 为了完成模型的转化，有必要对最短路问题的本质进行探讨。其实最终路问题用数学语言来表示就变成如下问题：给定 N 个点Pi(i =1,2, ) 组成集合Pi ，由集合中任一点Pi到另一点Pj的距离用dij表示，两点之间的没有路径，则设dij=+ ，显然dii=(0 i N ) ，指定始点为P1 终点PN，要求从点P1 出发到PN的最短路线。 下面把上例进行转化： （1）描述点 上述图 5-1 中的城市和点的对应关系如表 7-1 所示 表 7-1 城市和点的对应关系 （2）确定N，可见 N=13（3）确定dij ，可得d12=4 ，d13= 5 ，d1213=3（4）表示状态转移方程。在这里，定义f(i) 是由Pi 点出发至终点PN的最短路程，则状态转移方程就变成如的递推方程。 这是一个简单的函数方程，用 LINGO 可以很方便的解决。 下面说明lingo求解步骤： 第一步，在Lingo的命令窗口中输入此动态规划的模型，如图5-3所示： 然后单击 File 菜单下的 Save，将模型保存，以供以后使用。（当然也可以不保存模型。其程序的源代码如下： 其程序的源代码如下： model: !输入个新的模型; data: n=13;!定义城市的个数; enddata sets: cities/1.n/: F; !13个城市;!结构类型名为cities，结构变量是F，其包含n 个成员，F(1),F(n)， 其中F(i)表示将表示从第i个城市到第n个城市的最短路。; roads(cities,cities)/!roads类型中有n*n个成员，分别表示每两个城市之间是否有路(直接相连）; 1,21,3!表示城市1和城市2之间有路，下同; 2,42,52,63,53,63,74,84,9 5,85,9 6,96,10 7,97,108,118,12 9,119,12 10,1110,12 11,13 12,13 /: D, P;!D( i, j) 将表示城市i 到 j的距离; endsets data: D= 45 236 877 58 45 34 84 35 62 13 4 3; enddata F( SIZE( CITIES) = 0;! 其实SIZE( CITIES)就等于n. 如果你计算n个城市的最短距离，则第n个城市到第n个城市的旅行费用是0; FOR( CITIES( i)| i #LT# SIZE( CITIES): F( i) = MIN( ROADS( i, j): D( i, j) + F( j) );! 从城市i到城市n最短的距离一定是与i相连的所有城市j到城市n的最短距离（即F( j)与城市i到城市j距离(即 D( i, j)） 之和的最小值。; for(roads(i,j): P(i,j)=if(F(i) #eq# D(i,j)+F(j),1,0) !显然，如果P(i,j)=1,则点i到点n的最短路径的第一步是i - j，否则就不是。 由此，我们就可方便的确定出最短路径; ); end第二步，单击 Lingo 菜单下的 Solver 菜单项（或点击也可），对模型进行求解。其结果如图 5-4 所示：下面是其详细结果： 因篇幅有限，这里把“Row Slack or Surplus”结果省去。第三步，对结果进行分析，得出结论。 F(1)，F(13)分别显示了从P1,., P13点到终的距离，可以看出从始点到终点的最短距离为17，与手工求解结果一样。D(i, j) 显示的是Pi到Pj的距离如“D( 1, 2) 4.000000”表从点P1到点Pj的距离为4，这些值是在模型初始化时进行设定的。P(i, j) 显示的是从某点到终点的最短路径中是否过Pi到Pj的路径，如“P( 1, 2) 1.000000”表从某点到终点的最短路径过P1与Pj的路径，注意这里的某点不一定是始点。由此可以得出结论，某点到终点的最短路径分别为：根据“表 7-1 城市和点的对应关系”即可推出图 7-2 所示的各最短路径。 实验条件：1.