寄宿家庭分配問題

1、目錄摘要2一問題重述3二問題分析3三模型假設(shè)3四符號說明4五簡單人員分配方案45.1 以寄宿中心便于管理為目的的模型建立與求解4問題分析及模型建立4模型求解55.2 以增多團(tuán)隊人員鍛煉口語時間為目的的分配方案建立6六最優(yōu)化支出的寄宿方案76.1問題分析76.2模型建立76.3模型求解86.4結(jié)果修正9七10個團(tuán)隊最優(yōu)支出分配方案107.1 問題分析107.2 模型建立107.3 模型求解11八模型的評價、改進(jìn)及推廣118.1模型的評價118.2模型的改進(jìn)及推廣11九參考文獻(xiàn)12附錄12摘要通過對問題的分析，基本可以確定該問題為整數(shù)規(guī)劃問題，圍繞不同的題設(shè)我們建立了不同的目標(biāo)函數(shù)與約束條件，使用

2、lingo編程求解，最后對結(jié)果進(jìn)行改進(jìn)與微調(diào)得到最優(yōu)分配方案。對于問題一，題目并沒有給出明確的優(yōu)化方向，結(jié)果必然是多種多樣的。我們可以從寄宿中心便于管理方向出發(fā)，將寄宿人員分配到更少的家庭。但如果從寄宿人員要有更多的時間和寄宿家庭交流，鍛煉口語，我們又可以將寄宿人員分配到更多的家庭。于是我們考慮使家庭數(shù)最少與最多兩個方向建立整數(shù)規(guī)劃模型。為使模型簡化，在分配時暫不考慮性別因素，在床位分配好后再將性別考慮在內(nèi)，做具體分配。利用Lingo軟件編程求解，得到最少家庭數(shù)為20個，最多的家庭數(shù)為30個。在問題二中，首先將所有家庭分為三類：1)對入住學(xué)生性別無要求的；2)要求男生入住的；3)要求女生入住的

3、。對每類的每個家庭都設(shè)立一個相應(yīng)變量。我們建立的成本函數(shù)包括三個部分：1)固定的每人100美元寄宿費；2)每使用一個房間上稅50美元；3)如果使用的房間有空床則每床支付20美元。約束條件包括：1)男女不能混??；2)每個家庭分配的學(xué)生數(shù)不多于他們所提供的床位數(shù)；3)分配給要求男生入住家庭的學(xué)生數(shù)不大于提供的床位總數(shù)與實際男生數(shù)兩者中的較小者。女生類也有這一要求，模型的優(yōu)化目標(biāo)是成本支出最少。在求解時我們先不考慮男女問題，得出支出最少方案。由于此時無論怎么安排支出都不再變化，所以我們可以按照男女不能混住的原則，先安排完明確要求入住學(xué)生性別的家庭，后安排對性別無要求的家庭就可以得到合適分配方案，對結(jié)

4、果進(jìn)行修正后得到最優(yōu)方案。Lingo得到的最優(yōu)解為：8110美元，經(jīng)過修正后的結(jié)果為：8000美元。對于問題三，我們建立目標(biāo)函數(shù)與約束函數(shù)的原理、形式均與問題二的相似，變量由30個增加到了200個。最后在得到支出最少的方案約束下安排學(xué)生，安排的原則除問題二中的基本原則外，還需注意同一團(tuán)隊的學(xué)生應(yīng)安排到一起。得到的最少支出為：64050美元。由于學(xué)生除性別、團(tuán)隊信息外是可以不加區(qū)分的，若有兩個家庭都提供3個床位，且都要求男生入住，則它們也是可以不加區(qū)分的。所以對于學(xué)生、家庭、主辦方三者來說都有多種選擇方案，但各個方案的成本是相同的，因此在下面的討論中我們不追求唯一的方案，也不列出所有的可行方案。

