运筹学第五章动态规划.ppt

《运筹学第五章动态规划.ppt》由会员分享，可在线阅读，更多相关《运筹学第五章动态规划.ppt（48页珍藏版）》请在三一办公上搜索。

1、第五章 动态规划,动态规划简介,动态规划所解决的问题：多阶段问题,动态规划的核心。,动态规划的应用。,动态规划的优缺点。,核心:在于将问题公式化，也可以说，动态规划是将多阶段决策问题进行公式化的一种技术。,应用:工程、军事和商业等领域,优缺点:适用范围广，模型算法一体化，方便编程。一方面是大量的中间计算结果要求记录，造成对内存的较大需求；另一方面是由于没有统一的标准模型，使得动态规划的应用难度增加。,在现实中，我们经常会碰到需要做前后相互关联的具有链状结构的多次决策才可以解决的问题，也经常会遇到一些经过巧妙设计后可以转化为具有上述多次决策特点而得以解决的问题，我们称这样的问题为多阶段决策问题。

2、,例如，许多工程项目都能根据工程进度或者空间位置等，被分解成相应于整个事件的多个阶段来进行计划；许多涉及到要求回报最大的资金投入问题，都能通过将不同的投资方案表示成不同阶段的方式进行规划；也有一些静态规划(如线性规划、非线性规划等)在人为引入“时间”因素后，可以转化为多阶段决策的问题，而解决这些问题的最常用的就是动态规划方法。,返回,图5.1 例5.1示图,5.1 动态规划的基本概念和模型,5.1.1 动态规划的基本概念 下面结合实例来介绍动态规划的基本概念：【例5.1】如图5.1所示，在处有一水库，现需从点铺设一条管道到点，弧上的数字表示与其相连的两个地点之间所需修建的渠道长度，请找出一条由

3、到的修建线路，使得所需修建的渠道长度最短。,【例5.2】未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为1000件，每月中旬定购商品，并于下月初取到订货。据估计：今后四个月这种商品的购价和售价，如表5-1所示。假定商品在第一个月初开始经销时仓库已经存有该种商品500件，每月市场不限，问：应如何计划每个月的订购与销售数量，使这四个月的总利润最大(不考虑仓库的存储费用)？,记作：,动态规划基本概念,1.阶段与阶段变量,2.状态与状态变量,3.决策与决策变量,5.状态转移方程,4.策略,记作：,记作：,记作：,记作：,记作：,，,允许决策集,6.指标函数与最优函数,阶段是针对所给的问题，依

4、据其若干个相互联系的不同部分，给出的对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解决优化问题。从数学角度看，我们引入了一个变量来表示阶段，通常称为阶段变量，记作：。如果将整个问题分成了 个阶段，则。如例5.1中，在从 到 的过程中，依据按位置所作决策的次数及所作决策的先后次序，将问题分为4个阶段，记为；。例5.2中，在从第一个月到第四个月的整个经销过程中，依据按月所作决策的次数及所作决策的先后次序，将问题分为4个阶段，记为：。,返回,返回,后，作决策，就是在相应的允许决策集内确定一组，值，其结果是确定了下一阶段的状态，即仓库的库存量。,在例5.1中，作决策，就是

5、在所处位置选择下一步应遵循的路线，比如在状态 处作决策，就是从 中选取一条路线，此时如果再假设选取了路线，那么决策者在 处所作决策就是，即就是，而状态 处允许决策集就是，其结果是确定了下一阶段的状态。在例5.2中，作决策，就是在当前第 阶段库存量为 的情况下，决定当月的定购量和销售量，在依次引入决策变量，和与其相应的允许决策集,返回,后部子策略，简称为 子策略，记作,即,。,把从第一阶段 状态开始的子策略称为全策略，简称策略，记作，即,如例5.1中，为从起始状态 开始的一个全策略，为从第3阶段状态 开始的一个3子策略。在例5.2中，每个阶段既不订购也不销售，即，或 为从起始状态 开始的一个全策

6、略，为第2阶段 状态开始的一个2子策略。,在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用 表示。而把允许策略集合中达到最优效果的策略称为最优策略。,返回,例5.2中，在第二阶段状态 下作了决策 和 后，则当转移到第三阶段时，状态便已确定为。,状态转移描述了相邻阶段的状态与状态之间的关联关系。我们称这一关联关系的数学描述为状态转移方程。通常我们把描述第 阶段状态 到第 阶段的状态 转移规律的函数记作：。,同时对第 阶段的状态，一旦前一阶段达到 的决策变量取定，则第 阶段状态 也可以反推出来。我们把这一状态转移的过程用函数描述，记作：，,它表示若在从第 阶段到达第 阶段状态

