动态规划模型

1、编辑ppt1 动态规划模型例1：最短线路问题0A6A 问题：现选择一条从 到 的铺管线路，使总距离最短？ 若用穷举法要算23222148种不同线路，比较这48种结果即可得出，但当段数增加，且各段选择也增加时，穷举法将变得非常庞大，以至利用计算机都十分困难。 编辑ppt2下面用动态规划的方法计算最短线路问题的特性： 如果最短线路在第k站通过点 ，则这一线路在由 出发到达终点的那一部分线路，对于从 点到达终点的所有可能选择的不同线路来说，必定也是距离最短的。（反正法） kPkPkP 最短线路问题的这一特性启示我们，从最后一段 开始，用从后向前逐步递推的方法，求出各点到 的最短线路，最后求得从 到

2、的最短线路。 6A0A6A编辑ppt3k6时： 设 表示由 到 的最短距离； )(56Af5A6A设 表示由 到 的最短距离； )(56Bf5B6A显然 4)(56Af3)(56Bfk5时： 如果 表示由 到 的最短距离。 )(45Af4A6Amin)(45Af)(),()(),(56545654BfBAdAfAAd73543min（以下类似定义）（以下类似定义）编辑ppt4最短线路是 654AAA)(45Bf53245min)(),()(),(min5654556545BfBBdAfABd最短线路是 654ABB93646min)(),()(),(min)(565455654545BfBCd

3、AfACdCf最短线路是 654ABC编辑ppt5k4时： 75272min)(),()(),(min)(454344543434BfBAdAfAAdAf最短线路是 6543ABBA69251min)(),()(),(min)(454344543434CfCBdBfBBdBf最短线路是 6543ABBB编辑ppt689353min)(),()(),(min)(454344543434CfCCdBfBCdCf最短线路是 6543ABBCk3时： 136876min)(),()(),(min)(343233432323BfBAdAfAAdAf最短线路是 65432ABBAA编辑ppt7106573

4、min)(),()(),(min)(343233432323BfBBdAfABdBf最短线路是 65432ABBAB98363min)(),()(),(min)(343233432323CfCCdBfBCdCf最短线路是 65432ABBBC编辑ppt8128468min)(),()(),(min)(343233432323CfCDdBfBDdDf最短线路是 65432ABBCDk2时： 1396103131min)(),()(),()(),(min)(23212232122321212CfCAdBfBAdAfAAdAf最短线路是 654321ABBABA编辑ppt91612697108min

5、)(),()(),()(),(min)(23212232122321212DfDBdCfCBdBfBBdBf最短线路是 出发点只有 0A18163135min)(),()(),(min)(121011210101BfBAdAfAAdAf最短线路是 6543210ABBABAA最短距离为18。654321ABBBCB编辑ppt10说明 1)此例揭示了动态规划的基本思想。 2)动态规划方法比穷举法（48种）大大节省了计算量。 3)计算结果不仅得到了 到 的最短线路和最短距离，而且得到了其它各点到 的最短线路和最短距离，这对于很多实际问题来说是很有用处的。 0A6A6A动态规划法求解的数学描述 讨论

6、动态规划中最优目标函数的建立，一般有下列术语和步骤： 、阶段 用动态规划求解多阶段决策系统时，要根据具体情况，将系统适当地分成若干个阶段，以便分若干个阶段求解，描述阶段的变量称为阶段变量。 编辑ppt11 上例分六个阶段，是一个六阶段的决策过程。例中由系统的最后阶段向初始阶段求最优解的过程称为动态规划的逆推解法。 、状态状态表示系统在某一阶段所处的位置或状态。 上例中第一阶段有一个状态， ；即即0A第二阶段有两个状态， ；即即,11BA 过程的状态可用状态变量 来描述，某个阶段所有可能状态的全体可用状态集合来描述， kx01AS 如如,22223112DCBASBAS编辑ppt12、决策 某一

