基于最小生成树的G地区铺设光纤优化布局模型

 　摘 要：为了使在一个地区中铺设光纤网的费用最小，应抽象简化该地区的情况，并设计一个程序，将这个问题抽象为最小生成树的问题，通过LINGO软件来实现。文章建立的最小生成树模型的数据与公式完全的分离从而使得应用特别容易，此外，利用软件进行求解以使那些无法人工计算的最小生成�滴侍獾那蠼獗涞煤苋菀住� 
　　关键词：最小生成树；LINGO；优化布局 
　　中图分类号：F062.4 文献标识码：A 文章编号：1008-4428（2018）06-0144-02 
　　一、 引 言 
　　为了得到在一个地区中铺设光纤网费用最小的方案，首先应抽象简化该地区的情况，并设计一个程序，将这个问题抽象为最小生成树的问题，通过LINGO软件来实现。设计一个程序，使其成本最低。LINGO语言创建的模型直观简洁；由于@FOR、@SUM等语句不受循环和求和上下限的限制，在修改的时候，不需要改动目标函数和约束条件，因此容易扩展；数据初始化部分与其他部分相分离，因此，对于相同模型的不同数据进行计算时，其他语句不变，只需要改动数据部分；集合是LINGO非常独特的概念，集合中的成员可以自由地起名字，没有任何限制；可以根据需求来确定集合的使用数量，同时既可以代表已知常量，又可以代表决策变量；通过使用集合或者@FOR、@SUM等操作函数等简洁语言来描述经常使用的规划模型中的目标函数和约束条件，即使有大量的决策变量和数据，语句也不会因此而增加。 
　　在图论中，无圈的连通图称作树。例如12个城镇的一个光纤网就构成一棵树。而我们将一个问题可选择的方案画成图也构成一棵树。在一个连通图G中，我们选择适当的边来构成一个子图并保留G中全部顶点，这个子图就称作图G的生成树。该生成树的权就是各边的权数之和。最小生成树为使连通图G的权数最小的生成树。 
　　在我们的生活中，许多的实际问题都可以通过求最小生成树的问题来求解。例如，如何修理公路或桥梁来连接一些地区；如何架设通信网络或电话线来连接几个地区；如何修水渠或自来水管道以连接水源和待灌溉的土地，如何设置物流站点等等问题。文章是通过一个G地区铺设光纤的范例来说明此类问题的解决的。 
　　二、 G地区铺设光纤优化布局的模型选择 
　　铺设光纤优化布局问题可以近似描述为寻找一系列重心点之间的1个弧集合，这些弧把所有的重心点连接起来，并且这些弧的长度之和最小，跟最小生成树的定义极其类似，因此铺设光纤优化布局的问题可以抽象为一个近似的最小生成树问题。 
　　假设G地区在平原地区，且该地区由12个城镇组成，我们分别将其编号为1到12，相互之间的距离如下表1所示。首先设定由1城市往其余11个城市铺设光纤，即1表示为生成树的树根。每两个城镇之间的距离设定由下表1表示。由于受地形条件限制较少，因此每两个地区之间铺设光纤距离近似为两地之间的距离。且单位距离铺设光纤的费用为1，求使得在该地区铺设光纤总费用最小的架线方案。 
　　在现实生活中，许多的实际问题都可以用最小生成树的问题来解决。例如：如何修理公路来连接一些地区；如何架设通信网络来连接几个地区；如何修水渠来连接水源和待灌溉的土地等等问题。本文是通过一个G地区铺设光纤的范例来说明此类问题的解决。铺设光纤优化布局问题可以看作寻找一系列重心点之间的弧且使这些弧的长度之和最小的1个弧集合，这些弧把所有的重心点连接起来，并且这些弧的长度之和最小，跟最小生成树的定义极其类似，因此铺设光纤优化布局的问题可以抽象为一个近似的最小生成树问题。 
　　关于最小生成树问题，有以下概念，如果一个无向图是相互连通不包含有圈的，则称该图为树。如果有向图中的某一个顶点可以到达其余的任意顶点，则称此顶点为图G的根。如果有向图G的基础图是树且有根，则G是有向树。关于树的定理有：①设G是有限的无向图，如果顶点度满足d（v）2，V，则G有圈。②每棵树至少有一个顶点的度为1。③G是连通图且边数小于顶点数，则图G中至少有一个顶点的度为1。④设G是具有n个顶点的无向连通图，则G是树的必要充分条件是G有n-1条边。 
　　下面是关于LINGO的程序设计的一些问题：①LINGO用来表示模型中的事物中的集合是一组相关对象组成的集合，是从实际问题到数学问题的抽象，分为初始集合和衍生集合。②集合的三要素为集合的名称、属性、元素。初始集合定义的格式为：集合的名称/集合的元素/：集合的属性。③数据的初始化部分以DATA开始，ENDDATA结束是对上述集合中的元素赋值，数据间用格式或逗号做间隔。④@SUM函数表示求和，函数的调用格式如：MIN=@SUM（LINKS（M，N）：C（M，N）×X（M，N））。⑤求和括号内表示集合名称的为参数（LINKS（M，N）），第二个参数（C（M，N）×X（M，N））为求和的运算对象。需要根据系统内自带函数相应的逻辑关系与表达格式来生成约束表达式。 
　　而LINGO建模语言也有很多优点：首先，运用LINGO语言建立的模型相对来说比较直观简洁。其次，由于@FOR、@SUM等语句不受循环和求和上下限等条件的限制，对于LINGO语言建立的模型在修改时不需要改动目标函数和约束条件，因此更容易扩展。除此之外，数据初始化部分与其他部分相分离，因此对于相同模型的不同数据进行计算时，其他语句不变，只需要改动数据部分即可。同时，集合是LINGO非常独特的概念，集合中的成员可以任意地起名字。设置集合的属性时可以根据需求来确定其使用数量，同时集合既可以代表已知的常量，也可代表决策变量。最后，可以以简洁的语句使用集合或者@FOR、@SUM等操作函数描述频繁使用的规划模型中的目标函数和约束条件，而组成模型的语句也不会因该模型具有大量的决策变量和数据而增加。 
　　三、 G地区铺设光纤最优化模型 
　　铺设光纤优化布局问题可以近似描述为寻找一系列重心点之间的1个弧集合，这些弧把所有的重心点连接起来，并且这些弧的长度之和最小，跟最小生成树的定义极其类似，因此铺设光纤优化布局的问题可以抽象为一个近似的最小生成树问题。首先假设单位距离的光纤费用为1，进而我们以整个G地区铺设光纤的总费用，即总距离最小作为目标。当第i个城市与第j个城市之间由光纤相互连接时（i和j为1到12的整数，且i≠j），dij表示两个城市i和j之间的距离，xij=0或1（1表示连接，0表示不连接），并假设城市1是此生成树的根。则目标函数为min∑（i，j）∈Adijxij；s.t.∑j∈Vx1j≥1，（根至少有一条边连接到其他点）∑j∈Vxji=1，i≠1，（除根外，每个点只有一条边进入且各边不构成圈）。 　　经过LINGO运算，得到如下结果： 
　　X（1，3）1.0000005.000000；X（3，4）1.0000005.000000；X（4，7）1.0000005.000000；X（5，2）1.0000006.000000；X（5，9）1.0000004.000000；X（6，10）1.0000005.000000；X（7，8）1.0000003.000000；X（8，5）1.0000005.000000；X（8，11）1.0000005.000000；X（9，6）1.0000003.000000；X（10，12）1.0000004.000000 
　　由lingo的�算结果，我们得到了一个由11条边构成的使得总和最小的最小生成树。各个X的赋值如上，1和3相连且之间的距离为5，即1和3之间的费用为5；3和4相连且之间的距离为5，即3和7之间的费用为5；4和7相连且之间的距离为5，即4和7之间的费用为5；5和2相连且之间的距离为6，即5和2之间的费用为6；5和9相连且之间的距离为4，即5和9之间的费用为4；6和10相连且之间的距离为5，即6和10之间的费用为5；7和8相连且之间的距离为3，即7和8之间的费用为3；8和5相连且之间的距离为5，即8和5之间的费用为5；8和11相连且之间的距离为5，即8和11之间的费用为5；9和6相连且之间的距离为3，即9和6之间的费用为3；10和12相连且之间的距离为4，即10和12之间的费用为4，这12个地区相互之间的和的最小值是50，即铺设光纤最优方案长度为50，即铺设光纤总费用为50，铺设光纤优化布局问题可以近似描述为寻找一系列重心点之间的1个弧集合，这些弧把所有的重心点连接起来，并且这些弧的长度之和最小，跟最小生成树的定义极其类似，因此铺设光纤的优化布局问题可以抽象为一个近似的最小生成树问题。由LINGO的运算结果我们得到了一个由11条边构成的，并且使得总和最小的最小生成树。因此，使得铺设光纤费用最小的连接这几个地区各个边的距离如上，所有边的总距离的最小值是50，即铺设光纤最优方案的总距离为50，总费用也为50。 
　　参考文献： 
　　[1]余为波，王涛.基于图论的舰船通道路线优化[J].中国舰船研究，2008（1）：18-22. 
　　[2]许自昌.基于最小生成树的渠道系统优化布局模型[J].农业工程学报，2017，1（1）. 
　　[3]曲建华，崔岩，徐广印，姚新胜，应继来.基于最小生成树的河南省高速公路多义性路径标识站设置[J].河南科学，2012，5（5）. 
　　作者简介： 
　　毛潇潇，女，河南开封人，河南财经政法大学经济学院数量经济学硕士研究生。