上海交通大学：《运筹学》教学资源（课程讲义）第五章动态规划应用举例.pdf_大学文库

第五章动态规划应用举例（书第9章） §5.1资源分配问题将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等），恰当得分配给若干个使用者，使目标函数最优。 5.1.1一维资源无回收的分配问题设有某种资源，总数量为α，用于生产n种产品。若分配数量为x的资源给第i种产品的生产，则可得收益g(x)。问应如何分配资源，使生产n种产品的总收益最大？静态规划： maxz=8(x)+…+gn(xn) S.l.x+…+xn=a x,≥0，j=1,…,n 动态规划：设阶段：把资源分配给一个产品的生产作为一个阶段，k=1,…,n: 状态变量s:分配给第k种产品至第n种产品的资源数量，0≤s≤a: 决策变量4：分配给第k种产品的资源数量（即山=x),0≤山≤S: 状态转移方程：S+=S-山：指标函数：，4)=g4(),,4,,5,4,5)=之g,,)(加式) 最优值函数f(S):以数量为S,的资源分配给第k种产品至第种产品的生产时可获得的最大收益。则得基本方程： f(s)=max{8x(u)+i+(-4)乃，k=n,…,1 (s)=0 最终求得f(a)即为最大收益。例5.1.1P213 a=5,可用表格求解。注：当=4时，可马上利用已有结果求得。当=6时，也可利用已有表格再补充数据求得。 5.1.2一维资源有回收的分配问题设有数量为S1的某种资源，可投入A和B两种生产。对于A的生产，产品的年产量g和投入生产的资源数量u的关系为g=g(),这时资源的年完好率为a,0<a<l,即如果年初资源的数量为山，到年终时完好的资源数为au。对于B的生产，产品的年产量h和投入生产的机器数量u的关系为h=h(),这时资源的年完好率为b,O<b<1,即如果年初资源的数量为4，到年终时完好的资源数为bu。试问，应当如何决定每年投入A生产的资源数，使n年内产品的总产量达到最高。静态规划：设4：第k年投入A生产的资源数，S:第k年初的资源数，则第什1年初的资源数Sk1=a+b(s一4e), 第k年的产量g(4)+hs-,),得模型：

1 第五章动态规划应用举例(书第 9 章) §5.1 资源分配问题将数量一定的一种或若干种资源（例如原材料、资金、机器设备、劳力、食品等），恰当得分配给若干个使用者，使目标函数最优。 5.1.1 一维资源无回收的分配问题设有某种资源，总数量为 a，用于生产 n 种产品。若分配数量为 xi 的资源给第 i 种产品的生产，则可得收益 gi (xi)。问应如何分配资源，使生产 n 种产品的总收益最大？静态规划： 1 1 1 max ( ) ( ) . . 0, 1, , n n n j z g x g x st x x a xj n = ++ ++= ≥ = " " " 动态规划：设阶段：把资源分配给一个产品的生产作为一个阶段， k n =1, , " ；状态变量 k s ：分配给第 k 种产品至第 n 种产品的资源数量，0 k ≤ s ≤ a ；决策变量 k u ：分配给第 k 种产品的资源数量(即 k k u x = )，0 k k ≤ u s ≤ ；状态转移方程： k kk 1 s s u + = − ；指标函数： (, ) () kk k k k vsu gu = ， , 1 (, , ,, , ) () n kn k k n n n j j j k V su sus gu + = " = ∑ （加式）最优值函数 ( ) k k f s ：以数量为 k s 的资源分配给第 k 种产品至第 n 种产品的生产时可获得的最大收益。则得基本方程： 1 0 1 1 ( ) max { ( ) ( )}, , ,1 ( )0 k k kk k k k k k u s n n fs gu f s u k n f s + ≤ ≤ + + ⎧ = +−= ⎪ ⎨ ⎪⎩ = " 最终求得 1f ( ) a 即为最大收益。例 5.1.1 P213 a=5，可用表格求解。注：当 a=4 时，可马上利用已有结果求得。当 a=6 时，也可利用已有表格再补充数据求得。 5.1.2 一维资源有回收的分配问题设有数量为 s1 的某种资源，可投入 A 和 B 两种生产。对于 A 的生产，产品的年产量 g 和投入生产的资源数量 u 的关系为 g=g(u)，这时资源的年完好率为 a，0<a<1, 即如果年初资源的数量为 u, 到年终时完好的资源数为 au。对于 B 的生产，产品的年产量 h 和投入生产的机器数量 u 的关系为 h=h(u)，这时资源的年完好率为 b，0<b<1, 即如果年初资源的数量为 u, 到年终时完好的资源数为 bu。试问，应当如何决定每年投入 A 生产的资源数，使 n 年内产品的总产量达到最高。静态规划：设 k u ：第 k 年投入 A 生产的资源数，k s ：第 k 年初的资源数，则第 k+1 年初的资源数 1 ( ) k k kk s au b s u + =+ − ，第 k 年的产量 () ( ) k kk g u hs u + − ，得模型：

