资源描述
动态规划 资源分配问题 小组成员:黄秀梅 罗燕雯 杨俊 李彩霞 林琳 (女) 吴晶莹 邓桂兰 罗碧辉 资源分配问题 :只有一种资源有待于分配到 若干个活动,其目标是如何最有效地在各 个活动中分配这种资源。在建立任何效益 分配问题的 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
展开阅读全文