基于0-1规划的场地安排问题.doc

基于0-1规划的场地安排问题摘要一、问题的重述2009年，我校城南校区共有3021名同学报名参加江苏省高等数学竞赛，其中，878人报名参加经贸类考试，1724人报名参加工科类考试，200人报名参加文科类考试，219人报名参加数学类考试。为此特向教务处申请了如下教室作为考场，详见附录一表一。要根据考场的地理位置与容量，安排每个考场的考生人数以及监考教师数，在安排的过程中还要考虑如下几点：1、不同类型的考生不能分配在同一考场中；2、每个监考教师监考的考生人数要尽量相同；3、考场中会有一些突发状况，在安排考场时要尽量考虑周全；4、使用的教室要尽量少，以作备用教室及考务教二、问题的分析随着我国教育体制的改革的深入，学生人数的不断上升，手工安排考场易错难改、效率低的缺点就越来越突出。由于计算机具有速度快，处理能力强等特点，很自然的进入到这一领域中，用计算机进行考场安排能够快速的得到满足约束条件的可靠结果，具有考场安排时间短、人力省和质量高的优点，不但能使教务人员从繁杂的排考场任务中解脱出来，而且对于推动教学的发展出起了非常重要的作用。分析题目可得，要保证考试的公平性和一些突发状况，每个教室就不能安排与教室容量相同数目的考生，即每个教室的考生数目要小于教室容量，按照常识推算，一般考生数目大概占教室容量的1/2到1/3，而且还要求尽量的少用教室，所以选取教室是很重要的一步。每个老师的监考人数可以根据考场的实际情况来进行安排调控，所以可以放在最后再考虑。第一步就先单纯的选取部分教室作为考场，进行合理的选择安排，尽量使得选取的教室数量最少，以便空出足够教室作为备用考场和考务办公室。先对教室的类型和数目进行分析，如下表所示：表二 考场类型及数目教室类型可容学生数量教室数量教室类型可容学生数量教室数量A9618J1562B981K1601C1012L1872D1112M1952E1212N1992F1261O2002G1304P2091H1421Q2151I1445R2161在不考虑不同类考生坐在同一间教室的情况下，遵循选出最少的考场数原则，利用0-1规划模型，建立目标函数和约束条件，运用LINDO编程对所用考场进行选择。根据LINDO的运行结果选出教室作为考场。第二步，再根据“不同类别的考生不能安排在同一考场中”这一条件，对选出的教室进行合理的安排。共四类考生，先进行排序，再根据每种排序的顺序，运用LINDO进行编程，依次对不同类型的考生选出最优的教室，分析比较选出最合理的那一种，确定每类考生所在的考场。然后再进行手排，确定具体每个考场中考生的数目。最后，根据“每个监考教师监考的考生数目应尽量相同”这一条件，确定每个考场中所需安排的监考教师的数目，并计算每名教师监考的考生的数目。三、基本假设（1）假设容量为偶数的教室中的全部是双人课桌，容量为奇数的教室中只有一张单人桌，其他都为双人桌；（2）考生全部出席；（3）考试所需的硬件设施，教室都可以提供；（4）监考老师的数量足够，且每个监考老师都能准时出席。四、符号说明：教室的编号。：所有选出的教室总量。：第i个教室相对应的实际考生容量。：每类考试所用教室总量。：所有教室最多能容纳的考生总数。：考生的实际总数。五、模型的建立和求解5.1模型一0-1规划模型的数据处理在同一个考场中所需要的考场数量一定为大于或等于不同考生可以坐在同一个考场中所需要的考场数量，所以我们先按考不同考生可以坐在同一个考场中先选出教室，再根据不同类别考生不可以坐在同一考场中来安排考生。为了方便书写与表达，我们先对题目所给出的表格进行新的编排和归类，考虑到考试的公平性再结合实际，我们提出考场的实际考生最大容量为考场本身最大容量的1/3和1/2两种方案，新建的表格见下表三和表四。表三教室编号可容纳考生数（1/2容量）可容考生数（1/3容量）教室编号可容纳考生数（1/2容量）可容考数（1/3容量）14832266342248322765433483228654344832296543548323065436483231714774832327248848323372489483234724810483235724811483236724812483237785213483238785214483239805315483240936216483241936217483242976518483243976519493244996620503345996621503346100662255374710066235537481046924604049107712560405010872合计124382820871388表一是对教室进行新的编排，制定新的编号，并且给出了当实际容量为本身容量的1/2和1/3时各教室相对应的实际容量值，由表得设置（1/2容量）考场能容纳的学生总数为3330，设置（1/3容量）考场能容纳的学生总数为2216。表四教室类型可容学生数量可容考生数教室数量A964818B98491C101502D111552E121602F126631G130654H142711I144725J156782K160801L187942M195972N199992O2001002P2091041Q2151071R2161081表二是根据教室本身容量值指定的，我们将相同容量的教室归为一类并给出类名和一些相关数据。有表一可得：（5） 当设置实际考生容纳量为本身容纳量的1/3时，所有教室能容纳的最多考生总数，但考生的实际总数，即。所以设置教室实际考生容纳量为本身容纳量的1/3不可行。（2）当设制实际考生容纳量为本身容纳量的1/2时，所有教室能容纳的最多考生总数，但考生的实际总数，即。所以设置教室实际考生容纳量为本身容纳量的1/2可行。综上我们决定设置教室实际考生容纳量为本身容纳量的1/2的方法。5.2模型一0-1规划模型的建立与求解5.2.1教室的选择在满足学生需要的前提下尽可能使用少的的教室，运用0-1规划模型可以满足此要求，故设0-1变量为：要使选出的教室数最少，则在运用0-1规划后，应使所有0-1规划变量的总和最小，以此来建立目标函数。目标函数为:选出的教室，其实际的最大容纳量总和一定要大于等于考生总数，根据此来建立约束条件：表示第个教室相对应的实际考生容量，运用LINDO软件编程可选出所需要的教室，其结果见表五（编程见附录二）表五所选用的教室类型所选用的教室相应数量所选用的教室类型所选用的教室相应数量A12J2B1K1C2L2D2M2E2N2F1O2J4P1H1Q1I5R1表五表示所选出的各类教室，及各类教室所对应的数目，同时也给出了所选用的教室总数为44，和选用的教室编号。未选用的教室编号为5，6,7,9,14,17，选用的教室总数为44，所选用的教室总容纳量3042。5.2.2教室的安排在安排教室时，是有先后顺序的，即先安排哪类学生是不确定的，所以在有顺序的安排教室时根据排列组合原理，此情况总数应为种即24种情况。但根据观察，我们会发现参加文科类考试的人数总和与编号为46,47的两个教室实际最大容纳量总和相等，我以我们将文科类的考生直接安排到这两个教室中，所以此时再根据排列组合会发现。此时情况总和为种即6种情况，下面我们就对此六种情况进行分析并得出最优解。（1）按照经贸类，工科类，数学类的顺序进行安排，我们仍根据0-1规划模型进行求解。在对经贸类考生进行安排教室时，仍然按照使用最少的教室和尽量接近和不少于经贸类考生人数的约束条件。目标函数：根据上面的说明此约束条件为：运用LINDO软件编程计算，我们可以得出为参加经贸类考试所安排的教室的编号为:38,41,42,43,44,45,48,49,50。接着为工科类进行安排教室，此安排是在去除参加经贸类考试所安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件编程进行计算，我们可以得出为工科类选出的教室编号为:1,2,3,4,8,10,11,12,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,39,40。剩余的教室编号为13，15,16,18，从而得出剩余的所有教室实际最大容量总和为192，但参加数学类考试的学生总数为219，所以显然这种排法不合理。（编程见附录三）（2）按照数学类，工科类，经贸类的顺序进行安排安排的方法与5.2.2中的(1)相同。先为参加数学类考试的考生安排教室目标函数为：根据上面的说明此约束条件为：运用LINDO软件编程计算，我们可以得出为参加数学类考试所安排的考试编号为：40,49,50。接着为参加工科类考试的考生安排教室，此安排是在去除为参加数学类考试安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件编程进行计算，我们可以得出为工科类选出的教室结果为：1,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,41,42,43,44,45,48。而在已选出的44个教室中,剩余的教室编号为：2,3,4,10,11,12,13,15,16,18,19,20，21,22,23,24。即留给参加经贸类考试的教室只有这15个，通过计算可得剩余所有教室实际最大容量值总和为769，但参加数学类考试的学生总人数为878，所以显然此方案不成立。（编程见附录四）（3）按照数学，经贸，工科的顺序进行安排先为参加数学类考试的考生安排教室目标函数为：根据上面的说明此约束条件为：运用LINDO软件编程计算，我们可以得出为参加数学考试所安排的考场编号为：40,49,50。接着为参加经贸类考试的考生安排教室，此安排是在去除为参加数学类考试安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件编程进行计算，我们可以得出为经贸类选出的教室结果为：40,49,50。而在已选出的44个教室中,剩余的教室编号为：1,2,3,4,8,10,11,12,13,15,16,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35。即留给参加经贸类考试的教室只有这29个，通过计算可得剩余所有教室实际最大容量值总和为1619，但参加工科类考试的学生总人数为1724，所以显然此方案不成立。（编程见附录五）（4）按照经贸，工科，数学的顺序进行安排先为参加经贸类考试的考生安排教室目标函数为：根据上面的说明此约束条件为：运用LINDO软件编程计算，我们可以得出为参加经贸考试所安排的教室编号为：38,41,42,43,44,45,48,49,50。接着为参加工科类考试的考生安排教室，此安排是在去除为参加经贸类考试安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件进行计算，我们可以得出为工科类选出的教室结果为：1,2,3,4,8,10,11,12,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40。而在已选出的44个教室中,剩余的教室编号为：13,15,16,18。即留给参加数学类考试的教室只有这4个，通过计算可得剩余所有教室实际最大容量值总和为192，但参加数学类考试的学生总人数为219，所以显然此方案不成立。（编程见附录六）（5）按照工科类，经贸类，数学的顺序进行安排先为参加工科类考试的考生安排教室目标函数为：根据上面的说明此约束条件为：运用LINDO软件计算，我们可以得出为参加工科类的考试安排的教室编号为：27,28,29,31,32,33,34,35,36,37,38,39,40,41,45,48,49,50。接着为参加经贸类考试的考生安排教室，此安排是在去除为参加工科类考试安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件编程进行计算，我们可以得出为工科类选出的教室结果为：1,3,4,8,10,11,1218,19,20,21,22,23,30。而在已选出的44个教室中,剩余的教室编号为：2，13,15,16。即留给参加数学类考试的教室只有这4个，通过计算可得剩余所有教室实际最大容量值总和为192，但参加数学类考试的学生总人数为219，所以显然此方案不成立。（编程见附录七）（6）按照经贸类，数学类，工科的顺序进行安排先为参加经贸类考试的考生安排教室目标函数为：根据上面的说明此约束条件为：运用LINDO软件编程计算，我们可以得出为参加经贸类考试所安排的教室编号为：38,41,42,43,44,45,48,49,50。接着为参加数学类考试的考生安排教室，此安排是在去除为参加经贸类考试安排的教室的基础上的安排目标函数为：约束条件为：运用LINDO软件编程进行计算，我们可以得出为工科类选出的教室编码为：2,39,40。而在已选出的44个教室中,剩余的教室编号为：1,3,4,8,10,11,12,13,15,16,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37。即留给参加数学类考试的教室有30个，通过计算可得剩余所有教室实际最大容量值总和为1739，而参加工科类考试的学生总人数为1724，所以显然此方案成立。（编程见附录八）所以根据对上述六种情况的一一分析，我们便可得出第六种情况是符合题意的，故我们采用按照经贸，数学，工科的顺序为每个专业进行安排教室，并制定出下表六表六考生类型考场代码考场容纳人数考生人数差额文科类46、472002000经贸类38、41、42、43、44、45、48、49、508828784数学2、39、402212192工科类1、3、4、8、10、11、12、13、15、16、18到371739172415表六表示各类别考生安排的考场编号，考场实际最大容量值，实际考生人数以及差额。5.23教师的安排和最后的结果为了使每个教师所监考的学生数基本相同，所依我们尽可能的是每个教室的学生人数与教室实际容纳量的最大值相同，或相近。所以我们通过手排得出了最终的结果，见下表七表七考生类别教室代码可容考生数实际安排考生数监考教师数监考教师平均监考学生数文科类广A101100100425广B101100100425经贸类仁和1117878326法B2089393423.25博C2069797424.25博C4079797424.25博C3079999424.75博C5079999424.75仁和210104104426畅远211107105426.25仁和110108106426.5数学类广B1044848224健B2098078326法B3099393423.25工科类广B1034848224广B1054848224广B1064848224广B2044848224广B2064848224广B2144848224广B3054848224广B3064848224广B3074848224语3014848224语3134848224郁B2094949224.5博C5035050225博C4045050225博C2035555227.5博C3035555227.5畅远2106056228畅远1086056228博C5066356228广A1156565321.67广B2136565321.67广B3116565321.67广B1136565321.67法A1077171323.67郁B4097272324郁B3117272324畅远2097272324畅远1097272324法A1067272324仁和2117878326表七给出了每个学科安排的考场，每个考场安排的考生数和监考教师数以及监考教师平均监考考生数。六、模型的评价与推广6.1.模型的优缺点分析61.1.模型的优点1、本文用0-1规划模型来解决考场安排问题，运用LINDO编程选出最优的一部分教室，然后进行进一步的安排，可以减少所用教室的数目。2、运用LINDO编程选择安排教室，可以减少对所有教室进行考场安排的盲目性，省时高效的安排考场。3、运用0-1规划模型求解安排大大减轻了工作人员的工作量，大大节约了人力和时间。4、用0-1规划模型安排考场更加准确，更加周全。6.1.2.模型的缺点1、监考老师的安排只是在安排好考生后进行粗略的估算安排，没有很好的满足“每个监考教师的监考人数应该尽量相同”这一条件。2、在解决问题时达到了所用教室数最少这一条件，但是没有很好的考虑教师数目这一问题。3、安排考场时考虑了部分突发问题，但考虑的并不完全。4、安排考生时假定每个考场的考生数占教室容量的1/2，太过理想化了。6.2.模型的推广0-1规划是一种特殊形式的整数规划 。这种规划的决策变量仅取值0或1。0-1变量可以数量化地描述诸如开与关、取与弃、有与无等现象所反映的离散变量间的逻辑关系、顺序关系以及互斥的约束条件，因此0-1规划非常适合描述和解决如线路设计 、工厂选址、生产计划安排、旅行购物、背包问题、人员安排、代码选取、可靠性等人们所关心的多种问题。凡是有界变量的整数规划都可以转化为0-1规划来处理 。由于0-1规划具有深刻的背景和广泛的应用，一直受到人们的重视。 七、参考文献1宋学锋，运筹学：134-145，南京：东南大学出版社，2003.2。2王文波，数学建模及其基础知识详解：93-95，武汉：武汉大学出版社，2006.5。3宋一中，0-1规划及其解法J,数学实践与认识,第一期：75-81，1995.1。4林显宁，利用规划的方法求解一个最优问题，湖北广播电视大学学报，第30卷第3期：157-158,2010.3。附录附录一表一教室容量教室容量教室容量广B10396博C404101法B208187广B10496博C203111博C206195广B10596博C303111博C407195广B10696畅远210121博C307199广B10796畅远108121博C507199广B10896博C506126广A101200广B10996广A115130广B101200广B20496广B213130仁和210209广B20596广B311130畅远211215广B20696广B113130仁和110216广B21496法A107142广B30596郁B409144广B30696郁B311144广B30496畅远209144广B30796畅远109144语30196法A106144语50196仁和211156语31396仁和111156郁B20998健B209160博C503101法B309187附录二Minx1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x46+x47+x48+x49+x50Subject to55x1+97x2+55x3+99x4+50x5+97x6+50x7+63x8+99x9+60x10+72x11+72x12+60x13+107x14+72x15+71x16+93x17+93x18+49x19+72x20+72x21+100x22+65x23+100x24+48x25+48x26+48x27+48x28+48x29+48x30+48x31+65x32+48x33+48x34+48x35+65x36+48x37+48x38+48x39+48x40+48x41+65x42+80x43+108x44+78x45+104x46+78x47+48x48+48x49+48x50=3021endint 50附录三Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x48+x49+x50Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+78x38+80x39+93x40+93x41+97x42+97X43+99x44+99x45+104x48+107x49+108x50=878endint 42Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x39+x40Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+80x39+93x40=1724endint 33附录四Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x48+x49+x50Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+78x38+80x39+93x40+93x41+97x42+97X43+99x44+99x45+104x48+107x49+108x50=219endint 42Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x41+x42+x43+x44+x45+x48Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+78x38+80x39+93x41+97x42+97X43+99x44+99x45+104x48=1724endint 39附录五Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x41+x42+x43+x44+x45+x48Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+78x38+80x39+93x41+97x42+97X43+99x44+99x45+104x48=878endint 39附录六Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x48+x49+x50Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+78x38+80x39+93x40+93x41+97x42+97X43+99x44+99x45+104x48+107x49+108x50=878endint 42Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x39+x40Subject to48x1+48x2+48x3+48x4+48x8+48x10+48x11+48x12+48x13+48x15+48x16+48x18+49x19+50x20+50x21+55x22+55x23+60x24+60x25+63x26+65x27+65x28+65x29+65x30+71x31+72x32+72x33+72x34+72x35+72x36+78x37+80x39+93x40=1724endint 33附录七Minx1+x2+x3+x4+x8+x10+x11+x12+x13+x15+x16+x18+x19+x20+x21+x22+x23+x24+x25+x26+x27+x28+x29+x30+x31+x32+x33+x34+x35+x36+x37+x38+x39+x40+x41+x42+x43+x44+x45+x48+x49+x50Subject to48x1+48x2+48x3+48x4+48x