实验项目五动态规划.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. u?4(D2) = E2. u5?(E2) = F从而得最优路径：a58最短距离为：f1(A) =17。由