实验项目五动态规划_第1页
实验项目五动态规划_第2页
实验项目五动态规划_第3页
实验项目五动态规划_第4页
实验项目五动态规划_第5页
已阅读5页,还剩12页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

实验项目五动态规划实验学时:2实验目的:动态规划(dynamicprogramming,DP)是解决多阶段决策问题的一种有效的数量化方法,难度比较大,技巧性也很强。Lindo/lingo是求解动态规划比较常用的软件之一,通过本实验,掌握动态规划模型在Lindo/lingo中的求解。实验要求:1.掌握动态规划的建模步骤及方法;掌握动态规划模型在Lindo/lingo转化及求解;学会动态规划的执行结果分析实验内容及步骤:例:如图5-1所示,某地要从A向F地铺设一条输油管道,各点间连线上的数字表示距离。问应选择什么路线,可是总距离最短?图5-1下面简单说明动态规划的求解建模过程,有助于下一步在Lindo/lingo中模型的表示,这是一个很重要的过程,建议读者不要跳过。动态规划方法求解时注意事项:动态规划的三个基本要素:阶段、状态、决策。其中最关键的是状态的描述,最难的也是状态的设计,它关系到算法的时间、空间复杂度,也跟实现的复杂度息息相关。动态规划的两个条件:最优子结构、无后效性,其中后效性往往容易被忽视。动态规划本质是用空间换时间,在有大量重叠子问题的时候其优势才能充分体现出来。上例的求解过程如下:阶段与阶段变量:先把问题从中间站B,C,D,E用空间位置分成5个阶段,阶段用阶段变量k来描述,k=1,表示第一阶段,k=2表示第二阶段,…状态与状态变量:每一阶段的左端点(初始条件)集合称为本阶段的状态(即开始的客观条件,或称阶段初态)。如第三阶段有四个状态S3={C1,C2,C3,C4},第四阶段有三个状态S4={D1,D2,D3},…描述过程状态的变量称为状态变量:用小写s1,s2,s3…表示第一,第二,第三…阶段的状态变量。当处在状态C2时,我们可记s3=C2决策与决策变量:如当处于C2状态时,下一步怎么走?如何选择路线?即如何决策。是走向D1,还是走向D2?当过程处于某一阶段的某一状态时,可以作出不同的决策(或选择),从而确定下一阶段的状态,这种决定(或选择)叫决策。如选择D2,记u3(C2)=D2即当处于C2状态时,下一步的决策为D2。其中uk(sk)表示第k阶段当状态处于sk时的决策变量。一般地,用久耳)表示第k阶段从状态Sk出发的允许决策集合。如D3(C2)={D1,D2)显然,以Sk)E%Sk)。策略与最优策略:每一阶段产生一个决策,5个阶段的决策就构成一个决策序列:U1(S1),U2(S2),U3(S3),U4(S4),U5(S5)称为一策略。所谓策略是指按一定的顺序排列的决策组成的集合,也称决策序列。这里的最短路径成为最优策略。动态规划就是在允许策略集中选最优策略。状态转移方程:是描述由第k阶段到第k+1阶段状态转移规律的关系式。Sk+1FW上例中状态转移方程为:Sk+1=Uk(Sk)指标函数与最优指标函数:用于衡量所选定策略优劣的数量指标称为指标函数。相当于动态的目标函数,最后一个阶段的目标函数就是总的目标函数。它分阶段指标函数和过程指标函数。阶段指标函数是指第k阶段,从状态sk出发,采用决策uk时的效益,用dk(sk,uk)表示。最优指标函数是指从第k阶段状态sk采用最优策略到过程终止时的最佳效益值,用fk(sk)表示。例如:d(C2,D1)是指由C2出发,下一阶段的决策是D1的两点间的距离。即d(C2,D1)=4。f2(Bi)表示从B1至UF的最短距离。整个问题即为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}下分四种情况进行讨论:/4(£)^=111111JC!,"^D[7F1+CE]'!■=ininP-41-=7S “:(〃)=E】1屁以屈)十总曷:任十3」/4(A)=inm义(珏一耳)十上㈤)].f6+4!&而皿也)十兀㈤)J [2/4(A)=inm国(嘉勺十矣㈤旋 门+4;土临"㈤N〔3+3尸呻)四(5) k=31(5) k=31时务=(Q.C..*C4邮)二Di.同八石(弓)=皿 m)=i>2占〔Q)=4 ^(q)=Di了心叫 叩⑴二虎一(4)k二4时 &二(BlB2ITOC\o"1-5"\h\z了皿C])r(G)] p+121£伊i)=tnin■^(£;0+为(6:)=型戒沁1%二技,你芷)二%必(环Q)+运(Q)J "+完何理,晃)=1% 吗(星)=*(5)k=1时,S1={A}.泌3疆+克3])] .[4+13;_A(A)=nnn• >=mmS;:=17, =Bi… 伉(4■电+去㈤)J [5+1可^再按计算顺序的反推可得最优策略:u/3)=B1."2*(%)=C2.u3*(C2)=d2.u*4(D2)=E2.气*(E2)=F从而得最优路径:a58最短距离为:曾)=17。由上面的过程可以看出,在求解的各个阶段利用了第k段和第k+1段的如下关系:"fg)=mm屣囱+ k=5A32A(7.1)〈 al/s&)=0 (7-2)此递推关系称为动态规划的基本方程。式(7.2)称为边界条件。每步的计算过程及最路径如图5-2所示。图5-2当然本题也可用顺序法求解,但与逆序法无本质的区别。一般来说,当初始状态给定时,用逆序解法,当终止状态给定时,用顺序解法。若既给定了初始状态又给定了终止状态,则两种方法均可使用。下面用lingo来求解动态规划问题可以看出上面的求解过程是比较复杂的,用lingo来求解动态规划问题可以节省大量时间,但使用前要把问题进行一个转化,让lingo知道我们在用它做什么。为了完成模型的转化,有必要对最短路问题的本质进行探讨。其实最终路问题用数学语言来表示就变成如下问题:给定N个点P.(i=1,2,...,N)组成集合{「},由集合中任一点Pi到另一点乃的距离用%表示,两点之间的没有路径,则设d「+8,显然dii=(0<i<N),指定始点为P1终点PN,要求从点P1出发到PN的最短路线。下面把上例进行转化:(1)描述点上述图5-1中的城市和点的对应关系如表7-1所示表7-1城市和点的对应关系AEib2Clc2Gc4DiDPlP4外PsP7玮确定N,可见N=13确定dj,可得d12=4,d13=5,…,d1213=3表示状态转移方程。在这里,定义f(i)是由己点出发至终点PN的最短路程,则状态转移方程就变成如的递推方程。■- J这是一个简单的函数方程,用LINGO可以很方便的解决。下面说明lingo求解步骤:第一步,在Lingo的命令窗口中输入此动态规划的模型,如图5-3所示:LIMiO-UNG口 -LNKIIBitUhlGD虫trvtwHdpX口《MiMhei-linqdi旦整]回剑局尹|@会]:习节陪恒|,现画国区用园剩¥曜|X口《MiMhei-linqdi-I□厘nodel: jL编A个演的悝型:d.3.t3.:TF13.!定&项市卧卜嫩:>=ndd.ataseta?Citie=/L..n/=F;I―个碰;I赫卖型卷笥仁±让+结帽3Eflt亳P・耳包涪砰成ffbF(U?-?PInii耳中「心表示爵我示从第i个城市到那砰顾的量短路“:idad以皿七ycitied/!mad缎型中有・口5成员.分别莅的两个城■就t间是否有踏CS称连J1,2”咳示城血和域下2芝间有净下同;孕£52.6WE3,6幻T48口5,8耳96bP&107U10&L1&住9.L1 121妇1IQ/I21L1312,1.3药玖r.iDiI,.n与正示城口♦¥iu:i中endstts仲 ~顽厂 -:^^CdI9 :3:13pm/图5-3然后单击File菜单下的Save,将模型保存,以供以后使用。(当然也可以不保存模型。其程序的源代码如下:其程序的源代码如下:model:!输入个新的模型;data:n=13;!定义城市的个数;enddatasets:cities/1..n/:F;!13个城市;!结构类型名为cities,结构变量是F,其包含n个成员,F(1),…,F(n),其中F(i)表示将表示从第i个城市到第n个城市的最短路。;roads(cities,cities)/!roads类型中有n*n个成员,分别表示每两个城市之间是否有路(直接相连);21,3!表示城市1和城市2之间有路,下同;2,52,63,63,7TOC\o"1-5"\h\z4,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.如果你计算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所示:*tkiLliatiirhJ3lFrTH*15—■«1.WHR1*tkiLliatiirhJ3lFrTH*15—■«1.WHR1.卜常千Eft下面是其详细结果:Feasiblesolutioniound.TotalaolveiZLteT3.tj.onB:VaLuE13.00000L7.0000013.QQQQQ15.□□□□□12.oaoaolggga.ggg7.0000005.000000IJERE19{TL*jdccccco-u{MEJej[I口口口Cl口Cl'£{vrja□00000'R(O-T*LjaOOOOOO'fiC5)Q□ooooo-t(01*g)aCCCCCC■£防9jGOOOOOC'S上5}aOOOOOD^tSb5)aOODOOO'8(6金ia000000'S(BF)Qggg.己XrE:口QQQQQQ'L£}aQQQQQQ'E*£}a公眼W.'、9■?•?J!a,公(srE)a■:m■-eg'!Gmt■■=t£T)aoooooo■ttET}a000000'0(£1i000000T£(ZT)JC00000'(■"]Jioccc"gICTjJi

