摘 要
本文针对某地新开发的20个小区建设配套小学问题建立了0-1规划模型和优化模型。为问题一和问题二的求解,提供了理论依据。 模型一:
首先:根据目标要求,要建立最少学校的方案列出了目标函数: 然后:根据每个小区至少能被一所学校所覆盖,列出了个约束条件;
最后:由列出的目标函数和约束函数,用matlab进行编程求解,从而得到,在每个小区至少被一所学校所覆盖时,建立学校最少的个数是四所,并且一共有种方案。
模型二:
首先:从建校个数最少开始考虑建校总费用,在整个费用里面,主要是固定费用,由此在问题一以求解的条件下,进行初步筛选,得到方案1,4,8的固定成本最少。
然后:在初步得出成本费用最少时,对每个这三个方案进一步的求解,求出这三个方案的具体的总费用,并记下这三套方案中的最小费用。
其次:对这三套方案进行调整,调整的原则是:在保证每个小区有学校覆盖的条件下,用多个固定成本费用低的备选校址替换固定成本费用高的备选校址。在替换后,进行具体求解。 再次:比较各种方案的计算结果,从而的出了如下结论:
选用10,11,13,15,16号备选校址的选址方案,花费最少,最少花费为元。
最后:对该模型做了灵敏度分析,模型的评价和推广。
关键字:最少建校个数 最小花费 固定成本 规模成本 灵敏度分析 1. 问题重述
1.1问题背景:
某地新开发的20个小区内需要建设配套的小学,以方便小区内居民的的孩子上学。但是为了节省开支,建造的学校要求尽量的少,为此,设备选定的16个校址提供参考,各校址覆盖的小区情况如表1所示:
表1-1备选校址表
备选校址 | 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,7,8,9,11,13, 14 | 5,8,9,10 11,16,20 | 10,11,1516,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.2 问题提出:
问题一、求学校个数最少的建校方案,并用数学软件求解(说明你所使用的软件并写出输入指令)。
问题二、设每建一所小学的成本由固定成本和规模成本两部分组成,固定成本由学校所在地域以及基本规模学校基础设施成本构成,规模成本指学校规模超过基本规模时额外的建设成本,它与该学校学生数有关,同时与学校所处地域有关。设第个备选校址的建校成本可表示为
其中和由表1-2给出:
表1-2 学校建设成本参数表(单位:百万元)
备选校址 | 1 刘子蔚 | 2 | 3 | 4 | 虚拟主持人5 | 6 | 7 | 8 |
| 5 | 5 | 5 | 5 | 5 | 5 | 5 | 3.5 |
| 0.15 | 0.15 | 0.15 | 0.15 | 0.15 | 0.15 | 0.15 | 0.1 |
备选校址 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 3.5 | 3.5 | 3.5 | 3.5 | 2 | 2 | 2 | 2 |
| 0.1 | 0.1 | 0.1 | 0.1 | 0.05 | 0.05 | 0.05 | 0.05 |
| | | | | | | | |
考虑到每一小区的学龄儿童数会随住户的迁移和时间发生变化,当前的精确数据并不能作为我们确定学校规模的唯一标准,于是我们根据小区规模大小用统计方法给出每个小区的学龄儿童数的估计值,见表1-3:
表1-3.各小区1到6年级学龄儿童数平均值(样本均值)
小区 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 vrml实例 |
学龄儿童数 | 120 | 180 | 230 | 120 | 150 | 180 影片未分级 | 180 | 150 | 100 | 160 |
小区 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
学龄儿童数 | 180 | 240 | 210 | 220 | 280 | 260 | 320 | 380 | 360 | 300 |
| | | | | | | | | | |
考虑总成本最低的建校方案。
2. 模型假设与符号说明
2.1模型假设:
(1)入学的学生按照学校规划的人数进行入学。
(2)学校的建立不受地区和学生人数的影响,一旦确定就可顺利的建起。
(3)所建立的学校的规模可大可小。
(4)各小区的学生上学不受交通拥挤等的客观因素的影响。
2.2符号说明
备选的第个校址;
一共要建立学校的个数;
第个学校建校的固定成本;
第个学校建立的规模成本系数;
第个校址所需要花费的成本;
学生人数;
第个校址中所容纳学生人数;
第个小区入学人数;
第种方案的固定成本;
第种方案的最少花费;
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中,费用为:
整个小区里人学年龄儿童的总人数:
(1)
除去每所学校基本容纳人后,最大的规模成本费用是:
该费用远小于13,14,15,16号备选校址中的固定成本元,所以在建校个数相同时,费用的高低主要取决于固定成本,固定成本高,使整个建校方案成本高,固定成本低,是整个建校的成本减少,所以在选用地址时,优先考虑13,14,15,16号地址其次8,9,10,12号地址,最后1,2,3,4,5,6,7号地址。
其次:在初步筛选出的学校备选地址中,算出这些方案中花费的成本,比较并记下在建立最少个数学校时,花费最省的方案。
再次:对已选出的最少建校方案中进行调整,调整的原则是:在保证每个小区至少有一所学校所覆盖,将一所固定费用高的学校用两所固定费用小的代替。
最后:比较出各方案的费用,得出建立学校的最小费用。
4. 模型建立与求解
4.1模型一的求解:
根据问题一的分析,建立模型一:
要建立学校个数最少,其目标函数是:
(2)
将表1-1进行加工,将第个小区被第备选校址覆盖记为,否则为,得到表4-1;
表4-1 各个备选校址覆盖的小区
小区 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | ghtt8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 |
1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
3 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
4 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
5 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
6 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
7 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
9 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 0 |
10 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | 0 |
11 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
12 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
15 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
16 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| | | | | | | | | | | | | | | | | | | | |
横坐标:小区编号
纵坐标:备选校址的编号
由每个小区至少能被一所学校所覆盖及表4-1可得约束条件如下:
(3)
运行附录A的程序,解出得到满足该条件的建校方案有22种,分别如下表4-2:
表4-2 建立四所学校的选址各种方案
方案 | 1 | 2 | 3 | 4 | 5 | 6 |
校址 | 5,8,10,15 | 5,7,8,16 | 5,7,8,15 | 4,9,12,16 | 4,7,9,16 | 4,6,9,16 |
方案 | 7 | 8 | 9 | 10 | 11 | 12 |
校址 | 2,8,10,11 | 2,5,8,10 | 2,5,7,8 | 2,4,10,13 | 2,4,9,12 | 2,4,9,10 |
方案 | 13 | 14 | 15 | 16 | 17 | 18 |
校址 | 2,4,6,9 | 1,6,9,13 | 1,6,8,10 | 1,6,8,9 | 1,4,6,9 | 1,2,8,10 |
方案英语课文 | 19 | 20 | 21 | 22 | | |
校址 | 4,6,9,15 | 2,10,11,13 | 2,4,8,10 | 2,4,7,9 | | |
| | | | | | |
4.2模型二的求解:
由问题二的分析,先考虑在模型一中的结果中筛选出方案1,4,8的固定成本最少,下面对各方案进行计算:
方案1中建校最少花费的费用:
方案一选用5,8,10,15号校址,每个备选校址能覆盖的小区及所容纳的学生数量:
5号校址覆盖的小区:1,4,7,8,9,11,13,14 共有人数:
(4)
8号校址覆盖的小区:6,7,12,13,17,18 共有人数:
(5)
10号校址覆盖的小区:9,10,14,15,16,18,19 共有人数:
(6)
15号校址覆盖的小区2,3,5,11,20 共有人数:
(7)
学生入学最佳方案,先各校满足有人,然后优先考虑15号校址然后考虑10号和8号校址,最后考虑5号校址。那么,学生最优的入学安排如下:
5号校址覆盖1,4,7,8和13号小区里的30人,共人;
8号校址覆盖6,12,17和13号剩余的部分学生 共人
10号校址覆盖 9,10,14,15,16,18,19号小区,共人;
15号校址覆盖 2,3,5,11,20 共 人
(8)
(9)
共需最小花费元;
同理方案4的最小花费的费用:
4号校址覆盖1,6,12和7号小区的人 共 ;
9号校址覆盖9,13,14,15,17,18,19和7号小区的人 共人;
12号校址覆盖10,11,16,20号小区 共有人
16号小区覆盖2,3,4,5,8,号小区 共人
共需最小花费元;
同理方案8的最小花费的费用是:;
2号校址覆盖3,5,8,11,20号小区 共人;
10号校址覆盖9,10,15,16,19号小区,共人;
11号校址覆盖1,2,4,6,7号小区 共有人;
13号校址覆盖12,13,14,17,18号小区 共有人;
共需最小花费元。
对上述三种方案中,总费用最少的是方案一,花费为元。
从表1-2的数据可看出,在13,14,15,16号备选校址建两所学校的固定成本小于1,2,3,4,5,6,7好备选地址,对上面的三种方案根据问题二的分析进行调整:
方案1 的最优调整方案:
不选用5号备选地址,改为11号和16号,这时的固定成本为
(10)
此时在没有规模成本下,最多可容纳学生
(11)
剩下的学生
人 (12)
这部分学生所产生的最低规模成本
(13)
所以在方案一调整后的最少费用
元 (14)
因为在调整后的费用,该调整方案不可行;
同理,对方案4进行调整,建立五所学校:
将4号备选校址改为11号和13号备选地址这时的固定成本为
(15)
此时在没有规模成本下,最多可容纳学生
(16)
剩下的学生
人 (17)
这部分学生所产生的最低规模成本
(18)
所以在方案一调整后的最少费用
元 (19)