运筹08(第八章动态规划)ppt课件.ppt

《运筹08(第八章动态规划)ppt课件.ppt》由会员分享，可在线阅读，更多相关《运筹08(第八章动态规划)ppt课件.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程运筹学运筹学OPERATIONS RESEARCH2022/12/311病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第八章第八章 动态规划动态规划11多阶段决策最优化问题举例多阶段决策最优化问题举例22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理33离散确定性动态规划求解离散确定性动态规划求解44离散随机性动态规划求解离散随机性动态规划求解55一般数学规划模型的动态规划解法一般数学规划模型的动态规划解法2

2、022/12/312病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程11多阶段决策过程最优化问题举例多阶段决策过程最优化问题举例例例1 最短路径问题最短路径问题 下图表示从起点下图表示从起点A A到终点到终点E E之间各点的距离。求之间各点的距离。求A A到到E E的最的最短路径。短路径。BACBDBCDEC4123123123221647248386756110637512022/12/313病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程用穷举法的计算量用穷举法的计算

3、量:如果从如果从A A到到E E的站点有的站点有k k个，除个，除A A、E E之外每站有之外每站有3 3个位置则个位置则总共有总共有3 3k-1k-122条路径；条路径；计算各路径长度总共要进行计算各路径长度总共要进行 (k+1)3(k+1)3k-1k-122次加法以及次加法以及3 3k-1k-12-12-1次比较。随着次比较。随着 k k 的值增加时，需要进行的加法和比较的值增加时，需要进行的加法和比较的次数将迅速增加；的次数将迅速增加；例如当例如当 k=20k=20时，加法次数为时，加法次数为 4.25508339662274.255083396622710101515 次，次，比较比较

4、 1.37260754729771.372607547297710101414 次。若用次。若用1 1亿次亿次/秒的计算机计秒的计算机计算需要约算需要约508508天。天。2022/12/314病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程讨论：讨论：1、求求从从A到到E的的最最短短路路径径问问题题，可可以以转转化化为为四四个个性性质质完完全全相相同同，但但规规模模较较小小的的子子问问题题，即即分分别别从从Di、Ci、Bi、A到到E的最短路径问题。的最短路径问题。第四阶段：第四阶段：两个始点两个始点D1和和D2，终点只有一个；，终

5、点只有一个；分析得知：分析得知：从从D1和和D2到到E的最短路径唯一。的最短路径唯一。阶段阶段4本阶段始点本阶段始点（状态）（状态）本阶段各终点本阶段各终点（决策）（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)E D1 D2 10 6 10 6 E E2022/12/315病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程 第三阶段：第三阶段：有三个始点有三个始点C1，C2，C3，终点有，终点有D1，D2，对始点，对始点和终点进行分析和讨论分别求和终点进行分析和讨论分别求C1，C2，C3到到D1，

6、D2 的最短路的最短路径问题：径问题：表表-2 分析得知：分析得知：如果经过如果经过C1，则最短路为则最短路为C1-D2-E；如果经过如果经过C2，则最短路为则最短路为C2-D2-E；如果经过如果经过C3，则最短路为，则最短路为C3-D1-E。阶段阶段3本阶段始点本阶段始点（状态）（状态）本阶段各终点本阶段各终点（决策）（决策）到到E的最短距离的最短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)D1 D2 C1 C2 C3 8+10=18 7+10=17 1+10=116+6=12 5+6=11 6+6=12 12 11 11 D2 D2 D12022/12/316病原体侵入机体，消弱

7、机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第第二二阶阶段段：有有4个个始始点点B1,B2,B3,B4，终终点点有有C1,C2,C3。对对始始点点和和终终点点进进行行分分析析和和讨讨论论分分别别求求B1,B2,B3,B4到到C1,C2,C3 的的最最短短路路径问题：径问题：表表-3 分析得知：分析得知：如果经过如果经过B1，则走，则走B1-C2-D2-E；如果经过如果经过B2，则走，则走B2-C3-D1-E；如果经过如果经过B3，则走，则走B3-C3-D1-E；如果经过如果经过B4，则走，则走B4-C3-D1-E。阶段阶段2本阶段始点本阶段始点（状

8、态）（状态）本阶段各终点本阶段各终点（决策）（决策）到到E的最的最短距离短距离本阶段最优终点本阶段最优终点（最优决策（最优决策)C1 C2 C3 B1 B2 B3 B4 2+12=14 4+12=16 4+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 C32022/12/317病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程第一阶段：第一阶段：只有只有1个始点个始点A，终点有，终点有

