建模讲座 动态规划.pptVIP

动态规划 俞 辉 三峡大学理学院数学系 Email:yuhui@ctgu.edu.cn 引言 动态规划——Dynamic Programming 动态规划是运筹学的一个分支，是解决多阶段决策过程最优化的一种数学方法。 1951年，美国数学家贝尔曼等人提出了 “最优性原理”，即根据一类多阶段决策问题的特点，把多阶段决策问题变换为一系列相互联系的单阶段决策问题，然后分阶段逐个加以解决。 从而创建了解决最优化问题的一种新的方法 —— 动态规划。 引言 动态规划是解决某一类问题的一种方法，是分析问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因此，在学习动态规划时，除了对基本概念和方法正确地理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 引言 本部分我们主要研究离散决策过程， 介绍动态规划的基本概念、理论和方法， 通过一些典型的应用问题来说明它的应用。 多阶段决策过程及实例 多阶段决策过程（Multi-Stage decision process） 整个决策过程可按时间或空间顺序分解成若干相互联系的阶段，每一阶段都需作出决策，全部过程的决策是一个决策序列。 多阶段决策过程最优化的目标： 达到整个活动过程的总体效果最优，而非各单个阶段最优的简单总和。 多阶段决策过程及实例 多阶段决策问题的典型例子 多阶段决策问题的典型例子： 1 . 生产与存储问题：某工厂每季度需供应市场一定数量的产品，并将剩余产品存入仓库。一般每季度适当增加产量可降低生产成本，但会同时增加库存费用，如何安排一年的生产计划使生产与存储费用最小。 2. 设备更新问题：如果设备太陈旧就需要投入较高的维修费用，如果购买新设备就需要一次性投入较大的更新费用。根据市场预测，如何制定企业未来5年的设备更新计划？ 3. 最短路问题：给定一张网络图，如何确定两点之间的最短路径？ 多阶段决策问题的典型例子 4. 航天飞机飞行控制问题：由于航天飞机的运动的环境是不断变化的，因此就要根据航天飞机飞行在不同环境中的情况，不断地决定航天飞机的飞行方向和速度（状态），使之能最省燃料和实现目的（如软着落问题）。 5. 线性规划、非线性规划等静态的规划问题也可以通过适当地引入阶段的概念，应用动态规划方法加以解决。 多阶段决策过程及实例 请看如下典例——最短路线问题 多阶段决策过程及实例 贪心算法 每一步都走最短的线路： A—B2—C4—D3—E2—F2--G，长度为21 。不是最优： 最短的线路: A—B1—C2—D1—E2—F2--G，长度为18 枚举法 列出每条可能的路线，然后算出每条路的长度，从中选择最优路线。 缺点是线路太多，随点数增加很快。 标号法 标号法：只适用于这类最优路线问题的特殊解法。 标号法是借助网络图通过分段标号来求出最优路线的一种简便、直观的方法。 通常标号法采取“逆序求解”的方法来寻找问题的最优解，即从最后阶段开始，逐次向阶段数小的方向推算，最终求得全局最优解。 最短路问题 该方法比枚举法简单，计算的路远少于枚举法 计算过程分了六个阶段。 每个阶段都是一个子问题，有出发点和选择，并有不同的获得。 后一阶段的出发点由前阶段的出发点和选择确定 前一阶段的获得不仅与本阶段的选择有关还与后一阶段的获得有关。 这类问题称之为多阶段决策问题。 动态规划的基本概念和基本原理 1、阶段（stage） 把所给问题恰当地划分为若干个相互联系又有区别的子问题，通常根据时间顺序或空间特征来划分，以便按阶段的次序逐段解决整个过程的优化问题。 描述阶段的变量叫作阶段变量，阶段变量通常用k表示（k = 1，2，3，…，n）。 动态规划的基本概念和基本原理 2、状态（state） 用以描述事物(或系统)在某特定的时间与空间域中所处位置及运动特征的量，称为状态。它应能描述过程的特征并具有“无后效性”，又称马尔柯夫性，是指系统从某个阶段往后的发展，仅由本阶段所处的状态及其往后的决策所决定，与系统以前经历的状态和决策(历史)无关。 状态变量 —— sk（state variable） 状态集合 —— Sk（set of admissible states） 动态规划的基本概念和基本原理 3、决策（decision） 决策：确定系统过程发展的方案。 决策的实质是关于状态的选择，是决策者从给定阶段状态出发对下一阶段状态作出的选择。 决策变量 — uk（sk）（decision variable） 决策集合 — Dk（sk）（set of admissible decision） 动态规划的基本概念和基本原理 4、策略（policy） 策略也叫决策序列。 一组有序的决策序列构成一个策略， 从第k阶段至第n阶段的一个策略称为后部子策略。 动态规