学校选址问题
- 格式：doc
- 大小：33.50 KB
- 文档页数：7
如果您需要使用本文档，请点击下载按钮下载!
授课：XXX 数学建模（学校选址问题）
选址问题
背景 现如今，教育普及，学校的建设问题也就成为了一个需要考虑的问题。现在，某地新开发的20个小区需要建设配套的小学，设备选的校址共有16个，各校址覆盖的小区情况如下表所示：
备选校址 1 2 3 4 5 6 7 8
覆盖小区 1,2,3,
4,6 2,3,5,8,
11,20 3,5,11,20 1,4,6,7,
12 1,4,8,7,9,
11,13,14 5,8,9,10,
11,16,20 10,11,15,
16,19,20 6,7,12,
13,17,18
备选校址 9 10 11 12 13 14 15 16
覆盖小区 7,9,13,
14,15,17,
18,19
9,10,14,
15,16,18,
19 1,2,4,6,
7 5,10,11,
16,20,
12,13,14,
17,18 9,10,14,
15 2,3,,5,
11,20 2,3,4,
5,8
现在要用最少的校区，包含全部的小区，这问题关系到土地问题，应此，先建立以下模型。
本模型先建立矩阵，由于一个小区只需在一个校址内即可，所以再编程求解出所选校址。
模型假设 一、假设校区可以建得很大，也可以建的很小，不影响其他校区的建立。
二、假设任意小区到可选择的任意校区都一样，距离不考虑。
模型建立 建立矩阵，行表示备选校址，列表示小区号。若某校址能覆盖某小区，则在矩阵的相应位置上添“1”，否则添“0”，为了使矩阵成为方阵，故在矩阵的行最后添加四行全为“0”的行。最终，建立了一下矩阵：A=[
1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 如果您需要使用本文档，请点击下载按钮下载!
授课：XXX 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1如果您需要使用本文档，请点击下载按钮下载!
授课：XXX 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1
0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0
1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]
模型求解 对于以上方阵，可先将它与一个20行1列的矩阵B=[1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1]相乘，所得的结果就是各个小区所覆盖的小区数。由于本题是要求最少的校区，因此可先选择出覆盖最多的校区，然后将该校区所覆盖的小区全部删去，所以在矩阵里，只需将含“1”最多的行里面，反是“1”的位置的列的所有元素都变成“0”。如此反复，就会在最后一步发现只有矩阵的每一行最多只有1个“1”，且这个“1”在同一列。这样，只要记录下以上用来处理数据使列变零的行的行数，就是所需选出的校区。
这里，对于含“1”数相同，且都是最多的情况，采用矩阵变换后，变后的矩阵各行含一数较大的方式进行变换。如：若某一次变换可有两种选择，则将两种都分别变换，比较变换后的矩阵，看这两个矩阵中含“1”最多的行，哪个行含“1”多，则采用哪种变换。
（以上都是用MATLAB编程实现，具体程序见附录）
最后可以根据MATLAB里所得到的数据，再综合实际情况，加以选址。
计算的结果是，校区选择9 6 1三个，然后再在4 8 13中任选一个，一般选择包含小区最多的校址。所以本方法选出的最少校区为4个。
因此可选用1 6 8 9 四个校区，就可将20个小区都包含在内。对于一个小区，去两个或三个校区都可以的问题，可以根据建校离小区的距离来决定到底去哪个校区。如果您需要使用本文档，请点击下载按钮下载!
授课：XXX
模型推广和分析 本模型可以教方便的找出结果，且很容易推广到其他的选址问题，但是，未考虑到一些的实际问题，比如交通问题，小学生从家到校的安全问题，校区建成的成本，各小区人数等问题。
就本题而言，本程序所求出的个数4个，用很多其他方法程序也可求出，但本程序有个优点，就是本程序对于更多的数据，也可处理，且程序不用变。
附录 先编写函数f0，用来计算哪一行所包含的“1”最多（其中C=A*B）：
function y=f0(C)
s=0;
for i=1:20
if C(i)>s
s=C(i);
j=i;
end;
end
y=s;
再编写函数f1，用来计算哪几行都包含了最多的相同数目的“1”，输出的是该行的行数：
function y=f1(A,C)
s=f0(C);
k=1;
for i=1:20
if C(i)==s
t(k)=i;
k=k+1;
end;
end
y=t;
然后编写函数f2，用来将选出行中，为“1”的数的所在列的数都变成“0”：如果您需要使用本文档，请点击下载按钮下载!
授课：XXX function y=f2(A,b)
for k=1:20
if A(b,k)==1;
A(:,k)=0;
end;
end;
y=A;
然后编写程序f3，用来记录到底该选用哪一行，原则是变换后的矩阵，所有行中含“1”的个数最多的行，此行的含“1”数较多：
function y=f3(A,x)
B=[1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1];
p=size(x);
j=p(2);
D=A;
b=0;
for i=1:j
z=f2(D,x(i));
C=z*B;
m=f0(C);
if m>b
b=m;
yy=x(i);
end
D=A;
end;
y=yy;
最后，编写总程序，用来输出必选的行数(answer),和可选择的最后一行(x)：
A=[1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0如果您需要使用本文档，请点击下载按钮下载!
授课：XXX 0 1 1 0 1 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1
0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0
1 0 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 0 0 0
0 0 0 0 1 0 0 1 1 1 1 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 1 1
0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 1 1 0 0
0 0 0 0 0 0 1 0 1 0 0 0 1 1 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 0 1 1 0
1 1 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 0 0 0 0 0
0 1 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1
0 1 1 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0];
B=[1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1;1];
C=A*B;
D=A;
k=1;
w=f0(C);
while w>1
x=f1(D,C);
b=f3(D,x);
a(k)=b;
k=k+1;
D=f2(D,b);
