资源描述：
《第14章动态规划》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第14章动态规划本章通过将实际问题当作多阶段决策过程来建立数学模型，学习和掌握动态规划的相关知识及其求解的逆序算法，并结合计算机编程解决实际问题。14.1引例：生产计划的制定某工厂与用户订立合同，在四个月内出售一定数量的某种产品，产量限制为10的倍数，工厂每刀蝕多生产100件，产品可以存储，存储费用为每台2百元，每个月的需求量及每件产品的牛产成本见表14」。表14.1生产成本和需要量刀份每件生产成木（元）需要虽（件）170602727038012047660现在分别在（1）一刀初没冇存货可用和（2）一刀初冇20件存货可用这两种情况下确定每月的出产量，要求既能满足每
2、月的合同需求量，乂使牛产成本和存储费用达到最小。静态的看，木引例是一个整数规划问题，但这里我们可以把这个问题的解决动态地视为各刀（一般称为阶段）先后作出决策（这里指生产量）的过程——多阶段的决策过程，而在每个月作决策吋，不能仅考虑本月的费用（一般称为阶段指标）因为木刀的决策会对以后各刀的决策产生影响，因此应考虑从本月直到第四月末的总费用（总指标），而每月的决策依赖于各月初仓库的存货量（一般称为始端）和以前各月如何造成这货存量的情况无关（称为无后效性）。在例2中我们将计算一月初无存货可用时的最优决策见表2表14・2最优生产计划1刀2刀3刀4刀月初存储量（件）0407
3、00产量（件）10010()5()60则笫四月的决策即为月初仓储数为0时的最优决策，笫三、四月的决策即为第三月初仓储数为70时的最优决策，以及第二、三、四月的决策即为第二月初仓储数为4（）时的最优决策。因为若不然，如对应于第三月初仓储数为70时，第三、四月的最优决策是分别牛产80件和30件（即这样的费用比分别生产50件和6（）件更省），则我们保留第一、二月的生产数，而把第三第四月分别改为80件和30件，这个方案显然优于原来的方案，这和原來的方案是最优相才盾。这个性质可以简述为：最优决策的任何截断仍是最优的（最优性原理）。把这一最优化问题视为符合最优性原理、无后效性
4、的多阶段决策过程并进行求解的方法称为动态规划方法。14.2动态规划的基本理论复习14.2.1基本思想与逆序解法的直观回顾前面我们己简单介绍了动态规划。为了更便于了解动态规划的基本思想、描述方式和逆序解法，我们來看一个确定网络最短路径问题的例子。例1：（最短路径的确定）以下是一个赋权图，两顶点连线上的数字表图14.1直观上我们有这样一个重要常识：如果由起点Vj经过V,.点和Vj点而到达终点v16是一条戢矩路线，则由点片出发经过y点到达终点v16的这条路线，对于从气•点出发到达终点的所有可能选择的不同路线来说，必定也是最短路线。例如在最短路线问题中，若找到了儿T卩2T
5、v5TbTv12Tv15T%是由V)点到％点最如路线，则V8TV12TV15T%应该是由$点出发到达终点的所有川能选择的不同路线屮最短路线。这一特征即为上面所提到的最优性原理：最优性决策的任何截断仍是最优的，这是动态规划的基木原理。根据最优性原理，寻找最短路线可从最后一•段开始，用由后向前逐步递推的方法，求出各点到％点的最矩路线，最后求得由儿点到％点的最矩路线，所以动态规划的逆序求解方法是从终点逐段向始点方向寻找最短路线的一种方法。下面逐段完成计算。例1当然对以用图与网络实验中介绍的Dijkstra算法来求解，但这里我们将把该问题看成6个阶段的决策过程，并逆序逐段
6、求解，从而较肓观地揭示动态规划的基本思想。"6时,以/6(v14)表示由％到％的最短距离,以/6(v15)表示由片5到％的最短距离，则/6(v14)=4,/6(v15)=3ok=5时，出发点有三个町、片2和片3。若从儿1出发有％和儿5两个选择，以/5(Vh)表示由片］到%的最短距离,(“11*14)表示由仏到VI4的距离，^(VH,V15)表示由仏到仏的距离，血⑴J表示相应的选择或决策,则：/5(vH)=min{^5(vH,vI3)+/6(v14),6/5(v11,v15)+/6(vI5)}=min(3+4,5+3}=7可见u5(VH)=v14,其最短路径为V
7、
8、
9、—>v14—>v16o同理，从％出发也有岭4和儿5两个选择,人W】2)〃5山2$4)、d5(vn,v15)和u5(v12)意义与上面相似,则:f5(v12)=mind5(v12,v14)4-/6(v14),(v12,v15)+f6(v15)}=min{5+4,2+3}=5可见W5(v12)=v15,其最短路径为VI2Tv15Tv16o从儿3出发，同样有：/5(vI3)=min{J5(v13,v14)+/6(v14),J5(v13,v15)+/6(v15)}=min{6+4,6+3}=9可见(vJ3)=V
10、5,其最短路径为V
11、3TvJ5—>v)6ok=4时，有三个
12、出发点冬、