9、B1,B2,B3,B4。对始点和终。对始点和终点进行分析和讨论分别求点进行分析和讨论分别求A到到B1,B2,B3,B4的最短路径问题：的最短路径问题：表表10-4最后，可以得到：最后，可以得到：从从A到到E的最短路径为的最短路径为A B4 C3 D1 E 阶段阶段1本阶段始本阶段始点点(状态状态)本阶段各终点（决策）本阶段各终点（决策）到到E的最的最短距离短距离本阶段最优终本阶段最优终点点(最优决策最优决策)B1 B2 B3 B4 A4+12=16 3+13=163+14=172+12=14 14 B42022/12/318病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定

10、部位生长繁殖，引起不同程度的病理生理过程以上计算过程及结果，可用图以上计算过程及结果，可用图2表示，可以看到，以上方法不仅表示，可以看到，以上方法不仅得到了从得到了从A到到D的最短路径，同时，也得到了从图中任一点到的最短路径，同时，也得到了从图中任一点到E的最短路径。的最短路径。以上过程，仅用了以上过程，仅用了22次加法，计算效率远高于穷举法。次加法，计算效率远高于穷举法。BACBDBCDEC412312312332164724838675161060106121111121314141275122022/12/319病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生

11、长繁殖，引起不同程度的病理生理过程 动态规划动态规划是用来解决是用来解决多阶段决策过程最优化多阶段决策过程最优化的一种的一种方法方法。多阶段决策：多阶段决策：是动态决策问题的一种特殊形式；是动态决策问题的一种特殊形式；系统的动态过程可以按照时间等进程分为系统的动态过程可以按照时间等进程分为状态状态相互相互联系联系 而又相互而又相互区别区别的各个的各个阶段阶段；每个阶段都要进行决策每个阶段都要进行决策,目的是目的是使整个过程的决策使整个过程的决策 达达到最优效果到最优效果2022/12/3110病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理

12、生理过程动态规划问题具有以下动态规划问题具有以下基本特征基本特征 1.问问题题具具有有多多阶阶段段决决策策的的特特征征。阶阶段段可可以以按按时时间间划划分，也可以按分，也可以按空间空间划分。划分。2.每一阶段都有相应的每一阶段都有相应的“状态状态”与之对应。与之对应。3.每每一一阶阶段段都都面面临临一一个个决决策策，选选择择不不同同的的决决策策将将会会导导致致下下一一阶阶段段不不同同的的状状态态，同同时时，不不同同的的决决策策将将会会导致这一阶段不同的目标函数值。导致这一阶段不同的目标函数值。4.每每一一阶阶段段的的最最优优解解问问题题可可以以递递归归地地归归结结为为下下一一阶阶段段各各个个可

13、可能能状状态态的的最最优优解解问问题题，各各子子问问题题与与原原问问题题具具有有完完全全相相同同的的结结构构。能能否否构构造造这这样样的的递递推推归归结结，是是解解决决动动态态规规划划问问题题的的关关键键。这这种种递递推推归归结结的的过过程程，称称为为“不变嵌入不变嵌入”。2022/12/3111病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程 5.状态具有无后效性状态具有无后效性 当某阶段状态确定后，此阶当某阶段状态确定后，此阶段以后过程的发展不受此阶段以前各阶段状态的影响。段以后过程的发展不受此阶段以前各阶段状态的影响。动态规划

14、基本原理动态规划基本原理是将一个问题的最优解转化为求子问题的最是将一个问题的最优解转化为求子问题的最优解，优解，研究的对象研究的对象是决策过程的最优化，其是决策过程的最优化，其变量是变量是流动的时间流动的时间或变动的状态，最后到达整个系统最优。或变动的状态，最后到达整个系统最优。基本原理一方面基本原理一方面说明原问题的最优解中包含了子问题的最优解，说明原问题的最优解中包含了子问题的最优解，另一方面另一方面给出了一种求解问题的思路，将一个难以直接解决的给出了一种求解问题的思路，将一个难以直接解决的大问题，分割成一些规模较小的相同子问题，每一个子问题只大问题，分割成一些规模较小的相同子问题，每一个

