运筹(第八章动态规划)

1、2021-7-101 运筹学运筹学 OPERATIONS RESEARCH 2021-7-102 第八章第八章 动态规划动态规划 n 多阶段决策最优化问题举例多阶段决策最优化问题举例 n基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理 n离散确定性动态规划求解离散确定性动态规划求解 n离散随机性动态规划求解离散随机性动态规划求解 n一般数学规划模型的动态规划解法一般数学规划模型的动态规划解法 2021-7-103 1 1多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例 例例1 1 最短路径问题最短路径问题 下图表示从起点下图表示从起点A A到终点到终点E E之间各点的距离。

2、求之间各点的距离。求A A到到E E 的最短路径。的最短路径。 B A C B D B C D E C 4 1 2 3 1 2 3 1 2 3 2 2 1 6 4 7 2 4 8 3 8 6 7 5 6 1 10 6 4 3 75 1 2021-7-104 用穷举法的计算量用穷举法的计算量: : 如果从如果从A A到到E E的站点有的站点有k k个，除个，除A A、E E之外每站有之外每站有3 3个位个位 置则总共有置则总共有3 3k-1 k-1 2 2条路径；条路径； 计算各路径长度总共要进行计算各路径长度总共要进行 (k+1) 3(k+1) 3k-1 k-1 2 2次加法次加法 以及以及3

3、 3k-1 k-1 2-12-1次比较。随着次比较。随着 k k 的值增加时，需要的值增加时，需要 进行的加法和比较的次数将迅速增加；进行的加法和比较的次数将迅速增加； 例如例如 k=20k=20时，加法次数为时，加法次数为 4.25508339662274.2550833966227101015 15 次，比较次，比较 1.37260754729771.3726075472977101014 14 次。 次。 若用若用1 1亿次亿次/ /秒的计算机计算需要约秒的计算机计算需要约508508天。天。 2021-7-105 讨论：讨论： 1 1、以上求从、以上求从A A到到E E的最短路径问题，

4、可以转化为四个的最短路径问题，可以转化为四个 性质完全相同，但规模较小的子问题，即分别从性质完全相同，但规模较小的子问题，即分别从 D Di i 、C Ci i、B Bi i、A A到到E E的最短路径问题。的最短路径问题。 第四阶段：第四阶段：两个始点两个始点D D1 1和和D D2 2，终点只有一个；，终点只有一个； 表表-1-1 分析得知：从分析得知：从D D1 1和和D D2 2到到E E的最短路径唯一。的最短路径唯一。 阶段4 本阶段始点 （状态） 本阶段各终点（决策）到E的最短距离本阶段最优终点 （最优决策) E D1 D2 10 6 10 6 E E 2021-7-106 第三阶

5、段第三阶段：有三个始点有三个始点C C1 1，C C2 2，C C3 3，终点有，终点有D D1 1，D D2 2， 对始点和终点进行分析和讨论分别求对始点和终点进行分析和讨论分别求C C1 1，C C2 2，C C3 3到到 D D1 1，D D2 2 的最短路径问题：的最短路径问题： 表-2 分析得知：如果经过分析得知：如果经过C C1 1， ，则最短路为 则最短路为C C1 1-D-D2 2-E-E； 如果经过如果经过C C2 2， ，则最短路为 则最短路为C C2 2-D-D2 2-E-E； 如果经过如果经过C C3 3，则最短路为，则最短路为C C3 3-D-D1 1-E-E。 阶段

6、3 本阶段始点 （状态） 本阶段各终点（决策） 到E的最短距离 本阶段最优终点 （最优决策) D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=11 6+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D1 2021-7-107 第二阶段第二阶段：有有4 4个始点个始点B B1 1,B,B2 2,B,B3 3,B,B4 4，终点有，终点有C C1 1,C,C2 2,C,C3 3。 对始点和终点进行分析和讨论分别求对始点和终点进行分析和讨论分别求B B1 1,B,B2 2,B,B3 3,B,B4 4到到 C C1 1,C,C2 2,C,C3 3 的最短路

