《基数学建模论文于整数规划的实验安排问题研究.doc》由会员分享，可在线阅读，更多相关《基数学建模论文于整数规划的实验安排问题研究.doc（21页珍藏版）》请在三一文库上搜索。
1、基于整数规划的实验安排问题研究摘要现实生活中，学校学生人数众多，教授课程种类繁多，到了学期末则面临考试安排的问题。合理有序的考试安排不仅可以节省考生，老师等多方的时间，更可以令学生科学高效的复习与备考，因此正确、合理、高效地安排考试是学校考务管理人员最重视的事情之一。本文运用了整数规划的方法来尝试解决实验考试的安排问题。在安排过程中，要综合考虑人员冲突，时间最优等多方因素，为使模型的建立更加简洁明了，我们在模型的建立过程中引入矩阵和正态分布模型，并通过约束进行规划，最后求得在不同的条件下的最优考试安排。 在问题一中，本文首先对附件一中的数据进行整理归纳，结合实际情况，尝试建立整数规划模型来求得
2、实验考试所需要的最短时间。在考场位置和顺序的安排过程中我们发现需要考虑的条件有多重，所以采用矩阵法来表示考场中的座位情况以及考场安排情况等，并通过约束利用Lingo和Matlab软件求解，得到表五所示的实验考试安排。 在问题二中，本文首先忽略考场间移动所需时间对于目标函数的影响，在三个考场同时考试的情况下进行整数规划，再利用枚举法对所得结果进行处理，在数个忽略路程因素影响的结果中找出考场间移动所需要的最短时间，并给出如表八所示的实验考试安排。 在问题三中，本文对于可以提前交卷的前提条件进行模型估计，假设考生交卷时间满足正态分布的某一段图像，即集中在考试前某段时间有大批考生完成试验，而在此之前完
3、成试验的考生人数以小比率增加。然后以正态分布的期望代替不同题目所规定的考试时间，在问题一的整数模型中进行求解，对结果进行分析，进而给出实验考试安排。 最后，本文对文中模型的优缺点进行了评价和推广。关键词：整数规划 矩阵法 正态分布 实验安排一、问题重述1.1研究背景 随着我国教育体制改革的深入，学生人数的不断上升，课程设置不断向深度和广度发展，人工考试安排的易错难改、效率低的缺点就越来越突出。合理有序的考试安排不仅可以节省考生，老师等多方的时间，更可以令学生科学高效的复习与备考，因此正确、合理、高效地安排考试是学校考务管理人员最重视的事情之一。1.2待解决问题 2015年某校某专业进行职业技能
4、考试，包含有技能考题5道，要求每位考生必须完成其中三道：第一题为必考项目，余下的考题四选二。考生总人数79人，每位考生所选选项均已知，在只能提供A、B两个技能考场的情况下，结合以下三种情形，建立数学模型，合理设计考场分布和考试顺序，使得本次考试所用时间最短。 三种情形如下： （1）假定技能考题1考试时间为45分钟，而其他4个技能考题考试时间为30分钟，考生不能提前离开考场，即在固定的考试时间下，运用整数规划的方法建立模型，使得在最短的时间内完成考试。 （2）假定增加C考场能容纳20人，而3个考场不在同一个地方，3个考场之间往返的时间已知，结合（1）的条件建立优化模型，合理安排考试顺序。 （3）
5、假定（1）的考试时间均为最长考试时间，考生做完实验可以提前离开考场，与此同时下一位考生进场，在这种情况下建立相关模型，并给出考试安排。 要求： （1）A考场能容纳24个人同时开考，B考场能容纳32人同时开考。 （2）每个技能考题只能安排在同一个考场，每个技能考题同时开考的最大数量没有限制，但是一旦确定中途就不能更改。二、问题分析该问题属于考试安排，是一个涉及多种因素的组合规划问题。它首先要避免在课程安排中学生、教室产生冲突(所谓冲突，就是同一考场在同一时间段安排一场以上的考试，或者考生在同一时间段要进行两场不同科目的考试等情况)，并且要满足教室资源等约束条件。问题的特点在于考生考试课程不统一、
6、考试时间不一致、教室资源相当有限。解决问题的关键在于掌握各个考场占用次数，寻求教室、时间、考生之间的约束条件，进行合理建模并求解。 根据已知条件，利用excel统计出参加每个技能考题的考生人数（见图一）和自选两个技能考题相同的人数分布情况（见图二）。图一 各个考题的考生分布情况 由图一得知如下数据：考生参加技能考题1的人数为79人，参加技能考题2的人数是49人，参加技能考题3的人数是14人，参加技能考题4的人数为58人，参加技能考题5的人数为37人（由题干可知，技能考题1是考生必考题目，其余为选考题目）。图二 自选考题相同的人数分布情况由图二得知如下数据：选考技能考题2和技能考题3 的人数为1
7、1人，选考技能考题2和技能考题4 的人数为31人，选考技能考题2和技能考题5的人数为7人，选考技能考题3和技能考题5 的人数为3人，选考技能考题4和技能考题5 的人数为27人，不存在同时选择技能考题3和4的人（说明技能考题3和技能考题4可在同一时间段内考试）。2.1问题1的分析 因只存在两个考场、考试人数和考场人数的限制，要寻求最短考试时间的安排，需要先利用相关约束条件确定各个技能考题所需要的各个考场的次数，再结合每个考题考试时间的不一致，考生选题的多样化，在避免冲突的情况下得出考题、考场、时间的合理组合。2.2问题2的分析 该问题在问题一的基础上增设C考场，同时为了使模型更为合理，考虑考生在
8、不同考场间移动所需的时间情况。采用和问题一相同的模型，增加C考场增设后的约束情况，利用目标函数，借助矩阵进行最优化分析，得出合理的考试安排。2.3问题3的分析 该问题中允许考生提前离开考场，从而提前安排下一位考生考试，类比于泊松分布，利用排队论相关模型及结论，结合本次模型，进行规划求解，达到节省时间的目的。三、模型假设1问题一中，假设考生在结束一门考试后，可立即到达下个考试地点，即往返时间为0，同时忽略分发和回收考卷的时间。2假设考生可以连续进行不同考题的考试。3. 假设考生完成考试时间服从正态分布。4. 假设不存在考生缺考等特殊情况。四、定义与符号说明符号意义Xi各个考题所占用考场的次数Y每
9、个考题的考生人数Z每个考场的限制人数Cij第i个考生选第j个考题Ei考题在考场中的安排A考场往返时间Bij第i个考生在该场考试中出现与否考题占用分钟数Fij按考场次序，考题所花费时间Xij第i个考生在做考题时在第j个座位Dii=1，2，3，4，5分别代表选择123，124，125，135，145题的人数Di(n)在Di中选择与Di（m）相独立的n人五、问题一的解答 对于该考试安排，存在一些硬性约束，如一个考场在同一时间内只能进行一场考试，同一考生在同一时间段内不能出现在两个考场中，每位考生均进行三门考试；存在一些软约束，如每个考题在考场中出现的次数要尽可能的少，教室座位要尽可能占满即教室利用率
10、高，考试时间，5门考试时间要尽可能短等。通过分析题目要求，得出解决思路的流程图（见图三）：图三 解法流程图5.1问题一的非线性规划模型5.1.1求所需考场次数 5.1.1.1模型的建立 首先根据题目已知条件及问题的假设1，列出表一，利用相关约束，将多目标函数利用分层序列法转化为单目标规划问题（存在考试时间最短和座位空余数最少两个目标函数，以考试时间最短为第一重视程度，求出此目标的最优解，然后再以座位空余数最少为目标函数，保证前一个目标最优解的前提条件下求该目标的最优解），用lingo软件编程，求解各个考题所占用的A、B考场的次数（如：技能考题1占用A考场1次，占用B考场两次）。表一 考场 考题
11、12345限制人数AX11X12X13X14X15BX21X22X23X24X25总人数Y1Y2Y3Y4Y5 （1）定义如下矩阵：考题占用考场矩阵 ；考场限制人数矩阵；考题的考生人数矩阵；（2）典型字母的含义：表示技能考题1占用A考场的次数；表示参加技能考题1的考生人数；表示A考场的限制人数。（3）约束条件：（4）目标函数：A、B考场时间相差最短 空余座位数最少5.1.1.2模型的求解根据上述目标函数及约束条件，编程利用Lingo软件求解，运行结果如下图四所示：表二 两个考场占用分布表112345限制人数A1110224B2102032总人数79491458375.1.2人员在考场中安排结合上
12、述最优解，利用MATLAB软件编程，对矩阵的行和列分别进行以下约束：在约束前首先对所有同学考场安排进行初步划分：（1)同一位同学在考场的安排中，同一道考题只能选择一个座位； 同理对于每一行的相应分块进行划分 （2)考场的一个座位同时只能有一个同学进行试验 在各个约束条件确定之后，利用Matlab软件进行考试前后次序的排序问题，软件运行结果如下图五：结合假设2，得到如下结果（见图六）： A考场 B考场图四 考场考题考生分布图 所以考生安排如表三：D1+D3(7)D5D3+D4+D5(7)D2D5(24)D2D1+D3D5D1+D4D2此时最短考试时间为180min,教室利用率为84.64%（23
13、7/280）六、问题二的解答 6.1求所需考场次数6.1.1模型的建立 对于问题二而言，增加C考场，我们将采用与问题一相同的模型，进行相关参数的增加、修改，列出表五如下：表四考场考题12345限制人数AX11X12X13X14X15BX21X22X23X24X25CX31X32X33X34X353总人数Y1Y2Y3Y4Y5（1）约束条件如下：（2）目标函数：A、B、C考场时间相差最短： ；空余座位数最少：。6.1.2模型的求解利用lingo软件编程得到如下结果，用Excel体现出来（见表五）：表六 三个考场占用次数分布表12345限制人数A1110124B2100032C0003120总人数7
14、9491458376.2.考虑考场间往返时间的优化方案6.2.1模型的建立 在问题一模型的建立时，假设两场考试之间的时间间隔为零，而实际上这种情况是不可能发生的，考生在不同场次的考试之间一定会存在时间间隔，从而完成考场的转换，试卷的分发与回收等工作，所以问题二正是基于此实际情况，增加了间隔时间的设置，目标函数同样为求得在此条件下考试所需要的最短时间。根据附件2，A,B,C各个考场之间的往返时间分布情况如下图七: 根据题意，列出关于考题、时间、考生、考场的矩阵，利用其之间的关系，形成约束条件，以所有考生的往返时间最少为目标函数，利用lingo软件进行编程，求解最优解。（1）定义如下矩阵:考题按照
15、考场次序分布矩阵其中； 考题占用时间矩阵；考生选题分布矩阵其中；考生在考场出现情况矩阵其中出现 ；按考试次序，考题占用时间矩阵。（2）典型字母的含义： 表示技能考题1在A考场第一场考试中的考试与否，其中，A考场的 个数为，B考场的个数为， C考场的个数为，按照ABC考场的次序及q、w、v依次排列；表示技能考题1所花费的时间；表示第一个考生参加技能考题1考试的情况；表示第一位考生在该考试时间段内出现在该考场的情况；表示按照考场次序，A考场进行第一门考试所需的时间。（3）约束条件：，（其余的不再列出）（4）目标函数：min=min(考试时间)+min（路程时间）6.2.2优化模型的求解在各个约束条
16、件确定之后，利用Matlab软件进行考试前后次序的排序问题，软件运行结果如下图：此时利用枚举法可以求的在不同的考场分布及不同的人员分布等不同的情况下所需要花费的时间。而对结果进行对比则可在最有考场排布的前提下求得考虑考场间路程时间时所需要的最短时间。结合假设2，得到如下结果（见图五）： A考场 B考场 C考场图八 考场考题考生分布图 所以考生安排如表六：D1+D3+D5(6)D2+D5(1)D5(20)D1+D2(11)D4+D5(20)D2(20)D1+D4D2(20)+D3(7)D2(11)+D5(7)D3+D4+D5(7)D5(20)最短考试时间为141min,此时教室利用率为87.5%
17、（278/272）六、问题三的解答6.1模型的建立问题三和问题一的不同在于此时额外增加了一个条件：为了节省考试时间，允许做完实验的考生提前交卷，同时让下一个待考的同学进来做实验。此时可讲考生完成实验的时间看作随机分布。在现实生活中，通常考生都能在考试规定的时间内完成考题的解答，大部分考生会提前一部分时间完成，其中大部分在规定时间的90可以完成，小部分甚至会在距离收卷时间还有很多的时候便已经完成，所以可以近似的把考生考试所需时间看作正态分布的某一段图像，如图九所示：易知在正态分布的标准式中，代表期望，代表标准差，公式如下：结合图像可以看出，交卷子的概率分布可以用正态分布图像的一部分拟合，同时分布
18、函数图像为单调递增的图像，在某一点x后图像趋于稳定，与交卷子同学均已交卷所对应，可以验证猜想。利用MATLAB软件绘图并不断调整，大致确定在做第一道题和其余四道题期望分别取35和25时较为理想。在某场考试中，通过期望可以获得该场考试考生答题时间的均值，从而可以反映考生的平均答题时间，用期望来代替最大考试时间，利用问题一建立的整数模型进行规划，则可以获得较为满意的结果。6.2模型的求解利用问题一中的整数模型，首先利用Lingo软件求出考场的排布情况，如下图所示：表二 两个考场占用分布表112345限制人数A2010224B1202032总人数7949145837再利用Matlab软件进行考试前后
19、次序的排序问题，软件运行结果如下图五：结合假设2，得到如下结果（见图六）： A考场 B考场图四 考场考题考生分布图所以考生安排如表三：D1+D3(7)D5D2D3+D4+D5(7)D2D5(24)D5D1+D3D2D1+D4七、模型评价与推广 7.1模型的评价针对题目中所提出的三种不同情况，我们所建立的模型始终贯穿着简化的思想，比如引入矩阵表示考生，考场分布，问题三中简化随机模型等，进而通过约束进行最优化规划，但对于考生考试时间的冲突问题仍需通过枚举法等来辅助解决，将来对于模型的优化要着重考虑冲突问题的优化。6.2模型推广该多目标规划模型合理地解决了在考试时间最短、教室利用率尽可能高的情况下各
20、个考题对各个考场的占用次数，和各个考题分批考试的考生人数，在人工辅助下合理地对考题考试安排顺序进行调整，从而达到最优的考试安排。这种考试安排其实很类似于课程排课问题，对于排课问题，如果考虑到教师上课情况，只需要增加相关矩阵，相关约束条件，加之人工适当调整，便可解决问题，可见其推广前景明朗。八、参考文献1 黄勇,苏守宝.一种新的高校自动排考算法J.计算机工程与科学 2007(12).5 徐玖平、胡知能、李军，运筹学（II类），北京：科学出版社，2004. 九、附件此处附上编程的主要部分，各个步骤中所编程序的完整文件详见附件使用lingo求解题一的代码如下：model:sets: set1/1,2
21、/:f; set2/1.5/:x1,x2,a;endsetsdata:a=79,49,14,58,37;enddataf(1)=sum(set2:24*x1+32*x2-a);f(2)=abs(45*(x1(1)-x2(1)+30*(x1(2)+x1(3)+x1(4)+x1(5)-x2(2)-x2(3)-x2(4)-x2(5);!目标函数;min=smax(f(1),f(2);!约束条件;!24*x11+32*x21=79 24*x12+32*x22=49 24*x13+32*x23=14 24*x14+32*x24=58 24*x15+32*x25=37;for(set2:(24*x1+32
22、*x2)=a);b=45*x1(1)+30*(x1(2)+x1(3)+x1(4)+x1(5);c=45*x2(1)+30*(x2(2)+x2(3)+x2(4)+x2(5);for(set2:gin(x1);for(set2:gin(x2);gin(b);gin(c);End使用matlab求解题一的核心代码如下：%A为学生选题情况矩阵a=1 1 1 0 0;b=1 1 0 1 0;c=1 1 0 0 1;d=1 0 1 0 1;e=1 0 0 1 1;A=cat(1,a,a,a,a,a,a,a,a,a,a,a,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,
23、b,b,b,b,b,b,b,b,b,b,c,c,c,c,c,c,c,d,d,d,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e);%B为每道题需要的考场座位数矩阵f=24*(1+1+1+2)+32*(2+1+2);B=zeros(5,f);B(1,1:24+2*32)=1;B(2,24+2*32+1:2*24+3*32)=1;B(3,2*24+3*32+1:3*24+3*32)=1;B(4,3*24+3*32+1:3*24+5*32)=1;B(5,3*24+5*32+1:5*24+5*32)=1;%C为每个考生的座位分布范围矩阵C=A*B;%D为每个考生的座位分布矩阵D=zeros(79,280);for i=1:11; for j=1:280; D(i,j)=1; g=sum(D,1); %对每一列进行分别求和 h=sum(D(1:11,1:88),2);%对前11行，前88列的各行分别求和 k=sum(D(1:11,89:144),2); l=sum(D(1:11,145:168),2); if h(i,1)1|g(1,j)1|k(i,1)1|l(i,1)1|j168;%约束条件，前11个同学考第一道题只能一次 D(i,j)=0; end endend