15、子问题只解一次，并将结果保存起来以后直接引用，避免每次碰到时都解一次，并将结果保存起来以后直接引用，避免每次碰到时都要重复计算，以便各个击破，要重复计算，以便各个击破，分而治之，即分治法分而治之，即分治法，是一种解，是一种解决最优化问题的算法策略。决最优化问题的算法策略。动态规划求解可分为三个步骤：动态规划求解可分为三个步骤：分解、求解与合并。分解、求解与合并。2022/12/3112病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例2 资源分配问题资源分配问题 设有某种机器数台，用于完成两类工作设有某种机器数台，用于完成两类工作

16、A，B。由于机。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化器使用后有一定的损坏率，所以每年初的机器数量是变化的；的；A、B两项工作产生的收益也不同。如何合理的分配机两项工作产生的收益也不同。如何合理的分配机器的使用，可使得三年的总收益最大器的使用，可使得三年的总收益最大?假设第假设第k年年初完好机器数是年年初完好机器数是SK，用于用于A生产的机器数生产的机器数是是XK，则用于则用于B生产的机器数是（生产的机器数是（SK-XK）；）；用于用于A工作的设备的完好率是：工作的设备的完好率是：a%，用于，用于B工作的设工作的设备的完好率是：备的完好率是：b%。则下一年初的完好机器数是。则

17、下一年初的完好机器数是SK+1=a%XK+b%（SK-XK）第第k年的收益：年的收益：h(XK)+g(SK-XK)2022/12/3113病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例3 背包问题背包问题 设有设有n种物品，每一种物品数量无限。第种物品，每一种物品数量无限。第i种物品每件种物品每件重量为重量为wi公斤，每件价值公斤，每件价值ci元。现有一只可装载重量为元。现有一只可装载重量为W公斤的背包，求各种物品应各取多少件放入背包，使背公斤的背包，求各种物品应各取多少件放入背包，使背包中物品的价值最高。包中物品的价值最高。

18、这个问题可以用整数规划模型来描述。设这个问题可以用整数规划模型来描述。设xi为第为第i种种物品装入背包的件数（物品装入背包的件数（i=1,2,n），背包中物品的总），背包中物品的总价值为价值为z，则，则 Max z=c1x1+c2x2+cnxn s.t.w1x1+w2x2+wnxnW x1,x2,xn 0 且为整数。且为整数。2022/12/3114病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程一、基本概念：一、基本概念：1、阶阶段段(stage)k：表表示示决决策策顺顺序序的的离离散散的的量量，阶阶段段可可以按以按时间或空间时间

