文档介绍：校园卡充值点的最优位置
[摘要]本论文建立了校园卡充值点安排方案的最优化模型,为方便学生,让学生能够走最短的距离去充值点。在使各学院、楼栋、学生宿舍区到三个校园卡充值点的总路程最少的要求下,我们使用图论软件模拟计算出各学院、楼栋、学生宿舍区之间的最短距离,建立“0-1”模型,使用“启发式贪婪算法”,运用Lingo软件计算出三个最优点。最后在讨论分析后,对模型作出评价和改进,并结合实际情况对计算最优点的位置的方法进行改进。
模型:对题目中所给的各学院、楼栋、学生宿舍区之间的距离及路线,建立化折线为直线的模型。通过软件计算各点之间的最短距离,再用直线来代替折线连接任何两点,从而使得各点之间都是通过直线直接连接。结果见附录1。针对提出的问题,建立了最优化模型和“0-1”模型,使用“启发式贪婪算法”方便的求出较理想的三个点,并进一步求出它们之间的路线和总的最短距离。为了得到最优解,我们运用Lingo软件计算出三个最优点:6区(医学实验楼)、12区(基础实验大楼)和21区(教学主楼),。
本论文是从两栋楼之间的距离、楼栋分布的关系的变化分别对模型的灵敏度进行了分析。最后,结合实际情况,对模型进行了进一步的讨论,并给出了该进的目标函数,并提出了将该模型推广应用的领域。
关键词:图论软件“0-1”模型启发式贪婪算法 Lingo软件整数线性规划

1问题的提出
校园卡为广大校园中人的生活、工作、教学提供了极大的便利。在就餐、乘车、购物中,有了校园卡,一切事情都变得畅通无阻、简单易行。校园卡已成为我校师生日常生活中不可缺少的随身携带的物品,不过,近日来校园卡管理部门也收到一些有关校园卡充值方面的意见和抱怨,有部分师生反映现有的三个校园卡充值点主要集中在本科生公寓区(A区,B区,C区)布局不尽合理,有些学院距离充值点太远,步行来回要40到50分钟。希望校园卡管理部门对现有的校园卡充值点的布局作一些相应调整,使之更趋合理。
为此,校园卡管理部门在校园网上发布了一个通告,通告要求根据附图所示的各学院、楼栋、学生宿舍区的位置,在南昌大学新校区中重新确定三个校园卡充值点的最优位置(充值点设在某学院、楼栋、学生宿舍区),使从各学院、楼栋、学生宿舍区到三个校园卡充值点的总路程最少。

下图为校园简化示意图:图中vi表示各学院、楼栋、学生宿舍区的位置,连线为两点间道路,连线上数字为两点间距离(单位:公里)。
需要解决的问题
(1)问题1。结合上面的校园简化示意图,建立模型,计算出任意两个学院、楼栋、学生宿舍区的最短距离。
(2)问题2。结合问题(1)中所求的最短距离,建立自己的模型,为学校确定三个校园卡充值点的最优位置(充值点设在某学院、楼栋、学生宿舍区),使从各学院、楼栋、学生宿舍区到三个校园卡充值点的总路程最少。

2问题的分析
确定校园卡充值点的最优位置的问题是一个带约束条件较少的线性规划问题。对本问的处理的难处是同时考虑对三个点的总距离和最少。在实际生活中,影响选择最优充值点的因素很多。主要因素有各学院、楼栋、学生宿舍区之间距离、路线,各学院的学生人数,各楼栋上课教室安排,充值时间间隔,上课时间,学生老师的习惯充值时间,学校充值点的设备及容量大小等。在这些因素中,各学院、楼栋、学生宿舍区之间的距离和路线是影响该问题的主要因素,针对这个问题建立模型。由于是求各学院、楼栋、
学生宿舍区到三个充值点之间的最短距离,所以这应该属于整数线性规划问题。
按照上述思路要提出目标函数,要建立各个约束条件,要找出各点之间的最短距离。因而,对约束条件和问题作出分析都是解问题的关键。

由于题目要求重新确定三个校园卡充值点的最优位置(充值点设在某学院、楼栋、学生宿舍区),使从各学院、楼栋、学生宿舍区到三个校园卡充值点的总路程最少。所以可以得到以下条件:
(1)各学院、楼栋、学生宿舍区只能去一个充值点。
(2)各学院、楼栋、学生宿舍区到三个充值点之间的距离和最短。

(1)的分析
结合约束条件,问题主要包含两层意思:(1)两栋楼之间要有路线连接才能通过。
(2)任何两栋楼之间的路线最短。对于那些之间有路线连接的两栋楼,它们的最短距离就是连线上的数值;对于那些两点之间没有直接连接起来的两栋楼,它们是通过多条路线连接的,所以应该让学生走它们之间的最短路线。这个问题可以用图论软件解决,并采用化折线为直线的模型。
(2)的分析
求出路程最短点是运筹学中的目标规划问题,即在28栋楼中找出三个点,让其他
25栋楼到这三栋楼之间的路程和最小。我们可以运用Lingo软件编程计算。
3 模型的假设
(1)为了方便起见,规定按图