5、對于此次建立的模型，我們提出了一些合理性的假設(shè)，使模型簡化，所建立的整數(shù)規(guī)劃模型，有明確的優(yōu)化目標(biāo)，使用Lingo軟件可以很方便的解決。關(guān)鍵詞： 寄宿安排 非線性整數(shù)規(guī)劃 Lingo 成本優(yōu)化 結(jié)果修正一問題重述在暑期，北京“常青藤”文化旅行社國際部將與美國Homestay Center聯(lián)合開展一個美國文化之旅的夏令營活動，讓學(xué)生們通過本次夏令營走進(jìn)美國寄宿家庭，親身體驗美國本土生活，感受美國社會經(jīng)濟(jì)文化。本文需針對寄宿家庭和參加夏令營的人員供求關(guān)系做相關(guān)的研究工作，從而建立相關(guān)優(yōu)化模型為寄宿中心做出寄宿家庭接收學(xué)生的方案，并達(dá)到節(jié)省資金的目的。而建立該模型我們要綜合各方面的因素才能使模型合理

6、化。二問題分析對于該規(guī)劃問題，一定數(shù)量的學(xué)生可以有多種不同的分配方案，按照不同的題設(shè)要求可以建立不同的目標(biāo)函數(shù)與約束函數(shù)，但其本質(zhì)都是整數(shù)規(guī)劃問題。在本題中我們首先構(gòu)建成本函數(shù)，包括三個部分：1）每個學(xué)生固定的寄宿費100美元/人；2）安排有學(xué)生的家庭以家庭為單位上繳的稅費50美元/戶；3）如果住有學(xué)生的家庭有空床，則每床收20美元的空床費。問題二要求總的支出最少，問題三要求費用最少的同時保障同一個團(tuán)隊的學(xué)生住到一起，兩者都必須避免男女混住。針對問題二和三的費用目標(biāo)函數(shù)是相同的，在求解問題時，我們可以先把所有家庭按對入住學(xué)生的性別要求分為三類，每一類的每一個家庭都設(shè)立一個相應(yīng)變量，求解時先不考

7、慮男女與團(tuán)隊問題，求出費用最少的分配方案。這時，只要按照以上方案進(jìn)行分配成本都不再變化，此時我們再考慮男女與團(tuán)隊問題，按照男女不能混住的原則，先安排完明確要求入住學(xué)生性別的家庭，后安排對性別無要求的家庭可得到問題二的最優(yōu)分配方案。若同時把來自相同團(tuán)隊的學(xué)生安排到同一個家庭，就可以得到問題三的分配方案。由于安排的不同學(xué)生所需成本是相同的，則對于學(xué)生、家庭、主辦方三者來說都有不同的方案。但各個方案的成本是相同的，因此在下面的討論中我們不追求唯一的方案，也不列出所有可行方案。三模型假設(shè)1、學(xué)生除性別、團(tuán)隊信息外不再加以區(qū)分，團(tuán)隊除團(tuán)隊號外不加以區(qū)分，家庭除ID、床位數(shù)、性別要求外不加以區(qū)分；2、不考

8、慮學(xué)生、家庭、團(tuán)隊在夏利營活動中的各種變故導(dǎo)致的成本、方案變化；3、不考慮學(xué)生、家庭、團(tuán)隊的特殊要求，如有殘疾學(xué)生等。四符號說明符號解釋說明第家對性別沒有要求的家庭擁有的床位數(shù)第家性別要求為男性的家庭擁有的床位數(shù)第家性別要求為女性的家庭擁有的床位數(shù)第家對性別沒有要求的家庭入住人數(shù)第家性別要求為男性的家庭入住人數(shù)第家性別要求為女性的家庭入住人數(shù)所有性別要求為男性的家庭擁有的總床位數(shù)所有性別要求為女性的家庭擁有的總床位數(shù)該團(tuán)隊總的男性數(shù)該團(tuán)隊總的女性數(shù)該團(tuán)隊總?cè)藬?shù)取和中的較小者取和中的較小者五簡單人員分配方案5.1 以寄宿中心便于管理為目的的模型建立與求解問題分析及模型建立通過統(tǒng)計在ID為130的

