数学建模_学校选址问题模型

学校选址问题

摘 要

本文针对某地新开发的20个小区建设配套小学问题建立了0-1规划模型和优化模型。为问题一和问题二的求解，提供了理论依据。

模型一：

首先：根据目标要求，要建立最少学校的方案列出了目标函数：

s =∑x i

i =116

然后：根据每个小区至少能被一所学校所覆盖，列出了20个约束条件;

最后：由列出的目标函数和约束函数，用matlab 进行编程求解，从而得到，在每个小区至少被一所学校所覆盖时，建立学校最少的个数是四所，并且一共有22种方案。

模型二：

首先：从建校个数最少开始考虑建校总费用，在整个费用里面，主要是固定费用，由此在问题一以求解的条件下，进行初步筛选，得到方案1,4,8的固定成本最少。

然后：在初步得出成本费用最少时，对每个这三个方案进一步的求解，求出这三个方案的具体的总费用，并记下这三套方案中的最小费用。

其次：对这三套方案进行调整，调整的原则是：在保证每个小区有学校覆盖的条件下，用多个固定成本费用低的备选校址替换固定成本费用高的备选校址。在替换后，进行具体求解。

再次：比较各种方案的计算结果，从而的出了如下结论： 选用10,11,13,15,16号备选校址的选址方案，花费最少，最少花费为13378000元。

最后：对该模型做了灵敏度分析，模型的评价和推广。

关键字：最少建校个数 最小花费 固定成本 规模成本 灵敏度分析

1. 问题重述

1.1问题背景：

某地新开发的20个小区内需要建设配套的小学，以方便小区内居民的的孩子上学。但是为了节省开支，建造的学校要求尽量的少，为此，设备选定的16个校址提供参考，各校址覆盖的小区情况如表1所示：

1.2 问题提出：

问题一、求学校个数最少的建校方案，并 用数学软件求解（说明你所使用的软件并写出输入指令）。

问题二、设每建一所小学的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模学校基础设施成本构成，规模成本指学校规模超过基本规模时额外的建设成本，它与该学校学生数有关，同时与学校所处地域有关。设第i 个备选校址的建校成本c i 可表示为

2000⨯100⎧⎪βi ⨯(学生人数-600) ，　若学生人数超过600

c i =αi +⎨ 50

⎪0，　否则⎩

其中αi 和βi 由表1-2给出：

表1-2 学校建设成本参数表（单位：百万元）

考虑到每一小区的学龄儿童数会随住户的迁移和时间发生变化, 当前的精确数据并不能作为我们确定学校规模的唯一标准，于是我们根据小区规模大小用统计方法给出每个小区的学龄儿童数的估计值，见表1-3：

表1-3. 各小区1到6年级学龄儿童数平均值（样本均值）

2. 模型假设与符号说明

2.1模型假设：

（1）入学的学生按照学校规划的人数进行入学。

（2）学校的建立不受地区和学生人数的影响，一旦确定就可顺利的建起。 （3）所建立的学校的规模可大可小。

（4）各小区的学生上学不受交通拥挤等的客观因素的影响。 2.2符号说明 x i (i =1，2，……16):备选的第个i 校址；

s :一共要建立学校的个数；

αi (i=1,2,3……) :第i 个学校建校的固定成本；

βi (i=1,2,3……20) :第i 个学校建立的规模成本系数；

第i 个校址所需要花费的成本； c i :(i =1,2,3……16) ：

t :学生人数； g i (i =1,2,3……16):第i 个校址中所容纳学生人数； 第i 个小区入学人数； a i (i=1,2,3…20) ：

第i 种方案的固定成本； m i (i=1,2,3……) ：

第i 种方案的最少花费； w i (i=1,2,3……) ：

3. 问题的分析

3.1问题一的分析

首先：根据题目要求每一个小区至少被一所学校所覆盖，并且要使的建立的学校个数最少，为读取数据方便可先将表1-1的数据进行加工。

