运筹学(二)——动态的规划(1-2014).ppt

运筹学（二） ——动态规划 动态规划 动态规划是运筹学的一个分支，它是解决多阶段决策问题的一种数学方法。大约产生于上个世纪50年代， 已广泛的应用于工程技术、工农业生产以及军事等部门，并获得了显著的效果，尤其是在企业管理决策方面。 动态规划 在企业管理方面，动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制等问题，是现代企业管理中一种重要的决策方法。 主要内容 动态规划（1） ——动态规划基本原理与方法 动态规划（2） ——动态规划应用举例 运筹学（二） ——动态规划（1） 动态规划基本原理与方法 主要内容 1. 多阶段决策过程及实例 2. 动态规划基本概念 3. 动态规划基本原理 4. 动态规划与其它方法的比较 5. 动态规划的理论基础 6. 动态规划的具体解法 1. 多阶段决策过程与实例 在生产实践和科学实验中，存在这样一类活动过程：其过程分为若干个互相联系的阶段，在每一个阶段都需要作出决策，目的是使整个过程达到最好的活动效果。 示例1 例1 最短路线问题——给定一个线路网络，两点之间连线上的数字表示两点间的距离(或费用)，试求一条由A到G的铺管线路，使总距离为最短(或总费用最小)。 最短路线问题示意图 最短路线问题示意图 在最短线路问题中，各个阶段决策的选取不是任意确定的，它既依赖于当前所处的位置（或状态），又影响以后的决策（或发展）。当各个阶段决策确定后，就组成了一个决策序列，因而也就决定了整个过程的一条活动路线。 示例2 例2 机器负荷分配问题——某种机器可以在高低两种不同的负荷下进行生产。在高负荷下进行生产时，产品的年产量g和投入生产的机器数量u1的关系为 g=g(u1) 这时，机器的年完好率为a，即如果年初投入高负荷状态生产的完好机器数量为u，到年终时完好的机器就为au，其中0＜a＜1； 在低负荷下生产时，产品的年产量h和投入生产的机器数量u2的关系为 h=h(u2) 相应的机器年完好率为b，其中0＜b＜1。 假定开始生产时，完好的机器数量为s1。要求制定一个五年计划，在每年开始时，决定如何重新分配完好的机器在两种不同的负荷下生产的数量，使在五年内产品的总产量达到最高。 多阶段决策过程示意图 从决策的角度来看，上述前后关联具有链状结构的多阶段过程就称为多阶段决策过程，也称序贯决策过程。这种问题就称为多阶段决策问题。 在多阶段决策问题中，各个阶段采取的决策，一般来说与时间有关，决策依赖于当前的状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义。 但是，一些与时间没有关系的静态规划（如线性规划、非线性规划等）问题，只要人为地引进“时间”因素，也可以把它视为多阶段决策问题，用动态规划的方法去处理。 2. 动态规划基本概念 下面结合最短路线问题，对动态规划所涉及到的基本概念进行说明。 在最短路线问题中，从A点到G点可以分为6个阶段，是一个6阶段的多阶段决策问题。其目的是：在各个阶段上选择一个恰当的决策，使得由这些决策组成的一个决策序列所决定的一条路线是总路程最短的一条。 最短路线问题示意图 动态规划问题涉及到的基本概念主要有：阶段、状态、决策、策略、状态转移方程和指标函数（以及最优值函数）。 阶段 1）阶段 将所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。 描述阶段的变量称为阶段变量，常用k表示。 阶段 阶段的划分，一般是根据时间和空间的自然特征来划分，但要便于把问题的过程能转化为多阶段决策的过程。如例1可分为6个阶段来求解，k分别等于1、2、3、4、5、6。 阶段 最短路线问题中“阶段”的示意图 状态 2）状态 状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素。 状态 在例1中，状态就是某阶段的出发位置。它既是该阶段某支路的起点，又