企业运筹学--动态规划讲义.pptx

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

1、运筹学运筹学动态规划动态规划的概念与模型动态规划的概念与模型l静态决策 一次性决策l动态决策 多阶段决策决策x1x2Zu输入决策输出决策效应第一月x1x2r1u1第二月x3r2u2第三月x4r3u3多段决策过程多段决策过程T1x1x2r1u1T2x3r2u2Tkxkxk+!rkukTnxnxn+1rnunn个决策子问题K称为阶段变量xk描述k阶段初的状态，称为状态变量一般把输入状态称为该阶段的阶段状态。uk的取值代表k阶段对第k子问题所进行的决策，称为k阶段的决策变量rk为k阶段从状况xk出发,做决策uk之后的后果，称为k阶段的阶段效应。 具有无后效性的多段决策过程具有无后效性的多段决策过程

2、Xk+1=Tk (xk, uk)系统从k阶段往后的决策只与k阶段系统的状态xk有关,而与系统以前的决策无关，则称为具有无后效性的多段决策过程。 T1x1x2r1 (x1, u1)u1(x1)T2x3r2 (x2 ,u2)u2 (x2)Tkxkxk+!rk (xk,uk)uk (xk)Tnxnxn+1rn (xn,un)un (xn)K后部子过程后部子过程多段决策过程中从第k阶段到最终阶段的过程称为k-后部子过程，简称k-子过程。 Tkxkxk+!rk (xk,uk)uk (xk)Tnxnxn+1rn (xn,un)un (xn)动态规划模型动态规划模型Opt表示求优Xk是一个集合，表示k阶段状