7、阶段的状态确定之后，从该状态演变到下一阶段某一状态所作的选择称为决策。描述决策的变量称为决策变量 如上例中在第k阶段用 表示处于 状态时的决策变量。 )(kkxukx决策变量限制的范围称为允许决策集合。 用 表示第k阶段从 出发的决策集合。 )(kkxDkx、策略 由每阶段的决策 (i1,2,n)组成的决策函数序列称为全过程策略或简称策略，用p表示， )(iixu)(,),(),()(22111nnxuxuxuxP即即编辑ppt13 由系统的第k个阶段开始到终点的决策过程称为全过程的后部子过程，相应的策略称为后部子过程策略。 用 表示k子过程策略， )(kkxP)(,),(),()(11nnk

8、kkkkkxuxuxuxP即即 对于每一个实际的多阶段决策过程，可供选择的策略有一定的范围限制，这个范围称为允许策略集合。 允许策略集合中达到最优效果的策略称为最优策略。 、状态转移 某一阶段的状态变量及决策变量取定后，下一阶段的状态就随之而定。 编辑ppt14 设第k个阶段的状态变量为 ，决策变量为 ，则第k+1个阶段的状态 用 表示从k阶段到k+1阶段的状态转移规律，称它为状态转移方程。kx)(kkxu1kx),(1kkkkuxTx、阶段效益 系统某阶段的状态一经确定，执行某一决策所得的效益称为阶段效益，它是整个系统效益的一部分，是 阶段状态和 阶段决策的函数，记为 kxku),(kkku

9、xW、指标函数 指标函数是系统执行某一策略所产生的效益的数量表示，根据不同的实际问题，效益可以是利润、距离、产量或资源的耗量等。 编辑ppt15 指标函数可以定义在全过程上，也可以定义在后部子过程上。指标函数往往是各阶段效益的某种和式，取最优策略时的指标函数称为最优策略指标。 如上例中， 表示从 出发到终点 的最优策略指标。 )(45Af4A6A上例中 显然为零，称它为边值条件。 )(66Af 而动态规划的求解就是对kn,n-1,2,1逐级求出最优策略指标的过程。 、动态规划的基本方程)(),(min)(11kkkkkukkxfuxWxfk编辑ppt16例2：机器负荷分配问题 某种机器可以在高

10、低两种负荷下生产，年产量与年初投入生产的机器数有关。在高负荷下生产时，年产量 ，式中 为投入生产的机器数，年终的完好机器数为 ，称系数0.7为机器完好率。在低负荷下生产时，年产量 ，式中 为投入生产的机器数，机器完好率为0.9，设开始时，完好的机器数为 台，要求制定一个五年计划，在每年开始时决定如何重新分配完好机器在两种不同负荷下工作的数量，使五年的总产量最高。 118us 1u17 . 0 u225us 2u10001x编辑ppt17解：此问题与上例类似。 设阶段变量k表示年度； 状态变量 是第k年初拥有的完好机器数（也是第k-1年度末完好机器数）。 kx 决策变量 规定为第k年度中分配在高

11、负荷下生产的机器数。 ku 于是 是该年度分配在低负荷下生产的机器数。 kkux k=2 k=3 k=4 k=5 1k1x2x3x4x5x 1u2u3u4u5u编辑ppt18记 表示第k年到第五年末的最高总产量)(kkxfk5时)(58max)(55505555uxuxfxu5550835max55xuxxu最优点最优点5*5xu 这说明第5年初要把全部完好机器投入高负荷下生产。 k4时4444452 . 09 . 0)(9 . 07 . 0uxuxux因因为为)()(58max)(5544404444xfuxuxfxu所所以以)2 . 09 . 0(835max4444044uxuxxu编辑

12、ppt1944406 .134 . 12 .12max44xuxxu最优点最优点4*4xu k3时3333342 . 09 . 0)(9 . 07 . 0uxuxux因因为为)()(58max)(4433303333xfuxuxfxu所以所以)2 . 09 . 0(6 .1335max3333033uxuxxu33305 .1728. 024.17max33xuxxu最优点最优点3*3xu 编辑ppt20k2时2222232 . 09 . 0)(9 . 07 . 0uxuxux因因为为)()(58max)(3322202222xfuxuxfxu所所以以)2 . 09 . 0(5 .1735ma

13、x2222022uxuxxu22208 .205 . 075.20max22xuxxu最优点最优点0*2uk1时10001x因为因为1111122 . 09 . 0)(9 . 07 . 0uxuxux)()(58max)1000(221110111xfuxufxu所所以以)2 . 09 . 0(8 .2035max1111011uxuxxu编辑ppt21)2 . 09 . 0(8 .2035max1111011uxuxxu16. 172.23max11011uxxu2370010007 .237 .231x最优点最优点0*1u 由此知五年最高总产量为23700再由上递推知 10001x0*1u

14、9002x0*2u8103x810*3u5674x567*4u3975x397*5u编辑ppt22高负荷生产的完好机器的最优组合简记：397,567,810, 0, 0,*5*2*1uuu 这表明在前两年年初全部完好机器投入低负荷生产，后三年年初全部完好机器投入高负荷生产。 第五年末的完好机器数为 0.7397278台 在此例中，我们仅考虑最高产量，而未考虑五年计划后的完好机器数。 问题1：若计划为n个年度，怎样决策？ 问题2：若要求在第5年末完好的机器数为500台，如何决策使5年总产量最高？ 编辑ppt23这类问题称为固定终端问题1x2x3x4x5x5006x1u2u3u4u5u由上讨论知：

15、状态转移方程仍为 ) 1 (2 . 09 . 0)(9 . 07 . 01kkkkkkuxuxux 表示第k年初开始到第5年末的最高产量，称为最优值函数，其递推关系为 )(kkxf)2()2 . 09 . 0()(58(max)(10kkkkkkxukkuxfuxuxfkkk=1,2,3,4,50)(66xf编辑ppt24其中 为第k段的效益值，即第k年的产量。 )(58),(kkkkkkuxuuxy 表示第6年的产量不计算在总产量之内，故为零。 0)(66xf由假设 ， 5006x又根据(1)得 5562 . 09 . 0uxx一般地，当 确定后，选择 来确定 ，现在 已经给定，故 已经没有

16、选择余地，它由 和 确定。 5x5u6x6x5u6x5x于是25005 . 455 . 45655xxxu编辑ppt25由(2)可知035max)(5505555uxxfxu)25005 . 4(3555xx75005 .185x)2 . 09 . 0(35max)(4454404444uxfuxxfxu7500)2 . 09 . 0(5 .1835max4444044uxuxxu.max750070652144044uxxu75007 .214x最优值 0*4u编辑ppt267500)2 . 09 . 0(7 .2135max)(333303333uxuxxfxu75005 .243x最优值 0*3u类似地得到 75007 .21)(222xxf0*2u7