管理运筹学第08章动态规划

1、管理运筹学第8章 动态规划 动态规划(DYnamic Programming，缩写为DP)方法，是本世纪50年代初期由美国数学家贝尔曼(Richard E，Bellman)等人提出，后来逐渐发展起来的数学分支，它是一种解决多阶段决策过程最优化问题的数学规划法。动态规划的数学模型和求解方法比较灵活，对于连续的或离散的，线性的或非线性的，确定性的或随机性的模型，只要能构成多阶段决策过程，便可用动态规划方法求其最优解。因而在自然科学、社会科学、工程技术等许多领域具有广泛的用途，甚至一定程度上比线性规划（LP）、非线性规划（NLP）有成效，特别是对于某些离散型问题，解析数学无法适用，动态规划方法就成为

2、非常有用的求解工具。第8章 动态规划 为了便于说明动态规划方法的基本思想，先通过一个经典问题作为开篇，用来引入一些相关的基本概念。 如下面的一种最常见的最短路径问题： 【例8-1】 给定一个线路网络（如图8-1），两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到E的铺管线路，使总距离为最短（或总费用最小）。 8.1 动态规划基础知识8.1.1动态规划模型的分类动态规划是一种解决多阶段决策问题最优化的一种方法。动态规划模型根据多阶段决策过程的时间参量是离散还是连选的变量，可以将过程分为离散的决策过程和连续的决策过程。根据决策过程的演变是确定性的还是随机性的，过程又可分为确定性决策过

3、程和随机性决策过程。组合起来就有离散确定性、离散随机性、连续确定性和连续随机性四种决策过程模型。其关系如图8-2所示：8.1 动态规划基础知识8.1 动态规划基础知识8.1.2 动态规划的基本概念（1）阶段：把所给问题的过程，恰当地分为若干个相互联系的阶段，以便能按一定的次序去求解。阶段可以按时间或空间划分，常用字母k表示阶段变量。例8-1的问题中从A到E可以分成四个阶段，它们分别是从A到B，B到C，C到D，D到E。其阶段变量k为1，2，3，4,如图8-3所示：8.1 动态规划基础知识（2）状态：状态表示每个阶段开始所处的自然状况或客观条件，它描述了研究问题过程的状况，又称不可控因素。在例8-

4、1的问题中状态就是某阶段的出发位置，它及时该阶段的某支路的起点，又是前一阶段某支路的终点。状态可以是数量，也可以是字符。描述各阶段状态的变量称为状态变量，常用 表示第k阶段的状态变量。状态变量 的取值集合称为状态集合，用 表示。8.1 动态规划基础知识（3）决策：决策表示当过程处于某一阶段的某个状态时，所做出的不同的决定（或选择），常用 表示第k阶段且状态为 时的决策变量。其中 表示在第k阶段时某一状态，如 中的一个。称决策变量的取值范围为允许决策集合，并用 表示第k阶段从状态 出发的允许决策集合，显然有 。如问题1从第三阶段的状态C1出发，可选择下一阶段的D1和D2，其允许决策集合为： 如果

5、选择D2，则可表示为 8.1 动态规划基础知识（4）策略：策略是一个按顺序的决策组成的集合，由过程的第k阶段开始到终止状态为止的过程，称为问题的后部子过程（或称为k子过程）。各阶段决策确定后，整个问题的决策序列就构成一个策略，用 表示。对策略的选择范围称为允许策略集合，记作 ，其中 称为k子过程策略，简称子策略。是1到n阶段可以使整个问题达到最优的策略就是最优策略。动态规划的目的就是在允许策略集合中选最优策略。8.1 动态规划基础知识（5）状态转移方程：状态转移方程是确定过程由一个状态转移到另一个状态的演变过程。动态规划中某一状态以及该状态下的决策，与下一状态之间具有一定的函数关系，称这种函数

6、关系的表达式为状态转移方程。如果第k段的状态为 ，该阶段的决策为 ，则第k+1段的状态就可以用下式来表示：由于该式表示了不同状态之间的转移规律，所以称之为状态转移方程。问题1中的状态转移方程为 8.1 动态规划基础知识（6）指标函数：指标函数是用于衡量所选定策略优劣的数量指标。对于从第k段到第n段的过程，当第k段的状态为 ，采用策略为 时，这一过程的指标函数表示为 。常见的指标函数的形式有两种：指标和形式：其中 表示第j阶段的阶段指标。指标积形式：8.1 动态规划基础知识（7）最优值函数：指标函数的最优值，称为最优值函数。其最优值函数根据问题的不同，取指标函数的最小值或最大值。如对于从第k 段

