《动态规划模型.ppt》由会员分享，可在线阅读，更多相关《动态规划模型.ppt（27页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、动态规划模型 Four short words sum up what has lifted most successful Four short words sum up what has lifted most successful individuals above the crowd: a little bit more. individuals above the crowd: a little bit more. -author -author -date-date下面用动态规划的方法计算最短线路问题的特性： 如果最短线路在第k站通过点 ，则这一线路在由 出发到达终点的那一部分线路
2、，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（反正法） kPkPkP 最短线路问题的这一特性启示我们，从最后一段 开始，用从后向前逐步递推的方法，求出各点到 的最短线路，最后求得从 到 的最短线路。 6A0A6Ak6时： 设 表示由 到 的最短距离； )(56Af5A6A设 表示由 到 的最短距离； )(56Bf5B6A显然 4)(56Af3)(56Bfk5时： 如果 表示由 到 的最短距离。 )(45Af4A6Amin)(45Af)(),()(),(56545654BfBAdAfAAd73543min（以下类似定义）（以下类似定义）最短线路是 654AAA)(45B
3、f53245min)(),()(),(min5654556545BfBBdAfABd最短线路是 654ABB93646min)(),()(),(min)(565455654545BfBCdAfACdCf最短线路是 654ABCk4时： 75272min)(),()(),(min)(454344543434BfBAdAfAAdAf最短线路是 6543ABBA69251min)(),()(),(min)(454344543434CfCBdBfBBdBf最短线路是 6543ABBB89353min)(),()(),(min)(454344543434CfCCdBfBCdCf最短线路是 6543ABB
4、Ck3时： 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf最短线路是 65432ABBAA106573min)(),()(),(min)(343233432323BfBBdAfABdBf最短线路是 65432ABBAB98363min)(),()(),(min)(343233432323CfCCdBfBCdCf最短线路是 65432ABBBC128468min)(),()(),(min)(343233432323CfCDdBfBDdDf最短线路是 65432ABBCDk2时： 1396103131min)(),()(),()(),(min)(2
5、3212232122321212CfCAdBfBAdAfAAdAf最短线路是 654321ABBABA1612697108min)(),()(),()(),(min)(23212232122321212DfDBdCfCBdBfBBdBf最短线路是 出发点只有 0A18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf最短线路是 6543210ABBABAA最短距离为18。654321ABBBCB说明 1)此例揭示了动态规划的基本思想。 2)动态规划方法比穷举法（48种）大大节省了计算量。 3)计算结果不仅得到了 到 的最短线路和最短距离，而且得到了
6、其它各点到 的最短线路和最短距离，这对于很多实际问题来说是很有用处的。 0A6A6A动态规划法求解的数学描述 讨论动态规划中最优目标函数的建立，一般有下列术语和步骤： 、阶段 用动态规划求解多阶段决策系统时，要根据具体情况，将系统适当地分成若干个阶段，以便分若干个阶段求解，描述阶段的变量称为阶段变量。 上例分六个阶段，是一个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。 、状态状态表示系统在某一阶段所处的位置或状态。 上例中第一阶段有一个状态， ；即即0A第二阶段有两个状态， ；即即,11BA 过程的状态可用状态变量 来描述，某个阶段所有可能状态的全体可
7、用状态集合来描述， kx01AS 如如,22223112DCBASBAS、决策 某一阶段的状态确定之后，从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量称为决策变量 如上例中在第k阶段用 表示处于 状态时的决策变量。 )(kkxukx决策变量限制的范围称为允许决策集合。 用 表示第k阶段从 出发的决策集合。 )(kkxDkx、策略 由每阶段的决策 (i1,2,n)组成的决策函数序列称为全过程策略或简称策略，用p表示， )(iixu)(,),(),()(22111nnxuxuxuxP即即 由系统的第k个阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。
8、 用 表示k子过程策略， )(kkxP)(,),(),()(11nnkkkkkkxuxuxuxP即即 对于每一个实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许策略集合。 允许策略集合中达到最优效果的策略称为最优策略。 、状态转移 某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。 设第k个阶段的状态变量为 ，决策变量为 ，则第k+1个阶段的状态 用 表示从k阶段到k+1阶段的状态转移规律，称它为状态转移方程。kx)(kkxu1kx),(1kkkkuxTx、阶段效益 系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是 阶
9、段状态和 阶段决策的函数，记为 kxku),(kkkuxW、指标函数 指标函数是系统执行某一策略所产生的效益的数量表示，根据不同的实际问题，效益可以是利润、距离、产量或资源的耗量等。 指标函数可以定义在全过程上，也可以定义在后部子过程上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。 如上例中， 表示从 出发到终点 的最优策略指标。 )(45Af4A6A上例中 显然为零，称它为边值条件。 )(66Af 而动态规划的求解就是对kn,n-1,2,1逐级求出最优策略指标的过程。 、动态规划的基本方程)(),(min)(11kkkkkukkxfuxWxfk例2：机器负荷分
10、配问题 某种机器可以在高低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量 ，式中 为投入生产的机器数，年终的完好机器数为 ，称系数0.7为机器完好率。在低负荷下生产时，年产量 ，式中 为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为 台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。 118us 1u17 . 0 u225us 2u10001x解：此问题与上例类似。 设阶段变量k表示年度； 状态变量 是第k年初拥有的完好机器数（也是第k-1年度末完好机器数）。 kx 决策变量 规定为第k年度
11、中分配在高负荷下生产的机器数。 ku 于是 是该年度分配在低负荷下生产的机器数。 kkux k=2 k=3 k=4 k=5 1k1x2x3x4x5x 1u2u3u4u5u记 表示第k年到第五年末的最高总产量)(kkxfk5时)(58max)(55505555uxuxfxu5550835max55xuxxu最优点最优点5*5xu 这说明第5年初要把全部完好机器投入高负荷下生产。 k4时4444452 . 09 . 0)(9 . 07 . 0uxuxux因为因为)()(58max)(5544404444xfuxuxfxu所所以以)2 . 09 . 0(835max4444044uxuxxu4440
12、6 .134 . 12 .12max44xuxxu最优点最优点4*4xu k3时3333342 . 09 . 0)(9 . 07 . 0uxuxux因为因为)()(58max)(4433303333xfuxuxfxu所所以以)2 . 09 . 0(6 .1335max3333033uxuxxu33305 .1728. 024.17max33xuxxu最优点最优点3*3xu k2时2222232 . 09 . 0)(9 . 07 . 0uxuxux因为因为)()(58max)(3322202222xfuxuxfxu所所以以)2 . 09 . 0(5 .1735max2222022uxuxxu22
13、208 .205 . 075.20max22xuxxu最优点最优点0*2uk1时10001x因为因为1111122 . 09 . 0)(9 . 07 . 0uxuxux)()(58max)1000(221110111xfuxufxu所所以以)2 . 09 . 0(8 .2035max1111011uxuxxu)2 . 09 . 0(8 .2035max1111011uxuxxu16. 172.23max11011uxxu2370010007 .237 .231x最优点最优点0*1u 由此知五年最高总产量为23700再由上递推知 10001x0*1u9002x0*2u8103x810*3u567
14、4x567*4u3975x397*5u高负荷生产的完好机器的最优组合简记：397,567,810, 0, 0,*5*2*1uuu 这表明在前两年年初全部完好机器投入低负荷生产，后三年年初全部完好机器投入高负荷生产。 第五年末的完好机器数为 0.7397278台 在此例中，我们仅考虑最高产量，而未考虑五年计划后的完好机器数。 问题1：若计划为n个年度，怎样决策？ 问题2：若要求在第5年末完好的机器数为500台，如何决策使5年总产量最高？ 这类问题称为固定终端问题1x2x3x4x5x5006x1u2u3u4u5u由上讨论知：状态转移方程仍为 ) 1 (2 . 09 . 0)(9 . 07 . 01
15、kkkkkkuxuxux 表示第k年初开始到第5年末的最高产量，称为最优值函数，其递推关系为 )(kkxf)2()2 . 09 . 0()(58(max)(10kkkkkkxukkuxfuxuxfkkk=1,2,3,4,50)(66xf其中 为第k段的效益值，即第k年的产量。 )(58),(kkkkkkuxuuxy 表示第6年的产量不计算在总产量之内，故为零。 0)(66xf由假设 ， 5006x又根据(1)得 5562 . 09 . 0uxx一般地，当 确定后，选择 来确定 ，现在 已经给定，故 已经没有选择余地，它由 和 确定。 5x5u6x6x5u6x5x于是25005 . 455 .
16、45655xxxu由(2)可知035max)(5505555uxxfxu)25005 . 4(3555xx75005 .185x)2 . 09 . 0(35max)(4454404444uxfuxxfxu7500)2 . 09 . 0(5 .1835max4444044uxuxxu.max750070652144044uxxu75007 .214x最优值 0*4u7500)2 . 09 . 0(7 .2135max)(333303333uxuxxfxu75005 .243x最优值 0*3u类似地得到 75007 .21)(222xxf0*2u75004 .29)(111xxf0*1u21900750029400)1000(1f这是五年最高产量 这表明，如果限定五年后的完好机器数为500台，则总产量低于无限制的情况，最优策略也相应有所变化，由第一年到第四年全部完好机器投入低负荷生产。 为了计算第5年投入高负荷生产的完好机器数 ，先计算 5u9009 . 012xx8109 . 023xx7299 . 034xx6569 . 045xx所以 45225005 . 455xu 即第5年有452台机器投入高负荷生产，其余投入低负荷生产。