然后：在第一步完成后，利用加工后的表格，根据建立学校个数最小建立目标函数，每一个小区至少能被一所学校所覆盖，建立约束方程组。

最后：运用matlab 进行编程，进行运算，求解最少建校的方案，进行整理并用格列出。

3.2问题二的分析

首先：从表1-2中给定的数据可知：建校固定成本和规模成本最低的是13,14,15,16号备选校址，其次是8,9,10,11,12号备选地址, 费用最高的是1,2,3,4,5,6,7号备选地址。

然后：先从建校个数最少开始考虑建校的总费用，在问题一种可得到多种建校最少的方案，要进行初步筛选，因为在规模成本中，费用最高的是备选学校1,2,3,4,5,6,7中，费用为：

0.15*2000*100/50=600元/每人

整个小区里人学年龄儿童的总人数：

t =∑a i =4320 （1）

i =120

除去每所学校基本容纳600人后，最大的规模成本费用是：

015. （4320-4*600）600=172800

该费用远小于13,14,15,16号备选校址中的固定成本2000000元，所以在建校个数相同时，费用的高低主要取决于固定成本，固定成本高，使整个建校方案成本高，固定成本低，是整个建校的成本减少，所以在选用地址时，优先考虑13,14,15,16号地址其次8,9,10,12号地址，最后1,2,3,4,5,6,7号地址。

其次：在初步筛选出的学校备选地址中，算出这些方案中花费的成本，比较并记下在建立最少个数学校时，花费最省的方案。

再次：对已选出的最少建校方案中进行调整，调整的原则是：在保证每个小区至少有一所学校所覆盖，将一所固定费用高的学校用两所固定费用小的代替。

最后：比较出各方案的费用，得出建立学校的最小费用。

4. 模型建立与求解

4.1模型一的求解：

根据问题一的分析，建立模型一： 要建立学校个数最少，其目标函数是：

s =∑x i （2）

i =116

将表1-1进行加工，将第a i 个小区被第x i 备选校址覆盖记为1，否则为0，得到表4-1；

表4-1 各个备选校址覆盖的小区

纵坐标：备选校址的编号

由每个小区至少能被一所学校所覆盖及表4-1可得约束条件如下：

⎧x 1+x 4+x 5+x 11≥1

⎪x +x +x +x +x ≥1⎪12111516

⎪x 1+x 2+x 3+x 15+x 16≥1⎪

⎪x 1+x 4+x 5+x 11+x 16≥1⎪x +x +x +x +x ≥1

16

⎪23612

⎪x 1+x 4+x 8+x 9+x 11≥1⎪x +x +x +x ≥1⎪4589

⎪x 2+x 5+x 6+x 16≥1⎪

⎪x 5+x 6+x 9+x 10+x 14≥1⎪x +x +x +x +x ≥1⎪67101214st ⎨ (3) ⎪x 2+x 3+x 5+x 6+x 7+x 12+x 15≥1⎪x 4+x 8+x 13≥1⎪

⎪x 5+x 8+x 9+x 13≥1

⎪x +x +x +x +x ≥1⎪59101314⎪x 7+x 9+x 10+x 14≥1⎪

⎪x 6+x 7+x 10+x 12≥1⎪x +x +x ≥1⎪8913

⎪x 8+x 9+x 10+x 13≥1⎪x +x +x ≥1⎪7910⎪⎩x 2+x 3+x 6+x 7+x 12+x 15≥1

运行附录A 的程序，解出得到满足该条件的建校方案有22种，分别如下表4-2：

表4-2 建立四所学校的选址各种方案

4.2模型二的求解：

由问题二的分析，先考虑在模型一中的结果中筛选出方案1,4,8的固定成本最少，下面对各方案进行计算： 方案1中建校最少花费的费用：

方案一选用5,8,10,15号校址，每个备选校址能覆盖的小区及所容纳的学生数量：

5号校址覆盖的小区：1,4,7,8,9,11,13,14 共有人数：

