运筹学第章动态规划.ppt

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

1、2022/12/181第六章第六章 动态规划动态规划Dynamic Programming，DP美国数学家贝尔曼（Richard.Bellman,(19201984)创始时间上个世纪50年代创始人 动态规划是运筹学的一个主要分支动态规划是运筹学的一个主要分支,同时也是现代企同时也是现代企业管理中的一种重要决策方法业管理中的一种重要决策方法,它是解决它是解决多阶段决策过程多阶段决策过程的最优化的一种方法。的最优化的一种方法。2022/12/182动态规划动态规划模型分类模型分类离散确定型离散确定型离散随机型连续确定型连续随机型 动态规划解决问题的思路独特动态规划解决问题的思路独特,在处理某些优化

2、问题时在处理某些优化问题时,有有时比线性规划或者非线性规划更有效时比线性规划或者非线性规划更有效.需要需要丰富的想象力丰富的想象力去建去建立模型，并能用立模型，并能用创造性的技巧创造性的技巧去求解。去求解。其中其中离散确定性离散确定性是最基本的是最基本的,本章主要介绍这种类型的问题本章主要介绍这种类型的问题,介介绍动态规划的基本思想、原理和方法绍动态规划的基本思想、原理和方法.2022/12/183本章主要内容本章主要内容n多阶段决策过程及其问题举例多阶段决策过程及其问题举例 q最短路问题最短路问题n 动态规划的基本概念和基本方程动态规划的基本概念和基本方程 n动态规划应用举例动态规划应用举例

3、q资源分配问题资源分配问题q背包问题背包问题q生产库存问题生产库存问题q2022/12/1846.1 多阶段决策过程及其问题举例多阶段决策过程及其问题举例n动态规划研究的问题动态规划研究的问题-多阶段决策多阶段决策问题（顺序决策问问题（顺序决策问题）题）q研究的问题可以在研究的问题可以在时间或空间上时间或空间上划分为若干个划分为若干个相互联系相互联系阶段，阶段，称为称为”时段时段”。q在每一个时段都需要做出决策在每一个时段都需要做出决策,每时段的决策将影响到每时段的决策将影响到下一时段的决策下一时段的决策,因此决策者每段决策时因此决策者每段决策时,不仅要考虑不仅要考虑本本阶段目标最优阶段目标最

4、优,还应考虑最还应考虑最终目标的最优终目标的最优,最终达到整个最终达到整个决策活动的决策活动的总体目标最优总体目标最优.12状态状态状态n状态决策决策决策状态2022/12/185 动态规划方法与动态规划方法与“时间时间”关系很密切，随着时间过程关系很密切，随着时间过程的发展而决定各时段的决策，产生一个的发展而决定各时段的决策，产生一个决策序列决策序列，这就是，这就是“动态动态”的意思。的意思。然而，它也可以处理与时间无关的然而，它也可以处理与时间无关的静态问题静态问题，只要在问，只要在问题中题中人为地引入人为地引入“时段时段”因素因素，就可以将其转化为一个多，就可以将其转化为一个多阶段决策问

5、题。阶段决策问题。2022/12/1862511214106104131112396581052C1C3D1AB1B3B2D2EC2例例1 最短路径问题最短路径问题求从求从A A到到E E的最短路径。的最短路径。显然，这种运输网络问题是显然，这种运输网络问题是静态决策问题静态决策问题。但是，按照网络中点的分布，可以把。但是，按照网络中点的分布，可以把它分为它分为4 4个阶段，而作为多阶段决策问题来研究。个阶段，而作为多阶段决策问题来研究。2022/12/187 第一种方法第一种方法称做称做全枚举法或穷举法全枚举法或穷举法。它的基本思想是。它的基本思想是列举出所有可能发生的方案和结果，再对它们一

6、一进行比列举出所有可能发生的方案和结果，再对它们一一进行比较，求出最优方案。这里从较，求出最优方案。这里从A A到到E E的路程共有的路程共有3 33 32 21 11818条可能的路线，分别算出各条路线的距离，最后进行比条可能的路线，分别算出各条路线的距离，最后进行比较，可知最优路线。显然，当组成交通网络的节点很多时，较，可知最优路线。显然，当组成交通网络的节点很多时，用穷举法求最优路线的计算工作量将会十分庞大，而且其用穷举法求最优路线的计算工作量将会十分庞大，而且其中包含着许多重复计算中包含着许多重复计算 第二种方法第二种方法贪心算法贪心算法，即所谓，即所谓“局部最优路径局部最优路径”法，

