摘 要：在日常生产和生活中，往往有一类问题是关于有限的资源在一定条件下的合理利用问题，且要达到最大的利益或者价值。其中包含站点的位置选址问题，通常我们把这类问题归纳为整数规划中的最优问题，利用MATLAB软件我们可以轻松的得到问题的数值解。但对站点的位置选址问题，我们发现利用图论的理论，从图论角度进行分析和求解，可以更轻松。
关键词：整数规划；0-1规划；图论；孤立点
中图分类号：F22 文献标志码：A 文章编号：1673-291X（2013）07-0307-02
引言
数学模型（Mathematical Model）是用数学符号对一类实际问题或实际发生的现象的（近似的）描述。数学建模（Mathematical Modeling）则是获得该模型并对之求解、验证并得到结论的全过程。数学建模不仅是了解事物的基本规律，而且从应用的观点来看更重要的是预测和控制所建模的系统行为的强有力的工具[1]。图论是运筹学的一个重要分支，它是以图为研究对象，图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点表示事物，用连接两点间的线表示相应的两个事物之间具有的特定关系[2～3]。图论应用领域广泛，随着科学技术的发展和计算机的出现与广泛的应用，图论的理论得到了进一步的发展。特别是庞大的复杂系统工程和管理问题都可以转换成图的问题，从而可以解决很多工程设计和管理决策中的最优化问题。在本文中，我们引入下述两个案例：救护站的选址问题和消防站选址问题[4～5]，应用图论理论，根据实际问题的要求，在布点选址过程中不应该出现孤立点的结点，可以得到更简单的解决思路和方法。
一、问题简述
问题1：救护站的选址问题
某市有8个行政区，各区之间的救护车辆的行车时间（单位：min）（如表1所示）。市政府拟在市区内建立公共救护中
表1 各区之间的行车时间表
心，设计要求从各区到救护中心的行车路线都不超过10min。该市政府请你提供可行的设计方案：全市至少要建几个救护中心，具体建立在哪个区？
问题2：消防站的选址问题
某城市的消防总部将全市划分为11个防火区，现有4个消防站，图1给出的是该城市防火区域和消防站的位置示意。其中①，②，③，④表示消防站，1，2，…，11表示防火区域。根据历史的资料证实，各消防站的可在事先规定允许的时间内对所负责的区域火灾予以扑灭，图中虚线即表示各地区有那个消防站负责，没有虚线连接的表示不负责。现在总部提出：能否减少消防站的数目，仍能保证负责各地区的防火任务？如果可以的话，应当关闭那个？
图1 各城区和消防站示意图
二、救护站选址问题的分析与解决
对于问题1，我们通过各区之间的行车时间表数据建立各区之间的交通图，在该图中，我们过滤行车时间超过10分钟的数据，得到下页图2：各区之间不超过10分钟的交通图。
图2 各区之间不超过10分钟的的交通图
由于设置公共救护中心的宗旨是各区都应该能够救护到，且救护时间不超过10分钟，因此如果我们建立去掉某个区域的子图，子图中应该没有孤立点，这样就可以判定该区域是否应该保留。通过对图2去掉区域1，建立相应的子图，我们可以发现区域1去掉后，会有2、7两个区域形成孤立点，因此1区域应该建立公共救护中心，它解决了1、2、7区域的救护问题。而对3、4、5、6、8号区域进行分析，可以发现8号区域只和6号区域连通，去掉6号区域，8号区域将成为孤立点，而去掉其他各点都不会形成孤立点。因此分析可以得到：该问题最少要建立两个救护站，分别在1、6号区域设立公共救护站，就可以覆盖8个区域，实现公共救护问题。
三、消防站问题的分析与解决
在这个问题中，①，②，③，④四个消防站负责11个消防区域，现在的问题是能否减少消防站的数目，仍能保证各地区的防火任务？和上个问题的解决思路是一致的。如果我们建立去掉某个消防站的子图，那么根据消防的宗旨，应该在相应的子图中没有孤立点。当我们去掉①号消防站后，可以发现3号区域成为孤立点；当我们去掉③号消防站后，可以发现5号区域成为孤立点；当我们去掉④号消防站后，可以发现10号区域成为孤立点。唯有在去掉②号消防站后，没有孤立点的形成。因此②号消防站属于重复建设，可以去掉，并且对全市的消防安全没有影响。图3是去掉①号消防站，3号区域变成孤立点的示意图。
图3 去掉①号消防站的示意图
四、归纳总结
如何在条件允许的范围内，尽可能地找出一个“最好”的办法，把需要的事情做好始终是运筹学的中心问题 [5～6]。随着运筹学的分支越来越细密，理论方法越来越完善，研究领域越来越广泛，运筹学的实际意义也越来越凸显[7～8]。从不同的方法在解决同一个问题的灵活性上，我们可以看出运筹学中方法的多样性。也同时给我们提示：从不同的角度看问题、用不同的方法解决问题可能会使问题的解决得到事半功倍的效果。在本文中我们通过图论简单的理论，解决了布点问题。但是尽管本文提供了一种思想，但对于复杂情况下的布点情况没有进行进一步的分析，没有给出进一步的系统理论。因此我们有待于进一步进行研究，以期给出更好的结果。
参考文献：
[1] 叶其孝.数学建模教学活动与大学生教育改革[J].数学的实践与认识，1997，（1）：192-196.
[2] 姜启源，谢金星，叶俊.数学模型：第3版[M].北京：高等教育出版社，2003.
[3] 韩中庚，郭晓丽，杜剑平，等.实用运筹学模型、方法与计算[M].北京：清华大学出版社，2007.
[4] 刘鑫，邓晓莉.0-1整数规划在消防特勤站选址上的应用[J].消防技术与产品信息，2010，（6）：16-18.
[5] 李卫国.线性规划中图解法的最优解问题[J].长春理工大学学报，2010，（4）：178-179.
[6] 单泠，许亚丹.抓好数学建模教学，激发学生创新思维[J]，中国高等教育：半月刊，2001，（15-16）：54-55.
[7] 胡云权，郭耀煌.运筹学教程：第2版[M].北京：清华大学出版社，2003.
[8] Frank R.Giordano William P.Fox Steven B.Horton Maurice D.Weir 数学模型[M].叶其孝，姜启源，译.北京：机械工业出版社，2010：4.
Site Location Problem Solving from the Angle of Graph Theory
CHEN Hui，LI Jin-na
（Department of the Fundamentals，Yantai Vocational College，Yantai 264670，China）
Abstract：In daily production process and life，there is often existing a kind of problem concerning the total utilization of limited resources under certain conditions，and to achieve maximum benefit or value，which contains the location of the site location problem.We usually sum up this type of problem for the integer programming optimization ones.By using software MATLAB we can easily get the numerical solution.But for the location of the site location problem，we found it can be more easily that analyzing and solving from the graph theory angle，and by using graph theory.
Key words：Integer Linear Programming；0-1 integer programming；graph；isolated points[责任编辑 陈 鹤]