數(shù)學建模學校選址問題

1、學校選址問題摘要本文為解決學校選址問題，建立了相應的數(shù)學模型。針對模型一首先，根據(jù)已知信息，對題目中給出的數(shù)據(jù)進行處理分析。在保證每個小區(qū),學生至少有一個校址可供選擇的情況下，運用整數(shù)規(guī)劃中的0-1規(guī)劃法，列出建校方案的目標函數(shù)與其約束條件，通過軟件，使用計算機搜索算法進行求解。得出建立校址的最少數(shù)目為4個。再運用軟件編程，運行得到當建校的個數(shù)為4個時，學校選址的方案有22種，如下表：方案選址地點方案選址地點1581015122410132581015132491235781514249104491116152481054791616247964691617246974691518169138

2、21011131916810928101120168910258102114691125782212810針對模型二首先，對文中給出的學校建設成本參數(shù)表和各校區(qū)1到6年級學齡兒童的平均值（樣本均值）進行分析，可知20個小區(qū)估計共有4320個學齡兒童，當每個學校的平均人數(shù)都小于600時，至少需要建設8個學校；其次，模型一得到最少的建校數(shù)目為4個，運用軟件編程，依次列出學校個數(shù)為4、5、6、7、8時的最優(yōu)建校方案，分別算出其最優(yōu)建校方案下的總成本；最后，通過對比得出，最低的建?？偝杀緸?650萬，即選取校址10、11、13、14、15、16建設學校。最后，我們不但對模型進行了靈敏度分析， ，保證了

3、模型的有效可行。關(guān)鍵詞： 靈敏度 0-1規(guī)劃 總成本 選址 1 問題重述當代教育的普及，使得學校的建設已成為不得不認真考慮的問題。1.1已知信息1、某地新開發(fā)的20個小區(qū)需要建設配套的小學，備選的校址共有16個，各校址覆蓋的小區(qū)情況如表1所示：表1.備選校址表備選校址12345678覆蓋小區(qū)1,2,3,4,62,3,5,8,11,203,5,11,201,4,6,7,121,4,7,8,9,11,13,145,8,9,10,11,16,2010,11,1516,19,206,7,12,13,17,18備選校址910111213141516覆蓋小區(qū)7,9,13,14,15,17,18,199,1

4、0,14,15,16,18191,2,4,6,75,10,11,16,2012,13,14,17,189,10,14,152,3,5,11,202,3,4,5,82、在問題二中，每建一所小學的成本由固定成本和規(guī)模成本兩部分組成，固定成本由學校所在地域以及基本規(guī)模學?；A設施成本構(gòu)成，規(guī)模成本指學校規(guī)模超過基本規(guī)模時額外的建設成本，它與該學校學生數(shù)有關(guān)，同時與學校所處地域有關(guān)。設第個備選校址的建校成本可表示為，若學生人數(shù)超過人，其中和由表2給出：表2.學校建設成本參數(shù)表校址1234567891011121314151655555553.53.53.53.53.522220.150.150.150

5、.150.150.150.150.10.10.10.10.10.050.050.050.05并且考慮到每一小區(qū)的學齡兒童數(shù)會隨住戶的遷移和時間發(fā)生變化，當前的精確數(shù)據(jù)并不能作為我們確定學校規(guī)模的唯一標準，于是我們根據(jù)小區(qū)規(guī)模大小用統(tǒng)計方法給出每個小區(qū)的學齡兒童數(shù)的估計值，見表3：表3.各小區(qū)1到6年級學齡兒童數(shù)平均值小區(qū)12345678910學齡兒童數(shù)120180230120150180180150100160小區(qū)11121314151617181920學齡兒童數(shù)1802402102202802603203803603001.2提出問題1、要求建立數(shù)學模型并利用數(shù)學軟件求解出學校個數(shù)最少的建校

