寄宿家庭安排方案.doc

《寄宿家庭安排方案.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、4彥萸李数学建模校内模拟竞赛论文论文题目：寄宿家庭安排方案2012-7-17寄宿家庭安排方案【摘要】本文将寄宿家庭安排抽象为运输问题的模型，采用0-1整数规划表述。把所给的数据进行有规律的分类排序，根据寄宿屮心需要建立不同n标的0-1整数规划模型，运用软件求解，并运用贪心算法检验模型的求解。第一问，我们先对30个寄宿家庭按照性别要求、床位数进行排序，使数据有一定的规律，方便编程和结果分析。以所需要的总寄宿家庭数为H标，结合人数、性别要求、男女不混住等约束，建立0-1整数规划模型（见5.1.3模型I）,完成把2个组的所有学生分配到30个家庭的要求。用软

2、件对此模型求解，得到最优方案，最少需要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针对此问题，我们又运用了贪心算法进行求解，提供与厶加go求解的对照，以到达检验此模型的求解。第二问，由于问题的框架是在问题一的基础丄给出了具体的各种费用，所以我们对问题一的模型做了更新，其H标变为寄宿屮心总的支出费用最少，寄宿家庭数变为200个。同样的思路，建立0-1整数规划模型（见6.13模型II）,用

3、乙加go软件对此模型进行求解。求得的最优支出费用为7700美元，选择的家庭最少为14个。具体方案如下（列举一种，其他结果见6.2.2）：'寄宿家庭ID号男生入住的家庭27,43,50,81,86,122女生入住的家庭16,52,58,98,102,142,144,159第三问，考虑到10个团队中有一•些团队不愿与其他团队共寄一•檐，我们可以把这10个团队按照是否与其他团队共寄原则从新分组，以寄宿小心总的支出费用为H标，以每个组的人数、男女不混住、新分的组之间不共寄等为约束，建立0-1线性规划模型（见7.1.3模型III）。由于10个团队屮没有给出哪个

4、团队不愿与其他团队共寄，而总的情况种类又很多,我们在模型求解屮列举了有1个团队、有5个团队不与其他团队共寄的两种情况。结果解出最优支出费用为64050美元，最少寄宿家庭数为169个（具体结果见7.2.2）。然后又运用贪心算法的思想编写Matlab程序，对模型的求解进行检验。关键词：0-1整数规划贪心算法运输模型一•问题重述暑期将致，北京“常青藤”文化旅行社国际部与美国HomestayCenter联合为中学生打造了一个美国文化之旅的夏令营活动。此活动主要集小在素有“美国经济之都”之称的纽约地区，通过走访考察常青藤名校，深度了解普林斯顿、耶鲁、哈佛、麻省

5、理工等名校录取标准和教学理念，感受屮美教育文化的差异。同时，走进美国寄宿家庭，通过朝夕相处，接受纯正美式英语的熏陶，迅速提高英语听力及口语交流水平。通过夏令营，亲身体验美国本土生活，深度感受美国社会经济文化，让年青的屮学生们在激动不已的同时，开始重新设计充满挑战的未来。纽约片区的寄宿家庭通过向寄宿屮心(HomestayCenter)提岀申请，提交接受学生床位数，学生性别要求等相关信息。寄宿屮心审核通过，便获得接收寄宿学生的资格。寄宿家庭对寄宿学生无性别要求的，男生女生均可安排，但不能男女生混住。现在就所给的数据解决以下问题：1.现有一组男生30人，女

6、生40人的旅行团队，计划在ID为「30的家庭中进行安排。请你建模为寄宿中心做出寄宿家庭接收学生的方案。2.事实上，寄宿家庭提供的是有偿服务，每安排一位学生入住，寄宿中心就要向寄宿家庭支付100美元。但如果入住的学生少于其提供的床位，则每床加收20美元的空床费；另外，根据联邦法律，只要寄宿家庭提供了寄宿服务，无论入住人员多少，都要交税50美元，这项费用也由寄宿屮心承担。请更新你的模型，做出寄宿家庭接收学生方案，使支出费用最小。3•在寄宿家庭分配环节屮，总有些团队，如来自一个家庭，一个学校等，不希望与别的团队共寄一檐。现在寄宿屮心今年夏天共有10个团队，

7、其成员结构详见所给数据。请你为寄宿中心做出最优的寄宿方案，并求出最小的支出费用。二•问题分析本题主要在三种不同情况下，研究寄宿小心做出合理的寄宿方案选择问题。联系实际，寄宿屮心做出寄宿家庭接收学生的方案主要考虑的因素包括：各家庭提供的床位数,学生性别，所需要的寄宿家庭数，是否愿意与别的团队共寄，支出费用等因素。在满足学牛的居住要求的前提下，主要依据支出费用和寄宿家庭数，来确定出最佳的寄宿方案。在仅考虑完成寄宿安排方案的情况下，首先，需要对题H给出的寄宿家庭资源的ID为1〜30号的家庭进行性别要求分类，与每个家庭的床位数对应。然后，主要考虑男女不能混住

8、、寄宿家庭的性别要求、床位数，将30个男生、40个女生分配到30个寄宿家庭。并考虑以所需寄宿家庭的数F1为主