2022年动态规划模型 .pdf

《2022年动态规划模型 .pdf》由会员分享，可在线阅读，更多相关《2022年动态规划模型 .pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 2 讲动态规划模型动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化问题的一种数学方 法 。 1951年 美 国 数 学 家 贝 尔 曼（R.Bellman ）等人，根据一类多阶段决策问题的特点，提出了解决这类问题的“最优性原理”，研究了许多实际问题，从而创建了解决最优化问题的一种新方法动态规划。动态规划可以用来解决最优路径问题、资源分配问题、生产调度问题、库存问题、装载问题、排序问题、设备更新问题、生产过程最优控制问题。下面，以最短路径问题为例，说明动态规划的 基本思想方法和特点。（一） 、最短路径问题1、 问题提出如图 1-10 所示（ P56） ，从0A地要铺设一名师资料总结

2、- - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 18 页 - - - - - - - - - 条管道到6A地，中间必须经过五个中间站，第一站可以在11, BA两地中任选一个，类似的，第二、三、四、五站可供选择的地点分别是554443332222,BACBACBADCBA连接两点间的距离用图上两点连线上的数字表示，两点间没有连线的表示相应两点不能铺设管道，现要选择一条从0A到6A的铺管线路，使总距离最短。2、问题分析解决最短路径问题，最容易想到的方法是穷举法， 即列出所有可能发生的方案和

3、结果，再针对题目的要求对它们一一进行比较，求出最优方案。这种方法，在变量（或节点）的数目较小时有效 ；在变量数目很大时，计算量将会变得十分庞大，行不通 。因此，需要根据问题的特性，寻求一种简便的算法 。最短路径问题有一个特性 ：如果最短路径在第k站通过点kx，则这一线路在由kx名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 18 页 - - - - - - - - - 出发到达终点的那一部分线路，对于从点kx终点的所有可能选择的不同线路来说，必定也是距离最短的。这就是最优

4、性原理 。这就启发我们从最后一段开始，采用从后向前逐步递推的方法，求出各点到6A的最短线路，最后求得从0A到6A的最短线路 。（归结为一句话： 最有策略的子策略仍然是最优策略 ）3、问题求解为求解方便，将整个过程分为6个阶段，用)6,2,1(kk表示。（1）6k时，设)(56Af表示由5A到6A的最短距离，)(56Bf表示由5B到6A的最短距离，有4)(56Af，3)(56Bf（2）5k时， 1 从4A出发，有两种选择，到5A或5B，如 果)(45Af表 示4A到6A的 最 短 距 离 ，名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

5、- - 名师精心整理 - - - - - - - 第 3 页，共 18 页 - - - - - - - - - ),(545AAd表示4A到5A的距离，则73543min)(),()(),(min)(565455654545BfBAdAfAAdAf再用)(45Au表示相应的选择或决策，则545)(AAu。得到由4A出发到6A的最短线路是654AAA。 2 从5B出发，也有两种选择，到5A或5B，如果)(),(),(),(4554554545BuABdBBdBf的定义与 1 中相似，则53245min)(),()(),(min)(565455654545BfBBdAfABdBf545)(BBu。

6、得到由4B出发到6A的最短线路是654ABB。 3 从4C出发，同样有93646min)(),()(),(min)(565455654545BfBCdAfACdCf名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 18 页 - - - - - - - - - 545)(BCu。得到由4C出发到6A的最短线路是654ABC。（3）4k时，分别以333,CBA为出发点来计算，有75272min)(),()(),(min)(454344543434BfBAdAfAAdAf434)

7、(BAu，由3A出发的最短线路是6543ABBA。69251min)(),()(),(min)(454344543434CfCBdBfBBdBf434)(BBu， 由3B出 发 的 最 短 线 路 是3456BBBA。89353min)(),()(),(min)(454344543434CfCCdBfBCdCf434)(BCu， 由3C出 发 的 最 短 线 路 是6543ABBC。（4）3k时，分别以2222,DCBA为出发点来计算，有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第

8、 5 页，共 18 页 - - - - - - - - - 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf323)(AAu， 由2A出 发 的 最 短 线 路 是65432ABBAA。106573min)(),()(),(min)(343233432323BfBBdAfABdBf323)(ABu， 由2B出 发 的 最 短 线 路 是65432ABBAB。98363min)(),()(),(min)(343233432323CfCCdBfBCdCf323)(BCu， 由2C出 发 的 最 短 线 路 是65432ABBBC。128468min)