6、方案。 2、求出總成本最低的建校方案。2 問題假設與符號說明2.1 問題假設 1 每個學校配備的師資力量是同等的 2 每個小區(qū)的學生到附近小學上學的概率相同 3 每個學校各年級的收費相同 4 建設學校期間建筑材料的價格不會發(fā)生變化2.2 符號說明 ：（）第個備選校址的建校成本 ：（）學校建設成本（單位：百萬元）：（）學校建設的成本參數(shù)：（）學校的選址數(shù)目：建校的總成本3 問題分析學校選址是一類帶有復雜約束條件的優(yōu)化與規(guī)劃問題，在學校選址過程中，要從小區(qū)的覆蓋情況、人數(shù)、費用等方面綜合考慮，合理安排學校選址方案。問題1的分析首先，根據(jù)已知信息可知,新開發(fā)的20個小區(qū)需要建設配套的小學,設備選取的

7、校址共有16個；然后，結(jié)合附表1中備選校址表，對其進行處理分析，可知各校址覆蓋的小區(qū)情況，運用整數(shù)規(guī)劃中的0-1規(guī)劃法，在保證每個小區(qū)至少有一個可供選擇校址的前提下，列出建校方案的目標函數(shù)，并寫出與其有關(guān)約束條件的不等式；最后，通過軟件，使用計算機搜索法，算出建設學校的最少個數(shù)，由于軟件只能求解得到一種方案，因此再運用軟件編程，求解得出的各種方案，即為在滿足學校個數(shù)最少情況下的建校方案。問題2的分析首先,每建一所小學的成本由固定成本和規(guī)模成本兩部分組成，固定成本由學校所在地域以及基本規(guī)模、學?；驹O施成本構(gòu)成，規(guī)模成本指學校規(guī)模超過基本規(guī)模時額外的建設成本，它與該校學生數(shù)和其所處地域有關(guān)。由題

8、目中給出備選校址的建校成本關(guān)系式可知，在學校人數(shù)大于等于600人時，（1）如果選擇校址建設學校，每增加一個人，學校的建設成本增加6000元。（2）如果選擇校址建設學校，每增加一個人，學校的建設成本增加4000元（3）如果選擇校址建設學校，每增加一個人，學校的建設成本增加元其次，根據(jù)問題1的分析，結(jié)合題目中給出的建校成本關(guān)系式，可以算出建校個數(shù)最少時的最低成本。由于同一個小區(qū)可能被多個校址覆蓋，因此在處理被多個校址覆蓋的小區(qū)人數(shù)時，需要遵循兩個原則，（1）保證每個學校的學生盡量達到600人。（2）當同一小區(qū)被不同的學校覆蓋時，把該小區(qū)的學生分配到建校成本較低的學校。（3）當建設不同校址成本相同，

9、且都滿600人時，就平均分配。然后，通過對各小區(qū)1到6年級學齡兒童數(shù)平均值的處理分析，得到20個小區(qū)大約共有4320個學齡兒童。當每個學校的平均人數(shù)都小于600時，至少需要建設8個學校，才可能使建校費用達到最省。運用軟件編程依次求解出學校個數(shù)為5、6、7、8時的最優(yōu)建校方案，算出每個方案所花費的費用。最后，通過對比，得出總成本最低的建校方案。4 模型的建立與求解4.1 模型一的建立與求解根據(jù)問題1的分析，某地新開發(fā)的20個小區(qū)需要建設配套的小學，設備選的校址共有16個，要求出學校個數(shù)最少的建校方案，需保證每一個小區(qū)至少有一個小學可供選擇，每個校址覆蓋小區(qū)的情況見附表1。我們把每個校址設為，由于

10、每個校址覆蓋小區(qū)的不同，可知同一小區(qū)被不同校址覆蓋的情況，見下表表4-1 同一小區(qū)被不同校址覆蓋的情況不同的小區(qū)被覆蓋情況小區(qū)1小區(qū)2小區(qū)3小區(qū)4小區(qū)5小區(qū)6小區(qū)7小區(qū)8小區(qū)9小區(qū)10小區(qū)11小區(qū)12小區(qū)13小區(qū)14小區(qū)15小區(qū)16小區(qū)17小區(qū)18小區(qū)19小區(qū)20要求出建校個數(shù)最少的方案，顯然是優(yōu)化問題，針對問題特殊性，我們選用01規(guī)劃來解決這個問題。在保證每個小區(qū)的孩子至少有一個學?？晒┻x擇前提下，根據(jù)上表中每一個小區(qū)對應的不同覆蓋情況，使得覆蓋數(shù)必需要大于等于1，由此來列出約束條件。本問題是要解決建校個數(shù)最小的方案，即是求建校個數(shù)的最小值，用此來確定目標函數(shù)。如下：目標函數(shù)：約束條件：計算

