动态规划模型[稻谷书苑]

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

2、线路，最后求得从 到 的最短线路。 6 A 0 A 6 A 2优质课 k6时： 设 表示由 到 的最短距离； )( 56 Af 5 A 6 A 设 表示由 到 的最短距离； )( 56 Bf 5 B 6 A 显然 4)( 56 Af3)( 56 Bf k5时： 如果 表示由 到 的最短距离。 )( 45 Af 4 A 6 A min)( 45 Af )(),( )(),( 5654 5654 BfBAd AfAAd 7 35 43 min （以下类似定义）（以下类似定义） 3优质课 最短线路是 654 AAA )( 45 Bf 5 32 45 min )(),( )(),( min 56545

3、 56545 BfBBd AfABd 最短线路是 654 ABB 9 36 46 min )(),( )(),( min)( 56545 56545 45 BfBCd AfACd Cf 最短线路是 654 ABC 4优质课 k4时： 7 52 72 min )(),( )(),( min)( 45434 45434 34 BfBAd AfAAd Af 最短线路是 6543 ABBA 6 92 51 min )(),( )(),( min)( 45434 45434 34 CfCBd BfBBd Bf 最短线路是 6543 ABBB 5优质课 8 93 53 min )(),( )(),( mi

4、n)( 45434 45434 34 CfCCd BfBCd Cf 最短线路是 6543 ABBC k3时： 13 68 76 min )(),( )(),( min)( 34323 34323 23 BfBAd AfAAd Af 最短线路是 65432 ABBAA 6优质课 10 65 73 min )(),( )(),( min)( 34323 34323 23 BfBBd AfABd Bf 最短线路是 65432 ABBAB 9 83 63 min )(),( )(),( min)( 34323 34323 23 CfCCd BfBCd Cf 最短线路是 65432 ABBBC 7优质课

5、 12 84 68 min )(),( )(),( min)( 34323 34323 23 CfCDd BfBDd Df 最短线路是 65432 ABBCD k2时： 13 96 103 131 min )(),( )(),( )(),( min)( 23212 23212 23212 12 CfCAd BfBAd AfAAd Af 最短线路是 654321 ABBABA 8优质课 16 126 97 108 min )(),( )(),( )(),( min)( 23212 23212 23212 12 DfDBd CfCBd BfBBd Bf 最短线路是 出发点只有 0 A 18 163

6、 135 min )(),( )(),( min)( 12101 12101 01 BfBAd AfAAd Af 最短线路是 6543210 ABBABAA 最短距离为18。 654321 ABBBCB 9优质课 说明 1)此例揭示了动态规划的基本思想。 2)动态规划方法比穷举法（48种）大大节省了计算量。 3)计算结果不仅得到了 到 的最短线路和最短距 离，而且得到了其它各点到 的最短线路和最短距离， 这对于很多实际问题来说是很有用处的。 0 A 6 A 6 A 动态规划法求解的数学描述 讨论动态规划中最优目标函数的建立，一般有下 列术语和步骤： 、阶段 用动态规划求解多阶段决策系统时，要根

7、据具体 情况，将系统适当地分成若干个阶段，以便分若干个 阶段求解，描述阶段的变量称为阶段变量。 10优质课 上例分六个阶段，是一个六阶段的决策过程。 例中由系统的最后阶段向初始阶段求最优解的过程 称为动态规划的逆推解法。 、状态 状态表示系统在某一阶段所处的位置或状态。 上例中第一阶段有一个状态， ；即即 0 A 第二阶段有两个状态， ；即即, 11 BA 过程的状态可用状态变量 来描述，某个阶 段所有可能状态的全体可用状态集合来描述， k x 01 AS 如如, 22223112 DCBASBAS 11优质课 、决策 某一阶段的状态确定之后，从该状态演变到下一 阶段某一状态所作的选择称为决策