9、家庭對寄宿學(xué)生無性別要求的有16家，要求只住男生的有6家，要求只住女生的有8家，對此我們先對這些不同要求的家庭分類編號（見附錄一）。考慮到要使寄宿中心便于管理，以及減輕日后的回訪工作量，我們可以將該團(tuán)隊70人分配到更少的家庭，以此作為模型的優(yōu)化目標(biāo)（為表示有多少家庭住人，我們用/（+0.0001）表示，即只要不等于0，則表示該家庭有住人，計數(shù)為1，最后只要求和最小，便表示入住家庭最少）。為使模型簡化，在分配時暫不考慮性別因素，在床位分配好后在將性別考慮在內(nèi)，再做具體分配。建立模型為：模型一：其中: ai表示第家對性別沒有要求的家庭擁有的床位數(shù)；bj表示第家性別要求為男性的家庭擁有的床位數(shù)；ck

10、表示第家性別要求為女性的家庭擁有的床位數(shù)；Ai表示第家對性別沒有要求的家庭入住人數(shù)；Bj表示第家性別要求為男性的家庭入住人數(shù)；Ck表示第家性別要求為女性的家庭入住人數(shù)；b表示所有性別要求為男性的家庭擁有的總床位數(shù)；c表示所有性別要求為女性的家庭擁有的總床位數(shù)；M表示該團(tuán)隊總的男性數(shù)；F表示該團(tuán)隊總的女性數(shù)；Z表示該團(tuán)隊總?cè)藬?shù)；模型求解使用Lingo軟件編程求解（程序見附錄四）：得到結(jié)果之后按照男女不能混住的原則，先安排完明確要求男或女入住的家庭，其他人可安排到對性別沒有要求的家庭入住分配方案為：表1 以寄宿中心便于管理為目的分配方案表ID號床位數(shù)性別要求安排人數(shù)入住性別ID號床位數(shù)性別要求安排

11、人數(shù)入住性別1300 1652522303117120 34242183032431311930325414120200 6310 2142427323222200 8414123100 9303124404210301225100 11404126414112303 27515113323228424214220 29303215200 30100 入住家庭數(shù)為：205.2 以增多團(tuán)隊人員鍛煉口語時間為目的的分配方案建立 在5.1中，我們是以方便寄宿中心出發(fā)，但若從寄宿人員方向出發(fā)，為使得團(tuán)隊人員可以得到更多的鍛煉口語以及了解美國文化的時間，我們可以將成員分配到更多的家庭，并且保證每個家庭分

12、到的成員盡量少。通過統(tǒng)計，共有30個家庭提供寄宿服務(wù)，該團(tuán)隊共有70人，男生30人，女生40人。要使成員分配到更多的家庭，便要將這30個家庭全部分配寄宿人員，同時保證每個家庭分到的成員盡量少即可，此方法有很多分配方案，我們給出其中一種，作為參考：表2 以增多團(tuán)隊人員鍛煉口語時間為目的的分配方案表ID號床位數(shù)性別要求安排人數(shù)入住性別ID號床位數(shù)性別要求安排人數(shù)入住性別130211652232302117121234223183032431211930325413120202263121214223ID號床位數(shù)性別要求安排人數(shù)入住性別ID號床位數(shù)性別要求安排人數(shù)入住性別73222222022841

13、3123102293021244032103021251022114031264121123021275131133222284223142222293022152021301022六最優(yōu)化支出的寄宿方案6.1問題分析在問題二中，我們的目標(biāo)是求出成本最少并且滿足一定約束的分配方案，由于人是不可分割的整體，所以將該問題歸結(jié)為非線性整數(shù)規(guī)劃問題。為了方便討論，我們將所有家庭分為三類：要求男生入住的；要求女生入住的；對性別無要求的。首先不考慮男女性別，建立整數(shù)規(guī)劃模型求出成本最少的分配方案。然后，由于在以上成本最少的分配方案中無論怎么安排入住人員成本支出都不再變化，所以這時只需考慮男女分配分配就可以

14、了。按照男女不能混住的原則，先安排完明確要求男或女入住的家庭，其他人可安排到對性別沒有要求的家庭入住。6.2模型建立將30個家庭分為三類（見附錄一）A、B、C，按ID排序。成本函數(shù)中包括固定的每人100美元，共7000美元；每使用一個房間上稅50美元；如果使用的房間有空床則每床支付20美元。約束包括：每個家庭分配的人數(shù)不大于他們所要求的人數(shù)；B類家庭分配的總?cè)藬?shù)不大于他們提供的床位數(shù)之和與男生人數(shù)中較小的那個；C類家庭分配的總?cè)藬?shù)不大于他們提供的床位數(shù)之和與女生人數(shù)中較小的那個。據(jù)此建立模型如下：模型二：其中: ai表示第家對性別沒有要求的家庭擁有的床位數(shù)；bj表示第家性別要求為男性的家庭擁有

