运筹学第五章动态规划2课件

第五章动态规划动态规划简介动态规划所解决的问题：多阶段问题动态规划的核心。

动态规划的应用。动态规划的优缺点。核心:在于将问题公式化，也可以说，动态规划是将多阶段决策问题进行公式化的一种技术。

应用:工程、军事和商业等领域

优缺点:适用范围广，模型算法一体化，方便编程。一方面是大量的中间计算结果要求记录，造成对内存的较大需求；另一方面是由于没有统一的标准模型，使得动态规划的应用难度增加。在现实中，我们经常会碰到需要做前后相互关联的具有链状结构的多次决策才可以解决的问题，也经常会遇到一些经过巧妙设计后可以转化为具有上述多次决策特点而得以解决的问题，我们称这样的问题为多阶段决策问题。例如，许多工程项目都能根据工程进度或者空间位置等，被分解成相应于整个事件的多个阶段来进行计划；许多涉及到要求回报最大的资金投入问题，都能通过将不同的投资方案表示成不同阶段的方式进行规划；也有一些静态规划(如线性规划、非线性规划等)在人为引入“时间”因素后，可以转化为多阶段决策的问题，而解决这些问题的最常用的就是动态规划方法。返回【例5.2】未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为1000件，每月中旬定购商品，并于下月初取到订货。据估计：今后四个月这种商品的购价和售价，如表5-1所示。假定商品在第一个月初开始经销时仓库已经存有该种商品500件，每月市场不限，问：应如何计划每个月的订购与销售数量，使这四个月的总利润最大(不考虑仓库的存储费用)？表5-1今后四个月这种商品的购价和售价

月份购价售价110122893111341517记作：动态规划基本概念1.阶段与阶段变量2.状态与状态变量3.决策与决策变量5.状态转移方程4.策略记作：

记作：记作：记作：记作：，允许决策集6.指标函数与最优函数

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

返回后，作决策，就是在相应的允许决策集内确定一组，值，其结果是确定了下一阶段的状态，即仓库的库存量。

在例5.1中，作决策，就是在所处位置选择下一步应遵循的路线，比如在状态处作决策，就是从中选取一条路线，此时如果再假设选取了路线，那么决策者在处所作决策就是，即就是，而状态处允许决策集就是，其结果是确定了下一阶段的状态。在例5.2中，作决策，就是在当前第阶段库存量为的情况下，决定当月的定购量和销售量，在依次引入决策变量，和与其相应的允许决策集返回

后部子策略，简称为子策略，记作,即。把从第一阶段状态开始的子策略称为全策略，简称策略，记作，即

如例5.1中，为从起始状态开始的一个全策略，为从第3阶段状态开始的一个3子策略。在例5.2中，每个阶段既不订购也不销售，即，，或为从起始状态开始的一个全策略，为第2阶段状态开始的一个2子策略。在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用表示。而把允许策略集合中达到最优效果的策略称为最优策略。

返回

例5.2中，在第二阶段状态下作了决策和后，则当转移到第三阶段时，状态便已确定为。

状态转移描述了相邻阶段的状态与状态之间的关联关系。我们称这一关联关系的数学描述为状态转移方程。通常我们把描述第阶段状态到第阶段的状态转移规律的函数记作：。同时对第阶段的状态，一旦前一阶段达到的决策变量取定，则第阶段状态也可以反推出来。我们把这一状态转移的过程用函数描述，记作：，它表示若在从第阶段到达第阶段状态的过程中作的决策是，则第阶段起始状态为。

通常在第阶段某确定的状态下，一旦决策变量取定，则第阶段的状态也就确定，我们将这一过程称为状态转移。

如例5.1中，在第二阶段状态下作决策后，则当转移到第三阶段时，状态便已确定为；返回在例5.2中，

其中

依具体情况取或

。它表示在从第阶段的状态开始到第阶段的终止状态的允许策略集中，采用最优子策略所得到的指标函数值。如例5.1中，(5-1)类似有前部子策略的指标函数和最优函数与全策略的指标函数和最优值函数，依次如下：，；，。返回5.1.2动态规划的模型

一般地，动态规划模型包括5.1.1节(1)至(6)中所提到的诸要素。很显然，要建立动态规划问题的模型，一般可按以下步骤来进行：(1)把问题的过程划分为恰当的个阶段，引入阶段变量；(2)正确选择状态变量，使它既能描述过程的演变，又能满足无后效性，同时给出状态可能集；(3)确定决策变量及每个阶段的允许决策集；(6)

写出最优函数。

(4)写出状态转移方程；(5)指出阶段指标及指标函数；有在引入一个虚拟的第五阶段后，可将第五阶段到第五阶段的指标记为，上述过程则可以用一个带有初始条件的递推公式来完全描述：显然从开始，有当时当时；；；(5-2)。注：而事实上，从各点到的最短路线和最短路线距离都求出来了。

动态规划最优性原理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必然构成最优策略。”

将动态规划最优性原理应用于一般的多阶段问题求解即可得到类似(5-2)的递推公式(5-3)5.2.2动态规划的逆序解法下面以例5.2的求解为例，加深我们对这种方法的理解。解

