动态的设计规划.ppt

动 态 规 划 在实践中，人们常常会遇到这样决策问题，由于过程的特殊性，可以将决策的全过程依据时间和空间划分为若干个相互联系的阶段。动态规划方法的关键是将多阶段的决策问题变换成一系列的单阶段问题，并逐一解决。 最短线路问题的动态规划基本方程 动态规划建模 确定阶段和阶段变量 明确状态变量和状态可能集合，使它既能描述过程的演变，又要满足无后效性 确定决策变量和决策允许集合 确定状态转移方程 明确解得效应和目标，得到动态规划的基本方程 解析法求解动态规划 随机性动态规划问题 在实际问题中，多阶段决策过程往往有一些随机因素，状态转移不能完全确定，是按照某种已知的概率分布取值的，因此状态变量是一个随机变量。用动态规划方法来解决这种随机性的多阶段决策问题被称为随机性的动态规划。 例4 采购问题 某厂生产上需要在五周内必须采购一批原料，而这批原料估计在未来五周内价格有波动，试求在哪一周以什么价格购入，使其采购价格的数学期望值最小？已测得这批原料的浮动价格和概率如下 0.4 0.3 0.3 概率 700 600 500 单价 解：价格是随机变量。 按采购期限分为 5 个阶段，将每周的价格看作该阶段的状态。设 sk 为状态变量，表示第 k 周的实际价格。xk 为决策变量，当 xk = 1，表示第 k 周决定采购；当 xk = 0 表示第 k 周决定等待。 ykE 表示当第 k 周等待，以后采取最优决策时采购价格的期望值。 fk(sk) 表示第 k 周实际价格为 sk 时，从第 k 周至第 5 周采取最优决策所得的最小期望值。 最优决策为： 逆序递推关系式： * 什么是动态规划？ 这类决策问题，属于运筹学的又一个重要分支，是一种多阶段决策过程最优化问题，称为动态规划（Dynamic programming）问题。 动态规划在工程技术、企业管理、工农业生产及军事等部门都有广泛的应用。 动态规划不是一个具体的算法，而是求解某类问题的一种方法，考察问题的一种途径。必需对具体问题运用动态规划的原理和方法进行具体分析，因此解题时，要有丰富的想象力去建立模型，灵活的技巧去求解。 动态规划方法的关键是将多阶段的决策问题变换成一系列的单阶段问题，并逐一求解。 什么是动态规划？ 【例1】先看一个最优化的例子： 最短路线问题--–选择线路网络中由A到G的线路，使总距离（或总费用）最少？ A B1 B2 C1 C3 C4 C2 D1 E1 F1 G D2 D3 E2 E3 F2 5 3 1 3 6 6 8 7 6 6 6 3 3 3 3 3 3 3 8 5 5 8 4 4 2 2 2 2 1 5 共有2×3×2×2×2×1 = 48 条路线可供选择 什么是动态规划？ 向后递推 — 每阶段各节点到 G 点的最短距离 A B1 B2 C1 C3 C4 C2 D1 E1 F1 G D2 D3 E2 E3 F2 5 3 1 3 6 6 8 7 6 6 6 3 3 3 3 3 3 3 8 5 5 8 4 4 2 2 2 2 1 5 回代：A → B1 → C2 → D1 → E2 → F2 → G 4 3 7 5 9 7 6 8 13 10 9 12 13 16 18 【例2】机器负荷分配问题 某种机器可以在高低两种负荷下进行生产，在高负荷下生产的机器数量为 x ，产品的年产量为 gx ，机器的完好率为 a (0 a 1)；投产低负荷的机器数量 y ,年产量为 h y，相应的完好率为 b (a b 1) 。 刚开始生产时，完好的机器数量为 s1，要制定一个五年计划，确定每年投入高低两种负荷下生产的完好的机器数量，使 5 年内产品的总产量达到最大？ 设 s1 = 1000（台），g = 8，h = 5，a = 0.7，b = 0.9。 这是一个五阶段决策问题 s1 s2 s3 s5 s4 x1 x2 x3 x4 最短路线问题的动态规划模型 阶段变量 k = 1, 2, 3, …, 6 状态变量 如 s2 ∈S2 = { B1,B2 } 决策变量 x2(B1) ∈ D2(B1) = { C1,C2,C3 } 策略 如 A→ B1→C2 →D1 →E2 → F2→ G 状态转移方程 sk+1 = xk(sk) 阶段指标函数 Vkn = dk( sk, xk ) + dk+1( sk, xk ) +……+ d6( s6, x6 ) = dk( sk, xk ) + Vk+1,n(sk+1,xk+1,…,s6,x6)