运筹学教案(动态规划）.ppt

运筹学教案动态规划陈安明概述?动态规划为运筹学的一个分支,是用于求解多个阶段决策过程的最优化数学方法。?理论基础: 美国数学家贝尔曼( Richard Bellman) 研究提出的最优化原理( Principle of Decision) 把多阶段过程转化为一系列单阶段问题,逐个求解,创立一类求解多阶段过程优化问题的方法——动态规划( Dynamic Programming) ?动态规划的应用领域经济管理、工程技术、工农业生产及军事部门。具体讲:如最短路线,资源分配,库存管理,生产调度,排序,装载,市场营销, 设备维修与更新等方面。?主要解决时序或空间序阶段划分的多阶段问题。但对一些与时间甚至与空间都无关的静态问题,在引入特殊序之后用动态规划方法处理。多阶段决策过程及实例?多阶段决策问题举例从A地经 B、C、D、E到F地铺设管线, 问,怎样铺设,可使管线最短? A B 1B 2B 3 C 1C 2C 3 D 1D 2D 3 E 1E 2F 354 9543517 15846442 2 26975 1 4 若用穷举法求解,计算量大,且容易遗漏某一路径。本例可将其划分为五个阶段,用动态规划原理求其最短路径。思路: 从A站出发应经过哪些站点到 F站的总长度最短?若已作出从 A? Bi中之一决策,之后的问题变为,从各 Bi站点经哪些站点到 F点的总长度最短, 仍为一多阶段决策问题,与前一问题相似,解决方法也相似,只是少了一个阶段,问题变小了,若后一问题解决了,则前一问题也解决了。类似地,到了 C站、 D站、 E站,都面临同一问题,只是问题越来越小并易于解决。到了 E站,从其各点到 F的最短距离已易得, 再逆推,可求出 D站各点到 F点的最短距离,逐次逆推,到最后可以求出 A点到 F点的最短距离。这就是动态规划问题逆推算法。动态规划问题其它例子,见 P193 机器负荷问题。动态规划问题的基本概念以前述求最短路为例说明动态规划问题中概念。?阶段与阶段变量决策:处理问题时,从多个方案中作出的一某种选择。阶段:为解决复杂问题而把一个过程划分为若干个相互区别又相互联系的部分。一般地,一个决策可从一个阶段变到另一阶段。阶段的划分依据: 阶段一般是根据,( 1)时间( 2)空间等自然特征来划分。( 3)也可以是其他人为方式。阶段变量: 描述阶段的变量,一般用 k表示。为离散变量, 取值 1,2….n分别表示 1,2 …n阶段。 A B 1B 2B 3 C 1C 2C 3 D 1D 2D 3 E 1E 2F 354 9543517 15846442 2 26975 1 4 1 阶段 2 阶段 3 阶段 4 阶段 5 阶段§状态与状态变量状态: 表示每个阶段开始时所处的自然状况或客观条件,又称为不可控因素,是阶段的特征,通常一个阶段有若干个状态。如:前例,第一阶段状态为点 A, 第二阶段的状态有 B1,B2,B3三个状态。状态变量: 描述过程状态的变量称为,一般用x k表示第 k个阶段的状态变量。状态集: k 阶段所有可能状态构成的集合。记为 Sk,如 S2={B1,B2,B3} 状态的无后效性: 即当某阶段的状态一旦确定,则此后过程的演变不再受此前各状态和决策的影响, 或者说“未来与过去无关”。即由状态 x k出发的后部子过程可以看成一个以 x k为初始状态的独立过程。注: 阶段的划分与状态的选择要具有此性质, 是动态规划问题的特点。?决策与决策变量决策: 使在 k阶段,使状态从 x k到x k+1发生转移的选择。决策变量:描述决策的变量称为决策变量,一般用 u k表示第 k个阶段的决策变量。