7、径问题：的最短路径问题： 表-3 分析得知：如果经过分析得知：如果经过B B1 1，则走，则走B B1 1-C-C2 2-D-D2 2-E-E； 如果经过如果经过B B2 2，则走，则走B B2 2-C-C3 3-D-D1 1-E-E； 如果经过如果经过B B3 3，则走，则走B B3 3-C-C3 3-D-D1 1-E-E； 如果经过如果经过B B4 4，则走，则走B B4 4-C-C3 3-D-D1 1-E-E。 阶段2 本阶段始点 （状态） 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点（最优决策) C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+

8、12=16 7+12=19 1+11=12 7+11=18 8+11=19 5+11=16 6+11=17 2+11=13 3+11=14 1+11=12 12 13 14 12 C2 C3 C3 C3 2021-7-108 第一阶段：第一阶段：只有只有1 1个始点个始点A A，终点有，终点有B B1 1,B,B2 2,B,B3 3,B,B4 4 。对。对 始点和终点进行分析和讨论分别求始点和终点进行分析和讨论分别求A A到到B B1 1,B,B2 2,B,B3 3,B,B4 4的的 最短路径问题：最短路径问题： 表10-4 最后，可以得到：最后，可以得到： 从从A A到到E E的最短路径为的

9、最短路径为A A B B4 4 C C3 3 D D1 1 E E 阶段1 本阶段始 点(状态) 本阶段各终点（决策） 到E的最 短距离 本阶段最优终 点(最优决策) B1 B2 B3 B4 A4+12=16 3+13=163+14=172+12=14 12 B4 2021-7-109 以上计算过程及结果，可用图以上计算过程及结果，可用图2 2表示，可以看到，以表示，可以看到，以 上方法不仅得到了从上方法不仅得到了从A A到到D D的最短路径，同时，也得的最短路径，同时，也得 到了从图中任一点到到了从图中任一点到E E的最短路径。的最短路径。 以上过程，仅用了以上过程，仅用了2222次加法，计

10、算效率远高于穷举次加法，计算效率远高于穷举 法。法。 BA CB D B C D E C 4 1 2 3 1 2 3 1 2 3 3 2 1 6 4 7 2 48 3 8 6 7 5 1 6 10 6 0 10 6 12 11 11 12 13 14 14 4 B 12 751 2 2021-7-1010 例例2 2 资源分配问题资源分配问题 设有某种机器数台，用于完成两类工作设有某种机器数台，用于完成两类工作A A，B B。由于。由于 机器使用后有一定的损坏率，所以每年初的机器数机器使用后有一定的损坏率，所以每年初的机器数 量是变化的；量是变化的；A A、B B两项工作产生的收益也不同。如两

11、项工作产生的收益也不同。如 何合理的分配机器的使用，可使得三年的总收益最何合理的分配机器的使用，可使得三年的总收益最 大大? ? 假设第假设第k k年年初完好机器数是年年初完好机器数是S SK K， ，用于 用于A A生产的生产的 机器数是机器数是X XK K， ，则用于 则用于B B生产的机器数是（生产的机器数是（S SK K- X- XK K）；）； 用于用于A A工作的设备的完好率是：工作的设备的完好率是：a%a%，用于，用于B B工作工作 的设备的完好率是：的设备的完好率是：b%b%。则下一年初的完好机器数。则下一年初的完好机器数 是是 S SK+1 K+1= a% X = a% XK

12、 K+ b% + b% （S SK K- X- XK K） 第第k k年的收益：年的收益： h(X h(XK K)+ g(S)+ g(SK K- X- XK K) ) 2021-7-1011 例例3 3 背包问题背包问题 设有设有n n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i i种物品每种物品每 件重量为件重量为w wi i公斤，每件价值公斤，每件价值c ci i元。现有一只可装载重元。现有一只可装载重 量为量为W W公斤的背包，求各种物品应各取多少件放入背公斤的背包，求各种物品应各取多少件放入背 包，使背包中物品的价值最高。包，使背包中物品的价值最高。 这个问题可以用整

