论文部分内容阅读
一般的资源分配问题中,分配的资源单位多为整数;对接受资源的“个体”接受时间上先后要求不严格,比如集团公司拟将5台设备分配给下属的甲、乙、丙三个工厂,各工厂得到设备后,为公司提供的盈利(单位:万元)如表1;如何分配使公司盈利最多?
具体的求解过程省略,而问题中分配资源时顺序可以是甲、乙、丙;丙、乙、甲;甲、丙、乙等等多种组合,时间上不分先后。
一、实际的考试问题
某学生的期末考试时间安排如下:共有4科考试,A在10日上午;B在12日上午;C在13日下午;D在15日上午。由于种种原因,该同学在7日才开始复习,由于时间有限(运筹学解决问题通常是针对“资源”紧缺问题,否则就不用分析了),不可能每门科目都达到最好成绩。通常来说上午考试后,下午还是可以复习的,为了研究方便我们认为一门考试只占去半天时间,而复习是紧迫的,所以我将时间以半天为单位,此处只为说明问题,实际可以将一天分成很多份,处理方法一样。分配不同时间量时获得的分数如表2(应试人自己对此有所估计10,100,150分满均可)所示,问如何安排各科的复习时间,达到总分数最高(即最满意)?
从实际情况我们知道,一般来说复习时间越长成绩越好,上表反映了这一情况。空白的表格是因为不会发生此种情况,故不用填写相应数据。
而该问题明显对4科的时间分配有先后顺序,即不是同时的,所以多阶段决策分配的顺序组合就不能任意排列。而D是最后一科,理论上将涉及资源时间最长的一个,其次为C、B、A。资源总数为13个半天,后面的科目可能占用前面的时间,而前面的科目不能占用后面的时间,故而我们先分配D,再将分配的天数从13中去除,剩下的时间才一定是包含C、B、A!依次类推下去,下一个分配的是C……。这么处理需要重要的前提:时间比较紧迫;每科都尽量靠近各科的考试时间,我们前面已经提到,符合实际情况。所以该问题的分配顺序一定是D、C、B、A!!!
二、问题求解
K=4A科 S4={0,1,2,3,4,5,6},s4≥x4
K=3B科 S3={0,1,2,3,4,5,6,7,8,9},0≤s3-x3≤6
K=2C科 S2={0,1,2,3,4,5,6,7,8,9,10},0≤s2-x2≤9
K=1D科 S1=13,0≤s1-x1≤11
该学生最后的时间安排应为:A——1.5天,B——1.5天,C——2天,D——1.5天。考虑实际情况时,具体的安排不惟一,可以根据该学生的喜好在每科考试前安排相应的天数,这里列举一种方案7日、9日下午复习A;8日、11日下午复习B;9日上午、10下午、11上午、13日上午复习C;12日下午、14日复习D。该例与一般的资源分配问题不同之处有:资源不是整数。资源分配时有先后顺序。因为时间上有先后顺序,问题的结论可能惟一,但是安排顺序上会有很多中可能,如本例;但是动态规划的变化是无穷的,有关方面的讨论也是无穷尽的,本文只对某一方面问题提出自己的想法,期望能解决生活中类似的问题。
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
具体的求解过程省略,而问题中分配资源时顺序可以是甲、乙、丙;丙、乙、甲;甲、丙、乙等等多种组合,时间上不分先后。
一、实际的考试问题
某学生的期末考试时间安排如下:共有4科考试,A在10日上午;B在12日上午;C在13日下午;D在15日上午。由于种种原因,该同学在7日才开始复习,由于时间有限(运筹学解决问题通常是针对“资源”紧缺问题,否则就不用分析了),不可能每门科目都达到最好成绩。通常来说上午考试后,下午还是可以复习的,为了研究方便我们认为一门考试只占去半天时间,而复习是紧迫的,所以我将时间以半天为单位,此处只为说明问题,实际可以将一天分成很多份,处理方法一样。分配不同时间量时获得的分数如表2(应试人自己对此有所估计10,100,150分满均可)所示,问如何安排各科的复习时间,达到总分数最高(即最满意)?
从实际情况我们知道,一般来说复习时间越长成绩越好,上表反映了这一情况。空白的表格是因为不会发生此种情况,故不用填写相应数据。
而该问题明显对4科的时间分配有先后顺序,即不是同时的,所以多阶段决策分配的顺序组合就不能任意排列。而D是最后一科,理论上将涉及资源时间最长的一个,其次为C、B、A。资源总数为13个半天,后面的科目可能占用前面的时间,而前面的科目不能占用后面的时间,故而我们先分配D,再将分配的天数从13中去除,剩下的时间才一定是包含C、B、A!依次类推下去,下一个分配的是C……。这么处理需要重要的前提:时间比较紧迫;每科都尽量靠近各科的考试时间,我们前面已经提到,符合实际情况。所以该问题的分配顺序一定是D、C、B、A!!!
二、问题求解
K=4A科 S4={0,1,2,3,4,5,6},s4≥x4
K=3B科 S3={0,1,2,3,4,5,6,7,8,9},0≤s3-x3≤6
K=2C科 S2={0,1,2,3,4,5,6,7,8,9,10},0≤s2-x2≤9
K=1D科 S1=13,0≤s1-x1≤11
该学生最后的时间安排应为:A——1.5天,B——1.5天,C——2天,D——1.5天。考虑实际情况时,具体的安排不惟一,可以根据该学生的喜好在每科考试前安排相应的天数,这里列举一种方案7日、9日下午复习A;8日、11日下午复习B;9日上午、10下午、11上午、13日上午复习C;12日下午、14日复习D。该例与一般的资源分配问题不同之处有:资源不是整数。资源分配时有先后顺序。因为时间上有先后顺序,问题的结论可能惟一,但是安排顺序上会有很多中可能,如本例;但是动态规划的变化是无穷的,有关方面的讨论也是无穷尽的,本文只对某一方面问题提出自己的想法,期望能解决生活中类似的问题。
注:本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。