7、法，是说某人从是说某人从k出发，他并不顾及全线是否最短，只是选择出发，他并不顾及全线是否最短，只是选择当前最短途径当前最短途径，“逢近便走逢近便走”，错误地以为局部最优会致，错误地以为局部最优会致整体最优，在这种想法指导下，所取决策必是整体最优，在这种想法指导下，所取决策必是 A B3 C3 D1 E.距离为：距离为：1+11+8+5=252022/12/188 2511214106104131112396581052C1C3D1AB1B3B2D2EC2第第1阶段阶段第第4阶段阶段第第3阶段阶段第第2阶段阶段状态状态第三种方法是第三种方法是动态规划方法动态规划方法。2022/12/189 基本

8、思想：基本思想：如果起点如果起点A经过经过B1,C1,D1而到终点而到终点E，则由，则由C1出出发经发经D1到到E点这条子路线，是从点这条子路线，是从C1到到E的最短路线。所以，寻的最短路线。所以，寻找最短路线，应该找最短路线，应该从最后一段开始找，然后往前递推从最后一段开始找，然后往前递推.设设 sk：第：第k阶段初的状态（所处的结点）阶段初的状态（所处的结点）;xk(sk)：在在sk状态时第状态时第k阶段所作的决策阶段所作的决策,决定下一个状态的位决定下一个状态的位置置；d(sk,xk)：第第k阶阶段，采取策略段，采取策略xk 所发生的距离所发生的距离;fk(sk)：在第在第k阶段，由阶段

9、，由sk状态开始到终点状态开始到终点E的最短距离的最短距离.2022/12/18102511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=02022/12/18112511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=02022/12/18122511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=52022/12/18132511214106104131112396581052C1C3D1AB1B3

10、B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=52022/12/18142511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=82022/12/18152511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=72022/12/18162511214106104131112396581052C1C3D1AB1B3B2D2EC2f

11、4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=82022/12/18172511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=202022/12/18182511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1

12、)=20f2(B2)=142022/12/18192511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=202022/12/18202511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=20状态状态

13、最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态 最优决策最优决策 状态状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从从A到到E的最短路径为的最短路径为19，路线为，路线为AB 2C1 D1 E 2022/12/1821多阶段决策过程及实例多阶段决策过程及实例-标号法标号法B1AC3F2F1E3E2E1D3D2D1C4C2C1B2G531368766835342138223335526643437597681310912131618该点到该点到G点的最短距离点的最短距离第一阶段第二阶段第三阶段第四阶段第五阶段第六阶段从从G到

14、到A的解法称为的解法称为逆序解法逆序解法。注：因为从注：因为从A A到到G G的最短路与从的最短路与从G G到到A A的最短路是一样的，的最短路是一样的，因此也可以从因此也可以从A A出发来找。从出发来找。从A A到到G G的解法称为的解法称为顺序解法顺序解法。2022/12/1822 综上所述可见，综上所述可见，全枚举法全枚举法虽可找出最优方案，但不是虽可找出最优方案，但不是个好算法，个好算法，局部最优法局部最优法则完全是个错误方法，只有则完全是个错误方法，只有动态规动态规划方法划方法属较科学有效的算法。它的基本思想是，属较科学有效的算法。它的基本思想是，把一个比把一个比较复杂的问题分解为一

15、系列同类型的更易求解的子问题较复杂的问题分解为一系列同类型的更易求解的子问题，便于应用计算机。便于应用计算机。2022/12/18236.2 动态规划的基本概念和基本方程动态规划的基本概念和基本方程(一一)基本概念和基本方程基本概念和基本方程(1)阶段阶段：k=1,，n(2)状态变量状态变量sk：第：第k阶段的状态阶段的状态.状态变量取值的集合成为状态变量取值的集合成为状态集合状态集合，用，用Sk表示。状态集合可以是一表示。状态集合可以是一离散取值的集合离散取值的集合，也可以为一也可以为一连续的取值区间连续的取值区间，视具体问题而定，视具体问题而定(3)决策变量决策变量uk(sk)：第：第k阶

