第五章 动态规划应用举例（书第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 + − ，得模型：