文档介绍：*动态规划模型例1:最短线路问题问题:现选择一条从到的铺管线路,使总距离最短?若用穷举法要算2×3×2×2×2×1=48种不同线路,比较这48种结果即可得出,但当段数增加,且各段选择也增加时,穷举法将变得非常庞大,以至利用计算机都十分困难。*下面用动态规划的方法计算最短线路问题的特性:如果最短线路在第k站通过点,则这一线路在由出发到达终点的那一部分线路,对于从点到达终点的所有可能选择的不同线路来说,必定也是距离最短的。(反正法)最短线路问题的这一特性启示我们,从最后一段开始,用从后向前逐步递推的方法,求出各点到的最短线路,最后求得从到的最短线路。*k=6时:设表示由到的最短距离;设表示由到的最短距离;显然k=5时:如果表示由到的最短距离。*最短线路是最短线路是最短线路是*k=4时:最短线路是最短线路是*最短线路是k=3时:最短线路是*最短线路是最短线路是*最短线路是k=2时:最短线路是*最短线路是出发点只有最短线路是最短距离为18。*说明1)此例揭示了动态规划的基本思想。2)动态规划方法比穷举法(48种)大大节省了计算量。3)计算结果不仅得到了到的最短线路和最短距离,而且得到了其它各点到的最短线路和最短距离,这对于很多实际问题来说是很有用处的。动态规划法求解的数学描述讨论动态规划中最优目标函数的建立,一般有下列术语和步骤:1、阶段用动态规划求解多阶段决策系统时,要根据具体情况,将系统适当地分成若干个阶段,以便分若干个阶段求解,描述阶段的变量称为阶段变量。