寄宿家庭分配问题.doc

目录 摘要 2 一．问题重述 3 二．问题分析 3 三．模型假设 3 四．符号说明 4 五．简单人员分配方案 4 5.1 以寄宿中心便于管理为目的的模型建立与求解 4 5.1.1问题分析及模型建立 4 5.1.2模型求解 5 5.2 以增多团队人员锻炼口语时间为目的的分配方案建立 6 六．最优化支出的寄宿方案 7 6.1问题分析 7 6.2模型建立 7 6.3模型求解 8 6.4结果修正 9 七．10个团队最优支出分配方案 10 7.1 问题分析 10 7.2 模型建立 10 7.3 模型求解 11 八．模型的评价、改进及推广 11 8.1模型的评价 11 8.2模型的改进及推广 11 九．参考文献 12 附录 12 摘要 通过对问题的分析，基本可以确定该问题为整数规划问题，围绕不同的题设我们建立了不同的目标函数与约束条件，使用lingo编程求解，最后对结果进行改进与微调得到最优分配方案。 对于问题一，题目并没有给出明确的优化方向，结果必然是多种多样的。我们可以从寄宿中心便于管理方向出发，将寄宿人员分配到更少的家庭。但如果从寄宿人员要有更多的时间和寄宿家庭交流，锻炼口语，我们又可以将寄宿人员分配到更多的家庭。于是我们考虑使家庭数最少与最多两个方向建立整数规划模型。为使模型简化，在分配时暂不考虑性别因素，在床位分配好后再将性别考虑在内，做具体分配。利用Lingo软件编程求解，得到最少家庭数为20个，最多的家庭数为30个。 在问题二中，首先将所有家庭分为三类：1)对入住学生性别无要求的；2)要求男生入住的；3)要求女生入住的。对每类的每个家庭都设立一个相应变量。我们建立的成本函数包括三个部分：1)固定的每人100美元寄宿费；2)每使用一个房间上税50美元；3)如果使用的房间有空床则每床支付20美元。约束条件包括：1)男女不能混住；2)每个家庭分配的学生数不多于他们所提供的床位数；3)分配给要求男生入住家庭的学生数不大于提供的床位总数与实际男生数两者中的较小者。女生类也有这一要求，模型的优化目标是成本支出最少。在求解时我们先不考虑男女问题，得出支出最少方案。由于此时无论怎么安排支出都不再变化，所以我们可以按照男女不能混住的原则，先安排完明确要求入住学生性别的家庭，后安排对性别无要求的家庭就可以得到合适分配方案，对结果进行修正后得到最优方案。Lingo得到的最优解为：8110美元，经过修正后的结果为：8000美元。 对于问题三，我们建立目标函数与约束函数的原理、形式均与问题二的相似，变量由30个增加到了200个。最后在得到支出最少的方案约束下安排学生，安排的原则除问题二中的基本原则外，还需注意同一团队的学生应安排到一起。得到的最少支出为：64050美元。 由于学生除性别、团队信息外是可以不加区分的，若有两个家庭都提供3个床位，且都要求男生入住，则它们也是可以不加区分的。所以对于学生、家庭、主办方三者来说都有多种选择方案，但各个方案的成本是相同的，因此在下面的讨论中我们不追求唯一的方案，也不列出所有的可行方案。 对于此次建立的模型，我们提出了一些合理性的假设，使模型简化，所建立的整数规划模型，有明确的优化目标，使用Lingo软件可以很方便的解决。 关键词： 寄宿安排 非线性整数规划 Lingo 成本优化 结果修正 一．问题重述 在暑期，北京“常青藤”文化旅行社国际部将与美国Homestay Center联合开展一个美国文化之旅的夏令营活动，让学生们通过本次夏令营走进美国寄宿家庭，亲身体验美国本土生活，感受美国社会经济文化。本文需针对寄宿家庭和参加夏令营的人员供求关系做相关的研究工作，从而建立相关优化模型为寄宿寄宿家庭 二．问题分析 对于该规划问题，一定数量的学生可以有多种不同的分配方案，按照不同的题设要求可以建立不同的目标函数与约束函数，但其本质都是整数规划问题。在本题中我们首先构建成本函数，包括三个部分：1）每个学生固定的寄宿费100美元/人；2）安排有学生的家庭以家庭为单位上缴的税费50美元/户；3）如果住有学生的家庭有空床，则每床收20美元的空床费。问题二要求总的支出最少，问题三要求费用最少的同时保障同一个团队的学生住到一起，两者都必须避免男女混住。针对问题二和三的费用目标函数是相同的，在求解问题时，我们可以先把所有家庭按对入住学生的性别要求分为三类，每一类的每一个家庭都设立一个相应变量，求解时先不考虑男女与团队问题，求出费用最少的分配方案。这时，只要按照以上方案进行分配成本都不再变化，此时我们再考虑男女与团队问题，按照男女不能混住的原则，先安排完明确要求入住学生性别的家庭，后安排对性别无要求的家庭可得到问题二的最优分配方案。若同时把来自相同团队的学生安排到同一个家庭，就可以得到问题三的分配方案。由于安