8、。描述决策的变 量称为决策变量 如上例中在第k阶段用 表示处于 状 态时的决策变量。 )( kk xu k x 决策变量限制的范围称为允许决策集合。 用 表示第k阶段从 出发的决策集合。 )( kk xD k x 、策略 由每阶段的决策 (i1,2,n)组成的决策 函数序列称为全过程策略或简称策略，用p表示， )( ii xu )(,),(),()( 22111nn xuxuxuxP即即 12优质课 由系统的第k个阶段开始到终点的决策过程称 为全过程的后部子过程，相应的策略称为后部子 过程策略。 用 表示k子过程策略， )( kk xP )(,),(),()( 11nnkkkkkk xuxux

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

10、k u ),( kkk uxW 、指标函数 指标函数是系统执行某一策略所产生的效益的数 量表示，根据不同的实际问题，效益可以是利润、 距离、产量或资源的耗量等。 14优质课 指标函数可以定义在全过程上，也可以定义 在后部子过程上。指标函数往往是各阶段效益的 某种和式，取最优策略时的指标函数称为最优策 略指标。 如上例中， 表示从 出发到终点 的 最优策略指标。 )( 45 Af 4 A 6 A 上例中 显然为零，称它为边值条件。 )( 66 Af 而动态规划的求解就是对kn,n-1,2,1逐级 求出最优策略指标的过程。 、动态规划的基本方程 )(),(min)( 11 kkkkk u kk x

11、fuxWxf k 15优质课 例2：机器负荷分配问题 某种机器可以在高低两种负荷下生产，年产量 与年初投入生产的机器数有关。在高负荷下生产时， 年产量 ，式中 为投入生产的机器数， 年终的完好机器数为 ，称系数0.7为机器完 好率。在低负荷下生产时，年产量 ，式中 为投入生产的机器数，机器完好率为0.9，设开始 时，完好的机器数为 台，要求制定一个 五年计划，在每年开始时决定如何重新分配完好机 器在两种不同负荷下工作的数量，使五年的总产量 最高。 11 8us 1 u 1 7 . 0 u 22 5us 2 u 1000 1 x 16优质课 解：此问题与上例类似。 设阶段变量k表示年度； 状态变

12、量 是第k年初拥有的完好机器数（也 是第k-1年度末完好机器数）。 k x 决策变量 规定为第k年度中分配在高负荷 下生产的机器数。 k u 于是 是该年度分配在低负荷下生产的 机器数。 kk ux k=2 k=3 k=4 k=5 1k 1 x 2 x 3 x4 x 5 x 1 u 2 u 3 u 4 u 5 u 17优质课 记 表示第k年到第五年末的最高总产量)( kk xf k5时 )(58max)( 555 0 55 55 uxuxf xu 555 0 835max 55 xux xu 最优点最优点 5 * 5 xu 这说明第5年初要把全部完好机器投入高负荷下生产。 k4时 444445

13、 2 . 09 . 0)(9 . 07 . 0uxuxux因为因为 )()(58max)( 55444 0 44 44 xfuxuxf xu 所所以以 )2 . 09 . 0(835max 4444 0 44 uxux xu 18优质课 444 0 6 .134 . 12 .12max 44 xux xu 最优点最优点 4 * 4 xu k3时 333334 2 . 09 . 0)(9 . 07 . 0uxuxux因为因为 )()(58max)( 44333 0 33 33 xfuxuxf xu 所所以以 )2 . 09 . 0(6 .1335max 3333 0 33 uxux xu 333

14、 0 5 .1728. 024.17max 33 xux xu 最优点最优点 3 * 3 xu 19优质课 k2时 222223 2 . 09 . 0)(9 . 07 . 0uxuxux因为因为 )()(58max)( 33222 0 22 22 xfuxuxf xu 所所以以 )2 . 09 . 0(5 .1735max 2222 0 22 uxux xu 222 0 8 .205 . 075.20max 22 xux xu 最优点最优点 0 * 2 u k1时1000 1 x因为因为 111112 2 . 09 . 0)(9 . 07 . 0uxuxux )()(58max)1000( 2

15、2111 0 1 11 xfuxuf xu 所所以以 )2 . 09 . 0(8 .2035max 1111 0 11 uxux xu 20优质课 )2 . 09 . 0(8 .2035max 1111 0 11 uxux xu 16. 172.23max 11 0 11 ux xu 2370010007 .237 .23 1 x 最优点最优点0 * 1 u 由此知五年最高总产量为23700 再由上递推知 1000 1 x0 * 1 u 900 2 x0 * 2 u 810 3 x810 * 3 u 567 4 x 567 * 4 u 397 5 x 397 * 5 u 21优质课 高负荷生产

16、的完好机器的最优组合简记： 397,567,810, 0, 0, * 5 * 2 * 1 uuu 这表明在前两年年初全部完好机器投入低负荷 生产，后三年年初全部完好机器投入高负荷生产。 第五年末的完好机器数为 0.7397278台 在此例中，我们仅考虑最高产量，而未考虑五 年计划后的完好机器数。 问题1：若计划为n个年度，怎样决策？ 问题2：若要求在第5年末完好的机器数为500台， 如何决策使5年总产量最高？ 22优质课 这类问题称为固定终端问题 1 x 2 x 3 x 4 x 5 x 500 6 x 1 u 2 u 3 u 4 u 5 u 由上讨论知： 状态转移方程仍为 ) 1 (2 . 0

17、9 . 0)(9 . 07 . 0 1kkkkkk uxuxux 表示第k年初开始到第5年末的最高产量， 称为最优值函数，其递推关系为 )( kk xf )2()2 . 09 . 0()(58(max)( 1 0 kkkkkk xu kk uxfuxuxf kk k=1,2,3,4,5 0)( 66 xf23优质课 其中 为第k段的效益值，即第k年的产量。 )(58),( kkkkkk uxuuxy 表示第6年的产量不计算在总产量之 内，故为零。 0)( 66 xf 由假设 ， 500 6 x又根据(1)得 556 2 . 09 . 0uxx 一般地，当 确定后，选择 来确定 ，现 在 已经给

18、定，故 已经没有选择余地，它由 和 确定。 5 x 5 u 6 x 6 x 5 u 6 x 5 x 于是 25005 . 455 . 4 5655 xxxu 24优质课 由(2)可知 035max)( 55 0 55 55 uxxf xu )25005 . 4(35 55 xx 75005 .18 5 x )2 . 09 . 0(35max)( 44544 0 44 44 uxfuxxf xu 7500)2 . 09 . 0(5 .1835max 4444 0 44 uxux xu .max7500706521 44 0 44 ux xu 75007 .21 4 x 最优值 0 * 4 u 25优质课 7500)2 . 09 . 0(7 .2135max)( 3333 0 33 33 uxuxxf xu 75005 .24 3 x 最优值 0 * 3 u 类似地得到 75007 .21)( 222 xxf0 * 2 u 7