寄宿家庭分配问题

《寄宿家庭分配问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、目录摘要2一．问题重述3二．问题分析3三．模型假设3四．符号说明4五．简单人员分配方案45.1以寄宿中心便于管理为目的的模型建立与求解45.1.1问题分析及模型建立45.1.2模型求解55.2以增多团队人员锻炼口语时间为目的的分配方案建立6六．最优化支出的寄宿方案76.1问题分析76.2模型建立76.3模型求解86.4结果修正9七．10个团队最优支出分配方案107.1问题分析107.2模型建立107.3模型求解11八．模型的评价、改进及推广118.1模型的评价118.2模型的改进及推广11九．参考文献12附录121

2、8摘要通过对问题的分析，基本可以确定该问题为整数规划问题，围绕不同的题设我们建立了不同的目标函数与约束条件，使用lingo编程求解，最后对结果进行改进与微调得到最优分配方案。对于问题一，题目并没有给出明确的优化方向，结果必然是多种多样的。我们可以从寄宿中心便于管理方向出发，将寄宿人员分配到更少的家庭。但如果从寄宿人员要有更多的时间和寄宿家庭交流，锻炼口语，我们又可以将寄宿人员分配到更多的家庭。于是我们考虑使家庭数最少与最多两个方向建立整数规划模型。为使模型简化，在分配时暂不考虑性别因素，在床位分配好后再将性别考虑在

3、内，做具体分配。利用Lingo软件编程求解，得到最少家庭数为20个，最多的家庭数为30个。在问题二中，首先将所有家庭分为三类：1)对入住学生性别无要求的；2)要求男生入住的；3)要求女生入住的。对每类的每个家庭都设立一个相应变量。我们建立的成本函数包括三个部分：1)固定的每人100美元寄宿费；2)每使用一个房间上税50美元；3)如果使用的房间有空床则每床支付20美元。约束条件包括：1)男女不能混住；2)每个家庭分配的学生数不多于他们所提供的床位数；3)分配给要求男生入住家庭的学生数不大于提供的床位总数与实际男生数两

4、者中的较小者。女生类也有这一要求，模型的优化目标是成本支出最少。在求解时我们先不考虑男女问题，得出支出最少方案。由于此时无论怎么安排支出都不再变化，所以我们可以按照男女不能混住的原则，先安排完明确要求入住学生性别的家庭，后安排对性别无要求的家庭就可以得到合适分配方案，对结果进行修正后得到最优方案。Lingo得到的最优解为：8110美元，经过修正后的结果为：8000美元。对于问题三，我们建立目标函数与约束函数的原理、形式均与问题二的相似，变量由30个增加到了200个。最后在得到支出最少的方案约束下安排学生，安排的原则

5、除问题二中的基本原则外，还需注意同一团队的学生应安排到一起。得到的最少支出为：64050美元。由于学生除性别、团队信息外是可以不加区分的，若有两个家庭都提供3个床位，且都要求男生入住，则它们也是可以不加区分的。所以对于学生、家庭、主办方三者来说都有多种选择方案，但各个方案的成本是相同的，因此在下面的讨论中我们不追求唯一的方案，也不列出所有的可行方案。对于此次建立的模型，我们提出了一些合理性的假设，使模型简化，所建立的整数规划模型，有明确的优化目标，使用Lingo软件可以很方便的解决。关键词：寄宿安排非线性整数规划L

6、ingo成本优化结果修正18一．问题重述在暑期，北京“常青藤”文化旅行社国际部将与美国HomestayCenter联合开展一个美国文化之旅的夏令营活动，让学生们通过本次夏令营走进美国寄宿家庭，亲身体验美国本土生活，感受美国社会经济文化。本文需针对寄宿家庭和参加夏令营的人员供求关系做相关的研究工作，从而建立相关优化模型为寄宿中心做出寄宿家庭接收学生的方案，并达到节省资金的目的。而建立该模型我们要综合各方面的因素才能使模型合理化。二．问题分析对于该规划问题，一定数量的学生可以有多种不同的分配方案，按照不同的题设要求可以

7、建立不同的目标函数与约束函数，但其本质都是整数规划问题。在本题中我们首先构建成本函数，包括三个部分：1）每个学生固定的寄宿费100美元/人；2）安排有学生的家庭以家庭为单位上缴的税费50美元/户；3）如果住有学生的家庭有空床，则每床收20美元的空床费。问题二要求总的支出最少，问题三要求费用最少的同时保障同一个团队的学生住到一起，两者都必须避免男女混住。针对问题二和三的费用目标函数是相同的，在求解问题时，我们可以先把所有家庭按对入住学生的性别要求分为三类，每一类的每一个家庭都设立一个相应变量，求解时先不考虑男女与团队

8、问题，求出费用最少的分配方案。这时，只要按照以上方案进行分配成本都不再变化，此时我们再考虑男女与团队问题，按照男女不能混住的原则，先安排完明确要求入住学生性别的家庭，后安排对性别无要求的家庭可得到问题二的最优分配方案。若同时把来自相同团队的学生安排到同一个家庭，就可以得到问题三的分配方案。由于安排的不同学生所需成本是相同的，则对于学生、家庭、主办方三者来说都