Di:乳11:二I:12}2.□□□□□□D(10rID1.000000D(10r12)3.OCOCOC

Hi13)4.OCOCOC贝12;13}3.00000C{L2)_-000000卫(L0.00000Gp(2r£O.DOOOOGp(2f--00000GT::L0.000000'P(3r0.000000p(兀司1.000000p(乳7)0.000000p(、明1.000000p(〜A0.000000T(5j刃0.000000F(5』_.000000p(亏皂1-000000甲5r10;■',000000T;气0.000000L项1.□□□□□□PI:11}1.000000PI:盯12}0.000000PI:□f1UU.000000PI:12;1.000000?(10.11)1.OCOCOC申lOr12)0.000000P(13)1.000000P(12,13)1.000000因篇幅有限,这里把“RowSlackorSurplus"结果省去。第三步,对结果进行分析,得出结论。F(1),…,F(13)分别显示了从P1,.....,P13点到终的距离,可以看出从始点到终点的最短距离为17,与手工求解结果一样。D(i,j)显示的是Pi到Pj的距离如“D(1,2)4.000000〃表从点P1到点乃的距离为4,这些值是在模型初始化时进行设定的。P(i,j)显示的是从某点到终点的最短路径中是否过己到乃的路径,如“P(1,2)1.000000'表从某点到终点的最短路径过P1与乃的路径,注意这里的某点不一定是始点。由此可以得出结论,某点到终点的最短路径分别为:ET启—>RT鸟T与—耳1*ET片T鸟—>拓T兄;R—>昌—>*]T与;尸7T%T TR如%>■肖1■=根据''表7-1城市和点的对应关系〃即可推出图7-2所示的各最短路径。实验条件:1.清华出版社《运筹学教程》教材;2.Lindo/lingo计算机软件;实验思考:2、货郎担问题(travelingsalesmanproblem,TSP):一货郎从某城市

出发要经过n个城市,每个城市都要经过且只能经过一次,最后还要回到原先出发的城市,问应如何选择旅行路线可使总行程最短。设有6个城市,每个城市之间的距离如表5-2所示:表5-2城市123456107024548422396119627020324109321367643454324011372180798484210931137016161857523962136218016160290061196764798185729000出师表两汉:诸葛亮先帝创业未半而中道崩殂,今天下三分,益州疲弊,此诚危急存亡之秋也。然侍卫之臣不懈于内,忠志之士忘身于外者,盖追先帝之殊遇,欲报之于陛下也。诚宜开张圣听,以光先帝遗

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论