15、的床位數(shù)；ck表示第家性別要求為女性的家庭擁有的床位數(shù)；Ai表示第家對性別沒有要求的家庭入住人數(shù)；Bj表示第家性別要求為男性的家庭入住人數(shù)；Ck表示第家性別要求為女性的家庭入住人數(shù)；b表示所有性別要求為男性的家庭擁有的總床位數(shù)；c表示所有性別要求為女性的家庭擁有的總床位數(shù)；M表示該團(tuán)隊總的男性數(shù)；F表示該團(tuán)隊總的女性數(shù)；Z表示該團(tuán)隊總?cè)藬?shù)；6.3模型求解該問題是一個30變量的非線性整數(shù)規(guī)劃問題，可以使用Lingo來求解（見附錄五）。得到結(jié)果之后按照男女不能混住的原則，先安排完明確要求男或女入住的家庭，其他人可安排到對性別沒有要求的家庭入住。結(jié)果如下表：表3 最優(yōu)化支出寄宿方案ID號床位數(shù)性別要

16、求安排人數(shù)入住性別ID號床位數(shù)性別要求安排人數(shù)入住性別1303216520230321712034242183032431311930325414120200631312142427323222200841412310093032244042103031251001140412641411230312751211332322842421422029303215200301006.4結(jié)果修正由于軟件的求解方法與環(huán)境等原因，發(fā)現(xiàn)得出的結(jié)果還可以進(jìn)一步改進(jìn)，比如結(jié)果中三個家庭（均有三個床位）都住滿了，則可以把9個學(xué)生安排到另外兩個有4個和5個床位的家庭中，這樣就可以節(jié)省50美元；又比如原來住可以5個

17、人的卻只住了2個人的家庭，可以把另一個住三個人的家庭中的學(xué)生分配過來，這樣既節(jié)省了空床費又可以少繳稅。研究表格我們發(fā)現(xiàn)這種情況在Lingo得出的結(jié)果中是比較少見的，改進(jìn)分配方案可以使成本從8110美元下降到8000美元，具體分配方案見下表：表4 改進(jìn)后的寄宿方案ID號床位數(shù)性別要求安排人數(shù)入住性別ID號床位數(shù)性別要求安排人數(shù)入住性別130321652023032171203424218303243131193032541412020063131214242732322220084141231009303224404210303125100ID號床位數(shù)性別要求安排人數(shù)入住性別ID號床位數(shù)性別要求

18、安排人數(shù)入住性別114041264141123001275151133232284242142202930321520030100七10個團(tuán)隊最優(yōu)支出分配方案7.1 問題分析 對于10個團(tuán)隊，我們可以暫不考慮團(tuán)隊因素，將其看作一個整體，同樣按照第一問與第二問，將數(shù)據(jù)分類編號（見附錄二），再按照模型一得出支出最少的最優(yōu)分配。利用lingo軟件求解后，再考慮團(tuán)隊因素，將同一團(tuán)隊人員分配在同一家庭，以此得到最優(yōu)分配方案。7.2 模型建立其中: ai表示第家對性別沒有要求的家庭擁有的床位數(shù)；bj表示第家性別要求為男性的家庭擁有的床位數(shù)；ck表示第家性別要求為女性的家庭擁有的床位數(shù)；Ai表示第家對性別沒