由5.1.1中所述，例5.2中问题的模型如下：表示第个月月初的库存量；表示第个月已有库存的情况下，要定购的商品量，表示第个月已有库存的情况下，要销售的商品量(为方便，后面将分别依次用，来代替和)；(2)状态变量：(1)按月份分段：；(3)决策变量：图5.2图解法辅图1

返回最优点图5.2图解法辅图

返回最优点5.2.4逆序解法与顺序解法的关系从本质上讲，两种方法原理(除去其方向因素外)是相同的，在具体的求解过程中，也都是将原问题转化为一系列单个问题的求解。

但是，两种方法各有优势，如前向法求解例5.3时，有明显的优势。一般的，当初始状态给定时，用逆推法比较方便；当终止状态给定时，用顺推法比较方便。

后向法求出了各点到目标地的最短路线；而前向法求出了起点到各目的地的最短路线。

5.2.5动态规划和静态规划线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划；

两类规划在很多情况下原则上是可以相互转换的。动态规划可以看作是求使得指标函数达到最优的极值问题，状态转移方程，起始条件以及允许状态集，允许决策集等是约束条件，原则上它可以用线性规划或非线性规划方法求解。反过来，一些静态规划只要适当引入阶段变量、状态、决策变量等要素就可以用动态规划方法来求解。

【例5.4】

用顺序法和逆序法求解下面静态规划（顺序法和逆序法模型及其求解见板书）5.3动态规划应用举例5.3.1资源分配问题所谓资源分配问题，就是将数量一定的一种或若干种资源(如资金、原材料、机器设备、劳动力)恰当的分配给若干个使用者，从而使得总的经济效益最大。资源分配问题一般包括一种资源和多种资源的分配问题。

一种资源分配问题可叙述如下：设有数量为的某种资源，用于生产种产品，若以数量为的资源投入第种产品的生产，其收益相应的为，问如何分配这种资源，才能使得生产种产品的总收入最大？

(3)决策变量：(2)状态变量：其静态规划的数学模型的形式一般为：转化成动态规划模型为：(1)阶段变量：表示分配用于生产第种产品至第表示分配给生产第种产品的原料数，,这里把资源分配给一个或者几个使用者的过程作为一个阶段。种产品的原料数量；允许决策集：；(4)状态转移方程：注：利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。

利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。

(6)动态规划基本方程：(5)阶段指标：；；

【例5.5】

某公司拥有三家连锁商店，拟将新招聘的5名员工分配给甲、乙、丙三个商店，各商店得到新员工后，每年盈利情况如表5-2所示。问分配给各商店各多少员工，才能使得公司的总盈利最大？(单位：千元)表5-2分配新员工后，甲、乙、丙三个商店每年盈利情况(单位：千元)

012345甲03791213乙0510111111丙046111212工人数盈利数商店（求解见板书）在实际中，如销售后分配问题、机器设备分配问题、货物分配问题、投资分配问题等等，均属于这类资源分配问题。这种只将资源合理分配而不考虑回收的问题，又称之为资源平行分配问题。在资源分配问题中，还有一种要考虑资源回收利用的问题，这里决策变量为连续值，故又可以称之为资源连续分配问题，这类分配问题的一般叙述如下:第二年再将资源数量中的和分别投入到、两种生产，则第二年又可以得到收入为，如此继续进行年，试问：应该如何决定每年投入生产的资源量，才能使得总的收入最大？，设有数量为的某种资源，可投入和两种生产。第一年若以数量投入生产后,剩下的量就投入生产,则可以得到收入，其中和为已知函数，且。这种资源在投入到、生产后，年终还可以回收再投入生产。设年回收率分别为和则在第一年生产后，回收的资源量合计为。此问题的静态规划模型为：此问题的动态规划模型为:，按年份将整个过程分为个阶段；表示在第阶段可投入,两种生产的资源量；表示第阶段用于生产的资源量，表示用于生产的资源量，(3)决策变量：(2)状态变量：(1)阶段变量：允许决策集为：(4)状态转移方程：(6)动态规划基本方程：

(5)阶段指标：；【例5.6】(机器负荷分配问题)某种机器可以在两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为，其中为投入生产的机器数量，年完好率为；在低负荷下生产的产量函数为，其中为投入生产的机器数量，年完好率为。假设开始生产时完好的机器数量台，试问每年应如何安排机器在高、低两种负荷下的生产，使得五年内的产品总产量最高？

此问题的静态规划模型：

表示在第年初拥有的完好的机器数量；此问题的动态规划模型：表示第年度分配给高负荷下生产(6)动态规划基本方程：(5)阶段指标：(4)状态转移方程：允许决策集为的机器数量,(3)决策变量：(2)状态变量：，按年份将整个过程分为5个阶段；(1)阶段变量：设有个城市，分别用来表示，城市之间的距离为。一个推销商从城市1出发到其他每个城市去一次且只去一次，最后回到城市1，问怎样选择行走路线，才能使得行走总路程最短？其动态规划模型如下：将从城市1到城市的中间城市集合用表示第阶段到达城市之5.3.2旅行推销商问题表示，城，规定推销员是从城市1开始的，设推销员走到(2)状态变量：按经过城市的个数来分段，(1)阶段变量：个阶段，将整个过程分为问题一般描述如下：；前中途所经过的城市的集，则有，其中，因此，可选取作为描述过程的状态变量；