用规划论给出假期自习室开放的最佳方案

1、 宁波大学第七届大学生数学建模竞赛 2011 年 5 月 6 日 5 月 9 日参赛题目 A B（在所选题目上打勾）参赛队员 1 参赛队员 2 参赛队员 3 姓名刘柳吴安琪吕伟学号084773713084773026084773422学院理学院理学院理学院专业信息与计算科学信息与计算科学信息与计算科学年级三年级三年级三年级电话 562246564906563976Email xclliudana_i412686999宁波大学教务处宁波大学数学建模实践基地用规划论给出假期自习室开放的最佳方案摘 要本文针对我校暑期有同学留校，对教室有需求，讨论了教室开放最佳安排方案。在对调查所得的数据进行加工的基

2、础上，结合开放的约束条件，建立了0-1整数规划模型，运用LINGO软件对模型求解。在问题一中，要求是在满足学生学习条件的前提下，进行教室开放安排的最佳方案。首先调研了数据，再根据实际情况与假设和模型求解方便，对数据进行了加工，舍弃了部分数据同时对于教室号进行重新编号，然后根据题意和约束条件，建立0-1规划模型，利用软件得出最优方案为只需开放7个教室，具体方案见表一。问题二中，增加了空调教室可以提供更多的座位，而非空调教室提供的座位数较少，故将空调教室与非空调教室分开设置变量，建立模型求得最优解，共开放28个教室，其中5个为空调教室，其余为非空调教室，具体方案见表二。问题三分为三个部分，第一部分

3、是开放最少的教室，第二部分是尽可能多的提供空调教室，第三个部分是尽量将开放的教室集中在同一幢教学楼。我们认为，这两个问题的最优解不唯一，我们得出数个可行解，供校方根据不同的需要选择不同的方案。问题四是根据实际的数据对模型进行优化。根据所得数据，每年暑假留校学生约为4000人，但是首先由于阅览室开放，可以容纳约1000人，其次由于考研教室在建立模型初期视为不开放，而事实是开放的，则约有1000人去考研教室和考研阅览室自习，最后，由于部分留校同学选择参与社会实践活动，故约有500人不会每天去自修。综上所述，只需要为约1500位同学提供座位，建立模型求解。得出最优方案见表四。最后，本文分析了我校的实

4、际情况，提出了可以从节约电费等方面对模型进行改进。关键字0-1规划 目标规划 LINGO软件 Matlab软件一 问题重述1.1背景描述通常在每年的寒暑假期间，都会有部分同学选择留在学校里。为了给这些留校同学提供一个舒适的自习环境，我校每年都会在假期开放一部分教室作为自习室。但是开放的教室不能太多，若一个偌大的教室只有几个同学在里面学习，显然是非常浪费的，同时开放太多教室的话也会给教室的管理以及卫生打扫等工作带来不必要的麻烦。而另一方面教室开放太少的话，又不能很好地满足假期留校同学的学习要求。为此学校需要确定一个假期自习室开放的最佳方案。数据包括两个部分，一个是教室资源的具体情况，见附表；另一

5、个是往年留校的学生人数，以估算今年暑假留校的人数范围。1.2需要解决的问题（1）假定通过报名登记预计今年会有500名学生假期留在学校，而学校可以考虑开放的教室均位于第一教学楼至第五教学楼。考虑到舒适性假设每个教室只能提供座位数的50%给学生自习，给出一个合理的假期自习室开放方案。（2）若每一个非空调教室只能提供座位数的30%给学生自习，而每一个空调教室能提供座位数的70%给学生自习，给出相应的自习室开放方案。另外考虑，若预计的留校学生数有所变动，方案是否还适当？（3）若考虑到为了便于打扫，希望尽可能开放较少的教室，请给出相应的自习室开放方案；若考虑到为了提高学生自习时的舒适度，希望尽可能开放空

6、调教室，请给出相应的自习室开放方案；若考虑到为了便于管理，要求所有开放的教室集中在同一幢教学楼，那么应该使用哪一幢教学楼，相应的自习室开放方案又是怎样的？（4）根据往年暑假期间留校学生人数，预估今年的留校人数，并完善你们的自习室开放方案，对学校这方面政策的制定建言献策。二 问题分析2.1问题一的分析问题一所要解决的问题是在满足学生学习条件的前提下，进行教室开放安排的最佳方案。由于每一个教室只有开放和不开放两种可能，结合每一个教室可以容纳座位数一半的人数，故可以利用规划。2.2问题二的分析问题二在问题一的基础上多考虑了空调教室这一因素，由于这一个因素的加入，空调教室可以容纳更多的人自习，需要改变

