文档介绍：动态规划§(dynamicprogramming)是运筹学的一个分支,是求解多阶段决策问题的最优化方法。(multistepdecisionprocess)的优化问题时,提出了著名的最优性原理(principleofoptimality),把多阶段过程转化为一系列单阶段问题,逐个求解,创立了解决这类过程优化问题的新方法—动态规划。1957年出版了他的名著《DynamicProgramming》,这是该领域的第一本著作。动态规划问世以来,在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题,用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题,但是一些与时间无关的静态规划(如线性规划、非线性规划),只要人为地引进时间因素,把它视为多阶段决策过程,也可以用动态规划方法方便地求解。应指出,动态规划是求解某类问题的一种方法,是考察问题的一种途径,而不是一种特殊算法(如线性规划是一种算法)。因而,它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则,而必须对具体问题进行具体分析处理。因此,在学习时,除了要对基本概念和方法正确理解外,应以丰富的想象力去建立模型,用创造性的技巧去求解。例1最短路线问题下面是一个线路网,连线上的数字表示两点之间的距离(或费用)。试寻求一条由到距离最短(或费用最省)的路线。例2生产计划问题工厂生产某种产品,每单位(千件)的成本为1(千元),每次开工的固定成本为3(千元),工厂每季度的最大生产能力为6(千件)。经调查,市场对该产品的需求量第一、二、三、四季度分别为2,3,2,4(千件)。如果工厂在第一、二季度将全年的需求都生产出来,自然可以降低成本(少付固定成本费),但是对于第三、四季度才能上市的产品需付存储费,(千元)。还规定年初和年末这种产品均无库存。试制定一个生产计划,即安排每个季度的产量,使一年的总费用(生产成本和存储费)最少。,分为离散时间决策过程(discrete-timedecisionprocess)和连续时间决策过程(continuous-timedecisionprocess);根据过程的演变是确定的还是随机的,分为确定性决策过程(deterministicdecisionprocess)和随机性决策过程(stochasticdecisionprocess),其中应用最广的是确定性多阶段决策过程。§2基本概念、。(step)是对整个过程的自然划分。通常根据时间顺序或空间顺序特征来划分阶段,以便按阶段的次序解优化问题。阶段变量一般用表示。在例1中由出发为,由出发为,依此下去从出发为,共个阶段。在例2中按照第一、二、三、四季度分为,共四个阶段。(state)表示每个阶段开始时过程所处的自然状况。它应能描述过程的特征并且无后效性,即当某阶段的状态变量给定时,这个阶段以后