§3动≈规划的应用(1) 资源分配问题 例2.某公司拟将某种设备5台,分配给所属的甲、乙、丙三个 工厂。各工厂获得此设备后,预测可创造的利润如表10-5所示, 问这5台设备应如何分配给这3个工厂,使得所创造的总利润为 最大? 利 工厂 甲厂 乙厂 丙厂 设备台数 0 0 2345 0379 046 10 11 12 13 11 12 12 表105 管理蓦
管 理 运 筹 学 16 一、资源分配问题 例2. 某公司拟将某种设备5台，分配给所属的甲、乙、丙三个 工厂。各工厂获得此设备后，预测可创造的利润如表10-5所示， 问这5台设备应如何分配给这3个工厂，使得所创造的总利润为 最大？ 表10-5 盈利 工厂 设备台数 甲 厂 乙 厂 丙 厂 0 0 0 0 1 3 5 4 2 7 10 6 3 9 11 11 4 12 11 12 5 13 11 12 §3 动态规划的应用(1)
§3动恋规划的应用(1 解:将问题按工厂分为三个阶段,甲、乙、丙三个厂分 别编号为1、2、3厂。设 s1=分配给第k个厂至第3个厂的设备台数(k=1、2 3) x1=分配给第k个设备台数。 已知s1=5, 并有 2=71(S2x1) M1 从S与x,的定义,可知 以下我们从第三阶段开始计算 管理蓦
管 理 运 筹 学 17 解：将问题按工厂分为三个阶段，甲、乙、丙三个厂分 别编号为1、2、3厂。设 sk = 分配给第k个厂至第3个厂的设备台数（k=1、2、 3）。 xk =分配给第k个设备台数。 已知s1 =5, 并有 从 与 的定义，可知 以下我们从第三阶段开始计算。 3 2 2 2 2 2 s = T (s , x ) = s − x k s k x 3 3 s = x §3 动态规划的应用(1) 2 1 1 1 1 1 s =T (s , x ) = s − x
§3动恋规划的应用(1 第三阶段 显然将S3(S3=0,2,3,4,5)台设备都分配给第3工厂时, 也就是3=x3时,第3阶段的指标值(即第3厂的盈利) 为最大,即 maxr(S3,x3=r(S3,S3) 由于第3阶段是最后的阶段,故有 f3(s3)=maxr(S3,x3)=r(S3,S3) 其中x3可取值为0,1,2,3,4,5。其数值计算见表10-6。 管理蓦
管 理 运 筹 学 18 第三阶段: 显然将 台设备都分配给第3工厂时， 也就是 时，第3阶段的指标值（即第3厂的盈利） 为最大，即 由于第3阶段是最后的阶段，故有 其中 可取值为0,1,2,3,4,5。其数值计算见表10－6。 ( 0,1,2,3,4,5) s3 s3 = ( ) max ( , ) ( , ). 3 3 3 3 3 3 3 3 3 f s r s x r s s x = = 3 x max ( , ) ( , ) 3 3 3 3 3 3 3 r s x r s s x = §3 动态规划的应用(1) 3 3 s = x
§3动恋规划的应用(1 表10-6 rS,X 0 4 f(5)x 0 0 4 046 2345 113 12 124 12125
管 理 运 筹 学 19 表10－6 0 1 2 3 4 5 0 0 － － － － － 0 0 1 － 4 － － － － 4 1 2 － － 6 － － － 6 2 3 － － － 11 － － 11 3 4 － － － － 12 － 12 4 5 － － － － － 12 12 5 3 x 3 s ( , ) 3 3 3 r s x ( ) 3 3 f s 3 * x §3 动态规划的应用(1)
§3动恋规划的应用(1 其中x3表示取3子过程上最优指标值/(3)时的x3 决策,例如在表10-6中可知当3=4时,有(44)=12,有 f3(4)=12,此时x3=4,即当s3=4时,此时取x3=4 (把4台设备分配给第3厂)是最优决策,此时阶段指标值 (盈利)为12,最优3子过程最优指标值也为12 第二阶段: 当把S2(S2=0,1,2,345)台设备分配给第2工厂和第3工 厂时,则对每个2值,有一种最优分配方案,使最大盈利 即最优2子过程最优指标函数值为 f/2(S2)=max[z2(S2x2)+f3(S3) 运筹
管 理 运 筹 学 20 其中 表示取3子过程上最优指标值 时的 决策，例如在表10-6中可知当 =4时，有 有 此时 ，即当 时，此时取 （把4台设备分配给第3厂）是最优决策，此时阶段指标值 （盈利）为12，最优3子过程最优指标值也为12。 第二阶段： 当把 台设备分配给第2工厂和第3工 厂时，则对每个 值，有一种最优分配方案，使最大盈利 即最优2子过程最优指标函数值为 3 * x ( ) 3 3 f s 3 x 3 s (4,4) 12; r3 = (4) 12, f 3 = 3 4 * x = s3 = 4 x3 = 4 ( 0,1,2,3,4,5) s2 s2 = 2 s ( ) max[ ( , ) ( )] 2 2 2 2 2 3 3 2 f s r s x f s x = + §3 动态规划的应用(1)