13、数规划模型来描述。设这个问题可以用整数规划模型来描述。设x xi i为第为第I I 种物品装入背包的件数（种物品装入背包的件数（i i =1, 2, , =1, 2, , n n），背包），背包 中物品的总价值为中物品的总价值为z z，则，则 Max z = cMax z = c1 1x x1 1+c+c2 2x x2 2+ +c+ +cn nx xn n s.t. w s.t. w1 1x x1 1+w+w2 2x x2 2+w+wn nx xn nW W x x1 1, x, x2 2, , x, , xn n 0 0 且为整数。且为整数。 2021-7-1012 动态规划动态规划是用来解

14、决是用来解决多阶段决策多阶段决策过程最优化的一种过程最优化的一种 方法。方法。 多阶段决策：多阶段决策：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式； 系统的动态过程可以按照时间等进程分为状态系统的动态过程可以按照时间等进程分为状态 相互联系相互联系 而又相互区别的各个阶段；而又相互区别的各个阶段； 每个阶段都要进行决策每个阶段都要进行决策, ,目的是使整个过程的目的是使整个过程的 决策达到最优效果决策达到最优效果 多阶段决策求解思路：多阶段决策求解思路： 将多阶段决策问题（将多阶段决策问题（n n阶段）分解成阶段）分解成n n个具有递推关个具有递推关 系的单阶段决策问题，进行正