16、段的决定，阶段的决定，Dk(sk)为决策变量的取为决策变量的取值范围值范围.(4)状态转移方程状态转移方程sk1 T(sk,uk)：描述第描述第k阶段与第阶段与第k+1阶段阶段的状态变量的关系的状态变量的关系2022/12/1824(5)指标指标 v(sk,uk)：第：第k阶段状态阶段状态sk情况下采取决策情况下采取决策uk得到的结得到的结果（距离、得益、成本等）果（距离、得益、成本等）指标函数是指各阶段指标的累计。即指标函数是指各阶段指标的累计。即V(sk,uk,sn,un,sn+1)=vk(sk,uk)*vk+1(sk+1,uk+1)*vn(sn,un)它表示从第它表示从第k阶段的状态阶段

17、的状态sk开始到第开始到第n阶段的终止状态的指标阶段的终止状态的指标累计。式中累计。式中*表示某种运算符，一般为表示某种运算符，一般为加法运算或者乘积运算加法运算或者乘积运算。(6)最优指标函数最优指标函数fk(sk)：它表示从第：它表示从第k阶段的状态阶段的状态sk开始到开始到第第n阶段的终止状态的过程，采取最优策略得到的指标函数阶段的终止状态的过程，采取最优策略得到的指标函数值值 阶段函数阶段函数2022/12/1825逆推公式逆推公式fk(sk)OPT d(sk,uk)+fk+1(sk+1)k=n,1fn+1(sn+1)0或或fk(sk)OPTd(sk,uk)+fk+1(sk+1)k=n

18、-1,1fn(sn)OPTd(sn,un)多阶段决策问题中，常见的目标函数形式之一是取多阶段决策问题中，常见的目标函数形式之一是取各阶段效各阶段效益之和的形式益之和的形式.有些问题，如系统可靠性问题，其目标函数有些问题，如系统可靠性问题，其目标函数是取是取各阶段效益的连乘积形式各阶段效益的连乘积形式.总之，具体问题的目标函数总之，具体问题的目标函数表达形式需要视具体问题而定。表达形式需要视具体问题而定。Max或者或者min2511214106104131112396581052C1C3D1AB1B3B2D2EC2第第1阶段阶段第第4阶段阶段第第3阶段阶段第第2阶段阶段对对例例1(1)阶段阶段：

19、k1，2，4(2)状态变量状态变量：sk第第k阶段初所处的阶段初所处的位置位置,状态集合状态集合 Sk 如如S2:=B1,B2,B3.2022/12/1827(3)决策变量决策变量uk：在第在第k段段sk状态时决定选取的下一段的某状态时决定选取的下一段的某点点.(4)状态转移方程状态转移方程：sk1 uk(sk)(5)阶段效益阶段效益：d(sk,uk)为第为第k段，采取决策段，采取决策uk 到下一状态的距离到下一状态的距离.(6)最优指标函数最优指标函数：fk(sk)：第第k段，在段，在sk状态时到终点状态时到终点E的最短距离的最短距离.逆推公式：逆推公式：fk(sk)mind(sk,uk)+

20、fk+1(sk+1)k=4,1f5(s5)02022/12/1828（二）（二）贝尔曼贝尔曼最优化原理：最优化原理：一个最优策略具有这样的性质，即一个最优策略具有这样的性质，即不论初始状态与初始策略如何，对于不论初始状态与初始策略如何，对于先前决策所造成的状态而言，余下所先前决策所造成的状态而言，余下所有决策必构成最优决策有决策必构成最优决策。也即：也即：一个最优策略的子策略也是最一个最优策略的子策略也是最优的优的。A BMII II 2022/12/1829（三）解法步骤（三）解法步骤q反向条件优化反向条件优化q正向求最优解正向求最优解fk(sk)OPT d(sk,uk)+fk+1(sk+1

21、)k=n,1fn+1(sn+1)0fk(sk)OPT d(sk,uk)*fk+1(sk+1)k=n,1fn+1(sn+1)12022/12/18306.3 应用举例应用举例例例2 资源分配问题资源分配问题-1例例3 资源分配问题资源分配问题-2例例4 背包问题背包问题例例5 生产库存问题生产库存问题例例6 可靠性问题可靠性问题例例7 机器负荷分配问题机器负荷分配问题等等等等2022/12/1831例例 2 资源分配问题资源分配问题-1某公司准备将某公司准备将5 5台设备分配给所属的三个子工厂，各工厂获台设备分配给所属的三个子工厂，各工厂获得设备后的可盈利情况如表所示。得设备后的可盈利情况如表所