7、教室的“上座率”，在这个问题中，学生对于教室的“偏好”已经通过“上座率”体现，即有空调的教室会吸引更多的同学去，但是当教室的70%已满的时候，就不会有同学进入该教室；针对预计留校学生的变动，可以利用灵敏度分析来解决问题。2.问题三的分析对于问题三中的第一部分，应该是最优方案的必要条件；第二部分，尽量开放空调教室，以将空调教室的优先级调高，高于普通教室；第三部分，要求教室集中在一幢教学楼。2.问题四的分析根据宿管会的统计，每年暑假留校学生在4000到4500人，根据此数据进行安排。三 模型假设（一）假设同学去每一个教室的意愿相同，不存在教室的选取偏好，没有同学不愿意去的教室。（二）假设每一个教室

8、的每一个座位完好，不存在不可以使用或者同学不愿意去的座位。（三）假设每一个空调教室的空调状况良好，每一个空调教室的温度相同，即学生去任何一个空调教室的概率相同。（四）假设同学之间上自习相互独立，同学之间无影响；（五）假设学生去上自习的概率不受外界客观因素影响，如天气、病假等。（六）根据我校有一部分教室为考研教室，故这些教室不在计划开放范围内。四 符号说明 第i个教室是否开放 第i个教室的座位数 第i个教室中实际上自习的人数 总的开放教室数目五 模型的建立与求解5.1问题一模型的建立与求解5.1.1问题一模型的建立准备目标函数的分析：本题主要解决在满足同学自习需求的情况条件下，设计教室的开发最佳

9、方案的问题。根据题意并结合实际情况，可知教室的开放情况只存在两种情况，即开放与非开放，故本文就将这两种情况假设为1为教室的开放，0则为教室的非开放，故要建立0-1规划模型。设xi为教室的序号数，所以0-1规划模型的目标函数为的：min=；约束分析：1）据题意可知，从题目中每位同学上自习的可能性0.8，且独立上自习，同学之间无影响，故上自习的人数满足均匀分布，可以得到上自习的人的期望值为400人；2）又问题中要求开放的教室只提供百分之五十的座位，且在假设条件中为提高教室的利用效率，要求教室满座率不得低于四分之一则每间教室上自习的人数与开放教室的总座位数的比值应大于等25%，而小于等于50%，用表

10、示第间教室的座位数。故可以得到下面式(2)关系式：0.250.55.1.2问题一模型的建立根据题目中所给的条件以及调查所得的数据见附表一，结合以上所得的关系式，建立0-1规划模型，如下：min=；s.t. 5.1.3问题一模型的求解：教室的最佳开放方案。根据建立的建立的0-1规划模型，充分利用LINGO软件进行运算，程序过程及运行结果见附录二，最佳方案如表一：表一：开放教室安排表教室编号楼号教室座位数285213132295313132305413132364101-103132594401-403132684501-5031328451161325.2问题二模型的建立与求解5.2.1问题二模

11、型的建立准备目标函数的分析：由于教室的类型分为两种，为了计算方便，设i为空调教室编号，j为非空调教室编号，目标函数为：min=；约束分析：1）第一个约束不改变每位同学上自习的可能性0.8，且独立上自习，同学之间无影响，故上自习的人数满足均匀分布，可以得到上自习的人的期望值为400人；2）此问题中增加了“空调教室”，由于空调教室的可以提供更多的座位，而非空调教室提供的座位数下降，故只需要对问题一中的约束条件进行更改，可以得到下面式(2)关系式：对于空调教室：1.i32 0.250.7对于非空调教室33.j115 0.250.35.2.2问题二模型的建立：min=；s.t. 5.2.3问题二模型的

12、求解：利用LINGO软件进行运算，程序过程及运行结果见附录三，最佳方案如表二：表二：考虑空调教室的最佳安排方案教室编号楼号教室座位数教室编号楼号教室座位数11201-20313185520145285213132905208-2106829531313292521248305413132955304683155014597530868664414-4166910053144567441745103540668694502-50445104540990714506-50845105541068724509-51190107541245744513-515901105504687645174511

13、1550390775101-103901125508688451161321135507905.3问题三模型的建立与求解第二部分的问题要求优先开放空调教室，可以先计算出空调教室可以提供的座位数，利用matlab求出空调教室可以提供的座位数约为1700。故只用开放部分空调教室即可满足需求。程序过程及运算结果见附录四。第三部分的问题，要求在满足学生需求的情况下，将开放的教室尽量安排在同一幢教学楼。这一问题有数个可行解，可以先计算出每一栋教学楼满足舒适度的情况下能够提供的座位数。程序过程及结果见附录四。1号、2号、4号和4号教学楼可以提供的座位数分别为：549、781、924和1239。校方可以根据

