目的：动态规划dynamicprogramming,DP是解决多

1、实验目的：动态规划（dynamic programming, DP）是解决多阶段决策问题的一种有 效的数量化方法，难度比较大，技巧性也很强。Lindo/lingo是求解动态规划比较常用的 软件之一，通过本实验，掌握动态规划模型在Lindo/lingo中的求解。实验要求：1.掌握动态规划的建模步骤及方法；掌握动态规划模型在Lindo/lingo转化及求解；学会动态规划的执行结果分析实验内容及步骤：例：如图5-1所示，某地要从A向F地铺设一条输油管道，各点间连线上的数字表示距离。问应选择什么路线，可是总距离最短？图5-1下面简单说明动态规划的求解建模过程，有助于下一步在Lindo/lingo中模型

2、的表示，这 是一个很重要的过程，建议读者不要跳过。动态规划方法求解时注意事项：（1）动态规划的三个基本要素：阶段、状态、决策。其中最关键的是状态的描述，最难的也是状态的设计，它关系到算法的时间、空间复杂度，也跟实现的复杂度息息相关。（2）动态规划的两个条件：最优子结构、无后效性，其中后效性往往容易被忽视。（3）动态规划本质是用空间换时间，在有大量重叠子问题的时候其优势才能充分体现出来。上例的求解过程如下：（1）阶段与阶段变量：先把问题从中间站B，C，D，E用空间位置分成5个阶段，阶 段用阶段变量k来描述，k=1,表示第一阶段，k=2表示第二阶段，状态与状态变量：每一阶段的左端点(初始条件)集合

3、称为本阶段的状态(即开始 的客观条件，或称阶段初态)。如第三阶段有四个状态S3 = C1 ,C2, C3, C4,第四阶段有三个状态S4= D1, D2 , D3，描述过程状态的变量称为状态变量：用小写si ,s2 ,s3表示第一，第二，第三阶段 的状态变量。当处在状态C2时，我们可记s3= C2决策与决策变量：如当处于C2状态时，下一步怎么走？如何选择路线？即如何决策。 是走向D1，还是走向D2?当过程处于某一阶段的某一状态时，可以作出不同的决策(或 选择)，从而确定下一阶段的状态，这种决定(或选择)叫决策。如选择D2,记u3 (C 2) = D2即当处于C2状态时，下一步的决策为D2。其中

4、uk(sk)表示第k阶段当状态处于sk时的决策变量。一般地， 用久耳)表示第k阶段从状态Sk出发的允许决策集合。如D3(C2)= D1，宫显然，以SD GDk(Sk)。策略与最优策略：每一阶段产生一个决策，5个阶段的决策就构成一个决策序列：U1(S1)，U2(S2)，U3(S3)，U4(S4)，U5(S5)称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合，也称决策序列。这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。状态转移方程：是描述由第k阶段到第k+1阶段状态转移规律 的关系式。Sk+1 FW上例中状态转移方程为：Sk+1=Uk(Sk)指标函数与最优指标函数：用于

5、衡量所选定策略优劣的数量指标称为指标函数。相当 于动态的目标函数，最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程 指标函数。阶段指标函数是指第k阶段，从状态Sk出发，采用决策uk时的效益，用dk(S k, uk)表示。最优指标函数是指从第k阶段状态Sk采用最优策略到过程终止时的最佳效益 值，用。气)表示。例如：d (C2, D1)是指由C2出发，下一阶段的决策是D1的两 点间的距离。即d (C2, D1) =4。弓(BJ表示从B1至U F的最短距离。整个问题即为 曾)=?在这里我们选择逆序递推法求解：倒退着从F向A走，每倒退一步，思想上问自己：从现在出发，退向何处？到F的距离最

6、 短？ 我们分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下分四种情况进行讨论:gnEg 夫J5 + 3 |可口)寂El码(电.用)+兀).6 + 4|/二 iiiui s ?=J, 2+3.1g) = Ex/4 (A)Finq+ 泌)工)+g)=nim町(珏)=Ei.k=3 IMS = CCh c C4)*)=Dl*&)+如)皿 p+7|

7、=i2 Mfgjs + 5j同理，右(G)=N，呢(G) = Dw(G)=Ag)=D孟(匚4)=9蚯(Q) = D3.(4) k=4 肘 S3= BlB2皂乌)场2+12/2(51)=tnm =13:药(曷)=C?女 G) +，(Q).6 + 8.J同理，为3,)=1 土芯3=&(5) k=1 时，S1= AI. * 窿见)+ /皿). 4 + 13；./.(J)-nun 户 mm =h 一勤()=瓦|0i0 功+办(禺)J【5+19再按计算顺序的反推可得最优策略：u1*() = B1. u2*(B1) = C2. u3*(C2) = D2. u*4(D2) = E2. u5*(E2) = F

8、从而得最优路径：a58最短距离为：。3) =17。由上面的过程可以看出，在求解的各个阶段利用了第k段和第k+1段的如下关系:1晋霞此四)+作g*)正= 543单(7-1)履任)=。(7-2)此递推关系称为动态规划的基本方程。式(7.2)称为边界条件。每步的计算过程及最路径如图5-2所示。图5-2当然本题也可用顺序法求解，但与逆序法无本质的区别。一般来说，当初始状态给定时，用 逆序解法，当终止状态给定时，用顺序解法。若既给定了初始状态又给定了终止状态，则两 种方法均可使用。下面用lingo来求解动态规划问题可以看出上面的求解过程是比较复杂的，用lingo来求解动态规划问题可以节省大量时间， 但使

