运筹学动态规划1.pptx
图5.1 例5.1示图5.1 动态规划的基本概念和模型 5.1.1 动态规划的基本概念 下面结合实例来介绍动态规划的基本概念：【例5.1】如图5.1所示，在处有一水库，现需从点铺设一条管道到点，弧上的数字表示与其相连的两个地点之间所需修建的渠道长度，请找出一条由到的修建线路，使得所需修建的渠道长度最短。第2页/共47页 【例5.2】未来四个月里，利用一个仓库经销某种商品。该仓库的最大容量为1000件，每月中旬定购商品，并于下月初取到订货。据估计：今后四个月这种商品的购价和售价，如表5-1所示。假定商品在第一个月初开始经销时仓库已经存有该种商品500件，每月市场不限，问：应如何计划每个月的订购与销售数量，使这四个月的总利润最大(不考虑仓库的存储费用)？表5-1 今后四个月这种商品的购价和售价 月份购价售价110122893111341517第3页/共47页记作：动态规划基本概念1.阶段与阶段变量2.状态与状态变量3.决策与决策变量5.状态转移方程4.策略记作：记作：记作：记作：记作：，允许决策集6.指标函数与最优函数第4页/共47页5.1.2 动态规划的模型 一般地，动态规划模型包括5.1.1节(1)至(6)中所提到的诸要素。很显然，要建立动态规划问题的模型，一般可按以下步骤来进行：(1)把问题的过程划分为恰当的个 阶段，引入阶段变量 ；(2)正确选择状态变量 ，使它既能描述过程的演变，又能满足无后效性，同时给出状态可能集 ；(3)确定决策变量 及每个阶段的允许决策集 ；(6)写出最优函数。(4)写出状态转移方程；(5)指出阶段指标及指标函数；第13页/共47页5.2 动态规划的原理与求解5.2.1 动态规划的最优化原理 下面我们先研究一下例5.1这个特殊问题的求解。最短路线问题有一个重要特性：如图第14页/共47页有第15页/共47页第16页/共47页 在引入一个虚拟的第五阶段后，可将第五阶段到第五阶段的指标记为 ，上述过程则可以用一个带有初始条件 的递推公式来完全描述：显然从 开始，有当 时当 时；(5-2)第17页/共47页当 时，当 时，可以求得 的最短距离12，然后根据计算过程中的记录，反向追踪可求得最短路线，最短路线为或，；。，。第18页/共47页。注注：而事实上，从各点到 的最短路线和最短路线距离都求出来了。第19页/共47页 动动态态规规划划最最优优性性原原理理：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必然构成最优策略。”将动态规划最优性原理应用于一般的多阶段问题求解即可得到类似(5-2)的递推公式(5-3)第20页/共47页5.2.2 动态规划的逆序解法下面以例5.2的求解为例，加深我们对这种方法的理解。解 由5.1.1中所述，例5.2中问题的模型如下：表示第 个月月初的库存量；表示第 个月已有库存 的情况下，要定购的商品量，表示第 个月已有库存 的情况下，要销售的商品量(为方便，后面将分别依次用 ，来代替和 )；(2)状态变量：(1)按月份分段：；(3)决策变量：第21页/共47页状态转移方程：(4)允许决策集：(5)阶段指标：其中 表示第四阶段末的状态；(6)动态规划基本方程：求解（要求板书），；辅图1辅图2辅图3第22页/共47页5.2.3 动态规划的顺序解法 【例5.3】图5.3所示为一水利网络，为水库，分别为不同的供水目的地，试找出给各供水目的地供水的最短路线。图5.3 例5.3示图（模型及其求解见板书）第26页/共47页5.2.4 逆序解法与顺序解法的关系 从本质上讲，两种方法原理(除去其方向因素外)是相同的，在具体的求解过程中，也都是将原问题转化为一系列单个问题的求解。但是，两种方法各有优势，如前向法求解例5.3时，有明显的优势。一般的，当初始状态给定时，用逆推法比较方便；当终止状态给定时，用顺推法比较方便。后向法求出了各点到目标地的最短路线；而前向法求出了起点到各目的地的最短路线。第27页/共47页5.2.5 动态规划和静态规划线性规划和非线性规划所研究的问题，通常都是与时间无关的，故又可以称为静态规划；两类规划在很多情况下原则上是可以相互转换的。动态规划可以看作是求 使得指标函数达到最优的极值问题，状态转移方程，起始条件以及允许状态集，允许决策集等是约束条件，原则上它可以用线性规划或非线性规划方法求解。反过来，一些静态规划只要适当引入阶段变量、状态、决策变量等要素就可以用动态规划方法来求解。第28页/共47页【例5.4】用顺序法和逆序法求解下面静态规划（顺序法和逆序法模型及其求解见板书）第29页/共47页5.3 动态规划应用举例5.3.1 资源分配问题所谓资源分配问题，就是将数量一定的一种或若干种资源(如资金、原材料、机器设备、劳动力)恰当的分配给若干个使用者，从而使得总的经济效益最大。资源分配问题一般包括一种资源和多种资源的分配问题。一种资源分配问题可叙述如下：设有数量为的某种资源，用于生产种产品，若以数量为的资源投入第种产品的生产，其收益相应的为，问如何分配这种资源，才能使得生产种产品的总收入最大？第30页/共47页(3)决策变量：(2)状态变量：其静态规划的数学模型的形式一般为：转化成动态规划模型为：(1)阶段变量：表示分配用于生产第种产品至第表示分配给生产第种产品的原料数，,这里把资源分配给一个或者几个使用者的过程作为一个阶段。种产品的原料数量；允许决策集：；第31页/共47页(4)状态转移方程：注：利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。利用动态规划基本方程进行逐段计算，最后求得即为所求问题的最大总收入。(6)动态规划基本方程：(5)阶段指标：；第32页/共47页 【例5.5】某公司拥有三家连锁商店，拟将新招聘的5名员工分配给甲、乙、丙三个商店，各商店得到新员工后，每年盈利情况如表5-2所示。问分配给各商店各多少员工，才能使得公司的总盈利最大？(单位：千元)表表5-2 5-2 分配新员工后，甲、乙、丙三个商店每年盈利情况分配新员工后，甲、乙、丙三个商店每年盈利情况(单位：千元单位：千元)012345甲03791213乙0510111111丙046111212工人数盈利数商店（求解见板书）第33页/共47页 在实际中，如销售后分配问题、机器设备分配问题、货物分配问题、投资分配问题等等，均属于这类资源分配问题。这种只将资源合理分配而不考虑回收的问题，又称之为资源平行分配问题资源平行分配问题。在资源分配问题中，还有一种要考虑资源回收利用的问题，这里决策变量为连续值，故又可以称之为资源连续分配问题资源连续分配问题，这类分配问题的一般叙述如下:第34页/共47页第二年再将资源数量中的和分别投入到、两种生产，则第二年又可以得到收入为 ，如此继续进行 年，试问：应该如何决定每年投入生产 的资源量 ，才能使得总的收入最大？，设有数量为的某种资源，可投入和两种生产。第一年若以数量投入生产后,剩下的量就投入生产,则可以得到收入，其中和为已知函数，且。这种资源在投入到、生产后，年终还可以回收再投入生产。设年回收率分别为和则在第一年生产后，回收的资源量合计为。第35页/共47页此问题的静态规划模型为：此问题的动态规划模型为:，按年份将整个过程分为 个阶段；表示在第 阶段可投入,两种生产的资源量；表示第 阶段用于 生产的资源量，表示用于生产 的资源量，(3)决策变量：(2)状态变量：(1)阶段变量：允许决策集为：第36页/共47页(4)状态转移方程：(6)动态规划基本方程：(5)阶段指标：；第37页/共47页 【例5.6】(机器负荷分配问题)某种机器可以在两种不同的负荷下进行生产，设机器在高负荷下生产的产量函数为 ，其中 为投入生产的机器数量，年完好率为 ；在低负荷下生产的产量函数为 ，其中 为投入生产的机器数量，年完好率为 。假设开始生产时完好的机器数量台 ，试问每年应如何安排机器在高、低两种负荷下的生产，使得五年内的产品总产量最高？此问题的静态规划模型：第38页/共47页表示在第 年初拥有的完好的机器数量；此问题的动态规划模型：表示第 年度分配给高负荷下生产(6)动态规划基本方程：(5)阶段指标：(4)状态转移方程：允许决策集为的机器数量,(3)决策变量：(2)状态变量：，按年份将整个过程分为5个阶段；(1)阶段变量：第39页/共47页 设有 个城市，分别用 来表示，城市 之间的距离为 。一个推销商从城市1 出发到其他每个城市去一次且只去一次，最后回到城市1，问怎样选择行走路线，才能使得行走总路程最短？其动态规划模型如下：将从城市1到 城市的中间城市集合用表示第 阶段到达 城市之5.3.2 旅行推销商问题表示，城，规定推销员是从城市1开始的，设推销员走到(2)状态变量：按经过城市的个数来分段，(1)阶段变量：个阶段，将整个过程分为问题一般描述如下：；第40页/共47页前中途所经过的城市的集，则有 ，其中 ，因此，可选取 作为描述过程的状态变量；表示推销商在状态 下前往的下一个城表示从城市 到城市 的距离；表示从城市1经过 个城市 到达城市(7)动态规划基本方程：的最短路线的距离；(6)最优函数：(5)阶段指标：(4)状态转移方程：允许决策集为:(3)决策变量：市；第41页/共47页 【例5.7】求解四个城市面上旅行推销员问题，其距离矩阵如表5-3所示，当推销员从城市1出发，经过每个城市一次且仅一次，最后回到1城市，问应该按照怎样的路线走，才能使得总的行程最短？表5-3 例5.7中四个城市面上旅行距离123410856260853890547780城市城市距离第42页/共47页解 利用上面的分析很容易写出其模型，下面直接对其求解。边界条件为 第43页/共47页 所以，推销员的最短旅行路线是13421，最短路程为23。第44页/共47页 在实际生活中，很多问题都可以归纳为旅行售货商这类问题。如工厂里在钢板上要挖一些小圆孔，自动焊机的割嘴应走怎样的路线使得总路线最短、物资运送路线中，汽车应走怎样的路线使得总路程最短、城市里在一些地方铺设管道，管道应走怎样的路线才能使得总的管道长度最短等等。注注：动态规划所涉及的典型问题含有背包问题，设备更新问题等，有兴趣的同学可以参考其他相关教材。第45页/共47页小小 结结动态规划所解决的问题；动态规划是一种技术，是一种思想；动态规划模型及求解；动态规划的优缺点；用动态规划可以求解静态规划；第46页/共47页感谢您的观看！第47页/共47页
