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

1、學(xué)校選址問題摘要本文針對某地新開發(fā)的20個小區(qū)建設(shè)配套小學(xué)問題建立了 0-1規(guī)劃模型和 優(yōu)化模型。為問題一和問題二的求解，提供了理論依據(jù)。模型一：首先：根據(jù)目標要求，要建立最少學(xué)校的方案列出了目標函數(shù)：16S八Xii 4然后：根據(jù)每個小區(qū)至少能被一所學(xué)校所覆蓋，列出了20個約束條件；最后：由列出的目標函數(shù)和約束函數(shù)，用 matlab進行編程求解，從而得到， 在每個小區(qū)至少被一所學(xué)校所覆蓋時， 建立學(xué)校最少的個數(shù)是四所，并且一共有 22種方案。模型二：首先：從建校個數(shù)最少開始考慮建?？傎M用， 在整個費用里面，主要是固定 費用，由此在問題一以求解的條件下，進行初步篩選，得到方案 1,4,8的固定成

2、 本最少。然后：在初步得出成本費用最少時，對每個這三個方案進一步的求解， 求出 這三個方案的具體的總費用，并記下這三套方案中的最小費用。其次：對這三套方案進行調(diào)整，調(diào)整的原則是：在保證每個小區(qū)有學(xué)校覆蓋 的條件下，用多個固定成本費用低的備選校址替換固定成本費用高的備選校址。 在替換后，進行具體求解。再次：比較各種方案的計算結(jié)果，從而的出了如下結(jié)論：選用10,11,13,15,16號備選校址的選址方案，花費最少，最少花費為13378000 丿元。最后：對該模型做了靈敏度分析，模型的評價和推廣。關(guān)鍵字：最少建校個數(shù)最小花費固定成本規(guī)模成本靈敏度分析1問題重述1.1問題背景：某地新開發(fā)的20個小區(qū)內(nèi)

3、需要建設(shè)配套的小學(xué)，以方便小區(qū)內(nèi)居民的的孩子上學(xué)。但是為了節(jié)省開支，建造的學(xué)校要求盡量的少，為此，設(shè)備選定的16個校址提供參考，各校址覆蓋的小區(qū)情況如表1所示：表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,1011,16,2010,11,1516,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,1116,20,12,

4、13，14,17,189,10,14,152,3,5,11,202,3,4,5,81.2問題提出：問題一、求學(xué)校個數(shù)最少的建校方案，并用數(shù)學(xué)軟件求解（說明你所使用的 軟件并寫出輸入指令）。問題二、設(shè)每建一所小學(xué)的成本由固定成本和規(guī)模成本兩部分組成， 固定成 本由學(xué)校所在地域以及基本規(guī)模學(xué)?；A(chǔ)設(shè)施成本構(gòu)成， 規(guī)模成本指學(xué)校規(guī)模超 過基本規(guī)模時額外的建設(shè)成本，它與該學(xué)校學(xué)生數(shù)有關(guān)，同時與學(xué)校所處地域有 關(guān)。設(shè)第i個備選校址的建校成本g可表示為_ 広 X 2000 X100 （學(xué)生人數(shù) 600）, 若學(xué)生人數(shù)超過 600G = - i500,否則其中:i和1由表1-2給出：表1-2學(xué)校建設(shè)成本參數(shù)

5、表（單位：百萬元）備選校址1234567855555553.5耳0.150.150.150.150.150.150.150.1備選校址910111213141516ai3.53.53.53.522220.10.10.10.10.050.050.050.05考慮到每一小區(qū)的學(xué)齡兒童數(shù)會隨住戶的遷移和時間發(fā)生變化，當前的精確數(shù)據(jù)并不能作為我們確定學(xué)校規(guī)模的唯一標準，于是我們根據(jù)小區(qū)規(guī)模大小用統(tǒng) 計方法給出每個小區(qū)的學(xué)齡兒童數(shù)的估計值，見表1-3：表1-3.各小區(qū)1到6年級學(xué)齡兒童數(shù)平均值（樣本均值）小區(qū)12345678910學(xué)齡兒里數(shù)120180230120150180180150100160i=

6、1小區(qū)11121314151617181920學(xué)齡兒童數(shù)180240210220280260320380360300考慮總成本最低的建校方案2. 模型假設(shè)與符號說明2.1模型假設(shè)：(1) 入學(xué)的學(xué)生按照學(xué)校規(guī)劃的人數(shù)進行入學(xué)。(2) 學(xué)校的建立不受地區(qū)和學(xué)生人數(shù)的影響，一旦確定就可順利的建起。(3) 所建立的學(xué)校的規(guī)?？纱罂尚?。(4) 各小區(qū)的學(xué)生上學(xué)不受交通擁擠等的客觀因素的影響。2.2符號說明M =1,2,16):備選的第個i校址； s共要建立學(xué)校的個數(shù)；:i(i=1,2,3):第i個學(xué)校建校的固定成本； 'i (i=1,2,320):第i個學(xué)校建立的規(guī)模成本系數(shù)；G :(i =1