11、機隨機搜索的算法及編程實現(xiàn)采用計算機搜索算法，我們基于三點考慮：一方面，滿足約束的建校方案不止一種，應該從所有的可能方案中搜索選擇最佳的建校方案；另一方面，采取計算機搜索算法可以提高模型的推廣價值及結(jié)果的可信度；最后，計算機搜索避免了對結(jié)果最優(yōu)的理論證明，因為在搜索過程中結(jié)果的最優(yōu)性已經(jīng)得到證明。因此，我們給出計算機搜索的算法，流程圖如圖4-1所示。輸 入 數(shù) 據(jù)搜索可能方案目標函數(shù)最小值輸 出 結(jié) 果滿足各個約束條件開 始結(jié) 束圖4-1 模型1的算法流程圖同時，我們應用軟件，以題目中給出的數(shù)據(jù)為例，編程實現(xiàn)（見附錄B）得出即最少建校個數(shù)為4個，又結(jié)合編程，可解出當建校個數(shù)為4時，各種不同的方

12、案(過程見附錄C)，求出有22種方案，見表2表4-2 當建校個數(shù)為4時各種選擇方案校址方案100001001010000102000010110000000130000101100000010400010000100100015000100101000000160001010010000001700010100100000108010000000110100090100000101100000100100100101000000110100101100000000120101000001001000130101000010010000140101000011000000150101000101

13、0000001601010010100000001701010100100000001810000100100010001910000101010000002010000101100000002110010100100000002211000001010000004.2 模型二的建立與求解根據(jù)問題2的分析，每建一所學校的成本由固定成本和規(guī)模成本兩部分組成，固定成本由學校所在地域以及基本規(guī)模設施成本構(gòu)成，規(guī)模成本是指學校規(guī)模超過基本規(guī)模時額外的建設成本，它與該校的學生數(shù)有關(guān)，同時與學校所處地域有關(guān)。由題目中給出的計算建校成本方法，即表示建校的總費用，即固定成本與規(guī)模成本的和，為固定成本，為計算成

14、本規(guī)模的系數(shù)。的取值和學校所處的地域即校址有關(guān)，每個校址對應不同的數(shù)值見附表2由題目中給出的各個小區(qū)1到6年級學齡兒童數(shù)平均值，可知20個小區(qū)大概一共有4320個學生，考慮到每個小學的人數(shù)都可能小于600人，至少要建8個學校，但在此問題中，要求的是總成本最低的建校方案，根據(jù)常識，如果建的學校個數(shù)越少，總成本可能也是最少的，所以在保證每個小區(qū)的孩子都有一個學?？晒┻x擇的前提下，使建校的個數(shù)盡量少，在模型一中，算出建校個數(shù)最少時為4，即我們在此只選建校個數(shù)為4，5，6，7，8的方案來進行比較，得出總費用最少的那個建校方案。第一步：當建校個數(shù)為4時，有22種方案（模型一中已求出），篩選出總費用最少的

15、方案。通過對每一種方案的固定費用進行編程，求出第1種方案，第4種方案，第8種方案的固定費用都達到最低14（百萬）（過程見附錄D），因此我們選用這三種方案來進行比較。取出總費用最低的方案。由于不同校址可能同時覆蓋同一個小區(qū)，因此要對小區(qū)的人數(shù)進行調(diào)配，調(diào)配原則如下：（1）每個校址都盡量調(diào)到600左右。（2）因為七個校址，每增加一個人就得增加6000元，五個校址，每增加一個人就得增加4000元，四個校址，每增加一個人就得增加2000元，所以把能調(diào)配的人數(shù)，盡量分配到成本較低的校址，當然要保證前幾個校址都滿600人時。（3）當建設不同校址成本相同，且都滿600人時，就平均分配。第1種方案選擇5，8，

