运筹学第三版第六章_动态规划课件.ppt

1、第八章 动态规划,教学内容： 动态规划问题实例 动态规划的基本概念与原理 动态规划应用举例,引 言,动态规划是解决多阶段决策过程最优化的一种方法。 该方法是由美国数学家贝尔曼（R. E. Bellman)等人在20世纪50年代初提出的。他们针对多阶段决策问题的特点，提出了解决这类问题的“最优化原理”，并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。 Bellman在1957年出版了Dynamic Programming一书，是动态规划领域中的第一本著作。,第一节 动态规划问题及实例,动态规划是解决多阶段决策问题的一种方法，是现代企业管理中的一种重要

2、决策方法，可用于最优路径问题、资源分配问题、生产计划和库存问题、投资问题、装载问题、排序问题及生产过程的最优控制等。 动态规划模型的分类： 以“时间”角度可分成：离散型和连续型。 从信息确定与否可分成：确定型和随机型。 从目标函数的个数可分成：单目标型和多目标型。,第一节 动态规划问题及实例,一、多阶段决策过程 多阶段决策过程是指这样一类特殊的活动过程，他们可以按时间顺序分解成若干相互联系的阶段，在每个阶段都要做出决策，全部过程的决策是一个决策序列，所以多阶段决策过程也称为序贯决策过程。这种问题就称为多阶段决策问题。,二、多阶段决策问题的特点 过程可分为若干个相互联系的阶段；每一阶段都对应着一

3、组可供选择的决策；每一决策的选定即依赖于当前面临的状态，又影响以后总体的效果。,第一节 动态规划问题及实例,三、具体实例 1、最短路线问题,给定一个线路网络，,要从A向F铺设一条输油管道，各点间连,线上的数字表示距离，问应选择什么路线，可使总距离最短？,第一节 动态规划问题及实例,2、生产与存储问题：,某工厂每月需供应市场一定数量的产品。供应需求所剩余产品应存入仓库，一般地说，某月适当增加产量可降低生产成本，但超产部分存入仓库会增加库存费用，要确定一个每月的生产计划，在满足需求条件下，使一年的生产与存储费用之和最小。,第一节 动态规划问题及实例,3、投资决策问题,某公司现有资金Q亿元，在今后5

4、年内考虑给A、B、C、D四个项目投资，这些项目的投资期限、回报率均不相同，问应如何确定这些项目每年的投资额，使到第五年末拥有资金的本利总额最大。,第一节 动态规划问题及实例,4、设备更新问题,企业在使用设备时都要考虑设备的更新问题，因为设备越陈旧所需的维修费用越多，但购买新设备则要一次性支出较大的费用。,现在某企业要决定一台设备未来8年的更新计划，已预测到第j年购买设备的价格为Kj，Gj为设备经过j年后的残值，Cj为设备连续使用j-1年后在第j年的维修费用(j=1,28)，问应在哪年更新设备可使总费用最小。,第二节 动态规划的基本概念与原理,动态规划的基本概念 阶段； 状态； 决策和策略； 状

5、态转移方程； 指标函数。,第二节 动态规划的基本概念与原理,一。基本概念,阶段：是指问题需要做出决策的步数。阶段总数常记为n，相 应的是n个阶段的决策问题。阶段的序号常记为k，称为阶段 变量，k=1,2, ,n. k即可以是顺序编号也可以是逆序编号， 常用顺序编号。,状态：各阶段开始时的客观条件，第k阶段的状态常用状态 变量 表示，状态变量取值的集合成为状态集合，用 表示。,例如，案例1中，,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,第1阶段,第2阶段,第3阶段,第4

6、阶段,第5阶段,状态 1,状态 2,状态 3,状态 4,状态 5,状态 6,决策：是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为决策变量，用 表示。 表示第k阶段当状态处于sk时的决策变量。,例如： 表示走到C阶段,当处于C2 路口时，下一 步奔D1.,时的允许决策集合记为 ，例如：,决策变量允许的取值范围称为允许决策集合，第k阶段状态为,状态转移方程：是从上一阶段的某一状态值转变为下一阶段 某一状态值的转移规律，用,表示。,策略：一个按顺序排列的决策组成的集合。由每段的决策按顺序排列组成的决策函数序列 称为k子过程策略。简称子策略，记为 。即,当k=1时，此

