《建模方法教学资料》动态规划模型

《《建模方法教学资料》动态规划模型》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二部分动态规划模型动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种数学方法。1951年美国数学家贝尔曼(R.Bellman)等人，根据一类多阶段决策问题的特点，提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新方法一一动态规划。动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。下面，以最短路径问题为例，说明动态规划的基本思想方法和特点。(一)、最短路径问题1、问题提岀如图1-10所不(P56),从A)地要铺设一条管道到人地，中间必须经过五个

2、中间站,第一站可以在A两地中任选一个，类似的，第二、三、四、五站可供选择的地点分别是{令,B2,C2,P2},{A3,B3,C3},{A49B49C4},{A5,B5}连接两点间的距离用图上两点连线上的数字表示，两点间没有连线的表示相应两点不能铺设管道，现要选择一条从A）到人的铺管线路，使总距离最短。2、问题分析解决最短路径问题，最容易想到的方法是穷举法，即列出所有可能发生的方案和结果，再针对题目的要求对它们一一进行比较，求出最优方案。这种方法，在变量（或节点）的数目较小时有效；在变量数目很大时，计算量将会变得十分庞大，行不通。因此，需要根据问题的特性，寻求一种简便的算法。

3、最短路径问题有一个特性：如果最短路径在第k站通过点耳,则这一线路在由心出发到达终点的那一部分线路，对于从点心终点的所有可能选择的不同线路来说,必定也是距离最短的。这就是最优性原理。这就启发我们从最后一段开始，釆用从后向前逐步递推的方法，求出各点到人6的最短线路，最后求得从A）到人的最短线路。（归结为一句话：最有策略的子策略仍然是最优策略）3、问题求解为求解方便,将整个过程分为6个阶段,用k（k=1,2,•••,6）表示o（1）£=6时，设去（4）表示由人到人的最短距离，/6（耳）表示由艮到人的最短距离,有人(4)=4,f6(B5)=3（2）k=5时①从人4出发,有两种选择，

4、到4或昆,如果去（人）表示A4到A6的最短距离,〃5（儿，4）表示儿到人的距离，则3+41=min<5+3j5(a49a5)+/6(A)J5(A49B5)+/6(B5)r7再用处（儿）表示相应的选择或决策，则况5（4）=4。得到由儿出发到人的最短线^(A4)=min=1路是人4T人T人。0从坊出发，也有两种选择，到4或禺,如果/5（34），〃5（〃4，〃5），〃5（〃4,4），%5（〃4）的定r、5+4=minx>=52+3义与①中相似，贝!）仏©，4)+人(比)]^5(b4,b5)+/6(b5)JU5（d）-昆o得到由^4出发到A的最短线路是艮4TB5T人。J5(C4,B

5、5)+/6(B5)6+41=min<>=96+3同样有/；(C4)=min处«4）=耳。得到由C4出发到人的最短线路是ClT耳T人。(3)比=4时，

6、分别以A3,B3,C3为出发点来计算，有2+71=min<>=72+5f4(A3)=minJ4(A3,A4)+f5(A4)d4(A3,B4)+f5(B4)%4(人3)=〃4,由人3出发的最短线路是人3TB4T耳T人。/4(B3)=minj4(b39b4)+/5(b4)16/4(b3,c4)+/5(c4)J了、1+5=min<〉=6124-9/^(B3)=B4,由禺出发的最短线路是场T坊TT人。t/4(C3,B4)+/5(B4)

7、J4(C3,C4)+/5(C4)3+5=min<>=83+9◎GWd,由C3出发的最短线路是C3T色T耳T人。/；(C3)=min(4)£=3时，分别以龟用空匸空①空为出发点来计算，有/；(A2)=mind3(A2,A3)+f4(A3)d3(A2,B3)+/4(B3)X*、6+7=min<>=138+6w3（4）=4,由企出发的最短线路是人2T4TdTB5T人。；©）论严，九）+£（吟神+7j[J3（B2,B3）+/4（B3）J[5+6j均（场）=去，由场出发的最短线路是场T人T乞T昆T人。/；(C2)=minJ3(C2,B3)+/4(B3)6/3(C2,C3)+/4(C

8、3)=min(3+6L9[3+盯%3（G）=〃3，由G出发的最短线路是d3(D29B3)+f4(B3)J3(D29C3)+/4(C3)12C2T场TB4T耳T人。/3(Z)2)=minW3（^2）=C3,由3出发的最短线路是£>2TC3T乞T艮T人。（5）£=2时，分别以£小1为出发点来ar计算，有£(4i)=min<“2(A，企)+厶(%)〃2(4

9、,场)+厶(场)d2(A{,C2)+f3(C2<、1+13>=min<3+106+9V丿>=13(£)=场，由A出发的最短线路是Aj-3B。-A3~»B4~»8^-