2 1 1 max ( ( ) ( )) . . ( ), 1, , 1 0 , 1, , n k kk k k k kk k k gu hs u st s au b s u k n u sk n = + + − = +− = − ≤≤ = ∑ " " 动态规划：阶段：一年作为一个阶段， k n =1, , " ；状态变量 k s ：第 k 年初的的资源数量；决策变量 k u ：第 k 年分配给 A 生产的资源数量，0 k k ≤ u s ≤ ；状态转移方程： 1 ( ) k k kk s au b s u + =+ − ；指标函数： (, ) () ( ) kk k k k k v s u gu hs u = +− ， , 1 ( , , , , , ) ( ( ) ( )) n kn k k n n n k k k j k V s u s u s gu hs u + = " = +− ∑ （加式）最优值函数 ( ) k k f s ：第 k 年初有数量为 k s 的资源时，从第 k 年至第 n 年的最大总产量。则得基本方程： 1 0 1 1 ( ) max { ( ) ( ) ( ( ))}, , ,1 ( )0 k k kk k k k k k k k u s n n f s g u h s u f au b s u k n f s + ≤ ≤ + + ⎧ = + −+ + − = ⎪ ⎨ ⎪⎩ = " 最终求得 1 1 f ( ) s 即为最大收益。例 5.1.2 P217 1 gu uhu ua b s n ( ) 8 , ( ) 5 , 0.7, 0.9, 1000, 5 = == = = = 1 0 6 6 ( ) max {8 5( ) (0.7 0.9( ))}, 5, ,1 () 0 k k kk k k k k k k k u s fs u s u f u s u k f s + ≤ ≤ ⎧ = + −+ + − = ⎪ ⎨ ⎪⎩ = " 则 * 5 5 55 55 55 5 5 5 5 5 5 0 0 ( ) max {8 5( )} max {3 5 } 8 u s us us f s u su u s s = ≤≤ ≤≤ = +−= + = （都投入高负荷） 4 4 * 4 4 4 4 44 4 4 4 4 4 4 0 44 4 0 ( ) max {8 5( ) 8(0.7 0.9( ))} max {1.4 12.2 } 13.6 u s u s u s fs u s u u s u us s ≤ ≤ = ≤ ≤ = + −+ + − = += （都投入高负荷） * 3 3 3 3 33 3 3 3 3 3 3 3 0 ( ) max {8 5( ) 13.6(0.7 0.9( ))} 17.5 u s u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入高负荷） * 2 2 2 0 22 2 2 2 3 3 3 2 0 ( ) max {8 5( ) 17.5(0.7 0.9( ))} 20.8 u u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入低负荷） * 1 1 1 0 11 1 1 1 1 1 1 1 0 ( ) max{8 5( ) 20.8(0.7 0.9( ))} 23.7 u u s f s u su u su s = ≤ ≤ = + −+ + − = （都投入低负荷）由 1s =1000 得 * ** 1 2 1 11 1 u s u su s = = + −= = 0, 0.7 0.9( ) 0.9 900， * ** 2 3 2 22 2 u s u su s = = + −= = 0, 0.7 0.9( ) 0.9 810， * * ** 33 4 3 33 3 u s s u su u == = + − = = 810, 0.7 0.9( ) 0.7 567 ， * * ** 44 5 4 44 4 u s s u su u == = + − = = 567, 0.7 0.9( ) 0.7 397， * * ** 55 6 5 55 5 u s s u su u == = + − = = 397, 0.7 0.9( ) 0.7 278 。注：当要求第 5 年结束时，有完好机器 500 台，则 5 6 5 55 5 0.9 500 ( ) 500 3 s s au b s u u − = + − = ⇒=

