数学建模校内模拟竞赛论文
论文题目：寄宿家庭安排方案
2012717
f寄宿家庭安排方案
【摘要】
本文将寄宿家庭安排抽象为运输问题的模型，采用01整数规划表述。把所给的数据进行有规律的分类排序，根据寄宿中心需要建立不同目标的01整数规划模型，运用Li
go软件求解，并运用贪心算法检验模型的求解。
第一问，我们先对30个寄宿家庭按照性别要求、床位数进行排序，使数据有一定的规律，方便编程和结果分析。以所需要的总寄宿家庭数为目标，结合人数、性别要求、男女不混住等约束，建立01整数规划模型（见513模型Ⅰ），完成把2个组的所有学生分配到30个家庭的要求。用Li
go软件对此模型求解，得到最优方案，最少需要20个寄宿家庭，具体的方案如下（列举一种，其他结果见522）：
男生入住的家庭女生入住的家庭
寄宿家庭ID号
45811152426271237910121316182128
针对此问题，我们又运用了贪心算法进行求解，提供与Li
go求解的对照，以到达检验此模型的求解。
第二问，由于问题的框架是在问题一的基础上给出了具体的各种费用，所以我们对问题一的模型做了更新，其目标变为寄宿中心总的支出费用最少，寄宿家庭数变为200个。同样的思路，建立01整数规划模型（见613模型Ⅱ），用Li
go软件对此模型进行求解。求得的最优支出费用为7700美元，选择的家庭最少为14个。具体方案如下（列举一种，其他结果见622）：
男生入住的家庭女生入住的家庭
寄宿家庭ID号
274350818612216525898102142144159
第三问，考虑到10个团队中有一些团队不愿与其他团队共寄一檐，我们可以把这10个团队按照是否与其他团队共寄原则从新分组，以寄宿中心总的支出费用为目标，以每个组的人数、男女不混住、新分的组之间不共寄等为约束，建立01线性规划模型（见713模型Ⅲ）。
由于10个团队中没有给出哪个团队不愿与其他团队共寄，而总的情况种类又很多，我们在模型求解中列举了有1个团队、有5个团队不与其他团队共寄的两种情况。结果解出最优支出费用为64050美元，最少寄宿家庭数为169个（具体结果见722）。然后又运用贪心算法的思想编写Matlab程序，对模型的求解进行检验。
关键词：01整数规划贪心算法运输模型
1
f一．问题重述
暑期将致，北京“常青藤”文化旅行社国际部与美国HomestayCe
ter联合为中学生打造了一个美国文化之旅的夏令营活动。此活动主要集中在素有“美国经济之都”之称的纽约地区，通过走访考察常r