g 5=a1+a 4+a 7+a 8+a 9+a 11+a 13+a 14=1280人 （4）

8号校址覆盖的小区：6,7,12,13,17,18 共有人数：

g 8=a 6+a 7+a 12+a13+a 17+a 18=1510人 （5）

10号校址覆盖的小区:9,10,14,15,16,18,19 共有人数：

g 10=a9+a 10+a 14+a 15+a 16+a 18+a 19=780人 （6）

15号校址覆盖的小区2,3,5,11,20 共有人数：

g 15=a2+a 3+a 5+a 11+a 20=1040人 （7）

学生入学最佳方案，先各校满足有600人，然后优先考虑15号校址然后考虑10号和8号校址，最后考虑5号校址。那么，学生最优的入学安排如下：

5号校址覆盖1,4,7，8和13号小区里的30人，共600人； 8号校址覆盖6,12,17和13号剩余的部分学生 共920人 10号校址覆盖 9,10,14,15,16,18,19号小区，共1760人； 15号校址覆盖 2,3,5,11,20 共 1040人

2000⨯100⎧⎪βi ⨯(学生人数-600) ，　若学生人数超过600

c i =αi +⎨ 50

⎪0，　否则⎩

⎧c 5=5000000

⎪c =3500000+0.1*2000*100/50*(920-600)=3628000⎪8

（8） ⎨

⎪c 10=3500000+0.1*2000*100/50*(1760-600)=3964000⎪⎩c 15=2000000+0.05*2000*100/50*(1040-600)=2088000

（9） w 1=c 5+c8+c 10+c 15

共需最小花费 w 1=14680000元； 同理方案4的最小花费的费用：

4号校址覆盖1,6,12和7号小区的60 人 共 600；

9号校址覆盖9,13,14,15,17,18,19和7号小区的120人 共1990人； 12号校址覆盖10,11,16,20号小区 共有900人 16号小区覆盖2,3,4,5,8, 号小区 共830人 共需最小花费 w 4=14722000 元； 同理方案8的最小花费的费用是：；

2号校址覆盖3,5,8,11,20号小区 共1010人；

10号校址覆盖9,10,15,16,19号小区，共1160人； 11号校址覆盖1,2,4,6,7号小区 共有780人；

13号校址覆盖12,13,14,17,18号小区 共有1370人； 共需最小花费 w 8=14696000元。

对上述三种方案中，总费用最少的是方案一，花费为14680000元。

从表1-2的数据可看出，在13,14,15,16号备选校址建两所学校的固定成本小于1,2,3,4,5,6,7好备选地址，对上面的三种方案根据问题二的分析进行调整： 方案1 的最优调整方案：

不选用5号备选地址，改为11号和16号，这时的固定成本为

m 23=α8+α10+α11+α15+α16=14500000元 （10）

此时在没有规模成本下，最多可容纳学生

t =5*600=3000人 （11）

剩下的学生

t =4320-3000=1320人 （12）

这部分学生所产生的最低规模成本

1320*2000*100/50*0.05=264000 （13）

所以在方案一调整后的最少费用

w 23=14500000+236000=14736000元 （14）

w 1，该调整方案不可行；

同理，对方案4进行调整，建立五所学校：

将4号备选校址改为11号和13号备选地址这时的固定成本为

m 24=α9+α11+α12+α13+α16=14500000元 （15）

此时在没有规模成本下，最多可容纳学生

t =5*600=3000人 （16）

剩下的学生

t =4320-3000=1320人 （17）

这部分学生所产生的最低规模成本

1320*2000*100/50*0.05=264000 （18）

所以在方案一调整后的最少费用

w 23=14500000+236000=14736000元 （19）

因为在调整后的费用w 24w 1，该方案不可行；

同理，对方案8进行调整，建立五所学校

将2号备选地址改为15号和16号备选地址 用同方案一的方法计算该调整的后的最小花费： 10号校址覆盖9,10,15,16,19号小区，共1160人； 11号校址覆盖1,4,6,7号小区 共有600人；