3、态可能取值的范围，称为状态可能集合。Uk是一个集合，表示k阶段决策可能取值的范围，称为决策允许集合，一般来说对于不同状态，可以作的决策的范围是不同的。因此决策允许集合一般写为Uk(xk)。 ),(11kkknkuuuxrRoptnnkUuXxuxTxtskkkkkkkk1),(. .1动态规划的建模动态规划的建模 动态规划建模确定阶段与阶段变量明确状态变量和状态可能集合。确定决策变量和决策允许集合。确定状态转移方程。明确阶段效应和目标。动态规划的建模动态规划的建模确定阶段与阶段变量阶段的划分一般是按照决策进行的时间或空间上的先后顺序划分的，阶段数等于多段决策过程中从开始到结束所需要作出决策的数

4、目，阶段变量用k表示。明确状态变量和状态可能集合。状态变量必须包含在给定的阶段上确定全部允许决策所需要的信息。状态变量的确定决定了整个决策过程是不是具有无后效性，因而也决定着能不能用动态规划方法来求解。状态可能集是关于状态的约束条件，因此为了求解必须正确地确定状态可能集。动态规划的建模动态规划的建模确定决策变量和决策允许集合。与静态问题相同，决策变量应能够反映对问题所作的决策，决策变量也应有其相应的约束条件，在建模时应明确决策允许集合Uk(xk)。确定状态转移方程。系统k阶段从状态xk出发作了决策uk(xk)之后的结果之一是系统状态的转移，这一结果直接影响系统往后的决策过程，因此必须明确状态的

5、转移过程，即根据问题的内在关系，明确xk+1=Tk(xk,uk)中的函数Tk（ ）。动态规划的建模动态规划的建模明确阶段效应和目标。阶段效应rk(xk,uk)是在阶段k以xk出发作了决策uk之后所产生的后果，必须明确rk与xk，uk的关系，才能构成目标函数。目标函数是由阶段效应经过某种集结而得到的，如何集结视具体问题而定，同时还应根据问题确定目标是求最大还是最小。由于在经济系统中的大多数情况下，目标的集结方法都是求和，因此，在不作说明的情况下，往后的讨论都针对目标为和的形式进行。 动态规划解的概念动态规划解的概念多段决策过程中所要求解的是，从起始状态x1开始，进行一系列的决策，使目标R达到最优

6、最优目标值 R*最优策略 使得目标达到最优的决策序列。最优路线 在采取最优策略时，系统从x1开始所经过的状态序列求解动态规划模型 找到最优策略、最优路线和最优目标值。 ),(*2*1nuuu),(*1*2*1nxxx),(*1kkkkuxTx动态规划最优性原理动态规划最优性原理多段决策过程的特点 每个阶段都要进行决策 相继进行的阶段决策构成的决策序列 前一阶段的终止状态又是后一阶段的初始状态阶段最优决策不能只从本阶段的效应出发，必须通盘考虑，整体规划。阶段k的最优决策不应该只是本阶段效应的最优，而必须是本阶段及其所有后续阶段的总体最优，即关于整个k后部子过程的最优决策。动态规划最优性原理动态规

7、划最优性原理最优性原理 “最优策略具有的基本性质是：无论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，下余的决策序列必构成最优策略”。AMB动态规划最优性原理动态规划最优性原理最优性原理的含意 最优策略的任何一部分子策略，也是相应初始状态的最优策略。 每个最优策略只能由最优子策略构成。显然，对于具有无后效性的多段决策过程而言，如果按照k后部子过程最优的原则来求各阶段状态的最优决策，那么这样构成的最优决策序列或策略一定具有最优性原理所提示的性质。 贝尔曼函数贝尔曼函数贝尔曼函数fk(xk)： 在阶段k从初始状态xk出发，执行最优决策序列或策略，到达过程终点时，整个k-子过程中的目标函

8、数取值，称为条件最优目标函数，亦称贝尔曼函数。nkuxroptxfnkiiiiuukknk,.,2 , 1),()(条件最优策略 多段决策过程的任一阶段状态xk的最优策略 处于条件xk时的最优策略。条件最优决策 构成条件最优策略的决策)(kkxu,1nkkuuu贝尔曼函数贝尔曼函数条件最优目标函数值fk(xk) 执行条件最优策略时的目标函数值nkiiiikkuxrxf),()(条件最优路线 执行条件最优策略时的阶段状态序列),(1kkkkuxTx,11nnkkxxxx贝尔曼函数贝尔曼函数条件最优k-子策略 系统从xk出发，在k-后部子过程中的最优策略k-子过程条件最优目标函数 fk(xk)是从

9、xk出发系统在k-后部子过程中的最优目标值，多段决策问题所求解的最优目标函数值 R*=opt f1(x1*)动态规划基本方程 fk(xk)与fk1(xk1)之间的递推关系动态规划方法的依据是最优性原理动态规划基本方程动态规划基本方程设在阶段k的状态xk执行了任意选定决策uk后的状态是xk+1=Tk(xk,uk)。这时k-后部子过程就缩小为k+1后部子过程。根据最优性原理，对k+1后部子过程应采取最优策略，由于无后效性，k后部子过程的目标函数值为 ),(),(1kkkkkkkuxTfuxr),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTx动态规划基本方程动态

