寄宿家庭安排方案

数学建模校内模拟竞赛论文论文题目：寄宿家庭安排方案2012-7-171寄宿家庭安排方案【摘要】本文将寄宿家庭安排抽象为运输问题的模型，采用0-1整数规划表述。把所给的数据进行有规律的分类排序，根据寄宿中心需要建立不同目标的0-1整数规划模型，运用Lingo软件求解，并运用贪心算法检验模型的求解。第一问，我们先对30个寄宿家庭按照性别要求、床位数进行排序，使数据有一定的规律，方便编程和结果分析。以所需要的总寄宿家庭数为目标，结合人数、性别要求、男女不混住等约束，建立0-1整数规划模型（见5.1.3模型Ⅰ），完成把2个组的所有学生分配到30个家庭的要求。用Lingo软件对此模型求解，得到最优方案，最少需要20个寄宿家庭，具体的方案如下（列举一种，其他结果见5.2.2）：寄宿家庭ID号男生入住的家庭4,5,8,11,15,24,26,27女生入住的家庭1,2,3,7,9,10,12,13,16,18,21,28针对此问题，我们又运用了贪心算法进行求解，提供与Lingo求解的对照，以到达检验此模型的求解。第二问，由于问题的框架是在问题一的基础上给出了具体的各种费用，所以我们对问题一的模型做了更新，其目标变为寄宿中心总的支出费用最少，寄宿家庭数变为200个。同样的思路，建立0-1整数规划模型（见6.13模型Ⅱ），用Lingo软件对此模型进行求解。求得的最优支出费用为7700美元，选择的家庭最少为14个。具体方案如下（列举一种，其他结果见6.2.2）：寄宿家庭ID号男生入住的家庭27,43,50,81,86,122女生入住的家庭16,52,58,98,102,142,144,159第三问，考虑到10个团队中有一些团队不愿与其他团队共寄一檐，我们可以把这10个团队按照是否与其他团队共寄原则从新分组，以寄宿中心总的支出费用为目标，以每个组的人数、男女不混住、新分的组之间不共寄等为约束，建立0-1线性规划模型（见7.1.3模型Ⅲ）。由于10个团队中没有给出哪个团队不愿与其他团队共寄，而总的情况种类又很多，我们在模型求解中列举了有1个团队、有5个团队不与其他团队共寄的两种情况。结果解出最优支出费用为64050美元，最少寄宿家庭数为169个（具体结果见7.2.2）。然后又运用贪心算法的思想编写Matlab程序，对模型的求解进行检验。关键词：0-1整数规划贪心算法运输模型2一．问题重述暑期将致，北京“常青藤”文化旅行社国际部与美国HomestayCenter联合为中学生打造了一个美国文化之旅的夏令营活动。此活动主要集中在素有“美国经济之都”之称的纽约地区，通过走访考察常青藤名校，深度了解普林斯顿、耶鲁、哈佛、麻省理工等名校录取标准和教学理念，感受中美教育文化的差异。同时，走进美国寄宿家庭，通过朝夕相处，接受纯正美式英语的熏陶，迅速提高英语听力及口语交流水平。通过夏令营，亲身体验美国本土生活，深度感受美国社会经济文化，让年青的中学生们在激动不已的同时，开始重新设计充满挑战的未来。纽约片区的寄宿家庭通过向寄宿中心（HomestayCenter）提出申请，提交接受学生床位数，学生性别要求等相关信息。寄宿中心审核通过，便获得接收寄宿学生的资格。寄宿家庭对寄宿学生无性别要求的，男生女生均可安排，但不能男女生混住。现在就所给的数据解决以下问题：1.现有一组男生30人，女生40人的旅行团队，计划在ID为1~30的家庭中进行安排。请你建模为寄宿中心做出寄宿家庭接收学生的方案。2.事实上，寄宿家庭提供的是有偿服务，每安排一位学生入住，寄宿中心就要向寄宿家庭支付100美元。但如果入住的学生少于其提供的床位，则每床加收20美元的空床费；另外，根据联邦法律，只要寄宿家庭提供了寄宿服务，无论入住人员多少，都要交税50美元，这项费用也由寄宿中心承担。请更新你的模型，做出寄宿家庭接收学生方案，使支出费用最小。3.在寄宿家庭分配环节中，总有些团队，如来自一个家庭，一个学校等，不希望与别的团队共寄一檐。现在寄宿中心今年夏天共有10个团队，其成员结构详见所给数据。请你为寄宿中心做出最优的寄宿方案，并求出最小的支出费用。二．问题分析本题主要在三种不同情况下，研究寄宿中心做出合理的寄宿方案选择问题。联系实际，寄宿中心做出寄宿家庭接收学生的方案主要考虑的因素包括：各家庭提供的床位数，学生性别，所需要的寄宿家庭数，是否愿意与别的团队共寄，支出费用等因素。在满足学生的居住要求的前提下，主要依据支出费用和寄宿家庭数，来确定出最佳的寄宿方案。在仅考虑完成寄宿安排方案的情况下，首先，需要对题目给出的寄宿家庭资源的ID为1～30号的家庭进行性别要求分类，与每个家庭的床位数对应。然后，主要考虑男女不能混住、寄宿家庭的性别要求、床位数，将30个男生、40个女生分配到30个寄宿家庭。并考虑以所需寄宿家庭的数目为主要目标，建立最优化模型确定可供寄宿中心选择的寄宿方案。在第二问的情况下，寄宿家庭提供的是有偿服务，且提供了寄宿服务的都要交税，这些费用全部由寄宿中心承担。所以，在第一问的基础上更改为以支出费用为主要目标，在200个寄宿家庭中寻找寄宿分配方案。在此基础上按照相同的思路确定出最佳寄宿安排方案。第三问增加了有些团队不希望与别的团队共寄一檐这一条件，可考虑将此10个团队按照性别、是否愿意与别的团队共寄，分成若干组，即组与组之间不能共寄。例如，若有一个团队不愿与别的共寄，则可分为2个团队4个组。再把4个组的成员分配到200个寄宿家庭，以支出费用为目标结合约束条件即可确定最优方案。此种约束分配在现实3中具有重要意义，可以延伸到任意个不愿共寄的团队和个人。三．模型假设[1]假设每个团队内同性别的成员可以共寄一檐；[2]假设各个团体的学生都接受寄宿中心安排的寄宿家庭；[3]假设每个寄宿家庭的环境的因素不影响学生入住安排；[4]假设对每个家庭按照床位数进行排序时，具有相同床位数的家庭不存在优先顺序；[5]假设每个家庭均能接受任何寄宿中心安排入住的学生；[6]假设安排学生入住寄宿家庭后不存在家庭调换的情况。四．符号说明ijx：源点i能否可以把学生送往j号家庭ija：源点i送往j号家庭的人数jd：j号家庭的床位数1C：每个提供寄宿服务且有人入住的家庭所需缴纳的税费，在此题中已给出50美元2C：每个提供寄宿服务的家庭若床位没有住满，每个空床寄宿家庭需支付的空床费，在此题中已给出20美元3C：每个学生入住寄宿家庭，寄宿中心需支付给寄宿家庭的费用，此题中已给出100美元五．寄宿家庭接收学生选择模型（问题一）本节主要研究寄宿分配方案选择的数学模型与算法。为了寻找出选取寄宿家庭的方案，可以把此题看做运输问题模型[1]，以所需的总寄宿家庭数为目标，结合人数、性别要求、男女不混住等约束，求出可行方案。5.1模型Ⅰ分析与建立5.1.1最优分配思路的确立此问题的要求是给30名男生、40名女生男生分配寄宿地点，即把这70名对象分配到30个寄宿家庭。所以，可以把所有男生看做一个源点1，拥有30个货物；所有女生看做源点2，拥有40个货物。要解决的问题既是把这两个源点的货物全部运到30个目的地，每个目的地接收的货物不能超过其容量。因此，此寄宿家庭安排问题可以看做一个典型的运输问题。其模型的示意图如下：4图1问题抽象为运输问题的示意图为了便于数据的分析和处理，需要把ID号为1～30的数据进行分类，分类按着性别要求，得到的结果按照性别要求1、0、2的顺序排列。排序的结果为只能住男生的是1～6号，没有性别要求的是7～22号，只能住女生的是23～30号。（ID号为1～30的数据分类排序的详细结果参见附件2.1）5.1.2模型Ⅰ分析我们结合实际，考虑到寄宿中心根据自身工作量要求，总是希望与最少数量的寄宿家庭建立联系。所以，以方案中所需要的寄宿家庭数量为目标，再结合完成分配的一些约束条件，建立求解此问题的模型。下面将分析解决此问题的目标和约束条件。目标分析寄宿中心选择了寄宿家庭后，不可避免的会与这些家庭经常联系，例如了解学生寄宿的情况、探访学生，这就使得寄宿中心希望学生寄宿相对集中、寄宿家庭数目少，从而减少自己的工作量。基于5.1.1建立的运输模型示意图，引入0-1决策变量ijx表示是否从源点i运输到第j个寄宿家庭，则：10ijijxelse从送到第个寄宿家庭要使得学生入住的家庭数最少，对于运输问题的模型即希望目的地最少，则有：23011inijijMx（1.1）约束分析1)男生人数约束可寄宿男生的家庭包括性别要求为男和无性别要求的家庭，所以源点1的男生可以被送往的家庭号位1～22号，即源点1的30个男生将全部被送往122j号中的某些家庭。所以有：22111jjjaxB（1.2）其中，参数B为男生人数，可以根据实际情况设定，在此题中已给出为30人。52)每个家庭床位数对男生的约束男生被送往第j号家庭对应1ja人，第j号家庭拥有的床位数为jd个，每个家庭接收的人数不能大于提供的床位数。所以需要满足：1jjad1,2,,22jL（1.3）3)女生人数约束可寄宿女生的家庭包括性别要求为女和无性别要求的家庭，所以源点2的女生可以被送往的家庭号位7～30号，即源点2的40个女生将全部被送往730j号中的某些家庭。所以有：30227jjjaxG（1.4）其中，参数G为女生人数，可以根据实际情况设定，在此题中已给出为40人。4)每个家庭床位数女生的约束女生被送往第j号家庭对应2ja人，第j号家庭拥有的床位数为jd个，每个家庭接收的人数不能大于提供的床位数。所以需要满足：2jjad7,8,,30jL（1.5）5)男女不混住约束在无性别要求的家庭7,8,,22jL中，如果男生被送往j，则女生一定不能被送往相同的j号家庭，即要求男女不混住。所以满足：120jjxx7,8,,30jL（1.6）另外，源点i送往j号家庭的人数ija需满足：()ijaNN为自然数。5.1.3模型Ⅰ建立基于5.1.2分析，以（1.1）为目标，以(1.2)～(1.6)为约束，建立0-1、整数混合规划[2]的运输模型，表达式如下：23011inijijMx..ST22111jjjaxB1jjad1,2,,22jL（1.3）30227jjjaxG2jjad7,8,,30jL（1.5）120jjxx7,8,,30jL（1.6）6{0,1}ijx,ijaN模型说明：（1.3）、（1.5）为床位约束，分别表示一个寄宿家庭接收的男、女生人数不大于床位数。（1.6）男女不能混住约束，表示对于同一个寄宿家庭最多只有一类学生（男或女）入住。ijx——从源点i是否送到第j个寄宿家庭；ija——从源点i送到第j个寄宿家庭的人数；jd——第j号家庭拥有的床位数；B——男生人数，可以根据实际情况设定，在此题中已给出为30人；G——女生人数，可以根据实际情况设定，在此题中已给出为40人。5.2模型Ⅰ的求解（程序见附件1.1）5.2.1模型求解的方法此模型为一个标准的整数规划问题，可使用Lingo软件[3]求解。在Lingo中编写类似于运输问题模型的的程序，其数据量不是很大，其中的变量ijx用0-1约束条件，ija用整数约束条件。总体规划模型的语言比较简单，只需1秒便可解出结果。由于此题的方案数表较多，目标较少，得到的结果只是一个局部最优解。5.2.2求解的结果用Lingo软件多次求解的结果都是：需要的最少家庭数为20个。（1）具体方案举例寄宿家庭安排的一种具体方案：下表列举了一种具体的寄宿安排分配方案，一行代表每个家庭的床位数、寄宿情况、入住人数，性别列表示了寄宿学生的性别、是否寄住此家庭（“-”表示不寄住此家庭）。表1寄宿家庭安排的具体方案ID床位数入住人数性别ID床位数入住数性别133女1655女233女1710344女1830433男1932男544男20206302144女733女2220844男2310933女2444男1033女25101144男2644男1233女2755男1333女2844女14202