《ch3动态规划》PPT课件.ppt

第三章 动态规划 Operational Research 动态规划（Dynamic Programming）同前面介绍过的 线性规划方法不同，它不是一种算法，而是考察问题 的一种途径。动态规划是一种求解多阶段决策问题的 系统技术。由于动态规划不是一种特定的算法，因而 它不像线性规划那样有一个标准的数学表达式和明确 定义的一组规则，动态规划必须对具体问题进行具体 的分析处理。动态规划在工程技术、经济管理等各个 领域都有着广泛的应用，并且获得了显著的效果。 3.1 最短路径问题 3.2 贝尔曼最优化原理 3.3 WinQSB软件应用 第三章 动态规划 动态规划是解决多阶段决策问题 的一种方法. 1951年，美国数学家 贝尔曼（R.Bellman，19201984 ）研究了一类多阶段决策问题的 特征，提出了解决这类问题的基 本原理。在研究、解决了某些实 际问题的基础上，他于1957年出 版了动态规划这一名著。本 章将简要介绍动态规划的思想方 法及其应用。 动态规划解决问题的基本思路是：把整体比较 复杂的大问题划分成一系列较易于解决的小问 题，通过逐个求解，最终取得整体最优解。这 种“分而治之，逐步调整”的方法，在一些比较 难以解决的复杂问题中已经显示出优越性。经 过半个世纪的发展，动态规划解决问题的方法 已经广泛应用于经济、管理、军事、生物、工 程等诸多领域，并取得了很好效果。 所谓多阶段决策过程是指这样一类活动过程： 一个决策过程可以分为若干个相互联系的阶段 ，每个阶段都需要作一定的决策，但是每个阶 段最优决策的选择不能只是孤立地考虑本阶段 所取得的效果如何，必须把整个过程中的各个 阶段联系起来考虑，要求所选择的各个阶段决 策的集合策略，能使整个过程的总效果达 到最优。 3.1 最短路径问题 3.1 最短路径问题 【例3.1】设在E城的某公司要从S城运送一批 货物，两城之间有公路相连（见图3. 1(a)）， 其中 是可以供选择的 途经站点，各点连线上的数字表示相邻站点间 的距离。现在的问题是选择一条由S到E的路径 ，使得所经过的路径最短。 3.1 最短路径问题 (a) (b) 3.1 最短路径问题 分析：如果用枚举法，将有12条不同的路径， 每条路径对应一个由到的路径距离，其中最小 值所对应的路径即为最短路径。本问题的最短 路径有3条，路程均为21个单位： 第1条： 第2条： 第3条： 3.1 最短路径问题 当段数很多时，枚举法的计算量将极其庞大。 现在换个思路，寻找由S到E的最短路径。先把 最短路径问题所考虑的过程分为4个阶段： 由S到 为第1阶段； 由 到 为第2阶段； 由 到E为第4阶段。 由 到 为第3阶段； 3.1 最短路径问题 我们称由某点到终点的阶段数k为阶段变量， 如由 到E的阶段数为1（这时记由C到E 的阶段数为1，它与第1阶段是不同的概念）， 到E的阶段数为2（这时记由B到E的阶 段数为2），等等。可见阶段变量的取值正好 与实际进行的阶段相反（图（b）。 3.1 最短路径问题 在任一阶段开始时所处的位置称为状态变量， 在阶段k的状态变量记为 ，例如 为阶段3的 状态变量，可以取为 中任意一个。 当某一个状态给定后，需要做出决策以确定下 一步的状态，描述决策的变量称为决策变量， 在阶段k的决策变量记为 。例如在阶段2的状 态取 时的决策变量记为 ， 可取 为 。若 ，则表示由 到 ，从而 决定了下一步的状态是 。 3.1 最短路径问题 为了寻找由起点S到E终点的最短路径，我们考 察前面用枚举法找到的第1条最短路径： 容易看出：子路径“ ”也应是 从 出发到终点E的所有路径中最短的一条。 这个现象启发我们从阶段1开始，逐段逆向地 求出各点到终点E的最短路径，最后求得由起 点S到终点E的最短路径，这就是动态规划的基 本思想。 3.1 最短路径问题 以 表示在阶段k的状态变量为 、决策变 量为 时点 与 间的距离；记 为在 阶段k由点 到终点E的最短路径的长度。本例中要 求的是 。 在阶段1： 可以取 中任意一个，对应的有 在阶段2： 可以取 中任意一个，对应的有 3.1 最短路径问题 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”， 决策变量 ； 在阶段3： 可以取 中任意一个，对应 的有 3.1 最短路径问题 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”， 决策变量 或 ； 最后，在阶段4： 只可以取S，于是 3.1 最短路径问题 因此，由起点S到终点E的最短路径为 最短路径长度为21单位长度。 3.1 最短路径问题 由上述计算过程可知，对有n个阶段的最短路 径问题，可以逐段逆向地求出各点到终点的最 短路径，且在求解的每一步都利用阶段k和阶 段k-1间的递推关系： 此关系被称为求最短路径的动态规划基本方程 。求解最短路径问题的过程，本质上是解上述 基本方程的过程。 3.1 最短路径问题 本节学习要点 1.通过实例，了解什么是动态规划，了解动态规划在 管理中的几类应用例子 2.动态规划数学模型的组成及其特征 3.掌握求最短路径的动态规划基本方程 3.2 贝尔曼最优化原理 3.2 贝尔曼最优化原理 将求解最短路径问题的思路推广到一般多阶段 决策问题时，可以表述成： 贝尔曼最优化原理：一个过程的最优策略具有 这样的性质，即无论其初始状态和初始决策如 何，今后的诸决策，对以第一个决策所形成的 状态作为初始状态的过程而言，必须构成最优 策略。 这个原理是动态规划的理论基础。 3.2 贝尔曼最优化原理 应用动态规划方法解决一般多阶段决策问题时，其求 解过程如下： （1）把实际问题适当地划分成k个阶段，阶段变量为 ； （2）在每个阶段k，确定状态变量 为及此阶段可 能的状态集合 ； （3）确定决策变量 及每个阶段k的允许决策集 合 ； （4）列出递推关系即动态规划基本方程并计算： 3.2 贝尔曼最优化原理 【例3.2】（石油输送管道铺设优选问题）某石 油公司计划从A地到E地铺设一条石油输送管 道，为此在A地与E地之间必须建立三个油泵 加压站，如图3.2所示， 其中 分别为必 须建站的地区，而 分别为 可供选择的各站点，各点连线上的数字表示相 邻站点间铺设输送管道所需费用. 问：如何铺 设石油输送管道，能使总费用最少？ 3.2 贝尔曼最优化原理 (a) (b) 3.2 贝尔曼最优化原理 解 划分成4个阶段： 阶 段变量依次为4，3，2，1，如图3.2所示. 设阶 段k的状态变量为 。 在阶段1： 在阶段2： 可以取 中任意一个，对 应的有 3.2 贝尔曼最优化原理 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”， 决策变量 ； 3.2 贝尔曼最优化原理 在阶段3： 可以取 中任意一个 ，于是 3.2 贝尔曼最优化原理 从 出发到终点E最短路径为“ ”或 决策变量 或 ； 从 出发到终点E最短路径为“ ”， 决策变量 ； 从 出发到终点E最短路径为“ ”或 决策变量 或 ； 在阶段4： 3.2 贝尔曼最优化原理 因此，由起点A到终点E的费用最少路径有3条 ： 此3条路径对应的总费用均为11单位金额。 3.2 贝尔曼最优化原理 动态规划为我们提供了一种优秀的决策思想： 战略上追求全局优化，战术上稳扎稳打、步步 为营。这深刻地揭示了局部与全局的统一关系 。动态规划在实际中得到广泛应用，如可应用 于背包问题、资源分配问题、生产与存储问题 、设备更新问题等。 需要指出的是：动态规划是一种求解思路，注 重决策过程，而不是一种算法，不同的问题模 型各异。 3.2 贝尔曼最优化原理 本节学习要点 了解贝尔曼最优化原理. 掌握动态规划的决策思想：战略上追求全局优化，战 术上稳扎稳打、步步为营. 注意动态规划是一种求解思路，注重决策过程，而不 是一种算法，不同的问题模型各异. 3.3 WinQSB软件应用 本节结合最短路径问题、背包问题介绍WinQSB软件 的应用，其他问题的求解可参考本章参考文献. 求解动态规划问题，需要调用WinQSB软件中的子程 序“Dynamic Programming”. 方法：点击“开始”“程序 ”“WinQSB”“Dynamic Programming”,屏幕显示如图3.3 所示. 该程序有3个子模块：最短路问题（Stagecoach Problem）,背包问题（Knapsack Problem）,生产与存 储问题（Production and Inventory Scheduling）. 3.3 WinQSB软件应用 3.3 WinQSB软件应用 点击 1.最短路问题 【例3.3】用WinQSB软件求解例3.1. 解（1）调用WinQSB软件中的子程序“Dynamic Programming”， 建立新问题. 在图3.3中选择第一项，输入标题和站点数. （2）输入数据. 按照图3.1从左到右将相邻站点间的距离输入表 3.1中，其中 表示图3.1中从左到右第k 个站点，k=1,2,9 表3.1 3.3 WinQSB软件应用 （3）求解.点击菜单栏“Solve and Analyze” “Solve the Problem”,得到图3.4. 再点击“Solve”键，得到计算结果，见表 3.2. 可见由起点到终点的最短路径为 3.3 WinQSB软件应用 表 3.2 3.3 WinQSB软件应用 2. 背包问题 背包问题的一般提法是：设有一位旅行者携带背包去登山，已 知他所能承受的背包质量为a （单位：kg）， 种物品可供他选择选择 装入背包，其中 第 种物品的重量为为 （单单位：kg），其价值值（可以是表明该该物品对对登山的重要性 的函数 为为第种物品单单 问问：旅行者应应如何选择选择 携带带各物品的件数，以使总总价值值最大？ 背包问题问题 等同于车车、船、飞飞机、潜艇、人造卫卫星等工具的最 优优装载问题载问题 ，有广泛的实际实际 意义义. 现有n 的数量指标）是携带数量 位数量的价值， ). 3.3 WinQSB软件应用 【例3.4】已知1T的集装箱最大载重量为800kg.现有5种物品 各10件可供选择装箱，其中单位物品重量、价值见表3.3. 求 价值最大的装载方案. 表3.3 解 (1)调用WinQSB软件中子程序“Dynamic Programming” 建立新问题：在图3.3中选择第二项，输入标题和物品品种数 5，见图3.5. 3.3 WinQSB软件应用 （2）按表3.4形式输入数 据：第1列为物品名称，第 2列为物品限量及集装箱最 大载重量，第3列为单位物 品重量，第4列为物品价值 函数. 注：物品的数量仍用a,b,c,d,e表示. 3.3 WinQSB软件应用 表 3.4 3.3 WinQSB软件应用 （3）求解: 点击菜单栏“Solve and Analyze” “Solve the Problem”,得到表3.5. 由此表可见，