13号校址覆盖12,13,14,17,18号小区 共有1370人； 15号校址覆盖11,20 和5号小区的120人 共600人 16号校址覆盖3,4,8和5号小区的30人 共590人 所需花费w 25=13378000元；

在建立五所学校时，考虑到是否存在建立四所固定成本最低的学校和一所固 定成本较高的的学校。分析可知，要建立的四所低固定成本的学校只能选13,14，15,16号备选地址，而在这些学校覆盖后还有1,6,7,19号小区没有被学校覆盖，根据表4-1可知，没有一所学校能同时覆盖这四个小区，所以在建立五所学校学校时，不存在这种情况。

综合可知，其花费是w 25=13378000元 将方案继续调整： 若建立六所学校，固定成本w 最小是建立四所固定成本2000000和两所固定成本3500000，此时费用为w =15000000，大于w 25所以不可行，如再多建立学校均大于对方案8调整后的成本。所以，选用10,11,13,15,16号备选地址的花费最小，最小为13378000元

因为在调整后的费用w 23

5. 灵敏度分析

在问题二中可知道：建校的成本包括固定成本和规模成本。

情况一：如果1,2,3,4,5,6,7号备选校址固定成本降低到3500000~5000000元

时，初步筛选建校备选地址的方案不变，调整后的建校备选地址，总费用也不发生改变。

情况二：如果8,9,10,11,12号备选地址的固定成本降低到3500000~2000000元时，初步筛选的方案不变，调整后所选的建校备选地址不变，但最终的总费用会发生减小。

情况三：如果1,2,3,4,5,6,7号备选地址的规模成本的系数在0.1~0.15之间，其结果会和情况一的效果一样。

情况四：8,9,10,11,12号备选地址的规模成本的系数在0.05~0.1之间，其结果会和情况一的效果二样。

6. 模型评价与推广

5.1模型评价

优点：

1）模型原理简单明了，容易理解与运用。

2）适用范围广，模型对于其它的选址问题同样适用。

3）本模型对问题的描述精确、合理、推导严谨、理论性强。

4）模型的建立中有成熟的理论基础和利用专业的MATLAB 软件进行求解，可信度较高。

5）建立的模型与实际紧密联系，充分考虑现实学生入学情况的多样性，

从而使模型更贴近实际，通用性、推广性较强。

缺点：

1）在实际生活中，学生入学的选择会受到学校的教学质量，学习的设施得的影响，而在模型建立的过程里忽略了这种客观因素的影响。 2）在建立学校过程中，没有将全部的经费考虑到为，只给定了一个固定成本。

5.2 模型的推广

该模型是一个典型的0-1规划模型，在实际生活中有着一定的使用空间。该模型不仅可以对学校选址问题，还可以解决类似与该相似的选址问题，如：餐饮选址问题，邮局选址，连锁店选址问题。

7. 参 考 文 献

[1] 吴建国主编《数学建模案例精编》 北京水利水电出版社 2005.5 [2] 刘慧颖主编《MA TLAB 》 清华大学出版社 2008 [3] 姜启源 谢金星 叶俊主编《数学模型》（第三版）高等教育出版社 2003 [4] 吴振奎 王全文 主编《运筹学》 中国人民大学出版社 2006.2

8. 附 录

附录A

%*************求出最少建校方案*****************% function myfun3() i=1;

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 for 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+x16+x15>=1&... %约束条件

X 1+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+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+x14>=1&...

x7+x9+x10>=1&x2+x3+x6+x7+x12+x15>=1);

s(i)=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16;

x(i,:)=[x1,x2,x3,x4,x5,x6,x7,x8,x9,x10,x11,x12,x13,x14,x15,x16];

i=i+1;

end end end end end end end end end end end end end end end

[a b]=min(s) n=find(s==4) aa=length(n)

for i=1:aa %输出各种方案 x(n(i),:) end

end end