19、有要求的家庭入住人數(shù)；Bj表示第家性別要求為男性的家庭入住人數(shù)；Ck表示第家性別要求為女性的家庭入住人數(shù)；b表示所有性別要求為男性的家庭擁有的總床位數(shù)；c表示所有性別要求為女性的家庭擁有的總床位數(shù)；M表示該團(tuán)隊總的男性數(shù)；F表示該團(tuán)隊總的女性數(shù)；Z表示該團(tuán)隊總?cè)藬?shù)；7.3 模型求解 利用lingo軟件求解（程序見附錄六），得出結(jié)果后，考慮團(tuán)隊因素，將同一團(tuán)隊人員分配在同一家庭。得出寄宿人員分配表（附錄三），最少支出為：64050美元。八模型的評價、改進(jìn)及推廣8.1模型的評價對于模型一，我們是在不考慮寄宿中心花費，以方便寄宿中心管理為目標(biāo)建立的。對于這一整數(shù)規(guī)劃模型，可以很方便的用lingo軟件

20、求解。對于模型二，我們在模型一的基礎(chǔ)上加以改進(jìn)，建立了以最少花費為目的的整數(shù)規(guī)劃模型，該模型簡單，便于理解。但求出的最優(yōu)結(jié)果與實際有少許偏差，但經(jīng)過數(shù)據(jù)修正后，結(jié)果比較理想。這兩個模型解決了簡單的人員分配問題以及最優(yōu)支出分配方案的問題，經(jīng)過改進(jìn)后，可以很方便的解決一些類似實際問題。總的來說，我們的模型雖然需要人工給安排具體地家庭，但是這樣做的優(yōu)點就是模型調(diào)整的空間比較大，可以應(yīng)對某些學(xué)生與家庭的特殊要求或變化。8.2模型的改進(jìn)及推廣 我們所建立的模型是要解決寄宿中心花費最少的問題，現(xiàn)實生活中類似的問題也可以采用這個模型，比如酒店房間安排，學(xué)校宿舍分配等等。如果考慮到寄宿人員的一些實際問題，比如

21、：寄宿人員之間有互相認(rèn)識的，希望住在一起，還有一些特殊人員的安排，比如殘疾人、心臟病患者等。同時還要考慮到一些家庭對寄宿人員的一些特殊要求。從這幾個方面出發(fā)，對模型或結(jié)果加以改進(jìn)，模型將會更加完善，將會更好的解決實際問題。九參考文獻(xiàn)1 劉瓊蓀，數(shù)學(xué)實驗，北京：高等教育出版社，2004年。2 謝金星、薛毅，優(yōu)化建模與 LINDO/LINGO 軟件，清華大學(xué)出版社，2005年3 賴炎連，賀國平，最優(yōu)化方法，北京：清華大學(xué)出版社，2008年。4 郭 科，理工數(shù)學(xué)實驗，北京：高等教育出版社，2003年5 施光燕，董加禮，最優(yōu)化方法，高等教育出版社 1999年6 姜啟源，數(shù)學(xué)模型(第3版)，北京：高等教

22、育出版社 ,1999年7 葉其孝，數(shù)學(xué)建模（1-4），北京：高等教育出版社 ,2000年附錄附錄一(家庭分類編號表1)：編號ID床位數(shù)性別要求編號ID床位數(shù)性別要求a1130a163010a2230b1431a3930b2541編號ID床位數(shù)性別要求編號ID床位數(shù)性別要求a41030b3631a51140b4841a61230b52641a71520b62751a81830c1342a91930c2732a102020c31332a112220c41422a122310c51652a132440c61712a142510c72142a152930c82842附錄二(家庭分類編號表2)：編號ID

23、床位數(shù)性別要求編號ID床位數(shù)性別要求編號ID床位數(shù)性別要求a1130b1431c1342a2230b2541c2732a3930b3631c31332a41030b4841c41422a51140b52641c51652a61230b62751c61712a71520b73121c72142a81830b83731c82842a91930b93931c93232a102020b104051c103442a112220b114421c113532a122310b124731c124232a132440b135051c134642a142510b145311c144832a152930b15542

24、1c154932a163010b165721c165132a173320b176031c175252a183650b186111c185522a193830b196241c195632a204150b206741c205852a214350b217031c215922a224530b227131c226322a236520b237641c236422a246620b248151c247312a256840b258431c257552a266920b268651c267852編號ID床位數(shù)性別要求編號ID床位數(shù)性別要求編號ID床位數(shù)性別要求a277250b279121c277912a287450

