数学建模学校选址问题

学校选址问题

摘要

本文为解决学校选址问题，建立了相应的数学模型。 针对模型一

首先，根据已知信息，对题目中给出的数据进行处理分析。在保证每个小区, 学生至少有一个校址可供选择的情况下，运用整数规划中的0-1规划法，列出建校方案的目标函数与其约束条件，通过LINGO 软件，使用计算机搜索算法进行求解。得出建立校址的最少数目为4个。再运用MATLAB 软件编程，运行得到当建校的个数为4个时，学

首先，对文中给出的学校建设成本参数表和各校区1到6年级学龄儿童的平均值（样本均值）进行分析，可知20个小区估计共有4320个学龄儿童，当每个学校的平均人数都小于600时，至少需要建设8个学校；其次，模型一得到最少的建校数目为4个，运用MATLAB 软件编程，依次列出学校个数为4、5、6、7、8时的最优建校方案，分别算出其最优建校方案下的总成本；最后，通过对比得出，最低的建校总成本为1650万，即选取校址10、11、13、14、15、16建设学校。

最后，我们不但对模型进行了灵敏度分析， ，保证了模型的有效可行。

关键词： MATLAB 灵敏度 0-1规划 总成本 选址

1 问题重述

当代教育的普及，使得学校的建设已成为不得不认真考虑的问题。 1.1已知信息

1、某地新开发的20个小区需要建设配套的小学，备选的校址共有16个，各校址覆盖的小区情况如表1所示：

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

2000⨯100⎧

，若学生人数超过600人，其中c i =αi +⎨βi ⨯10⨯(学生人数-600（单元：元）)

50⎩

αi 和βi 由表2给出：

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

1.2提出问题

1、要求建立数学模型并利用数学软件求解出学校个数最少的建校方案。 2、求出总成本最低的建校方案。

2 问题假设与符号说明

2.1 问题假设

1 每个学校配备的师资力量是同等的

2 每个小区的学生到附近小学上学的概率相同 3 每个学校各年级的收费相同

4 建设学校期间建筑材料的价格不会发生变化 2.2 符号说明

3, 2, 116……）第i 个备选校址的建校成本 c i ：（i = αi ：（i =3, 2, 116……）学校建设成本（单位：百万元）

（i =1,2,3……16）学校建设的成本参数 βi ：

（i =3, 2, 116……）学校的选址数目 x i ：

C ：建校的总成本

3 问题分析

学校选址是一类带有复杂约束条件的优化与规划问题，在学校选址过程中，要从小区的覆盖情况、人数、费用等方面综合考虑，合理安排学校选址方案。 问题1的分析

首先，根据已知信息可知, 新开发的20个小区需要建设配套的小学, 设备选取的校址共有16个；

然后，结合附表1中备选校址表，对其进行处理分析，可知各校址覆盖的小区情况，运用整数规划中的0-1规划法，在保证每个小区至少有一个可供选择校址的前提下，列出建校方案的目标函数，并写出与其有关约束条件的不等式；

最后，通过LINGO 软件，使用计算机搜索法，算出建设学校的最少个数，由于LINGO 软件只能求解得到一种方案，因此再运用MATLAB 软件编程，求解得出的各种方案，即为在满足学校个数最少情况下的建校方案。 问题2的分析

首先, 每建一所小学的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模、学校基本设施成本构成，规模成本指学校规模超过基本规模时额外的建设成本，它与该校学生数和其所处地域有关。由题目中给出备选校址的建校成本关系式可知，在学校人数大于等于600人时，

（1）如果选择校址1~7建设学校，每增加一个人，学校的建设成本增加6000元。 （2）如果选择校址8~12建设学校，每增加一个人，学校的建设成本增加4000元 （3）如果选择校址13~16建设学校，每增加一个人，学校的建设成本增加2000元 其次，根据问题1的分析，结合题目中给出的建校成本关系式，可以算出建校个数最少时的最低成本。由于同一个小区可能被多个校址覆盖，因此在处理被多个校址覆盖的小区人数时，需要遵循两个原则，

（1）保证每个学校的学生尽量达到600人。

（2）当同一小区被不同的学校覆盖时，把该小区的学生分配到建校成本较低的学校。 （3）当建设不同校址成本相同，且都满600人时，就平均分配。

然后，通过对各小区1到6年级学龄儿童数平均值的处理分析，得到20个小区大约共有4320个学龄儿童。当每个学校的平均人数都小于600时，至少需要建设8个学校，才可能使建校费用达到最省。运用MATLAB 软件编程依次求解出学校个数为5、6、7、8时的最优建校方案，算出每个方案所花费的费用。

