动态规划资源分配问题

动态规划 资源分配问题 小组成员：黄秀梅 罗燕雯 杨俊 李彩霞 林琳 （女） 吴晶莹 邓桂兰 罗碧辉 资源分配问题 ：只有一种资源有待于分配到 若干个活动，其目标是如何最有效地在各 个活动中分配这种资源。在建立任何效益 分配问题的 DP(Dynamic Programming )模型 时，阶段对应于活动，每个阶段的决策对 应于分配到该活动的资源数量；任何状态 的当前状态总是等于留待当前阶段和以后 阶段分配的资源数量，即总资源量减去前 面各阶段已分配的资源量。 题目：一名大学生还有 7天就要进入有四门考试科目的期末考试。 他想尽可能有效地分配这 7天复习时间，每门学科至少需要 1天复习时间。他喜欢每天只复习一门课，所以他可能分配 给每门功课的时间是 1， 2， 3或 4天，由于最近学习了运筹学 他希望用 DP方法安排时间以使能从这四门课中得到最高的总学 分，他估计每门课的时间分配可能产生的学分如下表。用 DP 方法求解这个问题。 课程 学分 复习天数 1 2 3 4 1 2 3 4 4 3 5 2 4 5 6 4 5 6 8 7 8 7 8 8 数）前面阶段未分配完的天是仍待分配的天数（即状态变量：s k的 天数； 科目）是分配到阶段（考试（k 1， 2 ，3 ，4决策变量：x ，4。 考试科目阶段：k 1， 2 ，3 个阶段。成动态规划模型中的四这四门考试科目可以看 定的次序，因此，即使这里没有固少天给每门考试科目。 即应分配多4个 相应关联的决策，解：这个问题要求作出 k k 0sf 1,2, 3k )()(m a x)( 1 .,3,2,1 ),(m a x ) )(m a xxPxsf 1xxx x 7xxx x. )()()()(m a x xxxx ixx 5 * 5 * 1 ,.,2,1 * i 4 * 4 1 kkkkk 4321 4321 44332211 4321 i ）（ 将递推关系写出即是 且为整数大于等于 （ ）（），（ 目标可改写成 且为整数， ，使，是挑选 的效果量，我们的目标天给考试科目）表示分配（令 kkkkk sx kk ki ki kkkkkkk ki ii i xsfxPsf xsx sxxsfsf xP ts xPxPxPxP P kk 当 k=4时 ; f4(s4) = max p4(x4) 1 xk sk 1 sk 4 s4 1 2 3 4 x4 1 1 2 1 2 3 1 2 3 4 p4(x4) 2 2 4 2 4 7 2 4 7 8 f4(s4) 2 4 7 8 X4* 1 2 3 4 当 k=3时 ; f3(s3) = max p3(x3)+ f4(s4) 1 x3 s3 2 sk 5 计算结果 : S3 2 3 4 5 X3 1 1 2 1 2 3 1 2 3 4 p3(x3) 5 5 6 5 6 8 5 6 8 8 F3+ p3 7 9 8 12 10 10 13 13 12 10 f3(s3) 7 9 12 13 X3* 1 1 1 1或 2 当 k=1时 ; f1(s1) = max p1(x1)+ f2(s2) 1 x1 s1 s1=7 计算结果 : S 1 7 X1 1 2 3 4 P1(x1) 4 4 5 8 F2+ p1 21 19 17 18 f1(s1) 21 X1* 1 当 k=2时 ; f2(s2) = max p2(x2)+ f3(s3) 1 x2 s2 3 s2 6 计算结果 : S2 3 4 5 6 X2 1 1 2 1 2 3 1 2 3 4 p2(x2) 3 3 5 3 5 6 3 5 6 7 F3+ p2 10 12 12 15 14 13 16 17 15 14 f2(s2) 10 12 15 17 X2* 1 1或 2 1 1 天。科目复习 天；第四天；第三科目复习天；第二科目复习第一科目复习 为：，故最合理得时间安排， 回去得： ，再逆推）（得到的最高学分为综上计算，可知此人可 3 121 3u1u2u 21sf * 4 * 3 * 2 11