7、,2,316):第i個校址所需要花費的成本； t:學(xué)生人數(shù)；gi (i =1,2,316):第i個校址中所容納學(xué)生人數(shù)；ai (i=1,2,320):第i個小區(qū)入學(xué)人數(shù)； m (i=1,2,3):第i種方案的固定成本； w (i=1,2,3):第 i種方案的最少花費；3. 問題的分析3.1問題一的分析首先：根據(jù)題目要求每一個小區(qū)至少被一所學(xué)校所覆蓋，并且要使的建立的學(xué)校個數(shù)最少，為讀取數(shù)據(jù)方便可先將表1-1的數(shù)據(jù)進行加工。然后：在第一步完成后，利用加工后的表格，根據(jù)建立學(xué)校個數(shù)最小建立目 標函數(shù)，每一個小區(qū)至少能被一所學(xué)校所覆蓋，建立約束方程組。最后：運用matlab進行編程，進行運算，求解最

8、少建校的方案，進行整理 并用格列出。3.2問題二的分析首先：從表1-2中給定的數(shù)據(jù)可知：建校固定成本和規(guī)模成本最低的是 13,14,15,16號備選校址，其次是8,9,10,11,12號備選地址,費用最高的是 1,2,3,4,5,6,7號備選地址。然后：先從建校個數(shù)最少開始考慮建校的總費用，在問題一種可得到多種建 校最少的方案，要進行初步篩選，因為在規(guī)模成本中，費用最高的是備選學(xué)校 1,2,3,4,5,6,7 中，費用為：0.15*2000*100/50 =600元 /每人整個小區(qū)里人學(xué)年齡兒童的總?cè)藬?shù)：20ai=4320(1)除去每所學(xué)?；救菁{600人后，最大的規(guī)模成本費用是：015 (4

9、320-4*600 )600=172800該費用遠小于13,14,15,16號備選校址中的固定成本2000000元，所以在建校 個數(shù)相同時，費用的高低主要取決于固定成本，固定成本高，使整個建校方案成 本高，固定成本低，是整個建校的成本減少，所以在選用地址時，優(yōu)先考慮 13,14,15,16號地址其次8,9,10,12號地址，最后1,2,3,4,5,6,7號地址。其次：在初步篩選出的學(xué)校備選地址中，算出這些方案中花費的成本，比較并記下在建立最少個數(shù)學(xué)校時，花費最省的方案。再次：對已選出的最少建校方案中進行調(diào)整，調(diào)整的原則是：在保證每個小區(qū)至少有一所學(xué)校所覆蓋，將一所固定費用高的學(xué)校用兩所固定費用

10、小的代替。最后：比較出各方案的費用，得出建立學(xué)校的最小費用。4. 模型建立與求解4.1模型一的求解： 根據(jù)問題一的分析，建立模型一： 要建立學(xué)校個數(shù)最少，其目標函數(shù)是：16S 八 Xi(2)i A將表1-1進行加工，將第ai個小區(qū)被第Xi備選校址覆蓋記為1，否則為0，得到表4-1 ；表4-1各個備選校址覆蓋的小區(qū)小區(qū)123456789101112131415161718192011111010000000000000020110100100100000000130010100000100000000141001011000010000000051001001110101100000060000

11、10011110000100017000000000110001100118000001100001100011009000000101000111011101000000000110001110110111101010000000000000012000010000110000100011300000000000111001100140000000011000110000015011010000010000000011601111001000000000000橫坐標：小區(qū)編號i=1縱坐標：備選校址的編號由每個小區(qū)至少能被一所學(xué)校所覆蓋及表 4-1可得約束條件如下:X!X4X5X”_ 1X1X

12、2X11X15- X16_1X1X2X3X15x16_ 1X1X4X5 - X11x16_ 1x2x3xx12x 16 亠 1X1X4 XsX9X"丄1X4X2X6StJX2X5X5X *_1X6X9X10X14_1X7X10X12X14_1X3X5X6X7X12X8X13 -1XX9X13_1X9'X10 - X13X14_1X9X10X14_1X7 X10 - X12_1X9X13 - 1X9 X10- X13_1X9X10 -1X5X4X5X7X6X8X8十X7X5X8X9 _1X2X3X6X7X12X15 _ 1運行附錄A的程序，解出得到滿足該條件的建校方案有22種，

13、分別如下表4-2:表4-2建立四所學(xué)校的選址各種方案萬案123456校址5,8,10,155,7,8,165,7,8,154,9,12,164,7,9,164,6,9,16萬案789101112校址2,8,10,112,5,8,102,5,7,82,4,10,132,4,9,122,4,9,10萬案131415161718校址2,4,6,91,6,9,131,6,8,101,6,8,91,4,6,91,2,8,10萬案19202122校址4,6,9,152,10,11,132,4,8,102,4,7,94.2模型二的求解：由問題二的分析，先考慮在模型一中的結(jié)果中篩選出方案1,4,8的固定成本最

14、少，下面對各方案進行計算：方案1中建校最少花費的費用：方案一選用5,8,10,15號校址，每個備選校址能覆蓋的小區(qū)及所容納的學(xué)生 數(shù)量：5號校址覆蓋的小區(qū)：1,4,7,8,9,11,13,14共有人數(shù)：g5 =ai +創(chuàng) +a7 +a8 +a9+an +ai3+a)4=1280人(4)8號校址覆蓋的小區(qū)：6,7,12,13,17,18共有人數(shù)：g8=a6+a7+a12+a13+a17+a18=1510人(5)10號校址覆蓋的小區(qū) 910,14,15,16,18,19共有人數(shù):g10 =a9 +a10 + ai4 +a15 +a16 +a18+a19=780人(6)(11)15號校址覆蓋的小區(qū)2

