第四章动态规划 §1引言 1.1动态规划的发展及研究内容 动态规划( dynamic programming)是运筹学的一个分支,是求解多阶段决策问题 的最优化方法。20世纪50年代初R.E. Bellman等人在研究多阶段决策过程 multistep decision process)的优化问题时,提出了著名的最优性原理( principle of optimality),把 多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方 法一动态规划。1957年出版了他的名著《 Dynamic Programming》,这是该领域的第 本著作。 动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时 间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为 多阶段决策过程,也可以用动态规划方法方便地求解 应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是 种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习 时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的 技巧去求解 例1最短路线问题 下面是一个线路网,连线上的数字表示两点之间的距离(或费用)。试寻求一条由A 到G距离最短(或费用最省)的路线 ,Lc 例2生产计划问题 工厂生产某种产品,每单位(千件)的成本为1(千元),每次开工的固定成本为3 (千元),工厂每季度的最大生产能力为6(千件)。经调查,市场对该产品的需求量第 二、三、四季度分别为2,3,2,4(千件)。如果工厂在第一、二季度将全年的需 求都生产出来,自然可以降低成本(少付固定成本费),但是对于第三、四季度才能上 市的产品需付存储费,每季每千件的存储费为0.5(千元)。还规定年初和年末这种产品 均无库存。试制定一个生产计划,即安排每个季度的产量,使一年的总费用(生产成本 和存储费)最少 12决策过程的分类 根据过程的时间变量是离散的还是连续的,分为离散时间决策过程( discrete-time decision process)和连续时间决策过程( continuous-time decision process);根据过程的 演变是确定的还是随机的,分为确定性决策过程( deterministic decision process)和随-35- 第四章 动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解多阶段决策问题 的最优化方法。20 世纪 50 年代初 R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把 多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方 法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一 本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广 泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动 态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时 间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为 多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是 一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数 学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习 时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的 技巧去求解。 例 1 最短路线问题 下面是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由 A 到 G 距离最短（或费用最省）的路线。 例 2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为 1（千元），每次开工的固定成本为 3 （千元），工厂每季度的最大生产能力为 6（千件）。经调查，市场对该产品的需求量第 一、二、三、四季度分别为 2，3，2，4（千件）。如果工厂在第一、二季度将全年的需 求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上 市的产品需付存储费，每季每千件的存储费为 0.5（千元）。还规定年初和年末这种产品 均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本 和存储费）最少。 1.2 决策过程的分类 根据过程的时间变量是离散的还是连续的，分为离散时间决策过程（discrete-time decision process）和连续时间决策过程（continuous-time decision process）；根据过程的 演变是确定的还是随机的，分为确定性决策过程（deterministic decision process）和随