关于补考问题的数学模型.doc

小组成员： 梁丽雅、陈秀琴、单正瑞、程彪彪 （补考日程安排模型）摘要本文通过对某大学开学前的补考日程安排表进行分析规划，并针对11门考试科目在规定的两天共8个时间段内，每名补考学生都可以参加所需补考的科目补考，且不同科目可以在同一时间段内完成。首先考虑到在同一时段的课程补考不能冲突的限制条件，采用了0-1规划，找出最小目标函数和各项约束条件的数学表达式，建立数学规划模型。我们依据问题的限制条件，即同一时段课程安排补考的数量尽量多，建立一个求解目标函数值最大化的数学模型。模型的求解过程中，采用数学软件LINGO等编写相应的程序，对建立的模型进行求解，得出最优结果。表1 补考安排日程表时段一二三四五六七课程k1k4k8k9k2k3k5k6k7k10k11其次我们使用了图论法对问题进行了分层分析。得出和所建立的数学规划模型相同的解，至此验证了我们的模型的正确性。关键词：LINGO数学软件 0-1变量 线性规划 运筹学 图论正文：一、问题重述某大学开学前补考通常是在开学前的周六、周日完成（例如，2013年春季开学前补考时间就订在2月16日和17日两天），每天的考试时间分为4个时段，分别为：8:009:35，9:5511:30，13:3015:05，15:2517:00。由于有的学生有多门补考，因此，有些课程安排在一个时段补考会产生冲突（例如，学生张三要补考高等数学和普通物理，如果将这两门课安排在一个时段补考就产生冲突）。现有11门课程（K1，K2，K11）需要安排补考，表A给出11门课程的补考是否有冲突的情况。表A：11门课程补考有冲突的情况（为有冲突，为无冲突）课程K1K2K3K4K5K6K7K8K9K10K11K1K2K3K4K5K6K7K8K9K10K11请你完成以下工作：(1) 就该问题建立相应的数学模型、求解，帮助教务处制定一份详细的补考时间表，使得每位学生在每个时段都只需参加一门考试；(2) 如果有可能，补考时间尽量安排在上午；(3) 如果无法解决冲突问题，尽量使重要的课程不冲突（课程编号越小越重要，例如，K1比K2重要）。二、问题分析且由表A可知，K5、K7、K10、K11与其余科目都有冲突。故安排其在四个不同的时间段，且每个时间段仅可以有一门课程考试。现在表A中删除K5、K7、K10、K11，得到表B。表B：7门课程补考有冲突的情况（为有冲突，为无冲突）课程K1K2K3K4K6K8K9K1K2K3K4K6K8K9由表B可知，K8与剩下的6门课程无冲突。故K8不在接下来的讨论中。现在表B中删除K8，得到表C。表C：6门课程补考有冲突的情况（1为有冲突，0为无冲突）课程K1K2K3K4K6K9K1010000K2100000K3000111K4001010K6001101K9001010三、模型假设1.假设每个同学都会按时参加补考，并且保证同一时间段可以同时进行几门课程补考。2.假设每个同学在同一时间段只能参加一门补考。四、符号说明符号意义01规划中的变量，第门补考课程，取1（考试）或0（不考试）Z为在某一时段举行的科目数变量五、模型建立及求解1、建立如下图1模型。（依照安排时段尽量少，每个时段的课程尽量多的要求安排。）K1K2K3K4K6K9图1（将不冲突的两门课程相连）2、根据补考学生在同一时间段只能参加一门课程考试条件限制，且同一时段可以安排多门课程考试，Z为在某一时段举行的科目数。引入变量（i=1,2,3,4,6,9）表示补考课程。若（课程）在同一时段内安排补考，记，否则记。根据图2K1K2K3K4K6K9图2（相冲突的两门课程相连）则应该满足以下约束条件：（依照安排时段尽量少，每个时段的课程尽量多的要求安排。）下面介绍两种解法第一种解法（图表法）：为了能较直观地解决这个模型，可以根据该问题的模型图如下图：能同时进行补考的课程之间连上一条边，表示出同一名考生所需的补考科目是能在同一时间内补考的。因此确定哪些科目在要求内可以同时进行。K1K2K3K4K6K9图3（将不冲突的两门课程相连）（依照安排时段尽量少，每个时段的课程尽量多，序号小的尽量排在前面的要求安排。）以K1为起点做一个闭合回路，且不经过K2点有且仅有一个回路，K1、K4、K9，所以K1，K4，K9三门课程可以同时考试。将上图去掉K1、K4、K9得出图4 K2K6K3图4（将不冲突的两门课程相连）由于我们首先考虑课程编号小的课程，所以K2、K3两门课程可以同时考试，K6课程单独考试。由此可得：只要安排3个不同的时段即可。时段1内可以安排（k1）和（k4）和（k9），时段2内可以安排（k2）和（k3），时段3可以安排（k6）。第二种解法：用LINGO直接求解输入文件：（依照安排时段尽量少，每个时段的课程尽量多的要求安排。）model:max=k1+k2+k3+k4+k6+k9;k1+k2=1;k3+k4+k6=1;k3+k6+k9=1;GIN(k1);GIN(k2);GIN(k3);GIN(k4);GIN(k6);GIN(k9);end求解可以得到最优解如下： Global optimal solution found. Objective value: 3.000000 Objective bound: 3.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost K1 0.000000 -1.000000 K2 1.000000 -1.000000 K3 0.000000 -1.000000 K4 1.000000 -1.000000 K6 0.000000 -1.000000 K9 1.000000 -1.000000 Row Slack or Surplus Dual Price 1 3.000000 1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000根据LINGO所求得的解可以知道：k1=k4=k9=1或k2=k4=k9=1，且根据要求，可知：（k1）和（k4）、（k9）可以同时进行考试。接下来输入：model:max=k2+k3+k6;k2=1;k3+k6=1;GIN(k2);GIN(k3);GIN(k6);end求解可以得到最优解如下： Global optimal solution found. Objective value: 2.000000 Objective bound: 2.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost K2 1.000000 0.000000 K3 1.000000 -1.000000 K6 0.000000 -1.000000 Row Slack or Surplus Dual Price 1 2.000000 1.000000 2 0.000000 1.000000 3 0.000000 0.000000根据LINGO所求得的解可以知道：k2=k3=1或k2=k6=1，但我们附加条件，以序号小的优先，可知：（k2）和（k3）可以同时进行考试。综上所述：有（k1）、（k4）和（k9）可以同时进行考试，（k2）和（k3）也可同时进行考试。则有如下安排：第一时段，k1，k4，k8，k9。第二时段，k2，k3。第三时段，k5。第四时段，k6。第五时段，k7。第六时段，k10。第七时段，k11。六、模型的结果分析及检验 根据上面解，我们把能同时进行的比赛项目排在同一时间进行比赛排表，由此可以简单的排出如下补考日程安排表：表1 补考安排日程表时段一二三四五六七课程k1k4k8k9k2k3k5k6k7k10k11由表可以看出：每个时间段安排的补考安排都是不冲突的，从而说明这个线性规划模型是正确的，确立这个模型也是一种解决该类问题的方法。具体时间安排表如下：日期时间段补考课程2月16日周六8:009:35k1、k4、k8、k99:5511:30k2、k313:3015:05k515:2517:00 k62月17日周日8:009:35k79:5511:30k1013:3015:05k11七、模型讨论 1.模型优点： （1）该模型引用0-1变量是根据现有的数据资料假条件和假设建立数学规划模型，该模型都简单明确，容易接受。 （2）模型由于简单，容易接受，很多人在学这种方法可以掌握、推广解决到生活中去 。（3）模型体现了应用数学软件的优异性。 （4）图论法也是解决这类问题的较好的方法，对数学软件不熟悉的人可以是一种首选方法。2.模型不足：（1）这种方法主观性太强，依据不强。（2）本模型有较多的优点，但仍存在着一些缺陷，要求对对数学软件有一定的分析能力。比如：运用LINGO的数学软件不能得出一个该日程安排的完整的方案，只能得出：可以同时进行的课程如（k1=k4=k9=1），其余的还需根据条件分析得出。八、模型改进若具有很好的数学软件分析问题的能力，用影子条件来分析问题，可以更为简单方便。在进行模型求解的同时，对模型进行改写，如下：model:min=k1+k2+k3+k4+k6+k9;k1+k2=1;k3+k4+k6=1;k3+k6+k9=1;GIN(k1);GIN(k2);GIN(k3);GIN(k4);GIN(k6);GIN(k9);End Global optimal solution found. Objective value: 2.000000 Objective bound: 2.000000 Infeasibilities: 0.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost K1 0.000000 1.000000 K2 1.000000 1.000000 K3 1.000000 1.000000 K4 0.000000 1.000000 K6 0.000000 1.000000 K9 0.000000 1.000000 Row Slack or Surplus Dual Price 1 2.000000 -1.000000 2 0.000000 0.000000 3 0.000000 0.000000 4 0.000000 0.000000从这个模型我们可以得出：k2=k3=1或k2=k6=1，则有：（k2）和（k3）在这一时间段可以同时进行，且有（k2）和（k6）在这一时间段也可以同时进行。由条件有（k2）和（k3）同时进行。最后一门课程（k6）单独进行考试。九、模型推广在日常生活中，我们经常碰到工作日