《最优化理论_动态规划讲解课件.ppt》由会员分享，可在线阅读，更多相关《最优化理论_动态规划讲解课件.ppt（101页珍藏版）》请在三一办公上搜索。
1、动态规划,动态规划问题实例动态规划的基本概念与原理动态规划应用举例,引 言,动态规划是解决多阶段决策过程最优化的一种方法。该方法是由美国数学家贝尔曼（R.E.Bellman)等人在20世纪50年代初提出的。并成功地解决了生产管理、工程技术等方面的许多问题，从而建立了运筹学的一个新的分支，即动态规划。Bellman在1957年出版了Dynamic Programming一书，是动态规划领域中的第一本著作。,1 动态规划问题实例,例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
2、,6,2,3,1,4,3,要从A向F铺设一条输油管道，,各点间连线上的数字表示距离，问应选择什么路线，可使总,距离最短？,动态规划是解决多阶段决策问题的一种方法。所谓多阶段,决策问题是指这样的决策问题：其过程可分为若干个相互联,系的阶段，每一阶段都对应着一组可供选择的决策，每一决,策的选定即依赖于当前面临的状态，又影响以后总体的效果。,A,B,C,D,E,状态A,状态B,状态C,状态D,状态E,状态F,决策A,决策D,决策E,当每一阶段的决策选定以后，就构成一个决策序列，称为一个,决策B,决策C,策略，它对应着一个确定的效果。多阶段决策问题就是寻找使,此效果最好的策略。,2 动态规划的基本概念
3、与原理,一。基本概念,阶段：是指问题需要做出决策的步数。阶段总数常记为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阶段,第5阶段,状态1,状态2,状态3,状态4,状态5,状态6,决策：
4、是指从某阶段的某个状态出发，在若干个不同方案中,做出的选择。表示决策的变量，称为决策变量，用 表示,例如：表示走到C阶段,当处于C2 路口时，下一步奔D1.,时的允许决策集合记为，例如：,状态转移方程：是从上一阶段的某一状态值转变为下一阶段某一状态值的转移规律，用,表示。,决策变量允许的取值范围称为允许决策集合，第k阶段状态为,策略(Strategy)由过程的第一阶段开始到最后一阶段为止称为问题的全过程，由各阶段的决策构成的策略序列称为全过程策略，记为P1n。,k=1,k=2,k=3,k=4,k=5,k=6,策略,状态,指标函数：分阶段指标函数和过程指标函数。阶段指标函数,是指第k阶段从状态
5、出发，采取决策 时的效益，用,表示。而过程指标函数从第k阶段的某状态出发，,采取子策略,时所得到的阶段效益之和：,最优指标函数：表示从第k阶段状态为 时采用最佳策略,到过程终止时的最佳效益。记为,其中 opt 可根据具体情况取max 或min。,基本方程：此为逐段递推求和的依据，一般为：,式中opt 可根据题意取 max 或 min.,例如，例1的基本方程为：,最优性原理,动态规划最优化原理：不管该最优策略上某状态以前的状态和决策如何，对该状态而言，余下的诸决策必定构成最优子策略。即最优策略的任意后部子策略也是最优的。,A,B,C,将多阶段的决策过程划分为不同阶段，恰当地选取状态变量、决策变量
6、并定义最优指标函数，正确写出基本的递推关系和恰当的边界条件。求解时从边界条件开始，逆过程进行方向逐段递推寻优，在对每一个子问题进行求解时，都要使用前面已求出的子问题的最优结果，最后一个子问题的最优解就是整个问题的最优解。动态规划方法每一阶段最优决策选取是从全局考虑的，与该阶段的最优决策一般是不同的。,动态规划方法的基本思想,动态规划应用举例,例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）k=5 时，状态,它们到F 点的距离即为,最
7、短路。,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,（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,
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,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,即 D3 到F 的最短距离为5，其路径为,相应的决策为：,（
9、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,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
10、,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,（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,
11、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，相应的决策为,所以最优路线为：,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
12、,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,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
13、,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,或,类似地，可算出：,最优策略：,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,或,最短路径：,最短路长：,注：顺序解法与逆序解法无本质区别，一般来说，当初始状态给定时用逆序解法，当终止状态给定时用顺序解法。若问题给定了一个
14、初始状态与一个终止状态，则两种方法均可使用。,建立动态规划模型的步骤,分析问题。识别问题的多阶段特征，按照时间或者空间的先后顺序将过程适当地分为满足递推关系的若干阶段，对非时序的静态问题需要人为地赋予“时段”的概念；正确选择具有以下两个特征的状态变量及其取值范围(1)可知性。过程演变的各阶段状态变量取值能直接或者间接地被确定。(2)能确切描述过程的演变，且满足无后效性,确定决策变量及其取值范围根据状态变量和决策变量的含义，正确写出状态转移方程sk+1=T(sk,xk)根据问题，明确指标函数Fkn，最优指标函数fk(sk)及k阶段指标dk(sk,xk)的含义，并正确列出最优指标函数的递推关系及边
15、界条件检查所建立的动态规划模型是否正确表达了原问题的要求和各种限制条件,建立动态规划模型的步骤,例2 资源分配问题（离散型）,例：设有6百万元资金用于4个工厂的扩建，已知每个工厂的利润增长额同投资额的大小有关，见下表。问应如何确定对这四个工厂的投资额，使总利润增长额最大？,表1 利润增长额,（百元）,解：把对四个工厂的投资依次看成4个阶段的决策过程，,确定对第k个工厂的投资额看成第k个阶段的决策，k=1,2,3,4。图示如下：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,状态变量：可用于第k,k+1,n个工厂的投资额。,决策变量：第 k 阶段对第
16、k 个工厂的投资额。,允许决策集：,状态转移方程：,其中,阶段指标函数：第 k 阶段投资 元时所产生的利润。（见上表）,最优指标函数：第 k 阶段状态为 且采取最佳投资策略，从第 k 个工厂以及以后的最大总利润。,逆序法基本递推方程：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,解：（1）k=4时,考虑：若到最后一个，第4个工厂投资时，还有资金，若投资于第4个工厂的资金为，则最大利润为,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,（注意到此时=0）
17、,自然问：现在还有多少钱？即=？,=0，100，200，300，400，500，600都有可能。,下面分情况讨论：,工厂1,工厂2,工厂3,工厂4,投资x1,投资x2,投资x3,投资x4,状态,状态,状态,表1 利润增长额,（百元）,时，,时，,其他种情况类似讨论，我们把所有的结果汇总成一个表2。,表1 利润增长额,（百元）,表2 k=4 时决策表,表1 利润增长额,（百元）,（2）k=3时 到第三个工厂投资时，可利用的资金还有，,若向第三个工厂投资（万元），则自此即以后最大利润为：,表1 利润增长额,（百元）,同样问：=？，即现在还有多少钱？它是允许决策集上界。,同理,仅举一例：,表1 利润
18、增长额,（百元）,表2 k=4 时决策表,表1 利润增长额,（百元）,所有情况讨论结果汇总成下表：,表3 k=3 时决策表,（3）k=2 时,仅举一例：,表1 利润增长额,（百元）,表3 k=3 时决策表,关于 的其它取值情况及相应的最优决策列于下表,表4 k=2 时决策表,（4）k=1 时，此时,表1 利润增长额,（百元）,表4 k=2 时决策表,汇一表格：,表5 k=1 时决策表,此时对应最大值134 的有三个值：,所对应的最优策略分别为：,时，由状态转移方程,知：,所对应的,表4 k=2 时决策表,对应的,再由状态转移方程,对应的,表3 k=3 时决策表,所对应的,再由状态转移方程,对应
19、的,表2 k=4 时决策表,对应的,从而得一最优策略,同理还有另外三个最优策略:,所有解总利润最大增长额为,（百元）,加上刚才一组,资源分配问题（连续型）：设备负荷分配问题。,例（何坚勇/P-256）某公司有500辆运输卡车，在超负荷运输（即每天满载行驶500km以上）情况下，年利润为25万元/辆，这时卡车的年损坏率为0.3；在低负荷下运输（即每天行驶300km以下）情况下，年利润为16万元/辆。年损坏率为0.1。现要制定一个5年计划，问每年年初应如何分配完好车辆，在两种不同的负荷下运输的卡车数量，使在5年内的总利润最大？,解：这是一个以时间为特征的多阶段决策问题。,第1年,第2年,第3年,第
20、4年,投x1辆超负荷车,状态,状态,状态,投x2辆超负荷车,投x3辆超负荷车,投x4辆超负荷车,第5年,投x4辆超负荷车,状态,状态,阶段：将5年运输计划看成5个阶段的决策问题。k=1,2,3,4,5,状态变量：第k阶段初完好卡车数量，其中,决策变量：表示第k 阶段分配给超负荷运输的卡车数量。,显然，分配给低负荷的卡车数为,注：这里视，为连续变量。若=0.6表示有一辆卡车在第k年度有60的时间处于完好状态。=0.7表示有一辆卡车在第k年度有70时间在超负荷运输等等。,状态转移方程：,阶段指标函数：表示第 k 年度利润。,最优指标函数：第 k 年度初完好车辆数为 时，采用最优策略到第 5 年末所
21、产生的最大利润。,逆序递推式为：,1）k=5时,（注意到此时=0）,此时,2）k=4 时,同理，只有当,时，函数,才能达到极大值。故有,3）k=3 时,不难得到,4）k=2 时,可见，只有当,时，函数,才能达到,极大值。故有,5）k=1 时,同理，只有当,时，函数,才能达到,极大值。故有,（万元）,所对应的最优策略分别为：,时，由状态转移方程,由,且,再由,且,第一年初：500辆车全部用于低负荷运输。第二年初：还有450辆完好的车，也全部用于低负荷运输。第三年初：还有405辆完好的车，全部用于超负荷运输。第四年初：还有238.5辆完好的车，全部用于超负荷运输。第五年初：还有198.45辆完好的
22、车，全部用于超负荷运输。到第五年末，即第六年初，还剩余138.15辆完好的车。,实现最大利润,（亿元）,背 包 问 题,一般的提法为：一旅行者携带背包去登山。已知他所能承受 的背包重量的极限为a(千克)，现有n种物品可供他选择装入背包。第i种物品的单位重量为(千克)，其价值（可以是表明本物品对登山者的重要性指标）是携带数量 的函数（i=1，2，n）.问旅行者应如何选择携带物品的件数，以使总价值最大？,此模型解决的是运输工具包括卫星的最优装载问题。,其数学模型为：,设 为第 i 种物品装入的件数，则背包问题可归结为如下,形式的整数规划模型：,下面从一个例子来分析动态规划建模。,例7/P211 有
23、一辆最大货运量为10 t 的卡车，用以装载3种货物，每种货物的单位重量及相应单位价值如表7-4 所示。,应如何装载可使总价值最大？,表 7-4,设第 种货物装载的件数为,则问题可表为：,阶段k:将可装入物品按1，2，3的顺序排序，每段装入一种物品，共划分3个阶段，即k=1,2,3.接下来用顺序法求解,状态变量：在第k段开始时，背包中允许装入前k种物品的总重量。（）,决策变量：装入第k种物品的件数。,状态转移方程：,最优指标函数：在背包中允许装入物品的总重量不超过 kg，采取最优策略只装前k种物品时的最大使用价值,货物1,货物2,货物3,由此可得动态规划的顺序递推方程为：,货物1,货物2,货物3
24、,K=1 时,货物1,货物2,货物3,K=1 时,注意到：,例如：,时，,其它计算结果见表7-5：,表 7-5,货物1,货物2,货物3,K=2 时,其中,例如：,时，,表 7-5,其它计算结果见表7-6：,表 7-6,货物1,货物2,货物3,K=3 时,表 7-6,从,再由状态转移方程,表 7-6,货物1,货物2,货物3,再由状态转移方程,最大装载价值为,表 7-5,7.9(3)/P-239 用动态规划方法求解：,解：Sk+1：可用于第1到第k个项目的投资额 SkSk+1 ak xk 人为的划分三个阶段：k=1,2,3 阶段指标函数及其他分配情况如下图：,1,2,3,k=1,k=2,k=3,解
25、：Sk：可用于第k到第3个项目的投资额 Sk+1Sk ak xk 人为的划分三个阶段：k=1,2,3 阶段指标函数及其他分配情况如下图：,1,2,3,k=3,k=2,k=3,例5 货郎担问题,货郎担问题也叫推销商问题（traveling 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,一。动态
26、规划解,阶段变量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,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
27、,3,5,6,2,3,1,13,3,4,5,阶段指标函数:设从城市1出发，第k-1阶段到达到城市j,则城市j与下一阶段（第k阶段）的目的地城市i之间的距离为,最优指标函数：从城市1出发，经过S中k个城市,到,达城市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的最短路与距离。,1,2,3
28、,4,5,解：由边界条件知：,当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，在到2之前应为4。,即从城市1出发，途经2个城市2，4奔城3，在到3之前应为4。,即从城市1出发，途经2个城市2，3奔城4，在到4之前应为2。,当k=3时，从城市1出发，途经3个城市到达城市1的最短距离,货郎担的最短路线是1 2431。,逆推回去,行走距离为23。,人有了知识，就会具备各种分析能力，明辨是非的能力。所以我们要勤恳读书，广泛阅读，古人说“书中自有黄金屋。”通过阅读科技书籍，我们能丰富知识，培养逻辑思维能力；通过阅读文学作品，我们能提高文学鉴赏水平，培养文学情趣；通过阅读报刊，我们能增长见识，扩大自己的知识面。有许多书籍还能培养我们的道德情操，给我们巨大的精神力量，鼓舞我们前进。,