9、(),()(),(min)(343233432323CfCDdBfBDdDf323)(CDu， 由2D出 发 的 最 短 线 路 是65432ABBCD。（5）2k时，分别以11, BA为出发点来计算，有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 18 页 - - - - - - - - - 1396103131min)(),()(),()(),(min)(23212232122321212CfCAdBfBAdAfAAdAf212)(BAu， 由1A出 发 的 最 短

10、 线 路 是654321ABBABA。1612697108min)(),()(),()(),(min)(23212232122321212DfDBdCfCBdBfBBdBf212)(CBu， 由1B出 发 的 最 短 线 路 是654321ABBBCB。（6）1k时，出发点只有0A，有18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf101)(AAu， 由0A出 发 的 最 短 线 路 是6543210ABBABAA，距离为 18。综上所述，动态规划方法的基本思想是，把一个复杂的问题分解为一系列同一类型更容易求解的子问题，使计算过程单一化，便于

11、应用计算机。求解过程分为两个阶段，先按照整体最优的思想逆序 地求出各个可能状态的最优决策。然后，再顺序地求出整个问题的最优策略和最优路线。由于把最名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 18 页 - - - - - - - - - 优化应用到每个子问题上，于是，就系统地删去了所有中间非最优的方案组合，使计算工作量比直接枚举法大大减少。（二） 、基本概念和基本方程1、动态规划的基本概念（1）阶段和阶段变量用动态规划求解多阶段决策系统问题时，要根据具体情况， 将系统适

12、当地分成若干个阶段，以便分阶段决策。通常阶段是按照决策进行的时间或空间上的先后次序划分的，描述阶段的变量称为阶段变量。由系统的最后阶段向初始阶段求最优解的过程，称为动态规划的逆推解法。（2）状态和状态变量状态表示系统在某阶段所处的“起点”位置或状态。 各阶段的状态可用状态变量来描述，阶段k的状态变量记为kx。第k阶段所有可能状态的全体，可用状态集合kX来描述。上例中01AX212, AAX名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 18 页 - - - - - - -

13、 - - 22223,DCBAX（3）决策、决策变量和策略从一个阶段的某个状态出发，到达下一阶段，都有若干种选择。把过程从一个状态演变到下一阶段某一状态所作的选择或决定称为决策。描述决策的变量称为决策变量，记为)(kkxu。)(kkxu表示从第k阶段的状态kx出发所作的决策。并用)(kkxD表示第k阶段从kx出发的所有决策的集合。由每阶段的决策),2, 1)(nkxukk组成的决策序列称为全过程策略或策略，表示为nuuu,21。由系统的第k阶段出发到终点的决策过程称为全过程的后部子过程，相应的策略称为子策略。表示为nkuu,。对于每一实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范

14、围称为允许集合。 允许集合中达到最优效果的策略称为最优策略。（4）状态转移方程由第k阶段的状态kx，采用决策)(kkxu变名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 18 页 - - - - - - - - - 到第1k阶段的状态1kx的过程称为状态转移，并记为)(,(1kkkkkxuxTx该式表达了从k阶段到1k阶段的状态转移规律，故称为状态转移方程。（5）阶段效益多阶段决策过程中， 在阶段k的状态kx执行决策)(kkxu转到状态1kx，不仅带来系统状态的转移， 而

15、且也将对整个决策的结果或效益产生影响。用),(kkuxd表示在第k阶段中，从状态kx出发，采取策略)(kkxu，转移到1kx的效益，称为阶段效益。（6）最优策略与最优效益对于多阶段决策问题，自然都存在很多策略，而且每个策略都对应一种结果，把这些结果统称为效益。根据不同的实际问题，效益可以是利润、距离、产量或资源的消耗量等。显然一个多阶段决策问题的效益（决名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 18 页 - - - - - - - - - 策的目的）是各阶段效益的

16、和，使整体效益达到最优的策略，称为最优策略；相应于最优策略的整体效益称为最优效益。同（ 3）中子策略的定义类似，可以将最优效益定义在全过程上，也可以定义在后部子过程上。如果统一用)(kkxf表示从k阶段的状态kx出发到终点的最优效益，那么目的就是求)(11xf。（7）最优性原理对于无后效性的多阶段决策过程，最优策略具有最基本的性质：无论初始状态和初始决策如何， 对于前面的决策所造成的某一状态而言，余下的决策必是最优子策略。无后效性是指系统从某个阶段往后的发展，完全由本阶段所处的状态及其往后的决策决定，与系统以前的状态和决策无关，即当前状态就是过程往后发展的初始条件。2、动态规划的基本方程及一般

17、模型建立动态规划模型，需要进行以下几方面的工作：（1）选择阶段变量k；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 18 页 - - - - - - - - - （2）选择状态变量kx。状态变量必须能正确描述整个过程的演变特性，又要满足无后效性的原则；（3）选择决策变量ku；（4） 列出状态转移方程),(1kkkkuxTx；（5）列出动态规划基本方程：对于极小化问题)(),(min)(11kkkkkkxfuxdxf)1 , 1,(nnk称 为 动 态 规 划基 本 方

18、 程 。给 出 终 端 条件)(11nnxf，即可由后向前逐步推出)(11xf，得到最优效益。整个递推关系可表示为),()(1 ,1,)(),(min)(11111kkkknnkkkkkkuxTxxfnnkxfuxdxf常数这就是动态规划模型。（三）、应用举例名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 18 页 - - - - - - - - - 问题 1（机器负荷分配问题）某机器可以在高低两种不同的负荷下进行生产。在高负荷下生产时，产品产量118us，1u为投入生

19、产的机器数量，机器的年折损率为7.0，即年初完好的机器数量为1u， 年终就只剩下17.0u台是完好的，其余均需维修或报废。在低负荷下生产，产品年产量225us，其中2u为投入生产的机器数量，机器的年折损率为9.0b。设开始时， 完好的机器数为10001x台，要求制订一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使产品五年的总产量最高。模型建立这是一个典型的多阶段决策问题，用阶段变量k表示年度)5,4,3,2,1(k。（1）状态变量kx是第k年初拥有的完好机器数量， 它也是1k年度末的完好机器名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

20、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 18 页 - - - - - - - - - 数量。（2）决策变量ku为第k年度中分配在高负荷下生产的机器数量。于是kkux是该年度分配在低负荷下生产的机器数量。这里与前面的例子不同的是kkux ,均取连续变量以利于求解。kkux ,的非整数值可以理解为：如6.0kx表示一台机器在该年度正常工作时间只占60% ；3.0ku表示一台机器在该年度的30% 时间里在高负荷下工作。（3）由状态kx采取决策ku后的状态转移方程为)(9.07.01kkkkuxux)5,1(k（4）第k年度产品产量是（阶段

21、效益函数）)(58),(kkkkkkuxuuxd（5）若用)(kkxf表示第k年初从kx出发，采用最优策略，到第5 年末产品的最大值。则由最优化原理， 得动态方程（即所求模型）为)(9.07.0)(58max)(1kkkkkkkkkuxufuxuxf)5,2,1(k名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 18 页 - - - - - - - - - 其终端条件为0)(66xf。模型求解及结果利用动态规划的逆推解法，计算过程如下：5k时，5556555559.07

22、.0)(58max)(uxufuxuxf =)(58max55uxuk5553maxxu因为5553xu是关于5u的单调增加函数，且550 xu，故最优决策是5*5xu，此时5558)(xxf；类似可以依次求出4k时，44442.124.1max)(xuxf，取4*4xu，则4446.13)(xxf；3k时：333324.1728.0max)(xuxf，取3*3xu，则33352.17)(xxf；2k时：2222768.20504.0max)(xuxf，取0*2u，则222768.20)(xxf；1k时：1111691.23154.1max)(xuxf，取0*1u，名师资料总结 - - -精品

23、资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 18 页 - - - - - - - - - 则111691.23)(xxf；由此可知，最优策略为55443321,0,0 xuxuxuuu，即开始两年将完好机器全部投入低负荷生产，后三年将完好机器全部投入高负荷生产，这时最高产量为23691691.23)(111xxf（台）利用状态转移方程可以求出每年年初的完好机器数量：810,900,1000321xxx，278,397,569654xxx。问题 2 在问题 1 中增加限制条件，要求在第五年末完好

24、的机器数量为500 台，即5006x台。问这时如何安排生产，使产品五年总产量最高？分析与求解问题 1 中始端状态10001x是给定的，而终端状态没有限制，这是一种破坏性生产，在几年后产品停产、换型或设备更新的情况下是可行的。但若需2 生产，这样的方法是不可取的，因此，通常对终端是有要求的。由状态转移方程得500)(9.07.05556uxux名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 18 页 - - - - - - - - - 0)(66xf即25005.435x

25、u，这说明第五年的决策变量5u由5x唯一确定， 即决策集合)(55xD退化为一点，只有一种决策，所以5k时5556555559.07.0)(58max)(uxufuxuxf5553maxxu555)25005.4(3xx75005.185x利用递推关系，得4k时：)()(58max)(5544444xfuxuxf=7500)(9.07.05.1853max44444uxxxu750065.217.0max44xu显然最优决策为750065.21)(,0444*4xxfu类似可得75005.24)(,0333*3xxfu75001.27)(,0222*2xxfu75004.29)(,0111*1

26、xxfu名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 18 页 - - - - - - - - - 由此可见，为满足第五年末完好机器为500 台的要求，又要是产品产量最高，则前四年全部机器应在低负荷下生产，而在第五年只将部分机器投入高负荷生产，经计算，656,729,8109.0,9009.0,10005423121xxxxxxx由此得45225006565.45u，即第五年只能有 452 台机器投入高负荷生产，204 台机器投入低负荷生产，最高产量是2190075004.29)(111xxf这时产量较终端自由时低一些。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 18 页 - - - - - - - - -