动态规划讲解+例子.ppt

第一讲 动态规划(Dynamic Programming) 动态规划的基本概念和思想 最短路径问题 投资分配问题 背包问题 排序问题 二. 最短路径问题 动态规划求解的多阶段问题的特点： 每个阶段的最优决策过程只与本阶段的初始状态有关，而与以前各阶段的决策（即为了到达本阶段的初始状态而采用哪组决策路线无关）。换言之，本阶段之前的状态与决策，只是通过系统在本阶段所处的初始状态来影响本阶段及以后各个阶段的决策。或者说，系统过程的历史只能通过系统现阶段的状态去影响系统的未来。 具有这种性质的状态称为无后效性（即马尔科夫性）状态。 动态规划方法只适用于求解具有无后效性状态的多阶段决策问题。 三. 投资分配问题 四、背包问题 五、排序问题 (20,10,30) (20,0,30) (20,0,20) (0,0,30) (0,0,20) (0,0,10) (0,0,0) 最优 策略 155 135 110 85 60 25 0 f3(x) 60 50 40 30 20 10 0 投资 利润 第四阶段：求 f4(60)。即问题的最优策略。 最优策略为（20，0，30，10），最大利润为160万元。 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ c1 c2 … cj … cn 每件使用价值 a1 a2 … aj … an 重量（公斤/件） 1 2 … j … n 物品 这就是背包问题。类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 设 xj 为第 j 种物品的装件数（非负整数）则问题的数学模型如下： 用动态规划方法求解，令 fk(y) = 总重量不超过 y 公斤，包中只装有前k 种物品时的最大使用价值。 其中y ≥0， k ＝1,2, …, n 。所以问题就是求 fn(a) 其递推关系式为： 当 k=1 时，有： 例3：求下面背包问题的最优解 8 5 12 使用价值 3 2 5 重量（ai） x1 x2 x3 物品(xi ) 解：a＝5 ，问题是求 f3(5) 8 5 12 使用价值 3 2 5 重量（ai） x1 x2 x3 物品(xi ) 8 5 12 使用价值 3 2 5 重量（ai） x1 x2 x3 物品(xi ) 8 5 12 使用价值 3 2 5 重量（ai） x1 x2 x3 物品(xi ) * 动态规划是运筹学的一个分支，是求解多阶段决策过程最优化问题的数学方法。动态规划在经济管理、工程技术、工农业生产及军事部门中都有着广泛的应用，并且获得了显著的效果。学习动态规划，我们首先要了解多阶段决策问题。 最短路径问题：给定一个交通网络图如下，其中两点之间的数字表示距离（或运费），试求从A点到G点的最短距离（总运输费用最小）。 1 2 3 4 5 6 A B1 B2 C1 C2 C3 C4 D1 D2 D3 E1 E2 E3 F1 F2 G 5 3 1 3 6 8 7 6 3 6 8 5 3 3 8 4 2 2 2 1 3 3 3 5 2 5 6 6 4 3 背包问题 有一个徒步旅行者，其可携带物品重量的限度为a 公斤，设有n 种物品可供他选择装入包中。已知每种物品的重量及使用价值（作用），问此人应如何选择携带的物品（各几件），使所起作用（使用价值）最大？ c1 c2 … cj … cn 每件使用价值 a1 a2 … aj … an 重量（公斤/件） 1 2 … j … n 物品 类似的还有工厂里的下料问题、运输中的货物装载问题、人造卫星内的物品装载问题等。 生产决策