16、10，15這四個校址，由附表1可知5，8，10，15這四個校址分別覆蓋小區(qū)的情況，附表3可知每個小區(qū)的學齡兒童數(shù)。根據(jù)以上的調(diào)配原則我們對各個小區(qū)的學齡兒童數(shù)進行了合理分配，使總費用達到最少，分配方案如下：表4-3 當選擇第5，8，10，15校址時的人數(shù)分配情況校址581015分配的人數(shù)600111015701040根據(jù)以上表格可算出不同校址，建校的總費用（單位：百萬元），即校址5的分配人數(shù)等于600，即建校址5總費用為 校址8的分配人數(shù)大于600，即建校址8的總費用為校址10的分配人數(shù)大于600，即建校址10的總費用為校址15的分配人數(shù)大于600，即建校址15的總費用為即建這四個校址的總費用

17、為第4種方案選擇4，9，12，16這四個校址，按照以上的調(diào)配原則，對這四個校址進行人數(shù)的分配，如下表表4-4 當選擇第4，9，12，16校址時的人數(shù)分配情況校址491216分配的人數(shù)6001990900830 按照以上算每個校址的總費用的方法，分為人數(shù)小于等于600，大于600的兩種情況來進行計算，可得建校的總費用如下表表4-5 建第4，9，12，16校址時的費用校址491216建校的總費用（百萬）59.064.72.46即建這四個校址的總費用為第8種方案選擇2，10，11，13這四個校址，按照同樣的方法，算出建這四個校址的總費用，如下表表4-6 建第2，10，11，13校址時的分配人數(shù)與費用

18、校址2101113分配的人數(shù)101011607801370建校的總費用（百萬）7.465.744.223.54由以上表格可知，建這四個校址的總費用為通過對以上的三種方案進行比較，可知當建校個數(shù)為4時，選擇第1種方案，校址為5，8，10，15時，建校的總費用達到最小 第二步：當建校個數(shù)為5時，用編程求解出有349種方案可供選擇，在求出349方案的基礎上，進行編程求出第1種方案的固定費用達到最小，為13（百萬）。第1種方案選擇10，11，13，15，16這五個校址，根據(jù)這五個校址覆蓋小區(qū)的情況進行人數(shù)調(diào)配，使費用達到最少，同以上的方法，可求出不同校址分配人數(shù)及建校的總費用，見下表表4-7 建第10

19、，11，13，15，16校址時的分配人數(shù)與費用校址1011131516分配的人數(shù)11606001370600590建校的總費用（百萬）5.743.53.5422根據(jù)上表可知，建這五個校址的總費用為第三步：當建校個數(shù)為6時，編程求解出有1781種方案可供選擇，在求出不同方案的基礎下，進行編程求出第1種方案的固定費用達到最小，為15（百萬元）。第1種方案選擇10，11，13，14，15，16這六個校址，在保證費用達到最少的前提下，對人數(shù)進行調(diào)配，進而求出不同校址分配人數(shù)及建校的總費用，如下表4-8 建第10，11，13，14，15，16校址時的分配人數(shù)與費用校址101113141516分配的人數(shù)6

20、206001150760600590建校的總費用（百萬）3.583.53.12.3222通過以上表格，可算出建這六個校址總費用為第四步：當建校個數(shù)為7時，編程求解出有4702種方案可供選擇，在這基礎上求出第1種方案的固定費用達到最低為18.5（百萬元），由于它最小的固定費用都大于當建校個數(shù)為5，6時的總費用，因此把建校個數(shù)為7這種情況剔除。第五步：當建校個數(shù)為8時，求解出有7718中方案可供選擇，在第1種方案時固定費用達到最低為22（百萬），因為它最小的固定費用都大于當建校個數(shù)為4，5，6時的總費用，所以把建校個數(shù)為8這種情況剔除。通過以上的五步計算出來的結(jié)果，進行比較，可得當建校個數(shù)為6，校