14、留校人数的变化以及其他需要考虑的条件来选择开放的教学楼。5.4问题四模型的建立与求解5.4.1问题四模型的建立问题四实际上是对问题二的优化，根据所得数据，每年暑假留校学生约为4000人，但是首先由于阅览室开放，可以容纳约1000人，其次由于考研教室在建立模型初期视为不开放，而事实是开放的，则约有1000人去考研教室和考研阅览室自习，最后，由于部分留校同学选择参与社会实践活动，故约有500人不会每天去自修。综上所述，只需要为约1500位同学提供座位，故建立模型如下：min=；s.t. 5.4.2问题四模型的求解：利用LINGO软件进行运算，程序过程及运行结果见附录五，最佳方案如表四：表四：教室开

15、放安排方案教室编号楼号教室座位数教室编号楼号教室座位数11201-203131714506-5084521210-21262724509-5119031211-21580734510-5126941214-21662744513-5159051217-21950754514-5166961301-303807645174571305-30780775101-1039081309-31180785104-1066391313-31580795105-1078110230143805108-110631223041308151096014231256825112481623165683511448

16、182402438451161321924041038552014520240713086520240212411130875203-2056324250391885204-20663252504130895207-2096326251860905208-2106828521313291521160295313132925212483054131329352144831550145945216903255116095530468364101-10313296530390374102-1046997530868384105-10713298530790394106-108699953116040

17、4109-111132100531445414201-203132101531667454209-21190102540590464210-21269103540668474213-21590104540990504301-303132105541068544309-31190106541160564313-31590107541245594401-403132108541445634409-41190109541692644410-41269110550468654413-41590111550390664414-4166911255086867441745113550790684501-5

18、03132114551360694502-50445115551560704505-50760六 模型的分析与改进本文所涉及到的四个问题都为求在不同的约束条件下教室开放的最优方案。总的而言，约束条件只有一个，就是为学生尽可能的创造一个舒适的环境。然而在实际中，作为学校方案的制定者，还需要考虑到很多其他的方面，例如：当开启空调和电扇时，校方需要考虑如何安排才可以使得用电量最少。由于每一个教室的情况不同（提供的空调或电扇的数量不同、功率不同），需要更多的约束条件。另一方面，由于我校占地面积较大，分为三个校区，住在西区或者北区的假期留校生不太愿意来到本部自修。若校方考虑到实际情况想要同学们更方便的自

19、习，就需要将同学们的住宿地点作为一个条件加入到整个规划中，以便得出更优的解决方案。七 参考文献1 钱颂迪等，运筹学（本科版），北京：清华大学出版社，20052 薛定宇，陈阳泉，高等应用数学问题的MATLAB求解（第2版），北京：清华大学出版社，20083 姜启源、谢金星、叶俊，数学建模（第三版），北京：高等教育出版社，20034 LINGO教程（电子版）5 宋健，教室开放问题，附录附录一：宁波大学教室情况统计表教室编号楼号教室座位数教室编号楼号教室座位数11201-203131331306-3086421210-21262341310-3126031211-21580351314-316644

20、1214-21662364101-10313251217-21950374102-1046961301-30380384105-10713271305-30780394106-1086981309-31180404109-11113291313-31580414201-20313210230143424202-2044511230338434205-20760122304130444206-2084513230738454209-2119014231256464210-2126915231138474213-2159016231656484214-21669172315384942174518

21、240243504301-303132192404103514302-30445202407130524305-30760212411130534306-3084522241238544309-3119023241638554310-3126924250391564313-31590252504130574314-316692625186058431745275111-11332594401-403132285213132604402-40445295313132614405-40760305413132624406-4084531550145634409-411903255116064441

22、0-41269654413-41590664414-4166967441745684501-503132694502-50445704505-50760教室编号楼号教室座位数教室编号楼号教室座位数714506-5084594521690724509-5119095530468734510-5126996530390744513-5159097530868754514-51669985307907645174599531160775101-10390100531445785104-10663101531667795105-10781102540590805108-1106310354066881

23、51096010454099082511248105541068835114481065411608451161321075412458552014510854144586520240109541692875203-20563110550468885204-20663111550390895207-20963112550868905208-210681135507909152116011455136092521248115551560935214482401考研3501-503考研2418考研3505-507考研2501考研3508考研2502考研3510考研2511考研3512考研2514考

24、研5301考研2515考研5312考研2520考研5401考研3108-113考研5402考研3400考研5512考研3401考研5514考研3407考研3408考研3418考研3422考研注：1-32为有空调的教室，33-115为没有空调的教室附录二：model:!自习室开放规划问题;sets: power/1.115/:zws,x;endsetsdata:zws=131 62 80 62 50 80 80 80 80 43 38 130 38 56 38 56 38 43 103 130 130 38 38 91 130 60 32 132 132 132 45 60 64 60 64 1