7、决策函数序列成为全过程的一个策略，简称策略，记为：,在实际问题中，可供选择的策略有一定的范围，此范围称为允许策略集合，用P表示。,指标函数：分阶段指标函数和过程指标函数。阶段指标函数,是指第k阶段从状态 出发，采取决策 时的效益，用,表示。而过程指标函数是从第k阶段的某状态出发，,采取子策略,效益之和：,最优指标函数：表示从第k阶段状态为 时采用最佳策略,到过程终止时的最佳效益。记为,时所得到的阶段,其中 opt 可根据具体情况取max 或min。,基本方程：此为逐段递推求和的依据，一般为：,式中opt 可根据题意取 max 或 min.,例如，案例1的基本方程为：,最优性原理：最优策略的子策

8、略必为最优。不管过去的状态,和决策如何，从眼下直到最后的诸决策必构成最优子策略。,动态规划的优点：,可把一个N维优化问题化成N个一维优化问题求解。 函数方程中附加某些约束条件，可使求解更加容易。 求得最优解以后，可得所有子问题的最优解。,动态规划的缺点：,“一个”问题，“一个”模型，“一个”求解方法。且求解技巧要求比较高，没有统一处理方法。 状态变量维数不能太高，一般要求小于6。,第三节 动态规划应用举例,例1 最短路线问题,基本思想：如果起点A经过B1,C1,D1,E1而到终点F，则由C1出发经D1,E1到F点这条子路线，是从C1到F的最短路线。所以，寻找最短路线，应该从最后一段开始找，然后

9、往前递推。,状态变量 ：各路线的位置,决策变量 ：第k阶段当状态处于 时，决定下一个状态的位置,状态转移方程 ：上一阶段到下一阶段的转移规则,指标函数 ：从状态出发，采取决策时的路程距离,最优指标函数 ：第k阶段状态为时且采用最佳走线策略，使从k位置及以后的路线最短。,逆序递推方程：,（1）k=5 时，状态,它们到F 点的距离即为,最短路。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,

10、3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（2）k=4 时，状态,它们到F 点需经过中途,点E，需一一分析从E 到 F的最短路：先说从D1到F 的最短路,有两种选择：经过 E1, E2, 比较最短。,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,这说明由 D1 到F 的最短距离为7，其路径为,相应的决策为：,这说明由 D2 到F 的最短距离为5，其路径为,相应的决策为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E

11、1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即 D3 到F 的最短距离为5，其路径为,相应的决策为：,（3）k=3 时，状态,这说明由 C1 到F 的最短距离为12，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2

12、,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,即由 C2 到F 的最短距离为10，相应的决策为,即由 C3 到F 的最短距离为8，相应的决策为,即由 C4 到F 的最短距离为9，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4

13、,8,4,3,5,6,2,3,1,4,3,（4）k=2时，状态,这说明由 B1 到F 的最短距离为13，相应的决策为,即由 B2到F 的最短距离为15，相应的决策为,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,（1）k=1 时，只有一个状态点A, 则,即由 A到F 的最短距离为17，相应的决策为,所以最

14、优路线为：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,再按计算顺序反推可得最优决策序列：,顺序递推方程：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,例1：,1阶段,2阶段,3阶段,4阶段,5阶段,行走方向,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,

15、3,5,6,2,3,1,4,3,K=1 时,注意到：,所以,K=2 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,K=3 时,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,类

16、似地，可算出：,最优策略：,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E1,E2,F,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,4,3,或,最短路径：,最短路长：,注：顺序解法与逆序解法无本质区别，一般来说，当初始状 态给定时用逆序解法，当终止状态给定时用顺序解法。若问 题给定了一个初始状态与一个终止状态，则两种方法均可使 用。,例2 资源分配问题（离散型）,例：设有6万元资金用于4个工厂的扩建，已知每个工厂的利 润增长额同投资额的大小有关，见下表。问应如何确定对这 四个工厂的投资额，使总利润增长额最大？,表1 利润增长额,（百元）

17、,解：把对四个工厂的投资依次看成4个阶段的决策过程，,确定对第k个工厂的投资额看成第k个阶段的决策， k=1,2,3,4。图示如下：,状态变量 ：可用于第k, k+1,n个工厂的投资额。,决策变量 ：第 k 阶段对第 k 个工厂的投资额。,允许决策集 ：,状态转移方程：,其中,阶段指标函数 ：第 k 阶段投资 元时所产生的利 润。（见上表）,最优指标函数 ：第 k 阶段状态为 且采取最佳投资 策略，从第 k 个工厂以及以后的最大总利润。,逆序法基本递推方程：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,解：（1）k=4时

18、,考虑：若到最后一个，第4个工厂投资时，还有资金 ， 若投资于第4个工厂的资金为 ，则最大利润为,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,（注意到此时 =0）,自然问：现在还有多少钱？即 =？,=0，100，200，300，400，500，600都有可能。,下面分情况讨论：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,时，,时，,其他种情况类似讨论，我们把所有的结果汇总成一个表2。,表1 利润增长额,（百元）,表2 k=4 时决策表,表1 利润