25、b289411c288042a297710b2910011c298922a308230b3010331c309012a318340b3110431c319632a328520b3210721c329852a338740b3311121c339942a348830b3411241c3410252a359230b3511931c3510512a369310b3612431c3610622a379540b3712521c3710942a389710b3812921c3811022a3910130b3913021c3911532a4010830b4013531c4012122a4111340b4113

26、611c4112312a4211440b4213921c4212742a4311620b4315151c4312822a4411710b4415241c4413112a4511850b4515321c4514132a4612020b4615741c4614252a4712250b4716111c4714322a4812640b4816221c4814452a4913250b4916531c4914532a5013330b5016621c5014632a5113430b5116721c5114722a5213730b5217021c5214822a5313840b5317731c5315012a

27、5414030b5417841c5415642a5514950b5518441c5515832a5615450b5618711c5615952a5715510b5718931c5716342a5816040b5819321c5816942a5916420b5919641c5917132a6016820b6019931c6017232a6117520c6117322a6217930c6217432a6318010c6317632a6418650c6418132a6518820c6518242a6619230c6618322a6719740c6718532編號ID床位數(shù)性別要求編號ID床位數(shù)性別要

28、求編號ID床位數(shù)性別要求c6819032c6919122c7019432c7119522c7219832c7320012附錄三（10個團(tuán)隊入住人員分配表）：ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號130326101303282303261025252434242110331314431311104313145414111051206313111062222473232210721214841412108303289303261094242410303261102222411404261112121412303261124141413323221134

29、0429142222211440429152022611532324165252211620229171201171001830326118505291930326119313152020226120202210214242112122224222021712250529231001231202440417124313162510012521215264141212640429275151212742424284242212822224293032712921216ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號30100130210312121113112

30、032323221325052933202171333032934424221343032103532322135313163650517136110373131213730321038303171384042103931312139210405151214030321041505171413232442323221425252443505171432222444212121445252445303171453232446424221463232447313131472204832322148220493232214950521050515131501205132323151515165252

31、52315241416531101532121654212131545051105522223155100563232315642425572121315741416585252315832325592222315952524603131316040411061110161110624141216221216632222316342425642222316420221065200165313166620217166212166741413167212166840417168202110ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號ID號床位數(shù)性別要求安排人數(shù)入住性別團(tuán)隊號6920217169424

32、257031314170212110713131417132325725051717232325731201732207450517174323257552523175202110764141317632326771001773131678525231784141107912017930311080424231801008151514181323268230317182424268340417183222258431314184414110852021818532326865151418650511087404171871108830318188202110892222318931311090

33、1201903232691212141912222692303281923032109310019321211094110194323269540418195222269632324196414110971001974042109852524198323269942423199313110100110200120附錄四（問題一求解程序）：model:title: 30jiatin1;sets:seta/1.16/:a;setb/1.6/:b;setc/1.8/:c;setx/1.30/:x;endsetsdata:a=3,3,3,3,4,3,2,3,3,2,2,1,4,1,3,1;b=3,4,

34、3,4,4,5;c=4,3,3,2,5,1,4,4;enddatamax=sum(setx(n):x(n)/(x(n)+0.0001); for(setx(n):x(n)>=0);for(seta(i):x(i)<=a(i);for(setb(j):x(j+16)<=b(j);for(setc(k):x(k+22)<=c(k);sum(setx(n):x(n)=70;sum(seta(i):x(i)<=41;sum(setb(j):x(j+16)<=23;sum(setc(k):x(k+22)<=26;for(setx:gin(x);end附錄五（問題

35、二求解程序）：model:title:30jiatin2;sets:seta/1.16/:a;setb/1.6/:b;setc/1.8/:c;setx/1.30/:x;endsetsdata:a=3,3,3,3,4,3,2,3,3,2,2,1,4,1,3,1;b=3,4,3,4,4,5;c=4,3,3,2,5,1,4,4;enddatamin=sum(setx(n):50*x(n)/(x(n)+0.0001)+sum(seta(i):(a(i)-x(i)*20*x(i)/(x(i)+0.0001)+sum(setb(j):(b(j)-x(j+16)*20*x(j+16)/(x(j+16)+0.0001)+sum(setc(k):(c(k)-x(k+22)*20*x(k+22)/(x(k+22)+0.0001)+7000; f