19、或空间划分。划分。(顺序编号法、逆序编号法）顺序编号法、逆序编号法）2、状状态态(state)sk：反反应应前前一一阶阶段段决决策策的的结结果果，又又是是本本阶阶段段组组作作决决策策的的依依据据和和出出发发点点（能能确确定定地地表表示示决决策策过过程程当当前前特特征征的的量量）。状状态态可可以以是是数数量量，也也可可以以是是字符字符，数量状态可以是，数量状态可以是连续连续的，也可以是的，也可以是离散离散的。的。3、决决策策(decision)xk：从从某某一一状状态态向向下下一一状状态态过过渡渡时时所做的选择。决策是所在状态的函数，记为所做的选择。决策是所在状态的函数，记为x xk k(s(s

20、k k)。决决策策允允许许集集合合D Dk k(s(sk k)：在在状状态态s sk k下下，允允许许采采取取决决策的全体策的全体 x xk k(s(sk k)D)Dk k(s(sk k)22基本概念、基本方程与最优化原理基本概念、基本方程与最优化原理2022/12/3115病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程4、策略、策略Pk,n(sk)：从第从第k k阶段开始到最后第阶段开始到最后第n n阶段的决阶段的决策序列，称策序列，称k k子策略子策略。P P1,n1,n(s(s1 1)即为即为全过程策略。全过程策略。5、状态

21、转移方程、状态转移方程 S Sk+1k+1=T=Tk k(S(Sk k,X,Xk k)：某一状态以及该某一状态以及该状态下的决策，与下一状态之间的函数关系。状态下的决策，与下一状态之间的函数关系。6、指标函数或收益函数指标函数或收益函数(Return function)：是衡量对是衡量对决策过程进行控制的效果的数量指标，具体可以是收决策过程进行控制的效果的数量指标，具体可以是收益、成本、距离等指标。分为益、成本、距离等指标。分为k阶段指标函数、阶段指标函数、k子过子过程指标函数及最优指标函数。程指标函数及最优指标函数。k阶段指标函数阶段指标函数 从从k阶段状态阶段状态sk出发，选择决策出发，选

22、择决策xk所产生的第所产生的第k阶段指阶段指标，称为标，称为k阶段指标函数阶段指标函数,记为记为vk(sk,xk)。2022/12/3116病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程从从k阶段状态阶段状态sk出发，选择决策出发，选择决策xk,xk+1,xn所产生的过所产生的过程指标，称为程指标，称为k子过程指标函数或简称过程指标函数，子过程指标函数或简称过程指标函数，记为记为Vk(sk,xk,xk+1,xn)或或Vk，n为阶段数。为阶段数。过程指标函数过程指标函数最优指标函数最优指标函数从从k阶段状态阶段状态sk出发，对所有的

23、子策略，最优的过程指出发，对所有的子策略，最优的过程指标函数称为最优指标函数，记为标函数称为最优指标函数，记为fk(sk)，通常取，通常取Vk的最的最大值或最小值。大值或最小值。（Optoptimization表示表示“max”或或“min”2022/12/3117病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程动态规划要求过程指标满足动态规划要求过程指标满足递推关系递推关系，即，即(8-2)连和形式：连和形式：(8-3)最优指标函数是最优指标函数是(8-4)2022/12/3118病原体侵入机体，消弱机体防御机能，破坏机体内环境的

24、相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程动态规划数学模型由式动态规划数学模型由式(8-4)或或(8-6)、边界条件及状态转移方程、边界条件及状态转移方程构成。如连和形式的数学模型构成。如连和形式的数学模型 连乘形式连乘形式(vj0)：(8-5)最优指标函数是最优指标函数是(8-6)2022/12/3119病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程对于可加性指标函数，上式可以写为对于可加性指标函数，上式可以写为上上式式中中“opt”表表示示“max”或或“min”。对对于于可可乘乘性性指指标标函函数数，上式可

25、以写为上式可以写为上上式式称称为为动动态态规规划划最最优优指指标标的的递递推推方方程程，是是动动态态规规划划的的基基本本方方程。程。终终端端条条件件：为为了了使使以以上上的的递递推推方方程程有有递递推推的的起起点点，必必须须要要设设定定最最优优指指标标的的终终端端条条件件，即即确确定定最最后后一一个个状状态态n下下最最优优指指标标fn(sn)的值。的值。2022/12/3120病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程三、最优化原理三、最优化原理 作为整个过程的最优策略具有如下性质：作为整个过程的最优策略具有如下性质：不管在此

26、最优策略上的某个状态以前的状不管在此最优策略上的某个状态以前的状态和决策如何，对该状态来说，以后的所有决态和决策如何，对该状态来说，以后的所有决策必定构成最优子策略。就是说，策必定构成最优子策略。就是说，最优策略的最优策略的任意子策略都是最优的。任意子策略都是最优的。2022/12/3121病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程用逆序法列表用逆序法列表k=n=5 时，时，f5(v10)0 k=4，递推方程为，递推方程为 s4D4(s4)s5v4(s4,x4)v4(s4,x4)+f5(s5)f4(s4)最优决策最优决策x4*

27、v7v7v10v1055+0=5*5v7 v10v8v8v10v1088+08*8v8 v10v9v9v10v1044+0=4*4v9 v102022/12/3122病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程k=3，递推方程为，递推方程为表8-2 s3D3(s3)s4v3(s3,x3)v3(s3,x3)+f4(s4)f3(s3)最优决策最优决策x3*v5v5v7 7v v5 5v8 8v v5 5v9 9v7v8v92862+5=7*8+8=166+4=107v5v7 7v6v6 v7 7v v6 6v8 8v v6 6v9

28、9v7v8v9125812+5=175+8=138+4=12*12v6v9 92022/12/3123病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程k=2，递推方程为，递推方程为表表8-3 s2D2(s2)s3v2(s2,x2)v2(s2,x2)+f3(s3)f2(s2)最优决策最优决策x2*v2v2 v5 5v v2 2 v6 6v5v6101310+7=17*13+12=2517v2 v5 5v3v3 v5 5v v3 3 v6 6v5v67107+7=14*10+12=2214v3v5 5v4v4 v5 5v v4 4 v6

29、 6v5v6131113+7=20*11+12=2320v4v5 52022/12/3124病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程k=1，递推方程为，递推方程为表8-4 s1D1(s1)s2v1(s1,x1)v1(s1,x1)+f2(s2)f1(s1)最优决策最优决策x1*v1v1v2 2v v1 1v3 3v v1 1v4 4v2v3v42852+17=19*8+14=225+20=2519v1v2 2最优值是表最优值是表8-4中中f1(s1)的值，从的值，从v1到到v10的最短路长为的最短路长为19。最短路。最短路线从

30、表线从表8-4到表到表8-1回朔，查看最后一列最优决策，得到最短路回朔，查看最后一列最优决策，得到最短路径为：径为：v1 v2 v5 v7 v102022/12/3125病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例4.有有9支支巡巡逻逻队队负负责责3个个要要害害部部门门A、B、C的的巡巡逻逻，每每部部位位可可派派2-4支支巡巡逻逻队队，队队数数不不同同各各部部位位可可能能损损失失有有差差别别，如如表表，问问各部位应各派多少队，使总预期损失最小。各部位应各派多少队，使总预期损失最小。33离散确定性动态规划模型求解离散确定性动态

31、规划模型求解 部位部位 预期损失预期损失队数队数ABC2183824314352241031212022/12/3126病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程解解：设设将将向向三三个个部部位位A A，B B，C C派派巡巡逻逻队队作作为为三三个个阶阶段段，K=1K=1，2 2，3 3。决策变量决策变量 表示向第表示向第K K个部位派遣的巡逻队数。个部位派遣的巡逻队数。状态变量状态变量 表示第表示第K K个阶段时可供派遣的巡逻队数量。个阶段时可供派遣的巡逻队数量。状态转移方程：状态转移方程：阶阶段段指指标标函函数数：派派遣遣

32、 支支巡巡逻逻队队时时第第K K阶阶段段产产生的预期损失；生的预期损失；过程指标函数：过程指标函数：第第K K阶段到第阶段到第3 3阶段的预期损失。阶段的预期损失。最优指标函数：最优指标函数：决策允许集合决策允许集合D Dk k(s(sk k)=xk k|2|2xk k4,(k=1,2,3,4)4,(k=1,2,3,4)2022/12/3127病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，给时，给C C派巡逻队，派巡逻队，2 3 43245 24 -24 2 24 22 -

33、22 3 24 22 21 21 4 24 22 21 21 42022/12/3128病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程当当K=2K=2时，给时，给B B派巡逻队，派巡逻队，2 3 456738+22 35+24 -59 338+21 35+22 31+24 55 438+21 35+21 31+22 53 42022/12/3129病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程当当K=1K=1时，给时，给A A派巡逻队，派巡逻队，23 49最优方案：最

34、优方案：A A派派3 3支巡逻队，支巡逻队，B B派派4 4支巡逻队，支巡逻队，C C派派2 2支巡逻队；支巡逻队；或：或：A A派派4 4支巡逻队，支巡逻队，B B派派3 3支巡逻队，支巡逻队，C C派派2 2支巡逻队支巡逻队 18+53 14+55 10+59 69 3,42022/12/3130病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程例例5 资源分配问题资源分配问题 设有某种机器设有某种机器100，用于完成两类工作，用于完成两类工作A，B。由于机。由于机器使用后有一定的损坏率，所以每年初的机器数量是变化器使用后有一定的

35、损坏率，所以每年初的机器数量是变化的，设用于的，设用于A工作的设备的完好率是：工作的设备的完好率是：2/3，用于，用于B工作的设工作的设备的完好率是：备的完好率是：9/10；A、B两项工作产生的收益与机器台两项工作产生的收益与机器台数有关且分别为数有关且分别为g(x)=10 x(万元万元)，h(x)=7x(万元万元)。如何合理。如何合理的分配机器的使用，可使得三年的总收益最大的分配机器的使用，可使得三年的总收益最大?2022/12/3131病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程解：解：按年份分为三个阶段，按年份分为三个阶段

36、，K=1K=1，2 2，3 3；决策变量决策变量xk表示用于生产产品表示用于生产产品A A的机器数；的机器数；状态变量状态变量sk表示第表示第K年初年初完好机器数完好机器数；状态转移方程：状态转移方程：阶段指标函数：阶段指标函数：过程指标函数：过程指标函数：第第K K阶段到第阶段到第3 3阶段的最大收益为阶段的最大收益为 最优指标函数：最优指标函数：决策允许集合决策允许集合Dk(sk)=xk|0 xksk,(k=1,2,3)sK+1=2/3 xK+0.9（sK-XK）Vk(sk,xk)=10 xk+7(sk-xk)表示第表示第k年的收益年的收益2022/12/3132病原体侵入机体，消弱机体防

37、御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程逆序解法：逆序解法：边界条件边界条件f4(s4)=0 当当K=3K=3时时,第三年初分配机器第三年初分配机器x3台生产台生产A,A,s3-x3台生产台生产B,B,显然当显然当x3=s3时达到最大值，时达到最大值，因而此阶段的最优决策为因而此阶段的最优决策为x3*=s32022/12/3133病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程当当K=2K=2时时,第二年初分配机器第二年初分配机器x2台生产台生产A,A,s2-x2台生产台生产B,B,显然显

38、然s3是关于是关于s2,x2的的状态转移状态转移，因而有，因而有 2022/12/3134病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程最最优优方方案案：s1=100,x1*=0,s1x1=100,s2=90,x2*=90,s2x2*=0,s3=60,x3*=60,s3x3*=0。第一年所有机器第一年所有机器100100台用于生产台用于生产B B，第二年初完好机器第二年初完好机器9090台；台；第二年所有机器第二年所有机器9090台用于生产台用于生产A A，第三年初完好机器第三年初完好机器6060台；台；第三年所有机器第三年所有机

39、器6060台用于生产台用于生产A A，第四年初完好机器第四年初完好机器4040台。台。当当K=1K=1时时,第二年初分配机器第二年初分配机器x1台生产台生产A,A,s1-x1台生产台生产B,B,s1=100=100 2022/12/3135病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程【例例】公公司司有有资资金金6万万元元，投投资资A、B、C三三个个项项目目，一一个个单单位位投投资资为为2万万元元。每每个个项项目目的的投投资资效效益益率率与与投投入入该该项项目目的的资资金金有有关关。三三个个项项目目A、B、C的的投投资资效效益益(

40、万万元元)和和投投入入资资金金（万万元元）的的关关系见表系见表8-5。求对三个项目的最优投资分配，使总投资效益最大。求对三个项目的最优投资分配，使总投资效益最大。项目项目投入资金投入资金ABC0万元万元0002万元万元89104万元万元1520286万元万元303535【解解】设设xk为第为第k个项目的投资个项目的投资2022/12/3136病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程阶段阶段k：每投资一个项目作为一个阶段，：每投资一个项目作为一个阶段，k=1,2,3,4。k=4为虚设为虚设的阶段的阶段状态变量状态变量sk：投资

41、第：投资第k个项目前的资金数个项目前的资金数决策变量决策变量xk：第：第k个项目的投资额个项目的投资额决策允许集合：决策允许集合：0 xksk状态转移方程：状态转移方程：sk+1=skxk阶段指标：阶段指标：vk(sk，xk)见表见表8-5中的数据中的数据 递推方程：递推方程：终端条件：终端条件：f4(s4)=0数学模型为数学模型为 2022/12/3137病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程k=4，终端条件，终端条件f4(s4)=0。k=3，0 x3s3，s4=s3x3，s3=0，2，4，6状态状态s3决策决策x3(s

42、3)状态转移方程状态转移方程s4=s3x3阶段指标阶段指标v3(s3,x3)过程指标过程指标v3(s3,x3)+f4(s4)最优指标最优指标f3(s3)最优决策最优决策x3*02460 0 0 0+0=0*0 02 0 10 10+0=10*10 24 0 28 28+0=28*28 46 0 35 35+0=35*35 62022/12/3138病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程s2x2(s2)s3v2(s2,x2)f3(s3)v2(s2,x2)+f3(s3)f2(s2)x2*k=2，0 x2s2，s3=s2x2，s

43、2=0，2，4，60246 0 0 0 0 0+0=0*0 0 0 2 0 10 0+10=10*2 0 9 0 9+0=910 0 0 4 0 28 0+28=28*2 2 9 10 9+10=19 4 0 20 0 20+0=2028 0 0 6 0 35 0+35=35 2 4 9 28 9+28=37*4 2 20 10 20+10=30 6 0 35 0 35+0=3537 22022/12/3139病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程k=1，0 x1s1，s2=s1x1，s1=6 s1x1(s1)s2v1(s

44、1,x1)f2(s2)v1(s1,x1)+f2(s2)f1(s1)x1*6最优解为最优解为:s1=6,x1*=0,s2=s1x1=6,x2*=2,s3=s2x2*=4,x3*=4,s4=s3x3=0。投资的最优策略是，项目投资的最优策略是，项目A不投资，项目不投资，项目B投资投资2万元，项目万元，项目C投投资资4万元，最大效益为万元，最大效益为37万元万元 0 6 0 37 0+37=37*2 4 8 28 8+28=36 4 2 15 10 15+10=25 6 0 30 0 30+0=3037 02022/12/3140病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定

45、部位生长繁殖，引起不同程度的病理生理过程44离散随机动态规划模型求解离散随机动态规划模型求解随机动态规划：状态转移规律不定随机动态规划：状态转移规律不定，在给定的状态和决策，在给定的状态和决策下，下一阶段到达的状态是具有确定概率分布的随机变量。下，下一阶段到达的状态是具有确定概率分布的随机变量。第第k+1阶段阶段可能状态可能状态SkXkn21第第k阶段状态阶段状态决策决策P1，C1P2，C2Pn，CnP Pi i：在决策：在决策X Xk k下出现状态下出现状态i i的概率的概率C Ci i：在决策：在决策X Xk k下出现状态下出现状态i i时的指标函数时的指标函数2022/12/3141病原

46、体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程由于下一阶段的状态和阶段的效益值不确定，因而由于下一阶段的状态和阶段的效益值不确定，因而随机动态规划中，对指标函数进行优化时，要根据随机动态规划中，对指标函数进行优化时，要根据各阶段的各阶段的期望效益期望效益进行优化。进行优化。基本方程改写为：基本方程改写为：其中其中E（）表示期望值，边界条件（）表示期望值，边界条件fn+1(sn+1)的应根据的应根据问题的具体情况确定。问题的具体情况确定。2022/12/3142病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生

47、长繁殖，引起不同程度的病理生理过程解：解：阶段变量阶段变量K，每月投产一批作为一个阶段，每月投产一批作为一个阶段，K=1，2，3。状态变量状态变量 ：表示第：表示第K阶段已拥有的合格样品数，有阶段已拥有的合格样品数，有 两种可能状态两种可能状态 。表示已有一台以上的合格品；表示已有一台以上的合格品；表示还没有一台合格品。表示还没有一台合格品。例：某公司按合同在三个月内交出一新产品的合格样品，否例：某公司按合同在三个月内交出一新产品的合格样品，否则将赔偿则将赔偿15001500元，据估计，每投产一台合格的概率为元，据估计，每投产一台合格的概率为1/31/3，投产一批的准备结束费为投产一批的准备结

48、束费为250250元，每台试制费为元，每台试制费为100100元，若投元，若投产一批后全部不合格，可再投一批试制，但每投一批的周期产一批后全部不合格，可再投一批试制，但每投一批的周期需一个月，试确定每批投产多少台，使总的试制费用（包括需一个月，试确定每批投产多少台，使总的试制费用（包括可能发生的赔偿费）的期望值为最小可能发生的赔偿费）的期望值为最小2022/12/3143病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程决策变量决策变量xk k：表示第：表示第K K个阶段决定投产的数量。个阶段决定投产的数量。状态转移律：状态转移律：阶

49、段指标函数：第阶段指标函数：第k k阶段的费用支出阶段的费用支出最优指标函数最优指标函数 fk(sk)：表示第表示第K阶段在阶段在 Sk 状态下，做决策状态下，做决策xk时，到最后一个阶段的最小期望费用。时，到最后一个阶段的最小期望费用。允许决策集合允许决策集合D Dk k(sk k)：D Dk k(sk k)=1,2,N()=1,2,N(当当sk k=1)=1)，D Dk k(sk k)=0()=0(当当sk k=0)=0)；2022/12/3144病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程Sk=1Xk第第k阶段状态阶段状态

50、决策决策Sk=0Sk+1=1Sk+1=0第第k+1阶段状态阶段状态易知：易知：2022/12/3145病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程逆序解法：逆序解法：边界条件边界条件 当当K=3K=3时，第三阶段之后的最小期望费用，时，第三阶段之后的最小期望费用，010015001 13502 11173 9944 9465 9480946042022/12/3146病原体侵入机体，消弱机体防御机能，破坏机体内环境的相对稳定性，且在一定部位生长繁殖，引起不同程度的病理生理过程当当K=2K=2时，第二阶段之后的最小期望费用时，第二