22、示。问：如何分配这五台设备，问：如何分配这五台设备，才能使公司获得的收益最大？才能使公司获得的收益最大？工厂工厂 盈利（万元）盈利（万元）设备设备数数工厂工厂1工厂工厂2工厂工厂300001354271063101111412111251411122022/12/1832分析分析(1)阶段：阶段：k=1,2,3.(3)决策变量决策变量uk：对第对第k个企业的分配数个企业的分配数.(2)状态变量状态变量sk：对第对第k至至3个企业可分配的设备数个企业可分配的设备数 或：第或：第k阶段初可分配的设备数阶段初可分配的设备数.(4)状态转移方程：状态转移方程：sk1 sk uk.(5)最优指标函数最优

23、指标函数fk(sk)：第第k至至3个企业采取最优分配个企业采取最优分配策略可产生的最大收益策略可产生的最大收益.设分配给第设分配给第k个工厂的机器数为个工厂的机器数为uk工厂工厂1工厂工厂2工厂工厂32022/12/1833fk(sk)maxgk(uk)+fk+1(sk-uk)k=3,2,1f4(s4)0其中，其中，gk(uk)是阶段函数是阶段函数逆推公式：逆推公式：sk+12022/12/1834k=3,S3=0,1,2,3,4,5,f3(s3)maxg3(u3)+0g3(u3)+0max u3s3012345f3(s3)u3000010441204662304611113404611121

24、245046111212124,52022/12/1835k=2,S2=0,1,2,3,4,5,f2(s2)maxg2(u2)+f3(s3)g2(u2)+f3(s3)max最优最优决策决策 u2s2012345f2(s2)u20000(0,0)10+45+051(1,0)20+65+410+0102(2,0)30+115+610+411+0142(2,1)40+125+1110+611+411+0161,2(1,3)(2,2)50+125+1210+1111+611+411+0212(2,3)S3=S2-u32022/12/1836g1(u1)+f2(s2)max最优决策最优决策 u1s101

25、2345f1(s1)u150+213+167+1410+1012+514+0210,2(0,2,3)(2,2,1)k=1,S1=5,f1(s1)max g1(u1)+f2(s2)得到两种方案：得到两种方案：u1*0，u2*2，u3*3:工厂工厂1分配分配0台，工厂台，工厂2 分配分配2台，工厂台，工厂3分配分配3台台;u1*2，u2*2，u3*1:工厂工厂1分配分配2台，工厂台，工厂2 分配分配2台，工厂台，工厂3分配分配1台。台。总盈利均为总盈利均为21万元。万元。同理得到另一同理得到另一组最优解组最优解2022/12/1837一般分配问题一般分配问题某种资源，总量为某种资源，总量为a，分配

26、于分配于n种生产。若分配种生产。若分配 ui 用于第用于第 i 种种生产，收益为生产，收益为gi(ui)。问：应如何分配才能使总收入最大？问：应如何分配才能使总收入最大？容易建立其数学模型：容易建立其数学模型：max Z=g1(u1)+g2(u2)+gn(un)u1+u2+un=aui0 2022/12/1838fk(sk)maxg(sk uk)+fk+1(sk+1)k=n-1,2,1fn+1(sn+1)00uksk逆推公式：逆推公式：sk:第第k阶段初可分配的资源数阶段初可分配的资源数。uk:对第对第k个企业的分配资源数个企业的分配资源数.状态转移方程状态转移方程:sk+1=sk-uk例例3