3 得递推关系： 5 5 1 0 55 5 5 5 (0.9 500) / 3 ( ) max {8 5( ) (0.7 0.9( ))}, 4, ,1 ( ) max {8 5( )} k k kk k k k k k k k u s u s fs u s u f u s u k fs u s u + ≤ ≤ = − ⎧ = + −+ + − = ⎪ ⎨ = +− ⎪ ⎩ " 5.1.3 二维资源分配问题设有两种资源，总数量分别为 a 和 b，用于生产 n 种产品。若分配数量为 xi 的第一种资源和数量为 yi 的第二种资源给第 i 种产品的生产，则可得收益 gi (xi, yi)。问应如何分配资源，使生产 n 种产品的总收益最大？静态规划： 111 1 1 max ( , ) ( ,, ) . . , 0, 1, , nn n n n j j z g x y g x y st x x a y yb xy j n = + + ++= ++ = ≥ = " " " " 动态规划：设阶段：把资源分配给一个产品的生产作为一个阶段， k n =1, , " ；状态变量(,) k k s t ： k s 为分配给第 k 种产品至第 n 种产品的第一种资源的数量，0 k ≤ ≤ s a ； kt 为分配给第 k 种产品至第 n 种产品的第二种资源的数量，0 k ≤ ≤ t b ；决策变量(,) k k u v ： k u 分配给第 k 种产品的第一种资源的数量(即 k k u x = )，0 k k ≤ u s ≤ ； k v 分配给第 k 种产品的第二种资源的数量(即 k k v y = )，0 k k ≤ v t ≤ ；状态转移方程： k kk 1 s s u + = − ， k kk 1 t tv + = − ；指标函数： (( , ),( , )) ( , ) k kk k k k k k v st uv guv = ，子过程指标函数为加式；最优值函数 (,) k kk f s t ：以数量为 k s 的第一种资源和数量为 kt 的第二种资源分配给第 k 种产品至第 n 种产品的生产时可获得的最大收益。则得递推关系： 1 0 0 1 11 ( , ) max { ( , ) ( , ,)}, , ,1 ( , )0 k k k k k kk k k k k k kk k u s v t n nn fst guv f s ut v k n fst + ≤ ≤ ≤ ≤ + ++ ⎧ = + −− = ⎪ ⎨ ⎪ ⎩ = " 最终求得 1f (,) a b 即为最大收益。求解方法： 1．Lagrange 乘数法引入 Lagrange 乘数，将二种资源分配问题转化为一维资源分配问题。给定 λ ，考虑问题： 111 1 1 max ( , ) ( ,, ) ( ) . . , 0, 1, , nn n n n j j z g x y g x yy y st x x a xy j n = ++ − ++ λ ++= ≥ = " " " " 令 0 ( ) max{ ( , ) } i i i iii i y h x g x y y λ λ ≥ = − ，设最优解 ( ) i i y x λ 。则得一种资源分配问题：

6 1 0,1, ,min , 1 11 ( , ) max { ( ) ( , )}, , ,1 ( , )0 k k k k k k k k k k k k kk k kk s t u w v n nn f s t c u f s wu t vu k n fst + ⎧ ⎫ ⎪ ⎪ ⎡ ⎤⎡ ⎤ = ⎨ ⎬ ⎢ ⎥⎢ ⎥ ⎪ ⎪ ⎩ ⎭ ⎣ ⎦⎣ ⎦ + ++ ⎧ = +− − = ⎪ ⎨ ⎪ ⎩ = " " 最终求得 1f (,) a b 即为最大价值。 §5.3 生产与存储问题在生产与经营管理中，经常会遇到要合理安排生产与库存的问题，达到既满足社会需求，又尽量降低成本费用。因此，如何正确制定生产策略，确定不同阶段的生产量和库存量，使总的生产成本和库存费用最小，这就是生产与存储问题。某公司对某种产品要制定一个 n 阶段的生产计划。已知它的初始库存为零。在第 k 阶段末社会对该产品的需求为 dk，公司必须保证供应，并且生产数量为 xk的产品时的成本为 ck(xk)，并且产量上限为 m。若第 k 阶段末库存量为 vk，则存储费用为 hk(vk)。问该公司如何制定每个阶段的生产计划，使总费用最小？静态模型： 1 0 1 min ( ) ( ) . . 0, 0 ( ), 1, , 1 0 , 1, , 0, 1, , n kk kk k n k k jj j k k z cx hv st v v v x dk n x mk n vk n = = = + = = = −= − ≤≤ = ≥ = ∑ ∑ " " " 动态规划（顺序求解法）：设阶段：按月份划分，以上月多余产品入库后为阶段开始；状态变量 vk：第 k 阶段末的库存量(即第 k+1 阶段开始时的库存量)，允许状态集 0 1 0 min{ , } k n k j jk j jk v mk d d δ = =+ ≤≤ −∑ ∑ 决策变量 xk：第 k 阶段的生产量状态转移方程： kk kk 1 vv xd = +− − ，即 k k kk 1 v vdx − = + − 由 0 11 0,0 , 2, , k k v v kn δ =≤≤ = − − " ，得允许决策集： 111 x = + v d ， max{ ,0} min{ , }, 2, , kkk k kk 1 v d x v dmk n δ +− ≤≤ + = − " 阶段指标函数 () () kk kk cx hv + ，子过程指标函数具体加性；最优值函数 ( ) k k f v ：从第 1 阶段初始库存量为 0 到第 k 阶段末库存量为 vk时的最小总费用。得到基本方程： 1 11 1 1 min{ ,0} min{ , } 11 11 11 ( ) min { ( ) ( ) ( )}, 2, , ( ) min { ( ) ( )} kkk k kk kk k k k k kk kk v d x v dm xvd f v f v d x cx hv k n fv cx hv δ − − +− ≤≤ + = + ⎧ = +− + + = ⎪ ⎨ = + ⎪ ⎩ " 最终求得 (0) nf