21、址為10，11，13，14，15，16時，建校的總成本達到最小值（百萬元）。5 靈敏度分析由于本案例中對模型結(jié)果產(chǎn)生的影響因素有很多，我們在此選取了關(guān)鍵的參數(shù)進行靈敏度分析。模型對這些參數(shù)的敏感性反映了各種因素影響結(jié)果的顯著程度，通過對這些參數(shù)的靈敏度分析，對模型的推廣提出合理性的建議。5.1 模型一當改變校址個數(shù)時，建校的最少個數(shù)，以及在此情況下的建校方案可能會隨著變化，對此我們把校址增加，以此來驗證模型一的靈敏度。增加的校址: 校址1 覆蓋小區(qū) 2、4、5、9、10 校址1 覆蓋小區(qū) 3、6、7、13、15 校址1 覆蓋小區(qū) 1、8、18、19、20 校址1 覆蓋小區(qū) 11、12、14、1

22、6、17（注：覆蓋的小區(qū)的選擇是把20個小區(qū)隨機分配給增加的四個校址）運用軟件編程求解，得出下表： 表5-1 最少個數(shù)的建校方案隨著校址數(shù)目變化情況 校址個數(shù)1617181920最少學校個數(shù) 44444建校方案22 531739324723由上表可知，當備選校址增加到17、18、19、20個時，最少的建校個數(shù)依然為4個，并且建校方案隨著備選校址的增加而增加。5.2 對于模型二由于建校的總費用和固定成本，系數(shù)，學生的人數(shù)有關(guān)，根據(jù)題意，建校的固定成本是影響最優(yōu)方案的重要因素，假設在系數(shù)、學生人數(shù)不變的情況下，對模型二中的固定成本進行靈敏度分析。隨著社會的不斷進步，房價也隨之增高，根據(jù)資料顯示，固

23、定成本平均每年增長率為10%。由于建校個數(shù)為5、6時，總成本相差不多，所以以下只考慮這兩種情況，來進行說明。當建校個數(shù)為5時，由模型二算出的最小總成本（百萬元）。在學生人數(shù)、系數(shù)保持不變的前提下，固定費用增加10%，通過編程求出總的成本為（百萬元）。當建校個數(shù)為6時，由模型二得出最小總成本（百萬元）。在保證學生人數(shù)、系數(shù)不變的前提下，固定費用增加10%，求得總成本為（百萬元）。在以上的基礎上，固定費用再增加10%，求得當建校個數(shù)為5時，總成本（百萬元）。當建校個數(shù)為6時，總成本（百萬元）。在第二年里最優(yōu)方案就不再是建校個數(shù)為6時，這說明在第二年時就要考慮換方案，因為這時建校個數(shù)為6時達不到最優(yōu)

24、。6 模型的評價與推廣6.1 模型的評價優(yōu)點1 建立的優(yōu)化模型有成熟的理論基礎，又有相應專業(yè)軟件進行計算，得出的結(jié)果比較精確，可信度較高2 模型原理簡單明了，容易理解與靈活運用3 建立的模型與實際緊密聯(lián)系，充分考慮現(xiàn)實情況的多樣性，從而使模型更貼近實際，通用性、推廣性較強。缺點1 模型建立過程中，僅考慮了題中所給的幾個參數(shù)對學校選址問題的影響，沒有考慮到其它因素帶來的影響。2 模型復雜因素較多，不能對其進行全面的考慮，造成與實際有一定的不相符之處6.2 模型的推廣本模型在計算過程中使用了lingo軟件，并采用直接輸入的方法進行編程計算，配有流程圖，使模型在解決可能的實際問題時能夠較方便的找出結(jié)

