寄宿家庭安排方案建模论文.doc

寄宿家庭安排方案目录摘要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 结果10八模型的评价、改进及推广108.1模型的评价108.2模型的改进及推广11九参考文献11附录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美元的空床费。问题二要求总的支出最少，问题三要求费用最少的同时保障同一个团队的学生住到一起，两者都必须避免男女混住。针对问题二和三的费用目标函数是相同的，在求解问题时，我们可以先把所有家庭按对入住学生的性别要求分为三类，每一类的每一个家庭都设立一个相应变量，求解时先不考虑男女与团队问题，求出费用最少的分配方案。这时，只要按照以上方案进行分配成本都不再变化，此时我们再考虑男女与团队问题，按照男女不能混住的原则，先安排完明确要求入住学生性别的家庭，后安排对性别无要求的家庭可得到问题二的最优分配方案。若同时把来自相同团队的学生安排到同一个家庭，就可以得到问题三的分配方案。由于安排的不同学生所需成本是相同的，则对于学生、家庭、主办方三者来说都有不同的方案。但各个方案的成本是相同的，因此在下面的讨论中我们不追求唯一的方案，也不列出所有可行方案。三模型假设 1、学生除性别、团队信息外不再加以区分，团队除团队号外不加以区分，家庭除ID、床位数、性别要求外不加以区分；2、不考虑学生、家庭、团队在夏利营活动中的各种变故导致的成本、方案变化；3、不考虑学生、家庭、团队的特殊要求，如有残疾学生等。四符号说明 符号解释说明第家对性别没有要求的家庭拥有的床位数第家性别要求为男性的家庭拥有的床位数第家性别要求为女性的家庭拥有的床位数第家对性别没有要求的家庭入住人数第家性别要求为男性的家庭入住人数第家性别要求为女性的家庭入住人数所有性别要求为男性的家庭拥有的总床位数所有性别要求为女性的家庭拥有的总床位数该团队总的男性数该团队总的女性数该团队总人数取和中的较小者取和中的较小者五简单人员分配方案5.1 以寄宿中心便于管理为目的的模型建立与求解5.1.1问题分析及模型建立通过统计在ID为130的家庭对寄宿学生无性别要求的有16家，要求只住男生的有6家，要求只住女生的有8家，对此我们先对这些不同要求的家庭分类编号（见附录一）。考虑到要使寄宿中心便于管理，以及减轻日后的回访工作量，我们可以将该团队70人分配到更少的家庭，以此作为模型的优化目标（为表示有多少家庭住人，我们用/（+0.0001）表示，即只要不等于0，则表示该家庭有住人，计数为1，最后只要求和最小，便表示入住家庭最少）。为使模型简化，在分配时暂不考虑性别因素，在床位分配好后在将性别考虑在内，再做具体分配。建立模型为：模型一：其中: ai表示第家对性别没有要求的家庭拥有的床位数；bj表示第家性别要求为男性的家庭拥有的床位数；ck表示第家性别要求为女性的家庭拥有的床位数；Ai表示第家对性别没有要求的家庭入住人数；Bj表示第家性别要求为男性的家庭入住人数；Ck表示第家性别要求为女性的家庭入住人数；b表示所有性别要求为男性的家庭拥有的总床位数；c表示所有性别要求为女性的家庭拥有的总床位数；M表示该团队总的男性数；F表示该团队总的女性数；Z表示该团队总人数；5.1.2模型求解使用Lingo软件编程求解（程序见附录四）：得到结果之后按照男女不能混住的原则，先安排完明确要求男或女入住的家庭，其他人可安排到对性别没有要求的家庭入住分配方案为：表1 以寄宿中心便于管理为目的分配方案表ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别1300 1652522303117120 34242183032431311930325414120200 6310 2142427323222200 8414123100 9303124404210301225100 11404126414112303 27515113323228424214220 29303215200 30100 入住家庭数为：205.2 以增多团队人员锻炼口语时间为目的的分配方案建立 在5.1中，我们是以方便寄宿中心出发，但若从寄宿人员方向出发，为使得团队人员可以得到更多的锻炼口语以及了解美国文化的时间，我们可以将成员分配到更多的家庭，并且保证每个家庭分到的成员尽量少。通过统计，共有30个家庭提供寄宿服务，该团队共有70人，男生30人，女生40人。要使成员分配到更多的家庭，便要将这30个家庭全部分配寄宿人员，同时保证每个家庭分到的成员尽量少即可，此方法有很多分配方案，我们给出其中一种，作为参考：表2 以增多团队人员锻炼口语时间为目的的分配方案表ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别130211652232302117121234223183032431211930325413120202263121214223ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别732222220228413123102293021244032103021251022114031264121123021275131133222284223142222293022152021301022六最优化支出的寄宿方案6.1问题分析在问题二中，我们的目标是求出成本最少并且满足一定约束的分配方案，由于人是不可分割的整体，所以将该问题归结为非线性整数规划问题。为了方便讨论，我们将所有家庭分为三类：要求男生入住的；要求女生入住的；对性别无要求的。首先不考虑男女性别，建立整数规划模型求出成本最少的分配方案。然后，由于在以上成本最少的分配方案中无论怎么安排入住人员成本支出都不再变化，所以这时只需考虑男女分配分配就可以了。按照男女不能混住的原则，先安排完明确要求男或女入住的家庭，其他人可安排到对性别没有要求的家庭入住。6.2模型建立将30个家庭分为三类（见附录一）A、B、C，按ID排序。成本函数中包括固定的每人100美元，共7000美元；每使用一个房间上税50美元；如果使用的房间有空床则每床支付20美元。约束包括：每个家庭分配的人数不大于他们所要求的人数；B类家庭分配的总人数不大于他们提供的床位数之和与男生人数中较小的那个；C类家庭分配的总人数不大于他们提供的床位数之和与女生人数中较小的那个。据此建立模型如下：模型二：其中: ai表示第家对性别没有要求的家庭拥有的床位数；bj表示第家性别要求为男性的家庭拥有的床位数；ck表示第家性别要求为女性的家庭拥有的床位数；Ai表示第家对性别没有要求的家庭入住人数；Bj表示第家性别要求为男性的家庭入住人数；Ck表示第家性别要求为女性的家庭入住人数；b表示所有性别要求为男性的家庭拥有的总床位数；c表示所有性别要求为女性的家庭拥有的总床位数；M表示该团队总的男性数；F表示该团队总的女性数；Z表示该团队总人数；6.3模型求解该问题是一个30变量的非线性整数规划问题，可以使用Lingo来求解（见附录五）。得到结果之后按照男女不能混住的原则，先安排完明确要求男或女入住的家庭，其他人可安排到对性别没有要求的家庭入住。结果如下表：表3 最优化支出寄宿方案ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别1303216520230321712034242183032431311930325414120200631312142427323222200841412310093032244042103031251001140412641411230312751211332322842421422029303215200301006.4结果修正由于软件的求解方法与环境等原因，发现得出的结果还可以进一步改进，比如结果中三个家庭（均有三个床位）都住满了，则可以把9个学生安排到另外两个有4个和5个床位的家庭中，这样就可以节省50美元；又比如原来住可以5个人的却只住了2个人的家庭，可以把另一个住三个人的家庭中的学生分配过来，这样既节省了空床费又可以少缴税。研究表格我们发现这种情况在Lingo得出的结果中是比较少见的，改进分配方案可以使成本从8110美元下降到8000美元，具体分配方案见下表：表4 改进后的寄宿方案ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别130321652023032171203424218303243131193032541412020063131214242732322220084141231009303224404210303125100ID号床位数性别要求安排人数入住性别ID号床位数性别要求安排人数入住性别114041264141123001275151133232284242142202930321520030100七10个团队最优支出分配方案7.1 问题分析 对于10个团队，我们可以暂不考虑团队因素，将其看作一个整体，同样按照第一问与第二问，将数据分类编号（见附录二），再按照模型一得出支出最少的最优分配。利用lingo软件求解后，再考虑团队因素，将同一团队人员分配在同一家庭，以此得到最优分配方案。7.2 结果 利用lingo软件求解（程序见附录六），得出结果后，考虑团队因素，将同一团队人员分配在同一家庭。得出寄宿人员分配表（附录三），最少支出为：64050美元。八模型的评价、改进及推广8.1模型的评价对于模型一，我们是在不考虑寄宿中心花费，以方便寄宿中心管理为目标建立的。对于这一整数规划模型，可以很方便的用lingo软件求解。对于模型二，我们在模型一的基础上加以改进，建立了以最少花费为目的的整数规划模型，该模型简单，便于理解。但求出的最优结果与实际有少许偏差，但经过数据修正后，结果比较理想。这两个模型解决了简单的人员分配问题以及最优支出分配方案的问题，经过改进后，可以很方便的解决一些类似实际问题。8.2模型的改进及推广 我们所建立的模型只能解决寄宿中心花费最少的问题，但是没有考虑到寄宿人员的一些实际问题，比如：寄宿人员之间有互相认识的，希望住在一起。还有一些特殊人员的安排，比如残疾人、心脏病患者等。同时还要考虑到一些家庭对寄宿人员的一些特殊要求。从这几个方面出发，对模型加以改进，模型将会更加完善，将会更好的解决实际问题。九参考文献1 刘琼荪，数学实验，北京：高等教育出版社，2004年。2 谢金星、薛毅，优化建模与 LINDO/LINGO 软件，清华大学出版社，2005年3 赖炎连，贺国平，最优化方法，北京：清华大学出版社，2008年。4 郭 科，理工数学实验，北京：高等教育出版社，2003年5 施光燕，董加礼，最优化方法，高等教育出版社 1999年6 姜启源，数学模型(第3版)，北京：高等教育出版社 ,1999年7 叶其孝，数学建模（1-4），北京：高等教育出版社 ,2000年附录附录一(家庭分类编号表1)：编号ID床位数性别要求编号ID床位数性别要求a1130a163010a2230b1431a3930b2541a41030b3631a51140b4841a61230b52641a71520b62751a81830c1342a91930c2732a102020c31332a112220c41422a122310c51652a132440c61712a142510c72142a152930c82842附录二(家庭分类编号表2)：编号ID床位数性别要求编号ID床位数性别要求编号ID床位数性别要求a1130b1431c1342a2230b2541c2732a3930b3631c31332a41030b4841c41422a51140b52641c51652a61230b62751c61712a71520b73121c72142a81830b83731c82842a91930b93931c93232a102020b104051c103442a112220b114421c113532a122310b124731c124232a132440b135051c134642a142510b145311c144832a152930b155421c154932a163010b165721c165132a173320b176031c175252a183650b186111c185522编号ID床位数性别要求编号ID床位数性别要求编号ID床位数性别要求a193830b196241c195632a204150b206741c205852a214350b217031c215922a224530b227131c226322a236520b237641c236422a246620b248151c247312a256840b258431c257552a266920b268651c267852a277250b279121c277912a287450b289411c288042a297710b2910011c298922a308230b3010331c309012a318340b3110431c319632a328520b3210721c329852a338740b3311121c339942a348830b3411241c3410252a359230b3511931c3510512a369310b3612431c3610622a379540b3712521c3710942a389710b3812921c3811022a3910130b3913021c3911532a4010830b4013531c4012122a4111340b4113611c4112312a4211440b4213921c4212742a4311620b4315151c4312822a4411710b4415241c4413112a4511850b4515321c4514132a4612020b4615741c4614252a4712250b4716111c4714322a4812640b4816221c4814452a4913250b4916531c4914532a5013330b5016621c5014632a5113430b5116721c5114722a5213730b5217021c5214822a5313840b5317731c5315012a5414030b5417841c5415642a5514950b5518441c5515832a5615450b5618711c5615952a5715510b5718931c5716342a5816040b5819321c5816942a5916420b5919641c5917132编号ID床位数性别要求编号ID床位数性别要求编号ID床位数性别要求a6016820b6019931c6017232a6117520c6117322a6217930c6217432a6318010c6317632a6418650c6418132a6518820c6518242a6619230c6618322a6719740c6718532c6819032c6919122c7019432c7119522c7219832c7320012附录三（10个团队入住人员分配表）：ID号床位数性别要求安排人数入住性别团队号ID号床位数性别要求安排人数入住性别团队号1303261013032823032610252524342421103313144313111043131454141110512063131110622224732322107212148414121083032893032610942424103032611022224114042611121214123032611241414133232211340429142222211440429152022611532324165252211620229171201171001830326118505291930326119313152020226120202210214242112122224222021712250529ID号床位数性别要求安排人数入住性别团队号ID号床位数性别要求安排人数入住性别团队号2310012312024404171243131625100125212152641412126404292751512127424242842422128222242930327129212163010013021031212111311203232322132505293320217133303293442422134303210353232213531316365051713611037313121373032103830317138404210393131213921040515121403032104150517141323244232322142525244350517143222244421212144525244530317145323244642422146323244731313147220483232214822049323221495052105051513150120513232315151516525252315241416531101532121654212131545051105522223155100563232315642425572121315741416585252315832325592222315952524603131316040411061110161110ID号床位数性别要求安排人数入住性别团队号ID号床位数性别要求安排人数入住性别团队号62414121622121663222231634242564222231642022106520016531316662021716621216674141316721216684041716820211069202171694242570313141702121107131314171323257250517172323257312017322074505171743232575525231752021107641413176323267710017731316785252317841411079120179303110804242318010081515141813232