15、,3,5,11,20共有人數(shù)：g15=a2+a3 +a5 +冇 +a2° =1040人(7)學(xué)生入學(xué)最佳方案，先各校滿足有600人，然后優(yōu)先考慮15號校址然后考 慮10號和8號校址，最后考慮5號校址。那么，學(xué)生最優(yōu)的入學(xué)安排如下：5號校址覆蓋1,4,7，8和13號小區(qū)里的30人，共600人；8號校址覆蓋6,12,17和13號剩余的部分學(xué)生 共920人10 號校址覆蓋 9,10,14,15,16,18,19號小區(qū)，共 1760 人；15號校址覆蓋 2,3,5,11,20共 1040人_ lpi x200100 (學(xué)生人數(shù) 600),若學(xué)生人數(shù)超過 600G =8 S500，否則c5=5

16、000000c8=3500000+0.1*2000* 100/50*(920-600)=3628000c10 =3500000+0.1*2000* 100/50*(1760-600)=3964000( 8)c15 =2000000+0.05*2000* 100/50*(1040-600)=2088000w 1 = c 5 +c 8 + c 10 + c 15(9)共需最小花費 W1=14680000元；同理方案4的最小花費的費用：4號校址覆蓋1,6,12和7號小區(qū)的60人 共600;9號校址覆蓋9,13,14,15,17,18,19和7號小區(qū)的120人 共1990人；12號校址覆蓋10,11,

17、16,20號小區(qū) 共有900人16號小區(qū)覆蓋2,3,4,5,8，號小區(qū) 共830人共需最小花費 W4=14722000元；同理方案8的最小花費的費用是：；2號校址覆蓋3,5,8,11,20號小區(qū) 共1010人；10號校址覆蓋9,10,15,16,19號小區(qū)，共1160人；11號校址覆蓋1,2,4,6,7號小區(qū) 共有780人；13號校址覆蓋12,13,14,17,18號小區(qū) 共有1370人；共需最小花費 w8 =14696000元。對上述三種方案中，總費用最少的是方案一，花費為 14680000元。 從表1-2的數(shù)據(jù)可看出，在13,14,15,16號備選校址建兩所學(xué)校的固定成本小 于1,2,3,

18、4,5,6,7好備選地址，對上面的三種方案根據(jù)問題二的分析進行調(diào)整： 方案1的最優(yōu)調(diào)整方案：不選用5號備選地址，改為11號和16號，這時的固定成本為m>3 = ： 8+ ： 10 + ：d + ： 15 + ： 16=14500000元(10)此時在沒有規(guī)模成本下，最多可容納學(xué)生t=5*600=3000 人(11)剩下的學(xué)生t=4320-3000=1320 人（12）這部分學(xué)生所產(chǎn)生的最低規(guī)模成本1320*2000* 100/50*0.05=264000（13）所以在方案一調(diào)整后的最少費用w23=14500000+236000=1473600（元（14）因為在調(diào)整后的費用w23 -w1，

19、該調(diào)整方案不可行；同理，對方案4進行調(diào)整，建立五所學(xué)校：將4號備選校址改為11號和13號備選地址這時的固定成本為mfe4 = ： 9 + ： “ + ： 12+ ： 13+： 16=1450000阮（15）此時在沒有規(guī)模成本下，最多可容納學(xué)生t=5*600=3000 人（16）剩下的學(xué)生t=4320-3000=1320 人（17）這部分學(xué)生所產(chǎn)生的最低規(guī)模成本1320*2000* 100/50*0.05=264000（ 18）所以在方案一調(diào)整后的最少費用w23=14500000+236000=1473600（元（19）因為在調(diào)整后的費用w24 ' w.（，該方案不可行；同理，對方案8進