10 33 3 33 3 33 3 3 3 33 4 3 3 3 max{5 ,0} 12 3 33 max{5 ,0} 12 3 4 max{5 ,0} 12 * 33 3 3 3 ( ) min { ( )} min {17 220 20( 3)} min { 3 20 280} 3(12 ) 20 280 244 17 12 su s su s su s f s au f s u d u su u s ss s u s − ≤≤− − ≤≤− − ≤≤− = + +− = + − +− = −− + =− − − + = − = − k=2： 2 5 9 ≤ ≤ s ， max{8 ,0} max{ ,0} 14 2 3 22 2 22 2 − s = + − ≤≤+ −=− d d s u Hd s s ， 22 2 22 2 22 2 2 2 22 3 2 2 2 max{8 ,0} 14 2 22 max{8 ,0} 14 2 2 max{8 ,0} 14 * 22 2 2 2 ( ) min { ( )} min {13 244 17( 5)} min { 4 17 329} 4(14 ) 17 329 273 13 14 su s su s su s f s au f s u d u su u s ss s u s − ≤≤− − ≤≤− − ≤≤− = + +− = + − +− = −− + =− − − + = − = − k=1： 1 8 9 ≤ ≤ s ， 1 1 2 11 1 11 1 13 max{13 ,0} max{ ,0} 17 −= − = + − ≤≤ + −= − s s d d s u Hd s s ， 11 1 11 1 11 1 1 1 11 2 1 1 1 13 17 1 11 13 17 1 1 13 17 * 11 1 1 1 ( ) min { ( )} min {18 273 13( 8)} min {5 13 377} 4(13 ) 13 377 442 18 13 su s su s su s f s au f s u d u su u s ss s u s −≤≤ − −≤≤ − −≤≤ − = + +− = + − +− = −+ = − − + = − =− k=0： 0 s = 2 ， 0 0 1 00 0 00 0 8 max{8 ,0} max{ ,0} 9 − = − = + − ≤ ≤ + − =− s s d d s u Hd s s ， 00 0 00 0 00 0 0 0 00 1 0 0 0 8 9 0 00 8 9 0 1 8 9 * 00 0 0 0 ( ) min { ( )} min {11 442 18( )} min { 7 18 442} 7(9 ) 18 442 379 11 9 su s su s su s f s au f s u d u su u s ss s u s − ≤ ≤− − ≤ ≤− − ≤ ≤− = + +− = +− + = −− + =− − − + = − = − 0 s = 2 * * 0 0 10 00 → =− =→ = − + = u s ssdu 97 9 * * 1 1 2111 → = − =→ = − + = u s s sdu 13 4 5 * * 2 2 32 22 → = − =→ = − + = u s ssdu 14 9 9 * * 3 3 4333 → = − =→ = − + = u s s sdu 12 3 9 * * 4 4 54 44 → =− =→ = − + = u s ssdu 90 7 * * 5 5 6555 → = − =→ = − + = u s ssdu 11 4 4 * 6 → = u 0 得最优策略： ******* 01 23456 uuuuuuu ======= 7, 4, 9, 3, 0, 4, 0 ，最优值 0f (2) 379 22 357 = −= 。 §5.4 复合系统工作可靠性问题若某种机器的工作系统由 n 个部件串联组成，只要有一个部件失灵，整个系统就不能工作。为提高系统工作的可靠性，在每各部件上均装有其备用部件，并且设计了备用部件自动投入装置。显然，备用部件个数越多，整个系统的可靠性越大，但系统的成本、重量、体积等增大。因此，需考虑在一定限制条件下，如何选择各部件的备用件个数，使整个系统的工作可靠性最大

上海交通大学：《运筹学》教学资源（课程讲义）第五章 动态规划应用举例

上海交通大学：《运筹学》教学资源（课程讲义）第五章动态规划应用举例