动态规划研讨.ppt

A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 (最短路线为 ) 第二阶段（B →C）： B 到C 有 9 条路线。 首先考虑经过 的3条路线 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 (最短路线为 ) 考虑经过 的3条路线 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 (最短路线为 ) 考虑经过 的3条路线 A B2 B1 B3 C1 C3 D1 D2 E 5 2 14 12 6 10 10 4 3 12 11 13 9 6 5 8 10 5 2 1 C2 (最短路线为 ) 第一阶段（A →B）： A 到B 有 3 条路线。 （最短距离为19） 动态规划是用来解决多阶段决策过程最优化的一种数量方法。其精髓在于，它可以把一个n 维决策问题变换为几个一维最优化问题，从而一个一个地去解决。 需指出：动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种算法。必须对具体问题进行具体分析，运用动态规划的原理和方法，建立相应的模型，然后再用动态规划方法去求解。 即在系统发展的不同时刻（或阶段）根据系统所处的状态，不断地做出决策； 动态决策问题的特点： 系统所处的状态和时刻是进行决策的重要因素； 找到不同时刻的最优决策以及整个过程的最优策略。 后无效性（马尔科夫性） 现有数量为a（万元）的资金，计划分配给n 个工厂,用于扩大再生产。 假设：xi 为分配给第i 个工厂的资金数量（万元）；gi(xi)为第i 个工厂得到资金后提供的利润值（万元）。 问题：如何确定各工厂的资金数，使得总的利润为最大。 据此，有下式： 二. 投资分配问题 令：fk(x) 表示 以数量为 x 的资金分配给前k 个工厂，所得到的最大利润值。 用动态规划求解，就是求 fn(a) 的问题。 当 k=1 时， f1(x) = g1(x) （因为只给一个工厂） 当1＜k≤n 时，其递推关系如下： 设：y 为分给第k 个工厂的资金（其中 0≤y ≤ x ），此时还剩 x － y（万元）的资金需要分配给前 k－1 个工厂,如果采取最优策略，则得到的最大利润为fk－1(x－y) ,因此总的利润为： gk(y) ＋ fk－1(x－y) 如果a 是以万元为资金分配单位，则式中的y 只取非负整数0，1，2，…，x。上式可变为： 所以，根据动态规划的最优化原理，有下式： 例2：设国家拨给60万元投资，供四个工厂扩建使用，每个工厂扩建后的利润与投资额的大小有关，投资后的利润函数如下表所示。 投资 利润 0 10 20 30 40 50 60 g1(x) 0 20 50 65 80 85 85 g2(x) 0 20 40 50 55 60 65 g3(x) 0 25 60 85 100 110 115 g4(x) 0 25 40 50 60 65 70 解：依据题意，是要求 f4(60) 。 按顺序解法计算。 第一阶段：求 f1(x)。显然有 f1(x) ＝ g1(x)，得到下表 投资 利润 0 10 20 30 40 50 60 f1(x) ＝ g1(x) 0 20 50 65 80 85 85 最优策略 0 10 20 30 40 50 60 第二阶段：求 f2(x)。此时需考虑第一、第二个工厂如何进行投资分配，以取得最大的总利润。 最优策略为（40，20），此时最大利润为120万元。 同理可求得其它 f2(x) 的值。 最优策略为（30，20），此时最大利润为105万元。 最优策略为（20，20），此时最大利润为90万元。 最优策略为（20，10），此时最大利润为70万元。 最优策略为（10，0）或（ 0 ， 10 ） ，此时最大利润为20万元。