章动态规划.doc

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