19、增长额,（百元）,（2）k=3时 到第三个工厂投资时，可利用的资金还有 ，,若向第三个工厂投资 （万元），则自此即以后最大利润为：,表1 利润增长额,（百元）,同样问： =？，即现在还有多少钱？它是允许决策集上界。,同理,仅举一例：,表1 利润增长额,（百元）,表2 k=4 时决策表,表1 利润增长额,（百元）,所有情况讨论结果汇总成下表：,表3 k=3 时决策表,（3）k=2 时,仅举一例：,表1 利润增长额,（百元）,表3 k=3 时决策表,关于 的其它取值情况及相应的最优决策列于下表,表4 k=2 时决策表,（4）k=1 时 ，此时,表1 利润增长额,（百元）,表4 k=2 时决策表,汇

20、一表格：,表5 k=1 时决策表,此时对应最大值134 的有三个值：,所对应的最优策略分别为：,时，由状态转移方程,知：,所对应的,表4 k=2 时决策表,对应的,再由状态转移方程,对应的,表3 k=3 时决策表,所对应的,再由状态转移方程,对应的,表2 k=4 时决策表,对应的,从而得一最优策略,同理还有另外三个最优策略:,所有解总利润最大增长额为,（百元）,加上刚才一组,资源分配问题（连续型）：设备负荷分配问题。,例3:某公司有500辆运输卡车，在超负荷运输（即每天满载行 驶500km以上）情况下，年利润为25万元/辆，这时卡车的年 损坏率为0.3；在低负荷下运输（即每天行驶300km以下

21、）情 况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5 年计划，问每年年初应如何分配完好车辆，在两种不同的负荷 下运输的卡车数量，使在5年内的总利润最大？,解：这是一个以时间为特征的多阶段决策问题。,阶段：将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5,状态变量 ：第k阶段初完好卡车数量 ，其中,决策变量 ：表示第k 阶段分配给超负荷运输的卡车数量。,显然，分配给低负荷的卡车数为,注：这里视 ， 为连续变量。若 =0.6表示有一辆卡 车在第k年度有60的时间处于完好状态。 =0.7表示有 一辆卡车在第k年度有70时间在超负荷运输等等。,状态转移方程：,阶段指标函数 ：

22、表示第 k 年度利润。,最优指标函数 ：第 k 年度初完好车辆数为 时，采 用最优策略到第 5 年末所产生的最大利润。,逆序递推式为：,1） k=5时,（注意到此时 =0）,此时,2） k=4 时,同理，只有当,时，函数,才能达到极大值。故有,3） k=3 时,不难得到,4） k=2 时,可见，只有当,时，函数,才能达到,极大值。故有,5） k=1 时,同理，只有当,时，函数,才能达到,极大值。故有,（万元）,所对应的最优策略分别为：,时，由状态转移方程,由,得,再由,得,第一年初：500辆车全部用于低负荷运输。 第二年初：还有450辆完好的车，也全部用于低负荷运输。 第三年初：还有405辆完

23、好的车，全部用于超负荷运输。 第四年初：还有238.5辆完好的车，全部用于超负荷运输。 第五年初：还有198.45辆完好的车，全部用于超负荷运输。 到第五年末，即第六年初，还剩余138.15辆完好的车。,实现最大利润,（亿元）,思考：某公司有1000辆运输卡车，在超负荷运输（即每天 满载行驶500km以上）情况下，年利润为25万元/辆，这时 卡车的年损坏率为0.3；在低负荷下运输（即每天行驶 300km以下）情况下，年利润为16万元/辆。年损坏率为 0.1。现要制定一个5年计划，问每年年初应如何分配完好车 辆在两种不同的负荷下运输的卡车数量，使在第5年年末 剩余的完好卡车数量为500台，并且使

24、在5年内的总利润最 大？,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,逆序递推式为：,第1年,第2年,第3年,第4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,1） k=5时,（注意到此时 =0）,第 5 节 背 包 问 题,一般的提法为

25、：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a (千克)，现有n种物品可供他选择装入 背包。第i种物品的单位重量为 (千克)，其价值（可以是表 明本物品对登山者的重要性指标）是携带数量 的函数 （i=1，2，n）.问旅行者应如何选择携带物品的件 数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题。,其数学模型为：,设 为第 i 种物品装入的件数，则背包问题可归结为如下,形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例4 有一辆最大货运量为10 t 的卡车，用以装载3种 货物，每种货物的单位重量及相应单位价值如表7-4 所示。,应如何装载可使总价值最大