27、 资源分配问题资源分配问题-2 某工厂要进行某工厂要进行A,B,C三种新产品的试制，为提高三种产品研制三种新产品的试制，为提高三种产品研制成功的概率，决定调拨经费成功的概率，决定调拨经费2百万，并要求资金集中使用，也即百万，并要求资金集中使用，也即以百万为单位进行分配以百万为单位进行分配，其增加研发费与新产品不成功概率的，其增加研发费与新产品不成功概率的关系如表所示。关系如表所示。问如何分配资金，可使三种产品都研制不成功问如何分配资金，可使三种产品都研制不成功的概率最小。的概率最小。产产品品 不成功概率不成功概率费费用（百万）用（百万）ABC00.40.60.810.20.40.520.150

28、.20.3分析分析(1)阶段：阶段：k=1，2，3(3)决策变量决策变量uk：对第对第k阶段分配金额阶段分配金额(2)状态变量状态变量sk：第第k阶段初的可用金额阶段初的可用金额(4)状态转移方程：状态转移方程：sk1 sk-uk产品产品A产品产品B产品产品Cfk(sk)mingk(uk)*fk+1(sk+1)k=3,2,1f4(s4)1逆推公式：逆推公式：其中，其中，gk(uk)是阶段指标函数是阶段指标函数(5)最优指标函数最优指标函数fk(sk)：第第k至至3阶段采取最优分配策阶段采取最优分配策略，得到不成功概率最小略，得到不成功概率最小 u3s3g3(u3)minu3=0u3=1u3=2

29、f3(s3)u*3(s3)00.80.8010.80.50.5120.80.50.30.32k=3,S3=0,1,2,f3(s3)ming3(u3)*1 u2s2g2(u2)*f2(s2)minu2=0u2=1u2=2f2(s2)u*2(s2)00.6*0.80.48010.6*0.50.4*0.80.3020.6*0.30.4*0.50.2*0.80.162k=2,S2=0,1,2,f2(s2)ming2(u2)*f2(s2)g1(u1)*f2(s2)mins1 u1012f1(s1)u*1(s1)20.4*0.16=0.0640.2*0.3=0.060.15*0.48=0.0720.061

30、k=1,S1=2,f1(s1)max g1(u1)*f2(s2)得到方案：得到方案：u1*1，u2*0，u3*1:产品产品 A分配分配1百万，产品百万，产品 B分配分配0，产品，产品 C分配分配1百万百万f*=0.062022/12/1845 例例4 背包问题背包问题n某卡车载重能力为某卡车载重能力为10吨，现要装三种产品，已知每件产品吨，现要装三种产品，已知每件产品的重量和利润如表：的重量和利润如表：n 又规定又规定产品产品3至多装至多装2件件。n问如何安排运输可使总利润最大？问如何安排运输可使总利润最大？产品种类产品种类k重量重量Pk(吨吨/件件)利润利润(价值价值)rk(元元/件件)A4

31、150B3120C280设设u1,u2,u3分别为分别为1、2、3货物的装载件数，得到数学模型：货物的装载件数，得到数学模型：n阶段阶段 k=1,2,3，n状态变量状态变量sk 第第k阶段初的可装载能力，阶段初的可装载能力，n决策变量决策变量uk 第第k阶段的装载件数，阶段的装载件数，n状态转移方程状态转移方程:（tk为为k产品的单件重量）产品的单件重量）n递推公式递推公式:f4(s4)=0,k=3,2,1 动态规划方法求解动态规划方法求解产品产品A产品产品B产品产品C物品物品A物品物品B物品物品Ck=1k=2k=3k=4s1=10s2s3s4阶段阶段k状态变量状态变量：装载前背包装载前背包的

32、容量的容量决策变量决策变量：装载的件数装载的件数u1u2u3决策允许集合决策允许集合：装载件数的范围装载件数的范围0u1s1/t1u1为整数为整数状态转移方程状态转移方程：背包容：背包容量和装载件数的关系量和装载件数的关系阶段指标阶段指标：vk(sk,uk)=rkuk 在背包中第在背包中第k种物品的价值种物品的价值最优指标最优指标：fk(sk)=maxrkuk+fk+1(sk+1)终端条件终端条件：f4(s4)=0s2s1-t1x1s3=s2-t2x2s4=s3-t3x30u2s2/t2u2为整数为整数0u3s3/t3,2u3为整数为整数nk=3 u3s3r3u3=80u3minu3=0u3=