20、行調(diào)整，建立五所學(xué)校將2號備選地址改為15號和16號備選地址用同方案一的方法計算該調(diào)整的后的最小花費：10號校址覆蓋9,10,15,16,19號小區(qū)，共1160人；11號校址覆蓋1,4,6,7號小區(qū) 共有600人；13號校址覆蓋12,13,14,17,18號小區(qū) 共有1370人；15號校址覆蓋11,20和5號小區(qū)的120人 共600人16號校址覆蓋3,4,8和5號小區(qū)的30人 共590人所需花費w25=13378000元；在建立五所學(xué)校時，考慮到是否存在建立四所固定成本最低的學(xué)校和一所固定成本較高的的學(xué)校。分析可知，要建立的四所低固定成本的學(xué)校只能選13,14,15,16號備選地址，而在這些學(xué)

21、校覆蓋后還有 1,6,7,19號小區(qū)沒有被學(xué)校覆蓋， 根據(jù)表4-1可知，沒有一所學(xué)校能同時覆蓋這四個小區(qū)，所以在建立五所學(xué)校學(xué) 校時，不存在這種情況。綜合可知，其花費是 w25=13378000元將方案繼續(xù)調(diào)整：若建立六所學(xué)校，固定成本w最小是建立四所固定成本2000000和兩所固定 成本3500000，此時費用為w=15000000，大于W25所以不可行，如再多建立學(xué)校 均大于對方案8調(diào)整后的成本。所以，選用10,11,13,15,16號備選地址的花費最 小，最小為13378000元5. 靈敏度分析在問題二中可知道：建校的成本包括固定成本和規(guī)模成本。情況一：如果1,2,3,4,5,6,7號備

22、選校址固定成本降低到 3500000 5000000元 時，初步篩選建校備選地址的方案不變， 調(diào)整后的建校備選地址，總費用也不發(fā) 生改變。情況二：如果8,9,10,11,12號備選地址的固定成本降低到3500000 2000000 元時，初步篩選的方案不變，調(diào)整后所選的建校備選地址不變， 但最終的總費用 會發(fā)生減小。情況三：如果1,2,3,4,5,6,7號備選地址的規(guī)模成本的系數(shù)在 0.10.15之間， 其結(jié)果會和情況一的效果一樣。情況四：8,9,10,11,12號備選地址的規(guī)模成本的系數(shù)在0.05 0.1之間，其結(jié) 果會和情況一的效果二樣。6. 模型評價與推廣5.1模型評價優(yōu)點：1）模型原理

23、簡單明了，容易理解與運用。2）適用范圍廣，模型對于其它的選址問題同樣適用。3）本模型對問題的描述精確、合理、推導(dǎo)嚴謹、理論性強。4） 模型的建立中有成熟的理論基礎(chǔ)和利用專業(yè)的MATLAB軟件進行求解， 可信度較高。5）建立的模型與實際緊密聯(lián)系，充分考慮現(xiàn)實學(xué)生入學(xué)情況的多樣性， 從而使模型更貼近實際，通用性、推廣性較強。缺點：1） 在實際生活中，學(xué)生入學(xué)的選擇會受到學(xué)校的教學(xué)質(zhì)量，學(xué)習(xí)的設(shè)施得的 影響，而在模型建立的過程里忽略了這種客觀因素的影響。2）在建立學(xué)校過程中，沒有將全部的經(jīng)費考慮到為，只給定了一個固定成本。5.2模型的推廣該模型是一個典型的0-1規(guī)劃模型，在實際生活中有著一定的使用空

24、間。 該 模型不僅可以對學(xué)校選址問題，還可以解決類似與該相似的選址問題，女口：餐飲 選址問題，郵局選址，連鎖店選址問題。7. 參考文獻1 吳建國主編數(shù)學(xué)建模案例精編北京水利水電出版社2005.52 劉慧穎主編MATLAB清華大學(xué)出版社20083 姜啟源謝金星葉俊主編數(shù)學(xué)模型（第三版）高等教育出版社 2003吳振奎 王全文 主編運籌學(xué)中國人民大學(xué)出版社 2006.2附錄A%*求出最少建校方案*q/qfunction myfun3() i=1;for x1=0:1for x2=0:1for x3=0:1for x4=0:1for x5=0:1for x6=0:1for x7=0:1for x8=0:1for x9=0:1for x10=0:1for x11=0:1for x12=0:1for x13=0:1for x