15、推或逆推计算。系的单阶段决策问题，进行正推或逆推计算。 2021-7-1013 2.1 2.1 基本概念基本概念 1 1、阶段、阶段k k：表示决策顺序的离散的量，阶段可以按表示决策顺序的离散的量，阶段可以按 时间或空间划分。时间或空间划分。( (顺序编号法、逆序编号法）顺序编号法、逆序编号法） 2 2、状态、状态s sk k：反应前一阶段决策的结果，又是本阶段反应前一阶段决策的结果，又是本阶段 作决策的依据和出发点（能确定地表示决策过程作决策的依据和出发点（能确定地表示决策过程 当前特征的量）。状态可以是数量，也可以是字当前特征的量）。状态可以是数量，也可以是字 符，数量状态可以是连续的，也

16、可以是离散的。符，数量状态可以是连续的，也可以是离散的。 2 2基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理 2021-7-1014 3 3、决策、决策x xk k：从某一状态向下一状态过渡时所做的选从某一状态向下一状态过渡时所做的选 择。决策是所在状态的函数，记为择。决策是所在状态的函数，记为x xk k(s(sk k) )。 决策允许集合决策允许集合D Dk k(s(sk k) )：在状态在状态s sk k下，允许采取决策下，允许采取决策 的全体的全体 4 4、策略、策略Pk,n(sk)Pk,n(sk)：从第从第k k阶段开始到最后第阶段开始到最后第n n阶段的阶段的 决策

17、序列，称决策序列，称k k子策略。子策略。P1,n(s1)P1,n(s1)即为全过程策略。即为全过程策略。 2021-7-1015 5 5、状态转移方程、状态转移方程: : S Sk+1 k+1=T =Tk k(S(Sk k, X, Xk k) )：某一状态以及：某一状态以及 该状态下的决策，与下一状态之间的函数关系。该状态下的决策，与下一状态之间的函数关系。 6 6、阶段指标函数、阶段指标函数V Vk k(S(Sk k, X, Xk k) )：从状态从状态S Sk k出发，选择决出发，选择决 策策X Xk k所产生的第所产生的第k k阶段指标。阶段指标。 过程指标函数过程指标函数V Vk,n

18、 k,n(S (Sk k；X Xk k, X, Xk+1 k+1, X , Xn n) )：从状态从状态S Sk k 出发，选择决策出发，选择决策X Xk k, X, Xk+1 k+1, , Xn , , Xn所产生的过程指所产生的过程指 标。标。 2021-7-1016 动态规划要求过程指标具有可分离性动态规划要求过程指标具有可分离性，即即 V Vk,n k,n(s (sk k, x, xk k, x, xk+1 k+1, , x , , xn n) = V) = Vk k(s(sk k, x, xk k)+V)+Vk+1 k+1(s (sk+1 k+1, x , xk+1 k+1, , x

19、 , , xn n) ) 称指标具有称指标具有可加性可加性，或或 V Vk,n k,n(s (sk k, x, xk k, x, xk+1 k+1, , x , , xn n) = v) = vk k(s(sk k, x, xk k) )V Vk+1 k+1(s (sk+1 k+1, x , xk+1 k+1, , x , , xn n) ) 称指标具有称指标具有可乘性可乘性。 2.2 2.2 基本方程基本方程 最优指标函数最优指标函数f fk k(s(sk k) )：从状态从状态s sk k出发，对所有的策略出发，对所有的策略 P Pk,n k,n，过程指标 ，过程指标V Vk,n k,n的

20、最优值，即 的最优值，即 ),()( , )( nkknk sDx kk PsVsf opt kkk 2021-7-1017 对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为 上式中上式中“opt”opt”表示表示“max”max”或或“min”min”。 对于可乘性指标函数，上式可以写为对于可乘性指标函数，上式可以写为 以上式子称为动态规划最优指标的递推方程，是动以上式子称为动态规划最优指标的递推方程，是动 态规划的态规划的基本方程基本方程。 终端条件终端条件：为了使以上的递推方程有递推的起点，：为了使以上的递推方程有递推的起点， 必须要设定最优指标的终端条件，一般最后一个状

21、必须要设定最优指标的终端条件，一般最后一个状 态态n+1n+1下最优指标下最优指标f fn+1 n+1(s (sn+1 n+1) = 0 ) = 0。 n, 2 , 1k)s (f)x,s (v)s (f 1k1kkkk )s (Dx kkopt kkk n, 2 , 1k)s (f)x,s (v)s (f 1k1kkkk )s (Dx kkopt kkk 2021-7-1018 2.3 2.3 最优化原理最优化原理 作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质： 不管在此最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状 态和决策如何，对该状态来说，以

22、后的所有决态和决策如何，对该状态来说，以后的所有决 策必定构成最优子策略。就是说策必定构成最优子策略。就是说，最优策略的最优策略的 任意子策略都是最优的。任意子策略都是最优的。 2021-7-1019 例例1 某警卫部门共有某警卫部门共有9支巡逻队，负责三个要害部位支巡逻队，负责三个要害部位A、B、 C的警卫巡逻。每个部位分别可派出的警卫巡逻。每个部位分别可派出24支巡逻队，并且支巡逻队，并且 由于派出的队伍数量不同，各部位预期的损失有差别，由于派出的队伍数量不同，各部位预期的损失有差别， 详见下表。各部位应各分派多少支巡逻队可是预期的总详见下表。各部位应各分派多少支巡逻队可是预期的总 损失最

23、小。请用动态规划方法求解。损失最小。请用动态规划方法求解。 3 3离散确定性动态规划模型求解离散确定性动态规划模型求解 部位 巡逻队数 预期 损失 ABC 2183824 3143522 4103121 2021-7-1020 解：解：设将向三个部位设将向三个部位A A，B B，C C派巡逻队作为三个阶段，派巡逻队作为三个阶段，K=1K=1， 2 2，3 3。 决策变量决策变量 表示向第表示向第K K个部位派遣的巡逻队数。个部位派遣的巡逻队数。 状态变量状态变量 表示第表示第K K个阶段时可供派遣的巡逻队数量。个阶段时可供派遣的巡逻队数量。 状态转移方程：状态转移方程： 阶段指标函数：阶段指标

24、函数： 派遣派遣 支巡逻队时第支巡逻队时第K K阶段产阶段产 生的预期损失；生的预期损失； 过程指标函数：过程指标函数： 第第K K阶段到第阶段到第3 3阶段的预期损失。阶段的预期损失。 最优指标函数：最优指标函数： k x k s kkk xss 1 )( kk xp k x 3 , 13 , )( kkkk VxpV )()(min)( 11 )( kkKK SDx kk sfXPsf Kk 2021-7-1021 逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，给时，给C C派巡逻队，派巡逻队， ， 0)( 44 sf 5 , 4 , 3 , 2)( 3 sD4 , 3 , 2

25、 3 x 234 2 24 - 242 3 24 22 - 223 4 24 22 21 214 5 24 22 21 214 3 x 3 s )( 33 sf 3 * x )()(min)( 443333 sfxpsf )x,s (v 333 2021-7-1022 当当K=2K=2时，给时，给B B派巡逻队，派巡逻队， 23 4 5 38+22 35+24 - 593 6 38+21 35+22 31+24 554 7 38+21 35+21 31+22 534 )()(min)( 2232222 xsfxpsf 7 , 6 , 5)( 2 sD4 , 3 , 2 2 x 2 x 2 s

26、)( 22 sf 2 * x )()( 22322 xsfxp 2021-7-1023 当当K=1K=1时，给时，给A A派巡逻队，派巡逻队， )()(min)( 1121111 xsfxpsf 9)( 1 sD4 , 3 , 2 1 x 23 4 9 18+53 14+55 10+59 693，4 1 x 1 s )( 11 sf 1 * x )()( 11211 xsfxp 最优方案最优方案： A A派派3 3支巡逻队，支巡逻队，B B派派4 4支巡逻队，支巡逻队，C C派派2 2支巡逻队；支巡逻队； 或：或：A A派派4 4支巡逻队，支巡逻队，B B派派3 3支巡逻队，支巡逻队，C C派

27、派2 2支巡逻队支巡逻队 2021-7-1024 解解2 2：顺序解法：顺序解法 设将向三个部位设将向三个部位A A，B B，C C派巡逻队作派巡逻队作 为三个阶段，为三个阶段，K=1K=1，2 2，3 3。 决策变量决策变量 表示向第表示向第K K个部位派遣的巡逻队数。个部位派遣的巡逻队数。 状态变量状态变量 表示前表示前K-1K-1个阶段可派遣的巡逻队数个阶段可派遣的巡逻队数 量。量。 状态转移方程：状态转移方程： ， 阶段指标函数：阶段指标函数： 派遣派遣 支巡逻队时第支巡逻队时第K K 阶段产生的预期损失；阶段产生的预期损失； 最优指标函数：前最优指标函数：前K K个阶段的最优目标个阶

28、段的最优目标 k x k s kkk xss 1 )( kk xp k x )()(min)( 1 )( 1kkKK SDx kk sfXPsf Kk )( 1kkk xss 2021-7-1025 顺序解法：顺序解法： 边界条件边界条件 当当K=1K=1时，给时，给A A派巡逻队，派巡逻队， ， 0)( 10 sf 5 , 4 , 3 , 2)( 2 sD4 , 3 , 2 1 x 234 2 18 182 3 18 14 143 4 18 14 10 104 5 18 14 10 104 1 x 2 s )( 21 sf 1 * x )()( 1011 sfxp 2021-7-1026 当

29、当K=2K=2时，给时，给B B派巡逻队，派巡逻队， 7 , 6 , 5)( 3 sD4 , 3 , 2 2 x 23 4 5 38+14 35+18 522 6 38+10 35+14 31+18 482 7 38+10 35+10 31+14 533，4 2 x 3 s )( 32 sf 2 * x )()( 23111 xsfxp )()(min)( 212232 sfxpsf 2021-7-1027 当当K=3K=3时，给时，给C C派巡逻队，派巡逻队， )()(min)( 2223343 xsfxpsf 9)( 4 sD4 , 3 , 2 3 x 23 4 9 24+45 22+48

30、 21+52 692 3 x 4 s )( 43 sf 3 * x )()( 3233 sfxp 最优方案最优方案： A A派派3 3支巡逻队，支巡逻队，B B派派4 4支巡逻队，支巡逻队，C C派派2 2支巡逻队；支巡逻队； 或：或：A A派派4 4支巡逻队，支巡逻队，B B派派3 3支巡逻队，支巡逻队，C C派派2 2支巡逻队支巡逻队 2021-7-1028 例例2 2 资源分配问题资源分配问题 (P208(P208例例5 5） 假设第假设第k k年年初完好机器数是年年初完好机器数是S SK K， ，用于 用于A A生产的机器生产的机器 数是数是X XK K， ，则用于 则用于B B生产的

31、机器数是（生产的机器数是（S SK K - X - XK K）；）； 用于用于A A工作的设备的完好率是：工作的设备的完好率是： ，用于，用于B B工作的工作的 设备的完好率是：设备的完好率是：0.90.9。则下一年初的完好机器数。则下一年初的完好机器数 是是 S SK+1 K+1= X = XK K+0.9+0.9（S SK K- X- XK K） 第第k k年的收益：年的收益： 10X10XK K+ 7(S+ 7(SK K- X- XK K) ) 3 2 a 3 2 ,7)(10)(xxhxxg 0)( 44 sf边界条件：边界条件： )()(710max)( 11 0 kkkkk sx

32、kk sfxsxsf kk 2021-7-1029 0)( 44 sf逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时时，第三年初分配机器，第三年初分配机器 台生产台生产A A， 台生台生 产产B B ， 3 x 33 xs 33 344333 0 33 10)()(710max)( 33 sx ssfxsxsf sx 当当K=2K=2时时，第二年初分配机器，第二年初分配机器 台生产台生产A A， 台台 生产生产B B， 2 x 22 xs 22222 sx0 222222 sx0 33222 sx0 22 sxs 3 2 16s16x 3 2 max )xs ( 10 9 x 3 2

33、 10)xs (7x10max )s (f)xs (7x10max)s (f 22 22 22 2021-7-1030 当当K=1K=1时时，第，第1 1年初分配机器年初分配机器 台生产台生产A A， 台台 生产生产B B ， 1 x 11 xs 022009 . 02200max )( 10 9 3 2 10)(710max )()(710max)( 11 1000 111111 0 22111 0 11 1 11 11 xx xsxxsx sfxsxsf x sx sx 100 1 s 最优方案最优方案： 第一年所有机器第一年所有机器100100台用于生产台用于生产B B， 第二年初完好机

34、器第二年初完好机器9090台；台； 第二年所有机器第二年所有机器9090台用于生产台用于生产A A， 第三年初完好机器第三年初完好机器6060台；台； 第三年所有机器第三年所有机器6060台用于生产台用于生产A A， 第四年初完好机器第四年初完好机器4040台。台。 2021-7-1031 4 4离散随机动态规划模型求解离散随机动态规划模型求解 随机动态规划：随机动态规划：状态转移规律不定，在给定的状态状态转移规律不定，在给定的状态 和决策下，下一阶段到达的状态是具有确定概率分和决策下，下一阶段到达的状态是具有确定概率分 布的随机变量。布的随机变量。 第第k+1阶段阶段 可能状态可能状态 Sk

35、Xk n 2 1 第第k阶段状态阶段状态决策决策 P1，C1 P2，C2 Pn，Cn P Pi i：在决策：在决策X Xk k下出现状态下出现状态i i的概率的概率 C Ci i：在决策：在决策X Xk k下出现状态下出现状态i i时的指时的指 标函数标函数 2021-7-1032 随机动态规划中，对指标函数进行优化时，要根据随机动态规划中，对指标函数进行优化时，要根据 各阶段的各阶段的期望效益期望效益进行优化。进行优化。 基本方程改写为：基本方程改写为： )(),()( 11 )( kkkk SDx kk sfxsvEoptsf Kk 例：例：P210P210，例，例6 6 解：解： 阶段变

36、量阶段变量K K， 每月投产一批作为一个阶段，每月投产一批作为一个阶段，K=1K=1，2 2， 3 3。 状态变状态变 量量 ：表示第：表示第K K阶段所拥有的合格样品数，有两阶段所拥有的合格样品数，有两 种可能状态。种可能状态。 表示有一台以上的合格品；表示有一台以上的合格品； 表示没有一台合格品。表示没有一台合格品。 k s 0 k s 1 k s 2021-7-1033 决策变量决策变量 ：表示第：表示第K K个阶段决定投产的数量个阶段决定投产的数量。 k x 状态转移律状态转移律： k k x k x k sp sp 3 2 1)0( 3 2 ) 1( 1 1 阶段指标函数：阶段指标函

37、数： 0, 0 1,100250 ),( k kk kk s sx xsc 最优指标函数最优指标函数 ：表示第表示第K K阶段在阶段在 状态下，状态下， 做决策做决策 时，到最后一个阶段的最小期望费用。时，到最后一个阶段的最小期望费用。 )( kk sf k s k x 2021-7-1034 Sk=1 Xk 第第k阶段状态阶段状态 决策决策 Sk=0 Sk+1=1 Sk+1=0 K X 3 2 K X 3 2 1 第第k+1阶段状态阶段状态 )(),()( 11 )( kkkk SDx kk sfxscEoptsf Kk 易知：易知： 4 , 3 , 2, 0)0(ksf kk )0( 3

38、2 1 ) 1( 3 2 ),( min) 1( 11 11 )( kk x kk x kk SDx kk sf sfxsc sf k k Kk 2021-7-1035 逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，第三阶段之后的最小期望费用时，第三阶段之后的最小期望费用 0)0( 33 sf ) 1( 3 2 ),(min) 1( 4433 )( 33 3 33 sfxscsf x SDx 1500) 1( 44 sf 0 1 2 3 4 5 00 00 11500 1350 1117 994 946 9489464 3 x 3 s )( 33 sf 3 * x ) 1( 3 2

39、 ),( 4433 3 sfxsc x 1500 3 2 100250) 1( 3 2 ),( 33 34433 xx xsfxsc 1500) 1( 44 sf 2021-7-1036 当当K=2K=2时，第二阶段之后的最小期望费用时，第二阶段之后的最小期望费用 0)0( 22 sf ) 1( 3 2 ),(min) 1( 3322 )( 22 2 22 sfxscsf x SDx 0 1 2 3 4 5 00 00 1946 981 870 830 837 8303 2 x 2 s )( 22 sf 2 * x ) 1( 3 2 ),( 3322 2 sfxsc x 946) 1( 33

40、sf 946 3 2 100250) 1( 3 2 ),( 22 23322 xx xsfxsc 2021-7-1037 当当K=1K=1时，第一阶段之后的最小期望费用时，第一阶段之后的最小期望费用 ) 1( 3 2 ),(min) 1( 2211 )( 11 1 11 sfxscsf x SDx 0 1 2 3 4 5 1830 903 819 796 8147963 1 x 1 s )( 11 sf 1 * x ) 1( 3 2 ),( 2211 1 sfxsc x 830) 1( 22 sf 最优方案最优方案： 第一期投产第一期投产3 3台；第二期投产台；第二期投产3 3台；第三期投产台；第三期投产4 4台。台。 最小期望费用最小期望费用796796。 2021-7-1038 5 5一般数学规划模型的动态规划解法一般数学规划模型的