资源描述：
《寄宿家庭安排方案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数学建模校内模拟竞赛论文论文题目：寄宿家庭安排方案2012-7-1729寄宿家庭安排方案【摘要】本文将寄宿家庭安排抽象为运输问题的模型，采用0-1整数规划表述。把所给的数据进行有规律的分类排序，根据寄宿中心需要建立不同目标的0-1整数规划模型，运用软件求解，并运用贪心算法检验模型的求解。第一问，我们先对30个寄宿家庭按照性别要求、床位数进行排序，使数据有一定的规律，方便编程和结果分析。以所需要的总寄宿家庭数为目标，结合人数、性别要求、男女不混住等约束，建立0-1整数规划模型（见5.1.3模型Ⅰ），完成把2个组的所有学生分配到30个家庭的要求。用软件
2、对此模型求解，得到最优方案，最少需要20个寄宿家庭，具体的方案如下（列举一种，其他结果见5.2.2）：寄宿家庭号男生入住的家庭4,5,8,11,15,24,26,27女生入住的家庭1,2,3,7,9,10,12,13,16,18,21,28针对此问题，我们又运用了贪心算法进行求解，提供与求解的对照，以到达检验此模型的求解。第二问，由于问题的框架是在问题一的基础上给出了具体的各种费用，所以我们对问题一的模型做了更新，其目标变为寄宿中心总的支出费用最少，寄宿家庭数变为200个。同样的思路，建立0-1整数规划模型（见6.13模型Ⅱ），用软件对此模型进行求
3、解。求得的最优支出费用为7700美元，选择的家庭最少为14个。具体方案如下（列举一种，其他结果见6.2.2）：寄宿家庭号男生入住的家庭27,43,50,81,86,122女生入住的家庭16,52,58,98,102,142,144,159第三问，考虑到10个团队中有一些团队不愿与其他团队共寄一檐，我们可以把这10个团队按照是否与其他团队共寄原则从新分组，以寄宿中心总的支出费用为目标，以每个组的人数、男女不混住、新分的组之间不共寄等为约束，建立0-1线性规划模型（见7.1.3模型Ⅲ）。由于10个团队中没有给出哪个团队不愿与其他团队共寄，而总的情况种类
4、又很多，我们在模型求解中列举了有1个团队、有5个团队不与其他团队共寄的两种情况。结果解出最优支出费用为64050美元，最少寄宿家庭数为169个（具体结果见7.2.2）。然后又运用贪心算法的思想编写程序，对模型的求解进行检验。关键词：0-1整数规划贪心算法运输模型29一．问题重述暑期将致，北京“常青藤”文化旅行社国际部与美国HomestayCenter联合为中学生打造了一个美国文化之旅的夏令营活动。此活动主要集中在素有“美国经济之都”之称的纽约地区，通过走访考察常青藤名校，深度了解普林斯顿、耶鲁、哈佛、麻省理工等名校录取标准和教学理念，感受中美教育文
5、化的差异。同时，走进美国寄宿家庭，通过朝夕相处，接受纯正美式英语的熏陶，迅速提高英语听力及口语交流水平。通过夏令营，亲身体验美国本土生活，深度感受美国社会经济文化，让年青的中学生们在激动不已的同时，开始重新设计充满挑战的未来。纽约片区的寄宿家庭通过向寄宿中心（HomestayCenter）提出申请，提交接受学生床位数，学生性别要求等相关信息。寄宿中心审核通过，便获得接收寄宿学生的资格。寄宿家庭对寄宿学生无性别要求的，男生女生均可安排，但不能男女生混住。现在就所给的数据解决以下问题：1.现有一组男生30人，女生40人的旅行团队，计划在ID为1~30的
6、家庭中进行安排。请你建模为寄宿中心做出寄宿家庭接收学生的方案。2.事实上，寄宿家庭提供的是有偿服务，每安排一位学生入住，寄宿中心就要向寄宿家庭支付100美元。但如果入住的学生少于其提供的床位，则每床加收20美元的空床费；另外，根据联邦法律，只要寄宿家庭提供了寄宿服务，无论入住人员多少，都要交税50美元，这项费用也由寄宿中心承担。请更新你的模型，做出寄宿家庭接收学生方案，使支出费用最小。3.在寄宿家庭分配环节中，总有些团队，如来自一个家庭，一个学校等，不希望与别的团队共寄一檐。现在寄宿中心今年夏天共有10个团队，其成员结构详见所给数据。请你为寄宿中心
7、做出最优的寄宿方案，并求出最小的支出费用。二．问题分析本题主要在三种不同情况下，研究寄宿中心做出合理的寄宿方案选择问题。联系实际，寄宿中心做出寄宿家庭接收学生的方案主要考虑的因素包括：各家庭提供的床位数，学生性别，所需要的寄宿家庭数，是否愿意与别的团队共寄，支出费用等因素。在满足学生的居住要求的前提下，主要依据支出费用和寄宿家庭数，来确定出最佳的寄宿方案。在仅考虑完成寄宿安排方案的情况下，首先，需要对题目给出的寄宿家庭资源的ID为1～30号的家庭进行性别要求分类，与每个家庭的床位数对应。然后，主要考虑男女不能混住、寄宿家庭的性别要求、床位数，将30
8、个男生、40个女生分配到30个寄宿家庭。并考虑以所需寄宿家庭的数目为主要目标，建立最优化模型确定可供寄宿中心选择的寄宿方案