25、果，從而更容易推廣到其他的選址問題，例如，消防站的選址、醫(yī)院等公共基礎設施的選址。7 參考文獻1 吳建國主編數(shù)學建模案例精編中國水利水電出版社 2005.52 錢小軍主編 數(shù)量方法 高等教育出版社 1999.83 孫祥 徐流美 吳清編著MATLAB7.0基礎教程清華大學出版社 2005.54 姜啟源 謝金星 葉俊主編數(shù)學模型（第三版）高等教育出版社 2003.25 吳振奎、王文全 主編 運籌學，中國人民大學出版社，20048 附錄附錄A表1. 備選校址表備選校址12345678覆蓋小區(qū)1,2,3,4,62,3,5,8,11,203,5,11,201,4,6,7,121,4,78,9,11,13

26、,145,8,9,10,11,16,2010,11,15,16,19,206,7,12,13,17,18備選校址910111213141516覆蓋小區(qū)7,9,13,14,15,17,18,199,10,14,15,16,18,191,2,4,6,75,10,11,16,20,12,13,14,17,189,10,14,152,3,5,11,202,3,4,5,8表2. 學校建設成本參數(shù)表（單位：百萬元）備選校址1234567891011121314151655555553.53.53.53.53.522220.150.150.150.150.150.150.150.10.10.10.10.10

27、.050.050.050.05表3. 各小區(qū)1到6年級學齡兒童數(shù)平均值（樣本均值）小區(qū)12345678910學齡認數(shù)120180230120150180180150100160小區(qū)11121314151617181920學齡人數(shù)180240210220280260320380360300附錄B 確定最少校址個數(shù)：min=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16+x17+x18+x19+x20;x1+x4+x5+x11>=1;x1+x2+x11+x15+x16>=1;x1+x2+x3+x15+x16>=1;x1

28、+x4+x5+x11+x16>=1;x2+x3+x6+x12+x15+x16>=1;x1+x4+x8+x11>=1;x4+x5+x8+x9+x11>=1;x2+x5+x6+x16>=1;x5+x6+x9+x10+x14>=1;x6+x7+x10+x12+x14>=1;x2+x3+x5+x6+x7+x12>=1;x4+x8+x13>=1;ax5+x8+x9+x13>=1;x5+x9+x10+x13+x14>=1;x9+x10+x7+x14>=1;x6+x7+x10+x12>=1;x8+x9+x13>=1;x8+x

29、9+x10+x13>=1;x7+x9+x10>=1;x2+x3+x6+x7+x12+x15>=1;bin(x1);bin(x2);bin(x3);bin(x4);bin(x5);bin(x6);bin(x7);bin(x8);bin(x9);bin(x10);bin(x11);bin(x12);bin(x13);bin(x14);bin(x15);bin(x16);附錄C確定具體最少校址方案：function xk=0;for x1=0:1 for x2=0:1 for x3=0:1 for x4=0:1 for x5=0:1 for x6=0:1 for x7=0:1 fo

30、r x8=0:1 for x9=0:1 for x10=0:1 for x11=0:1 for x12=0:1 for x13=0:1 for x14=0:1 for x15=0:1 for x16=0:1 if x1+x4+x5+x11>=1&x1+x2+x11+x15+x16>=1&x1+x2+x3+x15+x16>=1&x1+x4+x5+x11+x16>=1&x2+x3+x6+x12+x15+x16>=1&x1+x4+x8+x11>=1&x4+x5+x8+x9+x11>=1&x2+x5+x6

31、+x16>=1&x5+x6+x9+x10+x14>=1&x6+x7+x10+x12+x14>=1&x2+x3+x5+x6+x7+x12+x15>=1&x4+x8+x13>=1&x5+x8+x9+x13>=1&x5+x9+x10+x13+x14>=1&x7+x9+x10+x14>=1&x6+x7+x10+x12>=1&x8+x9+x13>=1&x8+x9+x10+x13>=1&x7+x9+x10>=1&x2+x3+x6+x7+x1

32、2+x15>=1&x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16=5 z=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16; k=k+1; fprintf('第%d種',k); fprintf('%d=%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%dn',z,x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16); end end end end end end end end end end end end end end end endendk 附錄D 計算每種方案的固定成本for x2=0:1 for x3=0:1 for x4=0:1 for x5=0:1 for x6=0: