学校选址问题模型数学建模.pdf

学校选址问题 摘 要 本文针对某地新开发的 20 个小区建设配套小学问题建立了 0 1 规划模型和 优化模型 为问题一和问题二的求解 提供了理论依据 模型一 模型一 首先 根据目标要求 要建立最少学校的方案列出了目标函数 16 1i i xs 然后 根据每个小区至少能被一所学校所覆盖 列出了20个约束条件 最后 由列出的目标函数和约束函数 用 matlab 进行编程求解 从而得到 在每个小区至少被一所学校所覆盖时 建立学校最少的个数是四所 并且一共有 22种方案 模型二 模型二 首先 从建校个数最少开始考虑建校总费用 在整个费用里面 主要是固定 费用 由此在问题一以求解的条件下 进行初步筛选 得到方案 1 4 8 的固定成 本最少 然后 在初步得出成本费用最少时 对每个这三个方案进一步的求解 求出 这三个方案的具体的总费用 并记下这三套方案中的最小费用 其次 对这三套方案进行调整 调整的原则是 在保证每个小区有学校覆盖 的条件下 用多个固定成本费用低的备选校址替换固定成本费用高的备选校址 在替换后 进行具体求解 再次 比较各种方案的计算结果 从而的出了如下结论 选用 10 11 13 15 16 号备选校址的选址方案 花费最少 最少花费为13378000 元 最后 对该模型做了灵敏度分析 模型的评价和推广 关键字 关键字 最少建校个数 最小花费 固定成本 规模成本 灵敏度分析 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 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 2 问题提出 问题提出 问题一问题一 求学校个数最少的建校方案 并用数学软件求解 说明你所使用的 软件并写出输入指令 问题二问题二 设每建一所小学的成本由固定成本和规模成本两部分组成 固定成 本由学校所在地域以及基本规模学校基础设施成本构成 规模成本指学校规模超 过基本规模时额外的建设成本 它与该学校学生数有关 同时与学校所处地域有 关 设第i个备选校址的建校成本 i c可表示为 否则 若学生人数超过学生人数 0 600 600 50 1002000 i ii c 其中 i 和 i 由表 1 2 给出 表 1 2 学校建设成本参数表 单位 百万元 备选校址 1 2 3 4 5 6 7 8 i 5 5 5 5 5 5 5 3 5 i 0 15 0 15 0 15 0 15 0 15 0 15 0 15 0 1 备选校址 9 10 11 12 13 14 15 16 i 3 5 3 5 3 5 3 5 2 2 2 2 i 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 学龄儿童数 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 符号说明符号说明 1216 i x i 备选的第个i校址 s一共要建立学校的个数 i 1 2 3 i 第i个学校建校的固定成本 i 1 2 320 i 第i个学校建立的规模成本系数 1 2 316 i ci 第i个校址所需要花费的成本 t学生人数 1 2 316 i g i 第i个校址中所容纳学生人数 i 1 2 320 i a 第i个小区入学人数 i 1 2 3 i m 第i种方案的固定成本 i 1 2 3 i w 第i种方案的最少花费 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 50600 元 每人 整个小区里人学年龄儿童的总人数 20 1 4320 i i ta 1 除去每所学校基本容纳600人后 最大的规模成本费用是 0154320 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 模型一的求解 模型一的求解 根据问题一的分析 建立模型一 要建立学校个数最少 其目标函数是 16 1i i xs 2 将表 1 1 进行加工 将第 i a个小区被第 i x备选校址覆盖记为1 否则为0 得到表 4 1 表 4 1 各个备选校址覆盖的小区 小小 区区 1 2 3 4 5 6 7 8 9 1 0 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 2 0 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 可得约束条件如下 X1 14511 12111516 1231516 1451116 2361216 148911 4589 25616 5691014 67101214 235671215 48 1 1 1 1 1 1 1 1 1 1 1 xxxx xxxxx xxxxx xxxxx xxxxx xxxxx xxxx xxxx xxxxx xxxxx st xxxxxxx xx 13 58913 59101314 791014 671012 8913 891013 7910 23671215 1 1 1 1 1 1 1 1 1 x xxxx xxxxx xxxx xxxx xxx xxxx xxx xxxxxx 3 1 运行附录 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 共有人数 514789111314 a 1280gaaaaaaa人 4 8 号校址覆盖的小区 6 7 12 13 17 18 共有人数 86712131718 g a 1510aaaaa人 5 10 号校址覆盖的小区 9 10 14 15 16 18 19 共有人数 109101415161819 a 780gaaaaaa人 6 15 号校址覆盖的小区 2 3 5 11 20 共有人数 152351120 a 1040gaaaa人 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人 否则 若学生人数超过学生人数 0 600 600 50 1002000 i ii c 5 8 10 15 5000000 3500000 0 1 2000 100 50 920 600 3628000 3500000 0 1 2000 100 50 1760 600 3964000 2000000 0 05 2000 100 50 1040 600 2088000 c c c c 8 1581015 c wccc 9 共需最小花费 1 14680000 w元 同理方案同理方案 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人 共需最小花费 4 14722000 w元 同理方案同理方案 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人 共需最小花费 8 14696000 w元 对上述三种方案中 总费用最少的是方案一 花费为14680000元 从表 1 2 的数据可看出 在 13 14 15 16 号备选校址建两所学校的固定成本小 于 1 2 3 4 5 6 7 好备选地址 对上面的三种方案根据问题二的分析进行调整 方案方案 1 的最优调整方案的最优调整方案 不选用 5 号备选地址 改为 11 号和 16 号 这时的固定成本为 23810111516 14500000m 元 10 此时在没有规模成本下 最多可容纳学生 5 600 3000t人 11 剩下的学生 4320 3000 1320t人 12 这部分学生所产生的最低规模成本 1320 2000 100 50 0 05 264000 13 所以在方案一调整后的最少费用 23 14500000 236000 14736000 w元 14 因为在调整后的费用 231 ww 该调整方案不可行 同理 对方案同理 对方案 4 进行调整 建立五所学校 进行调整 建立五所学校 将 4 号备选校址改为 11 号和 13 号备选地址这时的固定成本为 24911121316 14500000m 元 15 此时在没有规模成本下 最多可容纳学生 5 600 3000t人 16 剩下的学生 4320 3000 1320t人 17 这部分学生所产生的最低规模成本 1320 2000 100 50 0 05 264000 18 所以在方案一调整后的最少费用 23 14500000 236000 14736000 w元 19 因为在调整后的费用 241 ww 该方案不可行 同理 对方案同理 对方案 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人 所需花费 25 13378000 w元 在建立五所学校时 考虑到是否存在建立四所固定成本最低的学校和一所固 定成本较高的的学校 分析可知 要建立的四所低固定成本的学校只能选 13 14 15 16 号备选地址 而在这些学校覆盖后还有 1 6 7 19 号小区没有被学校覆盖 根据表 4 1 可知 没有一所学校能同时覆盖这四个小区 所以在建立五所学校学 校时 不存在这种情况 综合可知 其花费是 25 13378000 w元 将方案继续调整 将方案继续调整 若建立六所学校 固定成本w最小是建立四所固定成本2000000和两所固定 成本3500000 此时费用为 15000000w 大于 25 w所以不可行 如再多建立学校 均大于对方案 8 调整后的成本 所以 选用 10 11 13 15 16 号备选地址的花费最 小 最小为13378000元 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 规划模型 在实际生活中有着一定的使用空间 该 模型不仅可以对学校选址问题 还可以解决类似与该相似的选址问题 如 餐饮 选址问题 邮局选址 连锁店选址