7、的状态 ，采用最优策略 到过程终止时的指标函数，用 来表示，并称之为最优指标函数。当第n段为决策过程的终止时， 和 的关系如下： = = = ，即某阶段的最优值函数属于该阶段的指标函数，是该阶段最优的指标函数。8.2 动态规划模型建立建立动态规划模型，就是在分析实际问题的基础上建立该问题的动态规划基本方程。成功地应用动态规划方法的关键，在于识别问题的多阶段特征，将问题分解成为可用递推关系式联系起来的若干子问题，或者说正确地建立具体问题的基本方程，这需要经验与技巧。而正确建立基本递推关系方程的关键又在于正确选择状态变量，保证各阶段的状态变量具有递推的状态转移关系。在建立动态规划模型时，必须做到以

8、下几点关系：(1)将问题的过程划分成恰当的阶段；(2)正确选择转台变量 ，使它既能描述过程的演变，又要满足无后效性；(3)确定决策变量 及每阶段的允许决策集合 ；8.2 动态规划模型建立(4)正确写出状态转移方程；(5)正确写出指标函数 的关系，它应满足下面三个性质：是定义在全过程和所有后部子过程上的数量函数；要具有可分离性，并满足递推关系,即函数 对于变量 要严格单调。8.2 动态规划模型建立下面以投资问题为例介绍动态规划的建模条件。【例8-2】 某公司现有资金20万元，若投资于三个项目，每个项目的投资额为 ，各个项目的收益分别是 ， ， 问应如何分配投资额才能使总收益最大？解：一般情况下，

9、可以把上述问题看成是典型的非线性规划问题，且可以建立模型如下：8.2 动态规划模型建立动态规划问题的复杂性在于各阶段决策之间的相互联系。因此，在最优化原理的基础上，人们提出了用动态规划方法解决问题的基本思路：先将多阶段决策过程划分阶段，并恰当选取状态变量、决策变量和定义最优指标函数，从而将问题化成一族具有递推关系的单阶段的决策问题，然后从边界条件开始逐段递推寻优，最后一个阶段决策问题的最优解就是整个问题的最优解。动态规划方法是既把当前一段与未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法，因此 每段的最优决策是从全局考虑的，与该段的最优选择一般是不同的。8.3 动态规划模型的求

10、解现在结合本章开篇中所提及的例8-1中的最短路径来介绍动态规划的基本解法。【例8-4】给定一个线路网络（见图8-4），两点之间连线上的数字表示两点间的距离（或费用），试求一条由A到E的铺管线路，使总距离为最短（或总费用最小）。8.3 动态规划模型的求解计算过程及结果，可用图8-5表示，可以看到，以上方法不仅得到了从A到D的最短路径，同时，也得到了从图中任一点到E的最短路径。其中粗线条的为最短路径。8.3 动态规划模型的求解以上的求解过程，仅用了18次加法，11次比较，计算效率远高于穷举法。在上述例题的逆序解法中，由于寻优的方向与多阶段决策过程的实际行进方向相反，从最后一段开始计算逐段前推，求得

11、全过程的最优策略，称这种求解方法为逆序解法。与之相反，把寻优方向与多阶段决策过程的实际行进方向相同，计算时从第一段开始逐段向后递推，计算后一阶段要用到前一阶段的求优结果，把最后一段计算的结果作为全过程的最优结果的解法称为顺序解法。顺序解法与逆序解法是动态规划问题求解的两大基本方法。8.3 动态规划模型的求解通过以上的分析，可以将动态规划方法的基本思想归纳如下：（1）动态规划方法的关键在于正确地写出基本的递推关系和恰当的边界条件（简言之为基本方程）。（2）在多阶段决策过程中，动态规划方法是即把前一段和未来各段分开，又把当前效益和未来效益结合起来考虑的一种最优方法。因此，每段决策的选取是从全局来考

12、虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐次变换得到的，从而确定了最优路线。8.3 动态规划模型的求解设计动态规划法解题的步骤：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值（写出动态规划方程）；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造一个最优解。步骤1-3是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤4可以省略，步骤3中记录的信息也较少；若需要求出问题的一个最优解，则必须执行步骤4，步骤3中记录的信息必须足够多以便构

13、造最优解。8.3 动态规划模型的求解动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。（1）最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。（2）重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。8.4 动态规划应用动态规划的方法的应用广泛，尤其是在企业管理、工程等方面有广泛的运用，并获得了显著的效果。在企业管理方面，动态规划