9、用前要把问题进行一个转化，让lingo知道我们在用它做什么。为了完成模型的转化，有必要对最短路问题的本质进行探讨。其实最终路问题用数学语言来 表示就变成如下问题：给定N个点P.(i =1,2,. ,N )组成集合，由集合中任 一点Pi到另一点乃的距离用%表示，两点之间的没有路径，则设=+8，显然dii=(0 i L: I 结+431 若为 oitdfi 结 W3ES亳 K 耳包含听成曲 L L 七 PIni I其中展示溜表示从第i个珈T科弟并域布的踊路井:I 口 adsfcxt M习/ ! m也炽中有上5成乱 分即表示符两个城贵走间是酬蹈CE揍褶连J 1?2 既示城诽和财2芝间百备 下同； 孕

10、 5 护 与B匀6 3,T*硒6fc P & 10 9 7j 108, L1 岛龙%L1 9. 121RJ1 10,1211.13013/：珏p. ir=： 1. J：|悔砌诚有二到的由endset s-|mjm T一; 据:npm 孟 . : -图5-3然后单击File菜单下的Save，将模型保存，以供以后使用。(当然也可以不保存模型。其程序的源代码如下：其程序的源代码如下：model:!输入个新的模型；data:n = 13;!定义城市的个数；enddatasets:cities/1.n/: F; !13个城市；!结构类型名为cities,结构变量是F,其包含n个成员， F(1)，,F(n

11、),其中F(i)表示将表示从第i个城市到第n个城市的最短路。；roads(cities,cities)/!roads类型中有n*n个成员，分别表示每两个城市之间是否有路(直 接相连)；2 1,3!表示城市1和城市2之间有路，下同；2,5 2,63,6 3,7 TOC o 1-5 h z 4,95,96,107,108,129,1210,121312,13/: D, P;!D( i, j)将表示城市i到j的距离； endsetsdata:D=452368775845348435621343； enddataF( SIZE( CITIES) = 0;!其实SIZE( CITIES)就等于n.如果你

12、计算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，否则就不是。由此，我们就可方便的确

13、定出最短路径；)；end第二步，单击Lingo菜单下的Solver菜单项（或点击.也可），对模型进行求解。其结果如图5-4所示:5-4下面是其详细结果:Eeaaihle solution found.Total 3clver iteratioris:N13.0000GF( 1J17.00000声2)13.00000珥3)15.0000Q珥匀12.00000F( 5)10.00000号司8.000000m.ooooooF日）7.000000F史5.000000VariableValue000000 E000000 T0 0 0 0 0 0 Z C C C C 0 9：3T J0T )aTT J0

14、T )(z- m i c(it 性)ac c c c av m(IT W)ac c c c c o * gS B)a000000 (TT JBja0 0 0 0 0 0 (DT *jaOOOOOOHC6 JL: a000000 *(oi ;a)a: t(6 J9)G0000009X w)a000000&(s w)a000000B(5)Q000000S(S r)QOOOOOOL(L忸)a000000Lt9 Jj a0000005(S Jj a000000?：9 *E)a000000E)a： z)a0000009t JT)a000000tIE JT)a000000 0(ET ) 2CCC匚匚匚:Z

15、T ) 2C 0 0 0 0 0 f- ) 20 C C C C C s(CL ) 213)4.000000D(12.13)3.000000p(i,2)1.000000p(n3)0.000000p(2,豹 000000p(2,5)1.000000p:A司o.oooooap(3r0.000000p(3用1.000000pt赢0.000000pt 8)1.000000p:、0.000000p(&8)0.000000p(&1.000000p(讯5)-.000000Pi:r10u . 0 0 0 0 0 0p:L勿0.000000F (L101-00000Q111.000000P (123.00000

16、0P (113.000000P(121.00 9 0 CIOP(10T11)1.000000甲10 r12)0 .00000011.13)1.00000012,13)1.000000因篇幅有限，这里把“Row Slack or Surplus结果省去。第三步，对结果进行分析，得出结论。F(1)，F(13)分别显示了从P1,., P13点到终的距离，可以看出从始点到终点的最短 距离为17,与手工求解结果一样D(i, j)显示的是Pi到Pj的距离如“D( 1, 2) 4.000000 表从点P1到点乃的距离为4,这些值是在模型初始化时进行设定的。P0, j）显示的是从某 点到终点的最短路径中是否过Pj到4的路径，如宁（1, 2） 1.000000表从某点到终点的 最短路径过P1与乃的路径，注意这里的某点不一定是始点。由此可以得出结论，某点到终 点的最短路径分别为：月T月一 月一 片T乩T与1十足 足T鸟 拓T R尸R T 耳 T *】T % ；3 T 片口 T 1 T Pi ；% 为=根据表7-1城市和点的对应关系即可推出图7-2所示的各最短路径。实验条件：1.清华出版社运筹学教程教材；2. Lindo/lingo计算机软件；实验思考：1、求下列网络图从起点到终点的最短路线及长度。