最后，通过对比，得出总成本最低的建校方案。

4 模型的建立与求解

4.1 模型一的建立与求解

根据问题1的分析，某地新开发的20个小区需要建设配套的小学，设备选的校址共有16个，要求出学校个数最少的建校方案，需保证每一个小区至少有一个小学可供选择，每个校址覆盖小区的情况见附表1。

我们把每个校址设为x i (i =1, 2, 3, ⋯⋯15由于每个校址覆盖小区的不同，可知同，16) ，一小区被不同校址覆盖的情况，见下表

要求出建校个数最少的方案，显然是优化问题，针对问题特殊性，我们选用0—1规划来解决这个问题。在保证每个小区的孩子至少有一个学校可供选择前提下，根据上表中每一个小区对应的不同覆盖情况，使得覆盖数必需要大于等于1，由此来列出约束条件。本问题是要解决建校个数最小的方案，即是求建校个数的最小值，用此来确定目标函数。如下：

目标函数：min z =∑x i

i =116

约束条件：

⎧∑x i ≥1(i =1, 4,5,11) ⎪i

⎪x ≥1(i =1, 4,5,11,16)

i ⎪∑i

⎪

⎪∑x i ≥1(i =4,5,8,9,11) ⎪i

⎪x ≥1(i =6,7,10, 12,14)

i ⎪∑i s . t ⎨

⎪∑x i ≥1(i =5,8,9,13) ⎪i ⎪

⎪∑x i ≥1(i =6,7,10,12) ⎪i

⎪∑x i ≥1(i =7,9,10) ⎪i

⎪x =0或1(i =1, 2,3……,16) ⎩i

∑x

i

i

≥1(i =1, 2,11,15,16) ≥1(i =2,3,6,12,15,16) ≥1(i =2,5,6,16) ≥1(i =2,3,5,6,7,12,15) ≥1(i =5,9,10，13,14) ≥1(i =8,9,13)

∑x

i

i

≥1(i =1, 2,3,15,16) ≥1(i =1, 4,8,11)

∑x

i i

i

∑x

i i

i

∑x ∑x

i

i

i

∑x ∑x

i i

i

≥1(i =5,6,9,10,14) ≥1(i =4,8,13) ≥1(i =7,9,10,14) ≥1(i =8,9,10,13)

i

∑x

i i

i

∑x

i

i

∑x ∑x

i

i

i

∑x

i

≥1(i =2,3,6,7,12,15)

计算机随机搜索的算法及编程实现

采用计算机搜索算法，我们基于三点考虑：一方面，满足约束的建校方案不止一种，应该从所有的可能方案中搜索选择最佳的建校方案；另一方面，采取计算机搜索算法可以提高模型的推广价值及结果的可信度；最后，计算机搜索避免了对结果最优的理论证明，因为在搜索过程中结果的最优性已经得到证明。

图4-1 模型1的算法流程图

同时，我们应用LINGO 软件，以题目中给出的数据为例，编程实现（见附录B ）

得出

min z =4

即最少建校个数为4个，又结合matlab 编程，可解出当建校个数为4时，各种不同的方案(过程见附录C) ，求出有22种方案，见表2

⎧1(第i 个校址被选中) x i =⎨

0(第i 个校址未选中) ⎩

4.2 模型二的建立与求解

根据问题2的分析，每建一所学校的成本由固定成本和规模成本两部分组成，固定成本由学校所在地域以及基本规模设施成本构成，规模成本是指学校规模超过基本规模时额外的建设成本，它与该校的学生数有关，同时与学校所处地域有关。由题目中给出的计算建校成本方法，即

2000⨯100⎧

(学生人数-600) 学校人数超过600⎪βi ⨯10⨯

c i =αi +⎨50

⎪学生人数小于等于600⎩0

c i 表示建校的总费用，即固定成本与规模成本的和，αi 为固定成本，βi 为计算成本

规模的系数。αi , βi 的取值和学校所处的地域即校址有关，每个校址对应不同αi , βi 的数值见附表2

由题目中给出的各个小区1到6年级学龄儿童数平均值，可知20个小区大概一共

有4320个学生，考虑到每个小学的人数都可能小于600人，至少要建8个学校，但在此问题中，要求的是总成本最低的建校方案，根据常识，如果建的学校个数越少，总成本可能也是最少的，所以在保证每个小区的孩子都有一个学校可供选择的前提下，使建校的个数尽量少，在模型一中，算出建校个数最少时为4，即我们在此只选建校个数为4，5，6，7，8的方案来进行比较，得出总费用最少的那个建校方案。