33、1u3=2f3(s3)u*3(s3)01000230808014100801601602C的单件重量为的单件重量为2,限制最多装限制最多装2件件u u2 2s s2 2（公斤）（公斤）（公斤）（公斤）r r2 2u u2 2+f+f3 3(s(s3 3)=120u=120u2 2+f+f3 3(s(s2 2-3u-3u2 2)f f2 2(s(s2 2)u*u*2 2最优决策最优决策最优决策最优决策u u2 2=0=0u u2 2=1=1u u2 2=2=2u u2 2=3=30 0,1,10 0+0+00 00 0(0,0)(0,0)2 20 0+80+8080800 0(0,1)(0,1)

34、3 30 0+80+80120+0120+01201201 1(1,0)(1,0)4 40 0+160+160120+0120+01601600 0(0,0)(0,0)5 50 0+160+160120+80120+802002001 1(1,1)(1,1)6 60 0+160+160120+80120+80240+0240+02402402 2(2,0)(2,0)7 70 0+160+160120+16120+160 0240+0240+02802801 1(1,2)(1,2)8 80 0+160+160120+16120+160 0240+80240+803203202 2(2,1)(2,

35、1)9 90 0+160+160120+16120+160 0240+80240+80360+0360+03603603 3(3,0)(3,0)10100 0+160+160120+16120+160 0240+16240+160 0360+0360+04004002 2(2,2)(2,2)k=2,k=2,装载物品装载物品装载物品装载物品B B，f f2 2(s(s2 2)B的单件重量为的单件重量为3u u1 1s s1 1(公斤公斤公斤公斤)r r1 1u u1 1+f+f2 2(s(s2 2)=150 u)=150 u1 1+f+f2 2(s(s1 1-4u-4u1 1)f f1 1(u(

36、u1 1)u*u*1 1最优决策最优决策最优决策最优决策u u1 1=0=0u u1 1=1=1u u1 1=2=210100+4000+400150+240150+240300+80300+804004000 0(0,2,2)(0,2,2)k=1k=1，装载物品，装载物品，装载物品，装载物品A A，f f1 1(u(u1 1)最优解为：最优解为：物品物品A装装0件，物品件，物品B装装2件，物品件，物品C装装2件。最大价值为件。最大价值为400元。元。A A的单件重量为的单件重量为4 42022/12/1852例例5 生产库存问题生产库存问题q某厂在年末估计，下年某厂在年末估计，下年4个季度市

37、场对该厂某产品的需个季度市场对该厂某产品的需求量均为求量均为dk=3(k=1,2,3,4)，该厂每季度生产此产品的能，该厂每季度生产此产品的能力为力为bk=5(k=1,2,3,4,)。q每季度生产这种产品的固定成本为每季度生产这种产品的固定成本为F=13（不生产时为（不生产时为0），每一产品的单位变动成本为），每一产品的单位变动成本为C=2。q本季度产品如不能售出，则需发生库存费用本季度产品如不能售出，则需发生库存费用g=1/件，仓件，仓库能贮存产品的最大数量库能贮存产品的最大数量Ek=4。q年初年末库存为年初年末库存为0，试问如何安排试问如何安排4个季度的生产，以保证在满足市场需求个季度的生

38、产，以保证在满足市场需求的前提下，使生产和库存总费用最小的前提下，使生产和库存总费用最小?2022/12/1853假设假设：第：第 k季度可以销售的产品是本季度初的库存及本季度可以销售的产品是本季度初的库存及本季度的产量季度的产量(1)阶段：阶段：k=1,2,3,4 n=4.(2)状态变量状态变量sk：第第k季度初的库存量季度初的库存量.(3)决策变量决策变量uk：第第k 个季度的产量个季度的产量.(4)转移方程：转移方程：sk1 sk+uk-dk.(5)最优指标函数最优指标函数 fk(sk)：第第k季度至第季度至第4个季度采取最优策个季度采取最优策略时的最小总费用略时的最小总费用.2022/

39、12/1854fk(sk)minwk(uk,sk)+fk+1(sk+1)k=4,3,2,1f5(s5)0逆推公式：逆推公式：k=4 u4s4s2=w4+0min0123f4(s4)u*4(s4)0191931171722151513000nk=3 u3s3w3+f4(s3+u3-3)min012345f3(s3)u*3(s3)019+1922+1725+15383117+1920+1723+1526+0265215+1918+1721+1524+024430+1916+1719+1522+019041+1717+1520+0180nK=2 u2s2w2+f3(s2+u2-3)min12345f

40、2(s2)u*2(s2)019+3822+2625+24484117+3820+2623+2426+17435215+3818+2621+2424+1927+18434nk=1 u1s1w1+f2(s1+u1-3)min345f1(s1)u*1(s1)019+4822+4525+43673 or 42022/12/1860例例5 可靠性问题可靠性问题某机器工作系统由某机器工作系统由n个部件组成，这些部件正常工作关系为个部件组成，这些部件正常工作关系为串联串联，每个部件都装有主要元件的，每个部件都装有主要元件的备用件备用件，并可自动投入，并可自动投入工作。工作。显然备用件越多，可靠性越大，但系统

41、的成本、重显然备用件越多，可靠性越大，但系统的成本、重量、体积会变大。量、体积会变大。若已知备用件总费用为若已知备用件总费用为 C，总重量为总重量为W.ck 为第为第 k个部件装配一个备用件的费用个部件装配一个备用件的费用问：在这两个限制条件下，应如何选用部件的备用件个数，问：在这两个限制条件下，应如何选用部件的备用件个数，使得正常工作的可靠性最大？使得正常工作的可靠性最大？wk 为第为第 k个部件装配一个备用件的重量个部件装配一个备用件的重量Pk 第第 k个部件的故障概率个部件的故障概率Max V=dk(sk,uk)nk=1n k=1ck uk Cn k=1wk uk W uk 0 且为整数

42、且为整数 设设uk 为第为第 k个部件装配备用件个数个部件装配备用件个数dk(sk,uk)为为第第 k个部件装配个部件装配uk个备用件时，机器正常工作的个备用件时，机器正常工作的概率概率动态规划模型：动态规划模型：(1)阶段：阶段：k=1,2,n(2)决策变量：决策变量：uk：第第k个部件上装个部件上装 备用件个数备用件个数(3)状态变量：状态变量：sk：第第k-n个部件允许的总费用个部件允许的总费用tk：第第k-n个部件允许的总重量个部件允许的总重量(4)状态转移：状态转移：sk+1=sk-ck uk tk+1=tk-wk uk(5)fk(sk，tk)：第第k-n个部件，采取最优策略时机个部

43、件，采取最优策略时机器正常工作的概率。器正常工作的概率。逆推公式：逆推公式：fk(sk，tk)=maxdk(sk,uk)*fk+1(sk+1，tk+1)fn+1(sn+1，tn+1)=1k=n,1n某复合系统由某复合系统由A,B,C三个部分串联而成，已知：三个部分串联而成，已知：qA、B、C相互独立；相互独立；q各部分的单件故障率分别为：各部分的单件故障率分别为：P1=0.4，P2=0.2，P3=0.5；q每个部分的单件价格为：每个部分的单件价格为：A部分单价部分单价c1=1万元；万元；B部部分单价分单价c2=2万元；万元；C部分单价部分单价c3=3万元；万元；q可投资购置部件金额为可投资购置

44、部件金额为10万元。万元。n求求A、B、C三部分各应购置多少部件才能使系统的总可靠三部分各应购置多少部件才能使系统的总可靠率最大？率最大？n令令A、B、C分别为阶段分别为阶段1、2、3。nsk第第k阶段及以后可用来购买部件总额阶段及以后可用来购买部件总额nuk第第k环节配备的件数环节配备的件数n状态转移方程：状态转移方程：sk+1=skckuk n第第k环节本身的可靠率为：环节本身的可靠率为：n令：令：fk(sk)表示表示k阶段尚有资金阶段尚有资金sk时，可能获得时，可能获得k段及以后各段及以后各段组成系统的最高可靠率。段组成系统的最高可靠率。n递推方程为：递推方程为：n fk(sk)=max

45、 dk(sk，uk)fk+1(skckuk)，f4(s4)=1n采用后向动态规划法，从第采用后向动态规划法，从第3阶段算起。阶段算起。u3s3u31u32f3(s3)=maxd3(s3,u3)u*3345670.50.50.50.50.51-0.251-0.250.50.50.50.750.7511122n阶段阶段2，此时考虑当把钱用于购置，此时考虑当把钱用于购置B和和C部件时，各应购置部件时，各应购置多少个部件为最优。多少个部件为最优。显然，此时显然，此时B、C应至少各配制应至少各配制1个部件，故个部件，故s2c2+c3=2+3=5；同时，；同时，A部件亦至少配备部件亦至少配备1个部件，故个

46、部件，故s2101=9。u2s2u21u22u23f2(s2)u*2567890.80.50.80.50.80.50.80.750.80.750.960.50.960.50.960.50.9920.50.40.40.480.60.611211n阶段1，A部件处，s1=10万元。u1s1u11u12u13u14u15f1(s1)u*1100.60.60.840.60.9360.480.97440.40.990.40.50422022/12/1869例例6 机器负荷分配问题机器负荷分配问题 某厂有某厂有120台同一规格完好的机器台同一规格完好的机器.n 每台机床全年在每台机床全年在高负荷高负荷下工

47、作可创利下工作可创利9万元，但机器的报万元，但机器的报废率高废率高,每年将有每年将有1/2的机器报废的机器报废.n在在低负荷低负荷下工作可创利下工作可创利6万元，每年将有万元，每年将有1/4的机器报废的机器报废.试拟定连续试拟定连续3年的分配计划，使得总利润最大。年的分配计划，使得总利润最大。2022/12/1870动态规划模型动态规划模型:n分三个阶段，分三个阶段，k1、2、3。n定义：定义：sk第第k阶段完好的机器数量。阶段完好的机器数量。nuk第第k阶段用于高负荷工作的机器数量。阶段用于高负荷工作的机器数量。n状态转移方程：状态转移方程：n阶段函数为：阶段函数为：n令：令：fk(sk)表

48、示表示k阶段尚有机器数量为阶段尚有机器数量为sk时，可能获得总收时，可能获得总收益，则递推方程为：益，则递推方程为：采用后向动态规划法，从第采用后向动态规划法，从第3阶段算起。阶段算起。例例7 不确定采购问题不确定采购问题某厂某厂5周内需采购一批原周内需采购一批原料，价格波动见右表料，价格波动见右表试求：在哪周，以什么价试求：在哪周，以什么价格购进，期望价格最低？格购进，期望价格最低？单价单价 P500 0.3600 0.3700 0.4分析分析(1)分分5个阶段个阶段 (2)状态变量状态变量sk：第第k周的实际价格周的实际价格Sk=500，600，700(3)决策变量决策变量uk：1 第第k

49、周采购周采购0 第第k周等待周等待SkE：第第k周等待，以后再采购的期望价格周等待，以后再采购的期望价格(4)最优指标函数最优指标函数fk(Sk)，第第k到到5周采用最优采购策略时的周采用最优采购策略时的最低期望价格。最低期望价格。基本方程：基本方程：fk(sk)=min sk，SkE k=4,3,2,1f5(s5)=s5k=5 f5(s5)=s5 x5=1 s5 500 600 700f5(s5)500 600 700 u5 1 1 1k=4 f4(s4)=min s4，S4ES4E=0.3 f5(500)+0.3 f5(600)+0.4 f5(700)=610 f4(s4)=min s4，

50、610=500,当当s4=500600,当当s4=600610,当当s4=700 u4=0 u4=1k=3 S3E=0.3 f4(500)+0.3 f4(600)+0.4 f4(700)=0.3500+0.3600+0.4610 =574 f3(s3)=min s3，S3E =min s3，574 500,当当s3=500 u3=1574,当当s3=600,700 u3=0=k=2 f2(s2)=min s2，551.8500,当当s2=500 u2=1551.8,当当s2=600,700 u2=0=k=1 f1(s1)=min s1，536.26500,当当s1=500 u1=1536.26