7、的过程中作的决策是，则第 阶段起始状态为。,通常在第 阶段某确定的状态 下，一旦决策变量 取定，则第 阶段的状态 也就确定，我们将这一过程称为状态转移。,如例5.1中，在第二阶段状态 下作决策 后，则当转移到第三阶段时，状态便已确定为；,返回,把衡量某一阶段决策效果的数量指标，称为阶段指标，记作：。指标可以是距离、利润、成本、产量和资源消耗等。通俗地讲，就是某一阶段决策对目标的贡献。,通俗地讲，就是 子策略对目标的贡献。通常指标函数与阶段指标应具有下述关系：其中 依具体情况而定，一般表示加法或乘法。指标函数的最优值，称为最优值函数，记为。即：,把衡量所实现的子策略优劣的数量指标称为指标函数，记

8、作,在例5.2中，,其中 依具体情况取 或。它表示在从第 阶段的状态 开始到第 阶段的终止状态 的允许策略集中，采用 最优子策略所得到的指标函数值。,如例5.1中，,(5-1),类似有前部 子策略的指标函数和最优函数与全策略的指标函数和最优值函数，依次如下：,，,；,，,。,返回,5.1.2 动态规划的模型,一般地，动态规划模型包括节(1)至(6)中所提到的诸要素。很显然，要建立动态规划问题的模型，一般可按以下步骤来进行：,(1)把问题的过程划分为恰当的个 阶段，引入阶段变量；,(2)正确选择状态变量，使它既能描述过程的演变，又能满足无后效性，同时给出状态可能集；,(3)确定决策变量 及每个阶

9、段的允许决策集；,(6)写出最优函数。,(4)写出状态转移方程；,(5)指出阶段指标及指标函数；,5.2 动态规划的原理与求解,5.2.1 动态规划的最优化原理,下面我们先研究一下例5.1这个特殊问题的求解。最短路线问题有一个重要特性：如图,有,在引入一个虚拟的第五阶段后，可将第五阶段到第五阶段的指标记为，上述过程则可以用一个带有初始条件 的递推公式来完全描述：,显然从 开始，有,当 时,当 时,；,；,；,(5-2),当 时，,当 时，,可以求得 的最短距离12，然后根据计算过程中的记录，反向追踪可求得最短路线，最短路线为,或,，,，,，,；,；,。,，,。,。,注：而事实上，从各点到 的最

10、短路线和最短路线距离都求出来了。,动态规划最优性原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必然构成最优策略。”,将动态规划最优性原理应用于一般的多阶段问题求解即可得到类似(5-2)的递推公式,(5-3),5.2.2 动态规划的逆序解法,下面以例5.2的求解为例，加深我们对这种方法的理解。,解 由中所述，例5.2中问题的模型如下：,表示第 个月月初的库存量；,表示第 个月已有库存 的情况下，要定购的商品量，表示第 个月已有库存 的情况下，要销售的商品量(为方便，后面将分别依次用，来代替和)；,(2)状态变量：,(1)按月份

11、分段：,；,(3)决策变量：,状态转移方程：,(4)允许决策集：,(5)阶段指标：,其中 表示第四阶段末的状态；,(6)动态规划基本方程：,求解（要求板书）,辅图1,辅图2,辅图3,图5.2 图解法辅图1,返回,最优点,图5.2 图解法辅图,返回,最优点,图5.2 图解法辅图 2,返回,最优点,5.2.3 动态规划的顺序解法,【例5.3】图5.3所示为一水利网络，为水库，分别为不同的供水目的地，试找出给各供水目的地供水的最短路线。,图5.3 例5.3示图,（模型及其求解见板书）,5.2.4 逆序解法与顺序解法的关系,从本质上讲，两种方法原理(除去其方向因素外)是相同的，在具体的求解过程中，也都

12、是将原问题转化为一系列单个问题的求解。但是，两种方法各有优势，如前向法求解例5.3时，有明显的优势。一般的，当初始状态给定时，用逆推法比较方便；当终止状态给定时，用顺推法比较方便。后向法求出了各点到目标地的最短路线；而前向法求出了起点到各目的地的最短路线。,5.2.5 动态规划和静态规划,线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划；,两类规划在很多情况下原则上是可以相互转换的。动态规划可以看作是求使得指标函数达到最优的极值问题，状态转移方程，起始条件以及允许状态集，允许决策集等是约束条件，原则上它可以用线性规划或非线性规划方法求解。反过来，一些静态规划只要适当