10、规划基本方程),(1kkkkuxTxnkiiiiuukkuxroptxfnk),()( ),(),(11nkiiiiuukkkuuxroptuxroptnkk)(),(11kkkkkuxfuxroptk动态规划基本方程动态规划基本方程),(1kkkkuxTxnkiiiikkuxrxf),()(nkiiiikkkuxruxr1),(),()(),(11kkkkkuxfuxroptk动态规划方法基本原理动态规划方法基本原理动态规划方法基本原理 ),(),()(1kkkkkkkukkuxTfuxroptxfk),(1kkkkuxTxrk(xk, uk)和xk+1=Tk(xk, uk)都是已知的函数求

11、fk(xk)需要首先求关于xk的所有k+1段状态xk+1的fk+1(xk+1)逆序地求出条件最优目标函数值集合和条件最优决策集合状态xk+1是由前面阶段的状态决定的用问题给定的初始条件，即可顺序地求出整个多段决策问题的最优目标函数值、最优策略和最优路线。动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n时，动态规划基本方程是 )(),()(11nnnnnunnxfuxroptxfn0)(11nnxf边界条件),()(nnnunnuxroptxfnk=n时的动态规划基本方程成为 )(,()(nnnnnnxuxrxf动态规划问题求解的一般

12、步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=n1时，动态规划的基本方程是)(),()(111111nnnnnunnxfuxroptxfn所有的fn(xn)都已经求出，因此可以根据xn=Tn-1(xn-1,un-1)就阶段n-1每个可能状态xn-1Xn-1求条件最优决策及相应的条件最优目标函数值fn1(xn1) )();(111111nnnnnnXxxuxf动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合k=1时，动态规划的基本方程是)(),()(22111111xfuxroptxfu所有的f2(x

13、2)都已经求出，因此可以根据x2=T1(x1,u1)就阶段1每个可能状态x1X1求条件最优决策及相应的条件最优目标函数值f1(x1) )();(111111Xxxuxf动态规划问题求解的一般步骤动态规划问题求解的一般步骤 逆序地求出条件最优目标函数值集合和条件最优决策集合)();(111111Xxxuxf),(111uxr)(22xf)();(111111nnnnnnXxxuxf),(111nnnuxr)(nnxf)();(nnnnnnXxxuxf),(nnnuxr动态规划问题求解的一般步骤动态规划问题求解的一般步骤 顺序地求出最优目标值、最优策略和最优路线若x1已知，则)(11*11xfop

14、tRXx )(*11xf)(11*xfR )()(111*1xuxu阶段1的条件最优决策就是阶段1的关于整个过程的最优决策若x1未知 )()(*11*1*1xuxu动态规划问题求解的一般步骤动态规划问题求解的一般步骤顺序地求出最优目标值、最优策略和最优路线)(11*11xfoptRXx )(*11xf*1x)()(*1*1*11xuxu),(*1*11*2uxTx)()(*2*2*22xuxu)()(*1*1*11nnnnxuxu),(*1*11*nnnnuxTx)()(*nnnnxuxu),(*1nnnnuxTx),(*2*22*3uxTx 动态规划四大要素、一个方程动态规划四大要素、一个方

15、程五个关键因素 四大要素、一个方程：状态变量及其可能集合决策变量及其允许集合状态转移方程阶段效应动态规划基本方程：),(1kkkkuxTx),(kkkuxr),(),()(1kkkkkkkukkuxTfuxroptxfk动态规划应用举例动态规划应用举例-定步数问题例41 某旅行者希望从s地起到t地，其间的道路系统如图47所示，图上圆圈表示途径的地方，称为节点，连结两地的箭线表示道路，其上的数字表示该段道路长度，箭头表示通行的方向。试求s到t的最短路。adbetcfs9757845646547图4-7动态规划应用举例动态规划应用举例-定步数问题adbetcfs9757845646547第一阶段第

16、一阶段 第二阶段第二阶段 第三阶段第三阶段划分阶段划分阶段 k=1,2,3 代表三个阶段代表三个阶段动态规划应用举例动态规划应用举例-定步数问题adbetcfs9757845646547状态变量状态变量xk取为取为k阶段所在地，则有：阶段所在地，则有： ,2211cbaXxsXx,4433tXxfedXx动态规划应用举例动态规划应用举例-定步数问题adbetcfs9757845646547k阶段决策是决定下一步走到哪里，阶段决策是决定下一步走到哪里，uk(xk)取为下一步的所在点。取为下一步的所在点。 ,)(11cbasUu,)()(22fdaUau,)()(22edbUbu,)()(22fe

17、dcUcu33tUu动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集由于第3阶段末已到达t，往后的距离自然是零，因此f4(t)=0对3阶段所有可能的状态X3=d, e, f计算f3( )如下)(),(min)(4433333xfudrdfUutdutftdr)(5)(),(min343)(),(min)(4433333xfuerefUuteuter)(70),(min33)(),(min)(4433333xfufrffUutfutfr)(40),(min33动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计

18、算如下t/tF3()U3()def5+07+04+0574tttr3(x3,u3)+f4(x4) f3(x3) u3(x3) 动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集adbetcfs9757845646547475动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a, b, c计算f2( )如下)(),(min)(3322)(222xfuarafaUu)(),(min3322,2xfuarfdu)(),()(),(min3232fffardfdarfau)(84457min2)(),(mi

19、n)(3322)(222xfubrbfbUu)(),()(),(min3232efebrdfdbrdbu)(107655min2动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对2阶段所有可能的状态X2=a, b, c计算f2( )如下)(),(min)(3322)(222xfucrcfcUu)(),()(),()(),(min323232fffcrefecrdfdcrdcu)(9467554min2动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集也可以用表格方法计算如下d/de/ef/fF2()U2()abc7+55+5

20、4+56+75+74+46+48109fddf2(x2) u2(x2) r2(x2,u2)+f3(x3) 动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集adbetcfs97578456465474759108动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集对1阶段所有可能的状态X1=s计算f1( )如下)(),(min)(2211)(111xfusrsfsUu)(),()(),()(),(min212121cfcsrbfbsrafasrcsu)(169710889min1a/ab/bc/cF2()U2()s9+88+10

21、7+916c动态规划应用举例动态规划应用举例-定步数问题顺序求最优策略、最优路线和最优目标函数值16)(11*11xfoptRXxsx *1csu)(*1cx *2dcu)(*2tx *4tdu)(*3dx *3动态规划应用举例动态规划应用举例-定步数问题逆序求条件最优目标函数集和条件最优决策集adbetcfs9757845646547475910816动态规划应用举例动态规划应用举例-不定步数问题acbdst6952448423图4-8例例42 用用f(i)表示表示I节点到节点到t节点的最短距离，则根据动态规划原理，节点的最短距离，则根据动态规划原理，应该有：应该有： 0)(tf)(),(m

22、in)(jfjirifj动态规划应用举例动态规划应用举例-不定步数问题acbdst6952448423图4-8例例42 可用迭代的方法来实现求解。可用迭代的方法来实现求解。迭代可以针对迭代可以针对f( )来进行，称为函数迭代法来进行，称为函数迭代法也可以针对策略也可以针对策略u(i)(i=s, a, b, c, d)进行，称为策略迭代法进行，称为策略迭代法0)(tf)(),(min)(jfjirifj不定步数问题不定步数问题-函数迭代法函数迭代法 函数迭代法步骤函数迭代法步骤选定一初始函数选定一初始函数f1(i) 0)(,),()(11tfdcbasitirif然后用递推关系求然后用递推关系求

23、fk(i) 可以一步到达的节点）为从（其中ijtfdcbasijfjirifkkjk0)(,)(),(min)(1fk(i)为从为从i点出发走点出发走k步到步到t的最短距离的最短距离 ，若对于某个，若对于某个k，有有fk+1(i)=fk(i)，对所有节点对所有节点i成立，则成立，则fk( )即为条件最优目标函即为条件最优目标函数，求解结束。数，求解结束。 否则重复上述过程，直至最优。否则重复上述过程，直至最优。不定步数问题不定步数问题-函数迭代法函数迭代法acbdst6952448423图4-8例例42 取取)(1sf)(1af)(1bf2)(1cf4)(1df0)(1tf88 ,9 ,0mi

24、n)(),(),(),(),(),(min)(1112bfbsrafasrsfssrsf不定步数问题不定步数问题-函数迭代法函数迭代法例例42 )(),(),(),(),(),(min)(1112dfbarcfcarafaaraf45 , 26 ,0min8)(),(),(),(),(),(),(),(min)(11112dfdbrcfcbrbfbbrafabrbf44 , 22 ,0 ,4min4)(),(),(),(),(),(min)(1112tftcrdfdcrcfccrcf02 , 43 , 20min2)(),(),(),(min)(112tftdrdfddrdf404 , 40m

25、in0)(2tf不定步数问题不定步数问题-函数迭代法函数迭代法例例42 sabcdtf1( )240f2( )84240f3( )1284240f4( )1284240不定步数问题不定步数问题-策略迭代法策略迭代法策略迭代法步骤：策略迭代法步骤： 1 给每个点给每个点i选择一个下一步到达的点选择一个下一步到达的点u0(i)，i=s, a, b, c, d 取取k=0 0)()()(,()(tfiufiuirifkkkkk)(),(minufuirku)(1iuk)()(1iuiukk2 由由 算出算出fk(i)3 由由解出解出则已经最优则已经最优,否则继续计算否则继续计算若若不定步数问题不定步

26、数问题-策略迭代法策略迭代法acbdst6952448423图4-8例例42 取取asu)(0dau)(0dbu)(0tcu)(0tdu)(00)(0tf2)(),()(00tftcrcf4)(),()(00tftdrdf844)(),()(00dfdbrbf945)(),()(00dfdaraf1899)(),()(00afasrsf不定步数问题不定步数问题-策略迭代法策略迭代法例例42 )()(),(min10iuufuirn找出求bsubfbsrafasr)(168899min)(),()(),(min100caudfdarcfcar)(84526min)(),()(),(min100c

27、budfdbrcfcbrafabr)(4442294min)(),()(),()(),(min1000tcutftcrdfdcr)(20243min)(),()(),(min100tdutftdr)(404min)(),(min10不定步数问题不定步数问题-策略迭代法策略迭代法acbdst6952448423图4-8例例42 bsu)(1cau)(1cbu)(1tcu)(1tdu)(11248)(),()(11bfbsrsf0)(1tf2)(),()(11tftcrcf4)(),()(11tftdrdf422)(),()(11cfcbrbf826)(),()(11cfcaraf不定步数问题不定

28、步数问题-策略迭代法策略迭代法bsubfbsrafasr)(124899min)(),()(),(min211caudfdarcfcar)(84526min)(),()(),(min211cbudfdbrcfcbrafabr)(4442284min)(),()(),()(),(min2111tcutftcrdfdcr)(20243min)(),()(),(min211tdutftdr)(404min)(),(min21不定步数问题不定步数问题-策略迭代法策略迭代法xu0f0u1f1u2sa18b12bad9c8cbd8c4cct2t2tdt4t4tt00资源分配问题资源分配问题 资源的多元分配

29、资源的多元分配 设有某种资源，总量为设有某种资源，总量为M，可以投入可以投入n种生产活动。已知用种生产活动。已知用于活动于活动k的资源为的资源为uk时的收益是时的收益是gk(uk)，问应如何分配资源，问应如何分配资源，使使n种生产活动的总收益最大。这种问题就是资源的多元分种生产活动的总收益最大。这种问题就是资源的多元分配问题。配问题。 )()()(max2211nnugugugZMuuutsn21. .0,21nuuu资源分配问题资源分配问题 资源的多元分配资源的多元分配 如果将如果将n种活动作为一个互相衔接的整体，对一种活动的资种活动作为一个互相衔接的整体，对一种活动的资源分配作为一个阶段，

30、每个阶段确定对一种活动的资源投源分配作为一个阶段，每个阶段确定对一种活动的资源投放量。则该问题成为一个多段决策问题。放量。则该问题成为一个多段决策问题。状态变量状态变量xk的选取原则是要能够据此确定决策的选取原则是要能够据此确定决策uk，以及满足以及满足状态转移方程所要求的无后效性。状态转移方程所要求的无后效性。在资源分配问题中，决策变量选为对活动在资源分配问题中，决策变量选为对活动k的资源投放量，的资源投放量，因此状态变量可以选择为阶段因此状态变量可以选择为阶段k初所拥有的资源量，即将要初所拥有的资源量，即将要在第在第k种到第种到第n种活动间分配的资源量。种活动间分配的资源量。资源的多元分配

31、资源的多元分配 关于状态变量关于状态变量xk的约束条件是的约束条件是 0 xkM关于决策变量关于决策变量uk的约束条件是的约束条件是 0ukxk 状态转移方程为状态转移方程为 xk+1=xk-uk 显然它满足无后效性要求。显然它满足无后效性要求。阶段效应为对活动阶段效应为对活动k投放资源投放资源uk时的收益，时的收益， rk(xk, uk)=gk(uk)目标函数是为目标函数是为n种活动投放资源后的总收益种活动投放资源后的总收益动态规划基本方程动态规划基本方程nkkkugR1)()()(max)(11kkkkukkxfugxfk资源的多元分配资源的多元分配 例例43 某公司拟将某公司拟将50万元

32、资金投放下属万元资金投放下属A、B、C三个部门，三个部门，各部门在获得资金后的收益如表所示，用动态规划方法求各部门在获得资金后的收益如表所示，用动态规划方法求总收益最大的投资分配方案（投资数以总收益最大的投资分配方案（投资数以10万元为单位）。万元为单位）。 投放资金（万元）投放资金（万元） 01020304050收收益益（万元）（万元） A01520252830B0010254570C01020304050资源的多元分配资源的多元分配 解解 该问题可以作为三段决策过程。对该问题可以作为三段决策过程。对A、B、C三个部门分三个部门分配资金分别形成配资金分别形成1，2，3三个阶段。三个阶段。xk

33、表示给部门表示给部门k分配资分配资金时拥有的资金数。金时拥有的资金数。uk表示给部门表示给部门k分配的资金数（以分配的资金数（以10万万元为单位）。状态转移方程是元为单位）。状态转移方程是xk+1=xk-uk。阶段效应如表所阶段效应如表所示。目标函数是阶段效应求和。示。目标函数是阶段效应求和。投放资金（万元）投放资金（万元） 01020304050收收益益（万元）（万元） A01520252830B0010254570C01020304050资源的多元分配资源的多元分配 首先逆序求条件最优目标函数值集合和条件最优决策集合。首先逆序求条件最优目标函数值集合和条件最优决策集合。 )()(max)(

34、4433333xfugxfu0)(44xf)(max)(3303333ugxfxu )()(3333ugxf从表可知从表可知g3( )是单调递增的函数，因此，当是单调递增的函数，因此，当u3=x3时达到最时达到最大。即：大。即： 33xu 资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。 )()(3333ugxf33xu 0)0(, 0)0()0(333ugf1) 1 (,10) 1 () 1 (333ugf2)2(,20)2()2(333ugf3)3(,30)3()3(333ugf4)4(,40)4()4(333u

35、gf5)5(,50)5()5(333ugf资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。 )()(3333ugxf33xu x3g3f3U30000110101220202330303440404550505资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。k=2时，时，0 x25 0u2x2 )()(max)(332202222xfugxfxu)()(max)0(33220022xfugfu0)0(0)0()0(232ufg)()(max

36、) 1 (33221022xfugfu0) 1 (1000100max)0() 1 () 1 ()0(max23232ufgfg)()(max)2(33222022xfugfu0)2(20010100200max)0()2() 1 () 1 ()2()0(max2323232ufgfgfg资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。k=2时，时，0 x25 0u2x2 )()(max)(332202222xfugxfxu0/x21/x2-12/x2-23/x2-34/x2-45/x2-5f2()U200+0001

37、0+100+010020+200+1010+020030+300+2010+1025+030040+400+3010+2025+1045+045450+500+4010+3025+2045+1070+0705资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。当当k=1时，有时，有x1=5，0u1x1=5 )()(max)5(22115011xfugfu)0()5() 1 ()4()2()3()3()2()4() 1 ()5()0(max212121212121fgfgfgfgfgfg0)5(70030102820253

38、0204515700max1u资源的多元分配资源的多元分配 逆序求条件最优目标函数值集合和条件最优决策集合。逆序求条件最优目标函数值集合和条件最优决策集合。当当k=1时，有时，有x1=5，0u1x1=5 )()(max)5(22115011xfugfu0/51/42/33/24/15/0f1()U150+7015+45 20+30 25+20 28+1030+0700资源的多元分配资源的多元分配 顺序求最优目标函数值和最优策略、最优路线顺序求最优目标函数值和最优策略、最优路线0/51/42/33/24/15/0f1()U150+7015+45 20+30 25+20 28+1030+07005

39、*1x0)5(*1u5*2x5)5(*2u0*4x0)0(*3u0*3x70)(11*11xfoptRXx资源的多段分配资源的多段分配 将一种有消耗性的资源，多阶段地在多种不同的生产活动中将一种有消耗性的资源，多阶段地在多种不同的生产活动中投放的问题称为资源的多段分配问题，下面讨论其中包含有投放的问题称为资源的多段分配问题，下面讨论其中包含有两个生产活动的简单情况。两个生产活动的简单情况。设有某种资源，初始的拥有量是设有某种资源，初始的拥有量是M。计划在计划在A，B两个生产部两个生产部门连续使用门连续使用n个阶段。已知在部门个阶段。已知在部门A投入资源投入资源uA时的阶段收益时的阶段收益是是g

40、(uA)，在部门在部门B投入资源投入资源uB时的阶段收益是时的阶段收益是h(uB)。又资源又资源在生产中将有部分消耗，已知每生产一个阶段后部门在生产中将有部分消耗，已知每生产一个阶段后部门A，B中中的资源完好率分别为的资源完好率分别为a和和b，0(a, b)1。求求n阶段间总收益最阶段间总收益最大的资源分配计划。大的资源分配计划。 资源的多段分配资源的多段分配 n段决策过程段决策过程状态变量状态变量xk为阶段为阶段k初拥有的资源量，初拥有的资源量，0 xkM，x1=M决策变量选为阶段决策变量选为阶段k在部门在部门A的资源投放量，即的资源投放量，即uA=uk，这里显这里显然有然有uB=xk- u

41、k，决策变量的约束条件是决策变量的约束条件是 0ukxk即最多将所拥有的资源都投入部门即最多将所拥有的资源都投入部门A，其时其时uB=0阶段阶段k末部站末部站A的剩余资源的剩余资源auk，部门部门B中则为中则为b(xk-uk)，因此状因此状态转移方程态转移方程xk+1=T(xk, uk)是是 xk+1=auk+b(xk-uk) 满足无后效性满足无后效性阶段效应阶段效应rk(xk, uk)即阶段收益即阶段收益rk(xk, uk)=g(uk)+h(xk-uk)目标函数是目标函数是n个阶段的总收益，即阶段效应求和。个阶段的总收益，即阶段效应求和。 资源的多段分配资源的多段分配 例例44 今有今有10

42、00台机床，要投放到台机床，要投放到A、B两个生产部门，计两个生产部门，计划连续使用划连续使用3年。已知对年。已知对A部门投入部门投入uA台机器时的年收益是台机器时的年收益是g(uA)=4(uA)2（元），机器完好率元），机器完好率a=0.5，相应的相应的B部门的年收部门的年收益是益是h(uB)=2(uB)2 （元），完好率（元），完好率b= 0.9。试求使试求使3年间总收年间总收益最大的年度机器分配方案。益最大的年度机器分配方案。 解解 以每年作为一个阶段，设状态变量和决策变量都是连续取以每年作为一个阶段，设状态变量和决策变量都是连续取值的。值的。K阶段状态变量阶段状态变量xk取为该年度初完

43、好的设备数，决策变取为该年度初完好的设备数，决策变量取为该年度投入量取为该年度投入A活动的设备数，则有活动的设备数，则有 0 xk1000， 0ukxk状态转移方程为：状态转移方程为：xk+1=0.5uk+0.9(xk-uk)资源的多段分配资源的多段分配 例例44解解 以每年作为一个阶段，设状态变量和决策变量都是连续取以每年作为一个阶段，设状态变量和决策变量都是连续取值的。值的。K阶段状态变量阶段状态变量xk取为该年度初完好的设备数，决策变取为该年度初完好的设备数，决策变量取为该年度投入量取为该年度投入A活动的设备数，则有活动的设备数，则有 0 xk1000， 0ukxk状态转移方程为：状态转

44、移方程为：xk+1=0.5uk+0.9(xk-uk)动态规划基本方程动态规划基本方程)()(24max)(1122kkkkkukkxfuxuxfk资源的多段分配资源的多段分配 逆序求条件最优目标函数值逆序求条件最优目标函数值fk(xk)和条件最优决策和条件最优决策k=3时，时，0u3x3，注意到注意到f4(x4)=0，有有 )(24max)(23323333uxuxfu23334)(xxf333)(xxuk=2时，时，0u2x2，有有 )(9 . 05 . 0(2)(24max)(22232222222uxufuxuxfu)(9 . 05 . 0 42)(24max222222222uxuux

45、uu222224. 5)(xxf0)(22xu资源的多段分配资源的多段分配 逆序求条件最优目标函数值逆序求条件最优目标函数值fk(xk)和条件最优决策和条件最优决策k=1时，时，0u1x1，x2=0.5u1+0.9(x1-u1)，f2(x2)(9 . 05 . 0(2)(24max)(11121121111uxufuxuxfu)(9 . 05 . 024. 52)(24max211111211uxuuxuu21112444. 6)(xxf0)(11xu1000*1x0)1000(*1u900*2x0)900(*2u405*4x810)810(*3u810*3x串联系统可靠性问题串联系统可靠性问

46、题 系统可靠性是指系统在规定的条件下能正常工作的概率，它是管理和工程系统可靠性是指系统在规定的条件下能正常工作的概率，它是管理和工程技术设计中经常要研究的问题。技术设计中经常要研究的问题。这儿要研究的是串联系统可靠性问题。例如某种仪器设备由这儿要研究的是串联系统可靠性问题。例如某种仪器设备由N个部件串联个部件串联构成，凡其中有一个部件出现故障，则整个系统便不能正常工作。构成，凡其中有一个部件出现故障，则整个系统便不能正常工作。为了提高系统工作的可靠性，一种方法是可以在每个部件上装有主要元件为了提高系统工作的可靠性，一种方法是可以在每个部件上装有主要元件的相同性能的备用件，并且带有备用元件自动投

47、入装置。的相同性能的备用件，并且带有备用元件自动投入装置。自然备用元件越多，系统的可靠性越高，但也会相应增加系统重量、体积自然备用元件越多，系统的可靠性越高，但也会相应增加系统重量、体积和费用，有时也会降低工作精度。和费用，有时也会降低工作精度。因此，在成本、重量、体积等一定的条件限制下，应如何选择各部件的备因此，在成本、重量、体积等一定的条件限制下，应如何选择各部件的备用元件数，使得整个系统的可靠性最大，就可以归结为一个动态规划问题。用元件数，使得整个系统的可靠性最大，就可以归结为一个动态规划问题。串联系统可靠性问题串联系统可靠性问题 例例45 某电气设备由三个部件串联而成，为提高该种设备在

48、指定工作条某电气设备由三个部件串联而成，为提高该种设备在指定工作条件下正常工作的可靠性，需在每个部件上安装一个、两个或三个主要元件件下正常工作的可靠性，需在每个部件上安装一个、两个或三个主要元件的相同备件。假设对部件的相同备件。假设对部件i(i=1，2，3)配备配备j个备件后的可靠性个备件后的可靠性Rij和所需费和所需费用用cij均已知，如表所示，若可用的总资金数量为均已知，如表所示，若可用的总资金数量为1万元，问如何配备各部万元，问如何配备各部件的备用元件数，才能使该设备在给定工作条件下的可靠性最大？件的备用元件数，才能使该设备在给定工作条件下的可靠性最大？ 备件数部件j=1j=2j=3Ci

49、1（千元)Ri1Ci2（千元）Ri2Ci3（千元）Ri3110.9030.9450.96230.7550.8860.97320.8030.9240.99串联系统可靠性问题串联系统可靠性问题 例例45 解解 以给不同的部件决定备件作为不同的阶段，则该以给不同的部件决定备件作为不同的阶段，则该问题是问题是3阶段决策问题阶段决策问题设状态变量设状态变量xk表示从第表示从第k个部件到第个部件到第3个部件允许使用的总费个部件允许使用的总费用（用（k=1,2,3）决策变量决策变量uk为第为第k部件配备的备用元件数（部件配备的备用元件数（k=1，2，3）。）。则据题意有：则据题意有：x1=10千元，且每个部

50、件都最少有一个备件，即千元，且每个部件都最少有一个备件，即uk1，若令若令sk表示为保障以后各部件均能获得一个备件所需的表示为保障以后各部件均能获得一个备件所需的资金数，则应有：资金数，则应有： 31kiikcs串联系统可靠性问题串联系统可靠性问题 例例4531kiikcs且据此可得：且据此可得：s1=6，s2=5，s3=2。从而可知：对从而可知：对uk有有 kkkuxsck1即当期所耗资金加上即当期所耗资金加上k+1期往后所用资金期往后所用资金sk+1不超过当前拥有不超过当前拥有资金数。资金数。串联系统可靠性问题串联系统可靠性问题 例例45根据上述分析可以写出各阶段的状态可能集合和决策允许集