25、32 69 132 69 132 132 45 60 45 90 69 90 69 45 132 45 60 45 90 69 90 69 45 132 45 60 45 90 69 90 69 45 132 45 60 45 90 69 90 69 45 90 63 81 63 60 48 48 132 45 40 63 63 63 68 60 48 48 90 68 90 68 90 60 45 67 90 68 90 68 60 45 45 92 68 90 68 90 60 60 enddata!目标函数;min=sum(power(i):x(i);!约束条件;sum(power(i)

26、:0.25*zws(i)*x(i)<=400;sum(power(i):0.50*zws(i)*x(i)>=400;for(power(i):bin(x(i);程序运行结果： Global optimal solution found. Objective value: 7.000000 Extended solver steps: 0 Total solver iterations: 47 Variable Value Reduced Cost ZWS( 1) 131.0000 0.000000 ZWS( 2) 62.00000 0.000000 ZWS( 3) 80.00000

27、 0.000000 ZWS( 4) 62.00000 0.000000 ZWS( 5) 50.00000 0.000000 ZWS( 6) 80.00000 0.000000 ZWS( 7) 80.00000 0.000000 ZWS( 8) 80.00000 0.000000 ZWS( 9) 80.00000 0.000000 ZWS( 10) 43.00000 0.000000 ZWS( 11) 38.00000 0.000000 ZWS( 12) 130.0000 0.000000 ZWS( 13) 38.00000 0.000000 ZWS( 14) 56.00000 0.000000

28、 ZWS( 15) 38.00000 0.000000 ZWS( 16) 56.00000 0.000000 ZWS( 17) 38.00000 0.000000 ZWS( 18) 43.00000 0.000000 ZWS( 19) 103.0000 0.000000 ZWS( 20) 130.0000 0.000000 ZWS( 21) 130.0000 0.000000 ZWS( 22) 38.00000 0.000000 ZWS( 23) 38.00000 0.000000 ZWS( 24) 91.00000 0.000000 ZWS( 25) 130.0000 0.000000 ZW

29、S( 26) 60.00000 0.000000 ZWS( 27) 32.00000 0.000000 ZWS( 28) 132.0000 0.000000 ZWS( 29) 132.0000 0.000000 ZWS( 30) 132.0000 0.000000 ZWS( 31) 45.00000 0.000000 ZWS( 32) 60.00000 0.000000 ZWS( 33) 64.00000 0.000000 ZWS( 34) 60.00000 0.000000 ZWS( 35) 64.00000 0.000000 ZWS( 36) 132.0000 0.000000 ZWS(

30、37) 69.00000 0.000000 ZWS( 38) 132.0000 0.000000 ZWS( 39) 69.00000 0.000000 ZWS( 40) 132.0000 0.000000 ZWS( 41) 132.0000 0.000000 ZWS( 42) 45.00000 0.000000 ZWS( 43) 60.00000 0.000000 ZWS( 44) 45.00000 0.000000 ZWS( 45) 90.00000 0.000000 ZWS( 46) 69.00000 0.000000 ZWS( 47) 90.00000 0.000000 ZWS( 48)

31、 69.00000 0.000000 ZWS( 49) 45.00000 0.000000 ZWS( 50) 132.0000 0.000000 ZWS( 51) 45.00000 0.000000 ZWS( 52) 60.00000 0.000000 ZWS( 53) 45.00000 0.000000 ZWS( 54) 90.00000 0.000000 ZWS( 55) 69.00000 0.000000 ZWS( 56) 90.00000 0.000000 ZWS( 57) 69.00000 0.000000 ZWS( 58) 45.00000 0.000000 ZWS( 59) 13

32、2.0000 0.000000 ZWS( 60) 45.00000 0.000000 ZWS( 61) 60.00000 0.000000 ZWS( 62) 45.00000 0.000000 ZWS( 63) 90.00000 0.000000 ZWS( 64) 69.00000 0.000000 ZWS( 65) 90.00000 0.000000 ZWS( 66) 69.00000 0.000000 ZWS( 67) 45.00000 0.000000 ZWS( 68) 132.0000 0.000000 ZWS( 69) 45.00000 0.000000 ZWS( 70) 60.00

33、000 0.000000 ZWS( 71) 45.00000 0.000000 ZWS( 72) 90.00000 0.000000 ZWS( 73) 69.00000 0.000000 ZWS( 74) 90.00000 0.000000 ZWS( 75) 69.00000 0.000000 ZWS( 76) 45.00000 0.000000 ZWS( 77) 90.00000 0.000000 ZWS( 78) 63.00000 0.000000 ZWS( 79) 81.00000 0.000000 ZWS( 80) 63.00000 0.000000 ZWS( 81) 60.00000 0.000000 ZWS( 82) 48.00000 0.000000 ZWS( 83) 48.00000 0.000000 ZWS( 84) 132.0000 0.000000 ZWS( 85) 45.00000 0.000000 ZWS( 86) 40.00000 0.000000 ZWS( 87) 63.00000 0.000000 ZWS( 88)