14、可以用来解决：例如最短路线（问题1）、资源分配（问题2）、库存管理（问题3）、设备更新、排序、装载等一系列问题，用动态规划方法比用其它方法求解更为方便。本节就几个经典问题求解来作为代表来讲述动态规划的应用。8.4 动态规划应用8.4.1 资源分配问题【例8-5】 某公司现有资金20万元，若投资于三个项目，每个项目的投资额为 ，各个项目的收益分别是 ， ， 问应如何分配投资额才能使总收益最大？解：由于公司现有的资金为20万元，可以知投资的三个项目资金之和应该不超过20万，且每个项目的资金数 ，综合题意，可以得出以下方程： s.t 8.4动态规划应用下面分别用逆序和顺序两种方法来求解该问题。1.逆

15、序解状态转移方程： k=1,2,3基本方程：对这种初始状态 =10（万元）已知的资金分配问题，采用逆序法。图8-6 逆序解图示8.4动态规划应用1.顺序解状态转移方程： k=1,2,3最优指标函数 ：第k阶段，当投资额为 时，从第1到第k阶段所获得的最大收益。总的收益基本方程： 图8-7 顺序解图示8.4动态规划应用8.4.2 库存管理问题【例8-6】 某公司根据市场调查，今后四个月产品的需求量预测如表8-2所示:在满足市场需求条件下，公司需定出一个4个月的生产计划。目标：总费用（=生产+库存）最小8.4动态规划应用已知：生产费用C跟产量k （件）(最大生产能力为6件)的关系为 （单位：千元）

16、若产品销不掉，则库存费为Ek=E（k）=0.5k（千元）且最大库存容量为3，计划初与期末库存量为0。8.4动态规划应用解：下面用逆序法建立动态规划基本方程： （2）从递推式可看出： 。且 8.5 动态规划算法简介及excel软件实现8.5.1 动态规划算法简介动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。（1）最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构性质，即满足最优化原理。（2）子问题重叠性质。子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算

17、多次。8.5 动态规划算法简介及excel软件实现8.5.2 动态规划的EXCEL建模与实现1.库存问题【例8-7】 某品牌车床生产商根据去年的市场需分析来预测明年的市场需求：一季度2 000台，二季度4 000台，三季度9 000台，四季度7 000台，现在企业每季度最多能生产6 000台，为了满足所有的预测需求，前两个季度必须要有一定的库存才能满足后两个季度的需要。已知每台车床的利润为400元，每个季度的库存成本是100元，请对公司明年的生产库存计划，使得公司的年利润最大。8.5 动态规划算法简介及excel软件实现其电子表格模型求解如下所示：（1）在Excel表格中填入已知数据，如表8-

18、7所示。8.5 动态规划算法简介及excel软件实现（2）设置目标、约束条件、自变量等关系，并设置相关公式之后然后按下solve，如图8-12所示。图8-12 设置参数8.5 动态规划算法简介及excel软件实现（3）选择保存结果，如图8-13所示。图8-13 保存结果8.5 动态规划算法简介及excel软件实现（4）最优解（见表8-8中绿色部分）8.5 动态规划算法简介及excel软件实现【例8-8】 某毛毯厂是一个小型的生产商，致力于生产家用和办公用的地毯。紧接的四个季度的生产能力、市场需求、每平方米的生产成本以及库存成本如表8-9所示。毛毯厂需要确定在这四个季度里每季度生产多少地毯，才能

19、使总生产和库存成本最小。8.5 动态规划算法简介及excel软件实现这里介绍另外一种解法，即用网络最优化问题中的最小费用流问题来求解。通过建立一个网络图来代表这个问题。首先根据四个季度建立四个产量节点和四个需求节点，每个产量节点由一个流出弧连接对应的需求节点。弧的流量代表了 该季度所生产的地毯数量。相对于每个需求节点，一个流出弧代表了库存的数量，即供给下季度需求节点的数量。图8-14显示了这个网络模型。图 8-14 最小费用流求解网络模型8.5 动态规划算法简介及excel软件实现其电子表格模型求解如下所示：（1）把已知条件填入Excel表格，如表8-10所示。8.5 动态规划算法简介及exc

20、el软件实现（2）设置目标、约束条件、自变量与因变量的关系等，并设置相关公式之后然后按下solve，如图8-16。图8-16 设置参数8.5 动态规划算法简介及excel软件实现（3）保存结果，按下OK，如图8-17所示。图8-17 保存结果8.5 动态规划算法简介及excel软件实现（4）得出结果，如表8-11所示。 表8-11 求解步骤及结果8.5 动态规划算法简介及excel软件实现2.资金管理问题某公司为了盘活市场，打算向银行贷款来开展更多的业务，现有两种不同的贷款方式:第一种是10年长期贷款，年利率7%，只能在2006年初贷1次，以后每年还息(10次) ，第10年后还本；第二种是1年短期贷款年利率10%，可以在20062015年初贷，可贷10次，下一年还本付息。应