13、引入阶段变量、状态、决策变量等要素就可以用动态规划方法来求解。,【例5.4】用顺序法和逆序法求解下面静态规划,（顺序法和逆序法模型及其求解见板书）,5.3 动态规划应用举例,5.3.1 资源分配问题,所谓资源分配问题，就是将数量一定的一种或若干种资源(如资金、原材料、机器设备、劳动力)恰当的分配给若干个使用者，从而使得总的经济效益最大。资源分配问题一般包括一种资源和多种资源的分配问题。,一种资源分配问题可叙述如下：设有数量为的某种资源，用于生产种产品，若以数量为的资源投入第种产品的生产，其收益相应的为，问如何分配这种资源，才能使得生产种产品的总收入最大？,(3)决策变量：,(2)状态变量：,其

14、静态规划的数学模型的形式一般为：,转化成动态规划模型为：,(1)阶段变量：,表示分配用于生产第种产品至第,表示分配给生产第种产品的原料数，,这里把资源分配给一个,或者几个使用者的过程作为一个阶段。,种产品的原料数量；,允许决策集：,；,(4)状态转移方程：,注：利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。,利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。,(6)动态规划基本方程：,(5)阶段指标：,；,；,（求解见板书）,在实际中，如销售后分配问题、机器设备分配问题、货物分配问题、投资分配问题等等，均属于这类资源分配问题。这种只将资源合理分配而不考虑

15、回收的问题，又称之为资源平行分配问题。,在资源分配问题中，还有一种要考虑资源回收利用的问题，这里决策变量为连续值，故又可以称之为资源连续分配问题，这类分配问题的一般叙述如下:,第二年再将资源数量中的和分别投入到、两种生产，则第二年又可以得到收入为，如此继续进行 年，试问：应该如何决定每年投入生产 的资源量，才能使得总的收入最大？,此问题的静态规划模型为：,此问题的动态规划模型为:,，按年份将整个过程分为 个阶段；,表示在第 阶段可投入,两种生产的资源量；,表示第 阶段用于 生产的资源量，,表示用于生产 的资源量，,(3)决策变量：,(2)状态变量：,(1)阶段变量：,允许决策集为：,(4)状态

16、转移方程：,(6)动态规划基本方程：,(5)阶段指标：,；,【例5.6】(机器负荷分配问题)某种机器可以在两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为，其中 为投入生产的机器数量，年完好率为；在低负荷下生产的产量函数为，其中 为投入生产的机器数量，年完好率为。假设开始生产时完好的机器数量台，试问每年应如何安排机器在高、低两种负荷下的生产，使得五年内的产品总产量最高？,此问题的静态规划模型：,表示在第 年初拥有的完好的机器数量；,此问题的动态规划模型：,表示第 年度分配给高负荷下生产,(6)动态规划基本方程：,(5)阶段指标：,(4)状态转移方程：,允许决策集为,的机器数量,(3)

17、决策变量：,(2)状态变量：,，按年份将整个过程分为5个阶段；,(1)阶段变量：,设有 个城市，分别用 来表示，城市 之间的距离为。一个推销商从城市1 出发到其他每个城市去一次且只去一次，最后回到城市1，问怎样选择行走路线，才能使得行走总路程最短？,其动态规划模型如下：,将从城市1到 城市的中间城市集合用,表示第 阶段到达 城市之,5.3.2 旅行推销商问题,表示，,城，,规定推销员是从城市1开始的，设推销员走到,(2)状态变量：,按经过城市的个数来分段，,(1)阶段变量：,个阶段，,将整个过程分为,问题一般描述如下：,；,前中途所经过的城市的集，则有，其中，因此，,可选取 作为描述过程的状态

18、变量；,表示推销商在状态 下前往的下一个城,表示从城市 到城市 的距离；,表示从城市1经过 个城市 到达城市,(7)动态规划基本方程：,的最短路线的距离；,(6)最优函数：,(5)阶段指标：,(4)状态转移方程：,允许决策集为:,(3)决策变量：,；,；,【例5.7】求解四个城市面上旅行推销员问题，其距离矩阵如表5-3所示，当推销员从城市1出发，经过每个城市一次且仅一次，最后回到1城市，问应该按照怎样的路线走，才能使得总的行程最短？,解 利用上面的分析很容易写出其模型，下面直接对其求解。,边界条件为,所以，推销员的最短旅行路线是13421，最短路程为23。,在实际生活中，很多问题都可以归纳为旅行售货商这类问题。如工厂里在钢板上要挖一些小圆孔，自动焊机的割嘴应走怎样的路线使得总路线最短、物资运送路线中，汽车应走怎样的路线使得总路程最短、城市里在一些地方铺设管道，管道应走怎样的路线才能使得总的管道长度最短等等。,注：动态规划所涉及的典型问题含有背包问题，设备更新问题等，有兴趣的同学可以参考其他相关教材。,小 结,动态规划所解决的问题；,动态规划是一种技术，是一种思想；,动态规划模型及求解；,动态规划的优缺点；,用动态规划可以求解静态规划；,