第一步：

当建校个数为4时，有22种方案（模型一中已求出），筛选出总费用最少的方案。通过matlab 对每一种方案的固定费用进行编程，求出第1种方案，第4种方案，第8种方案的固定费用都达到最低14（百万）（过程见附录D ），因此我们选用这三种方案来进行比较。取出总费用最低的方案。

由于不同校址可能同时覆盖同一个小区，因此要对小区的人数进行调配，调配原则如下：

（1）每个校址都尽量调到600左右。

（2）因为1~7七个校址，每增加一个人就得增加6000元，8~12五个校址，每增加一个人就得增加4000元，13~16四个校址，每增加一个人就得增加2000元，所以把能调配的人数，尽量分配到成本较低的校址，当然要保证前几个校址都满600人时。

（3）当建设不同校址成本相同，且都满600人时，就平均分配。

第1种方案选择5，8，10，15这四个校址，由附表1可知5，8，10，15这四个校址分别覆盖小区的情况，附表3可知每个小区的学龄儿童数。根据以上的调配原则我们对各个小区的学龄儿童数进行了合理分配，使总费用达到最少，分配方案如下：

根据以上表格可算出不同校址，建校的总费用（单位：百万元），即 校址5的分配人数等于600，即建校址5总费用为

c 5=α5 c 5=5

校址8的分配人数大于600，即建校址8的总费用为

c 8=3.5+0.1⨯0.04⨯(1110-600)

c 8=5.54

校址10的分配人数大于600，即建校址10的总费用为

c 10=3.5+0.1⨯0.04⨯(1570-600)

c 10=7.38

校址15的分配人数大于600，即建校址15的总费用为

c 15=2+0.05⨯0.04⨯(1040-600)

c 15=2.88

即建这四个校址的总费用为

C =c 5+c 8+c 10+c 15

C =20.8

第4种方案选择4，9，12，16这四个校址，按照以上的调配原则，对这四个校址进行人数的分配，如下表

按照以上算每个校址的总费用的方法，分为人数小于等于600，大于600的两种情况来进行计算，可得建校的总费用如下表

即建这四个校址的总费用为

C =5+9.06+4.7+2.46

C =21.22

第8种方案选择2，10，11，13这四个校址，按照同样的方法，算出建这四个校址的总费用，如下表

由以上表格可知，建这四个校址的总费用为

C =7.46+5.74+4.22+3.54

C =20.96

通过对以上的三种方案进行比较，可知当建校个数为4时，选择第1种方案，校址为5，8，10，15时，建校的总费用达到最小

C =20.8

第二步：

当建校个数为5时，用matlab 编程求解出有349种方案可供选择，在求出349方案的基础上，进行编程求出第1种方案的固定费用达到最小，为13（百万）。

第1种方案选择10，11，13，15，16这五个校址，根据这五个校址覆盖小区的情况进行人数调配，使费用达到最少，同以上的方法，可求出不同校址分配人数及建校的总费用，见下表

根据上表可知，建这五个校址的总费用为

C =5.74+3.5+3.54+2+2

C =16.78

第三步：

当建校个数为6时，编程求解出有1781种方案可供选择，在求出不同方案的基础下，进行编程求出第1种方案的固定费用达到最小，为15（百万元）。

第1种方案选择10，11，13，14，15，16这六个校址，在保证费用达到最少的前提下，对人数进行调配，进而求出不同校址分配人数及建校的总费用，如下

通过以上表格，可算出建这六个校址总费用为

C =3.58+3.5+3.1+2.32+2+2

C =16.5

第四步：

当建校个数为7时，编程求解出有4702种方案可供选择，在这基础上求出第1种方案的固定费用达到最低为18.5（百万元），由于它最小的固定费用都大于当建校个数为5，6时的总费用，因此把建校个数为7这种情况剔除。

第五步：

当建校个数为8时，求解出有7718中方案可供选择，在第1种方案时固定费用达到最低为22（百万），因为它最小的固定费用都大于当建校个数为4，5，6时的总费用，所以把建校个数为8这种情况剔除。

通过以上的五步计算出来的结果，进行比较，可得当建校个数为6，校址为10，11，13，14，15，16时，建校的总成本达到最小值16.5（百万元）。

5 灵敏度分析