26、？,表 7- 4,设第 种货物装载的件数为,则问题可表为：,阶段k: 将可装入物品按1，2，3的顺序排序，每段装入一 种物品，共划分3个阶段，即k=1,2,3.,状态变量 ：在第k段开始时，背包中允许装入前k种 物品的总重量。,决策变量 ：装入第k种物品的件数。,状态转移方程：,最优指标函数 ：在背包中允许装入物品的总重量不超 过 kg时，采取最优策略只装前k种物品时的最大使用价值,由此可得动态规划的顺序递推方程为：,货物1,货物2,货物3,K=1 时,货物1,货物2,货物3,K=1 时,注意到：,例如：,时，,其它计算结果见表7-5：,表 7- 5,货物1,货物2,货物3,K=2 时,其中,

27、例如：,时，,表 7- 5,其它计算结果见表7-6：,表 7- 6,货物1,货物2,货物3,K=3 时,表 7- 6,从,再由状态转移方程,表 7- 6,货物1,货物2,货物3,再由状态转移方程,表 7- 5,最大装载价值为,总结：今后解背包问题应先从k=3入手：,k=3时,下面应有重点地从k=2中求解三个最优函数值：,K=2 时,所以从第一阶段应有重点地求以下四个数：,K=1 时,由此逐一逆推代回上式：,由此逐一逆推代回上式：,由此逐一逆推代回上式：,最后,最优策略：,再由状态转移方程,再由状态转移方程,最大装载价值为,思考：用动态规划方法求解：,解：我们用背包问题顺序解的思路： 人为的划分

28、三个阶段：k=1,2,3 阶段指标函数及其他分配情况如下图：,1,2,3,动态规划的顺序递推方程为：,1,2,3,1,2,3,最优决策为,所对应的最优解为,例（二维背包） 有一辆最大货运量为13t、最大容量为10 件的卡车，用以装载3种货物，每种货物的单位重量及相 应单位价值如下表所示。应如何装载可使总价值最大？,解：设装载第i种货物的件数为 （i=1,2,3），则问题可表述为,1,2,3,关于件数的约束:,关于重量的约束:,基本方程式：,1,2,3,问题就是求：,1,2,3,1,2,3,同理可求得,所以最优决策方案为 ：,最优装载价值为：,例5 货郎担问题,货郎担问题也叫推销商问题（trav

29、eling salesman problem）, 其一般提法为：有n个城市，用1，2，n表示，城i, j之间 的距离为 ，有一个货郎从城1出发到其他城市一次且仅一 次，最后回到城市1，怎样选择行走路线使总路程最短？,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,一。动态规划解,阶段变量k：按所经过的城市个数划分阶段k, k=1,2,n-1.,状态变量 ：设第k 阶段到达城市i 时途中所经过的k个城市,集合为S，则,其中,1,2,3,6,4,5,7,8,9,10,11,12,4,5,

30、2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,例如： ，表示推销商从城1出发途径城市2,3,4 到达城市5时，须先途经城市2,4到达城市3，再奔城市5。,决策变量 ：第k 阶段到达城市i 的最短路线上邻接i 的前一,个城市 。,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,阶段指标函数 : 设从城市1出发，第k-1阶段到达到城市j, 则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为,最优指标函数 ：从城市1出发，经过S中k

31、个城市,到,达城市i的最短距离.,1,2,3,6,4,5,7,8,9,10,11,12,4,5,2,3,6,8,7,7,5,8,4,5,3,4,8,4,3,5,6,2,3,1,13,3,4,5,则动态规划的顺序递推关系为:,最后算出 ,即为全程的最短距离,同时 可得最优策略,即最优行走路线.,例1 已知 4个城市间距离如表1，求从城市1出发，经其他城 市一次且仅一次最终回到城市1的最短路与距离。,解：由边界条件知：,当k=1时，从城市1出发，经过1个城市到达城市i的最短距离 为：,即从城市1出发，途经1个城市奔城2，应先到4，再到2。,即从城市1出发，途经1个城市奔城3，应先到4，再到3。,即从城市1出发，途经1个城市奔城4，应先到2，再到4。,当k=2时，从城市1出发，途经2个城市到达城市i的最短距离 为,即从城市1出发，途经2个城市3，4奔城2，应先到4，再到2。,即从城市1出发，途经2个城市2，4奔城3，应先到4，再 到3。,即从城市1出发，途经2个城市2，3奔城4，应先到2，再到4。,当k=3时，从城市1出发，途经3个城市到达城市1的最短距离,货郎担的最短路线是1 2431。,逆推回去,行走距离为23。,第七讲：设备更新问题 企业中经常会遇到一台设备应该使用多少年更新最合算的问 题。一般来说，一台设备在比较新时，年运转量大，经济收入 高，故障