实验项目五动态规划

实验项目五 动态规划

实验学时：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)=F

k=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。

由上面的过程可以看出，在求解的各个阶段利用了第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,2 1,3!表示城市1和城市2之间有路，下同;

2,4 2,5 2,6

3,5 3,6 3,7

4,8 4,9

5,8 5,9

6,9 6,10

7,9 7,10

8,11 8,12

9,11 9,12

10,11 10,12

11,13

12,13

/: D, P;!D( i, j) 将表示城市i 到 j的距离;

endsets

data:

D=

4 5

2 3 6

8 7 7

5 8

4 5

3 4

8 4

3 5

6 2

1 3

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.清华出版社《运筹学教程》教材；

2. Lindo/lingo 计算机软件；

实验思考：

1、 求下列网络图从起点到终点的最短路线及长度。

2、货郎担问题（traveling salesman problem ，TSP）：一货郎从某城市