由于本案例中对模型结果产生的影响因素有很多，我们在此选取了关键的参数进行灵敏度分析。模型对这些参数的敏感性反映了各种因素影响结果的显著程度，通过对这些参数的灵敏度分析，对模型的推广提出合理性的建议。 5.1 模型一

当改变校址个数时，建校的最少个数，以及在此情况下的建校方案可能会随着变化，对此我们把校址增加，以此来验证模型一的灵敏度。

增加的校址: 校址1 覆盖小区 2、4、5、9、10 校址1 覆盖小区 3、6、7、13、15 校址1 覆盖小区 1、8、18

、19、20 校址1 覆盖小区 11、12、14、16、17

（注：覆盖的小区的选择是把20个小区随机分配给增加的四个校址） 运用LINGO 软件编程求解，得出下表：

由上表可知，当备选校址增加到17、18、19、20个时，最少的建校个数依然为4个，并且建校方案随着备选校址的增加而增加。

5.2 对于模型二

由于建校的总费用和固定成本αi ，系数βi ，学生的人数有关，根据题意，建校的固定成本αi 是影响最优方案的重要因素，假设在系数βi 、学生人数不变的情况下，对模型二中的固定成本αi 进行灵敏度分析。

随着社会的不断进步，房价也随之增高，根据资料显示，固定成本αi 平均每年增长率为10%。由于建校个数为5、6时，总成本相差不多，所以以下只考虑这两种情况，来进行说明。

当建校个数为5时，由模型二算出的最小总成本C =16.78（百万元）。在学生人数、系数βi 保持不变的前提下，固定费用αi 增加10%，通过编程求出总的成本为C =18.08（百万元）。

当建校个数为6时，由模型二得出最小总成本C =16.5（百万元）。在保证学生人数、系数βi 不变的前提下，固定费用αi 增加10%，求得总成本为C =18（百万元）。

在以上的基础上，固定费用αi 再增加10%，求得当建校个数为5时，总成本C =19.51（百万元）。当建校个数为6时，总成本C =19.65（百万元）。

在第二年里最优方案就不再是建校个数为6时，这说明在第二年时就要考虑换方案，因为这时建校个数为6时达不到最优。

6 模型的评价与推广

6.1 模型的评价 优点

1 建立的优化模型有成熟的理论基础，又有相应专业软件进行计算，得出的结果比较精确，可信度较高

2 模型原理简单明了，容易理解与灵活运用

3 建立的模型与实际紧密联系，充分考虑现实情况的多样性，从而使模型更贴近实际，通用性、推广性较强。 缺点

1 模型建立过程中，仅考虑了题中所给的几个参数对学校选址问题的影响，没有考虑到其它因素带来的影响。

2 模型复杂因素较多，不能对其进行全面的考虑，造成与实际有一定的不相符之处 6.2 模型的推广

本模型在计算过程中使用了lingo 软件，并采用直接输入的方法进行编程计算，配有流程图，使模型在解决可能的实际问题时能够较方便的找出结果，从而更容易推广到其他的选址问题，例如，消防站的选址、医院等公共基础设施的选址。

7 参考文献

[1] 吴建国主编《数学建模案例精编》中国水利水电出版社 2005.5 [2] 钱小军主编 《数量方法》 高等教育出版社 1999.8

[3] 孙祥 徐流美 吴清编著《MATLAB7.0基础教程》清华大学出版社 2005.5 [4] 姜启源 谢金星 叶俊主编《数学模型》（第三版）高等教育出版社 2003.2 [5] 吴振奎、王文全 主编 《运筹学》，中国人民大学出版社，2004

8 附录

附录A

附录B

确定最少校址个数：

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+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;a x5+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+x9+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 x k=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 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+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+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+x12+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+%d\n',z,x1,x2,x3,x4,x5,x6,x7,x8,x 9,x10,x11,x12,x13,x14,x15,x16);

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

end end end end k

附录D

计算每种方案的固定成本 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+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+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+x12+x15>=1&x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16==6 z=x1+x2+x3+x4+x5+x6+x7+x8+x9+x10+x11+x12+x13+x14+x15+x16;

k=k+1;

s=x1*5+x2*5+x3*5+x4*5+x5*5+x6*5+x7*5+x8*3.5+x9*3.5+x10*3.5+x11*3.5+x12*3.5+x13*2+x14*2+x15*2+x16*2;

fprintf(' 第%d种:',k)

fprintf('%d=%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d+%d----%d\n',z,x1,x2,x3,x4,x5,x6,x 7,x8,x9,x10,x11,x12,x13,x14,x15,x16,s);

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

end end end end