动态规划资源分配问题-ppt课件

1、动态规划资源分配问题 小组成员：黄秀梅 罗燕雯 杨俊 李彩霞 林琳 女 吴晶莹 邓桂兰 罗碧辉资源分配问题：只需一种资源有待于分配到假设干个活动，其目的是如何最有效地在各个活动中分配这种资源。在建立任何效益分配问题的DP(Dynamic Programming )模型时，阶段对应于活动，每个阶段的决策对应于分配到该活动的资源数量；任何形状的当前形状总是等于留待当前阶段和以后阶段分配的资源数量，即总资源量减去前面各阶段已分配的资源量。 标题：一名大学生还有7天就要进入有四门考试科目的期末考试。他想尽能够有效地分配这7天复习时间，每门学科至少需求1天复习时间。他喜欢每天只复习一门课，所以他能够分配

2、给每门功课的时间是1，2，3或4天，由于最近学习了运筹学他希望用DP方法安排时间以使能从这四门课中得到最高的总学分，他估计每门课的时间分配能够产生的学分如下表。用DP方法求解这个问题。 课程 学分复习天数1 2 3 4 1 2 3 4 3 5 24 5 6 45 6 8 78 7 8 8数）前面阶段未分配完的天是仍待分配的天数（即状态变量：sk的天数；科目）是分配到阶段（考试（k1，2，3，4决策变量：x，4。考试科目阶段：k1，2，3个阶段。成动态规划模型中的四这四门考试科目可以看定的次序，因此，即使这里没有固少天给每门考试科目。即应分配多4个相应关联的决策，解：这个问题要求作出kk0sf1

3、,2,3k )()(max)(1 .,3 , 2 , 1 ),(max)(maxxPxsf1xxx x 7xxx x.)()()()(maxxxxxixx5*5*1,.,2, 1*i4*41kkkkk43214321443322114321i）（将递推关系写出即是且为整数大于等于（）（），（目标可改写成且为整数，使，是挑选的效果量，我们的目标天给考试科目）表示分配（令kkkkksxkkkikikkkkkkkkiiiixsfxPsfxsxsxxsfsfxPtsxPxPxPxPPkk当k=4时;f4(s4) = max p4(x4) 1 xk sk 1 sk 4s41 2 3 4x411 21 2

4、 31 2 3 4p4(x4)22 42 4 72 4 7 8f4(s4)2 4 7 8X4*1 2 3 4 当k=3时; f3(s3) = max p3(x3)+ f4(s4) 1 x3 s3 2 sk 5 计算结果:S32 3 4 5X311 21 2 31 2 3 4p3(x3)55 65 6 85 6 8 8F3+ p379 812 10 1013 13 12 10f3(s3)791213X3*1111或2 当k=1时; f1(s1) = max p1(x1)+ f2(s2) 1 x1 s1 s1=7 计算结果:S1 7X1 1 2 3 4P1(x1) 4 4 5 8F2+ p121 19 17 18f1(s1)21X1*1 当k=2时; f2(s2) = max p2(x2)+ f3(s3) 1 x2 s2 3 s2 6 计算结果:S23456X211 21 2 31 2 3 4p2(x2)33 53 5 6 3 5 6 7F3+ p21012 1215 14 1316 17 15 14f2(s2)10121517X2*11或211天。科目复习天；第四天；第三科目复习天；第二