最小生成树的Excel求解

【摘 要】最小生成树在社会生活中应用广泛。利用Excel中的“规划求解”功能简单巧妙地求解出最小生成树。

【关键词】Excel；规划求解；最小生成树

物流点之间道路的选择，城市、企业内部网络线路铺设，自来水管路的布置，天然气管路的安放等等涉及到我们生活方方面面，这些都可以用《运筹学》的知识来减少成本，优化线路。Excel的计算功能非常强大，利用Excel的“规划求解”功能求解最小生成树应用到上述方面可以产生较好的经济意义。

任意两点之间至少有一条边相连的网络图叫做连通图，一个不含圈的连通图称为树。根据树的性质，对于有m个点，n（n≥m）条边的网络图经过去边之后，最终得到m个点、m-1条边的树。如果对网络图各边赋权，则权数和最小的树称之为最小生成树。应用到生活当中则是线路最短、成本最小的网络图。在传统的运筹学里求解最小生成树有避圈法和破圈法，避圈法和破圈法对点和边较少的网络图求解最小生成树具有简单方便的优点。但在点和边较多的情况下，则避圈法和破圈法有些不知所措。Excel是常用的办公软件，它所含的“规划求解”附件具有强大的计算功能，国内外学者也研究过利用Excel中的“规划求解”来求最小生成树，邱爽[1]曾借助Excel规划求解找寻最小生成树，但需要定义每个点的流入量、流出量、净流入量和流入流出合计量，对于复杂的网络图，很容易漏掉一些点的流入流出量。也有一些专门的软件可以求解最小生成树，但终究不如excel软件使用普遍。

对于一个网络图，每一条边都可能成为树的枝，最小生成树要求经过网络图里每一个节点，所以用excel求解最小生成树时首先需要将任意一点出发的每一条线路全部列举出来，而且还需要将反向的线路也列举出来。这在Excel中使用复制粘贴功能很容易实现。根据树的定义，连通图必须经过每一个节点，并且网络图里的边最多经过一次，这样就构成了规划求解的约束条件。现在以一个网络图为例来求解最小生成树。

有V1、V2、V3、V4、V5、V6、V7七个点构成如图1，各边权数如图所示，求最小生成树。

用Excel求解的基本步骤如图3所示：

1）列出所有正向和反向的边（以流入流出表示线段的首尾端点）。

2）列出各边的权数。

3）設置0-1变量（0代表不经过这条边，1则代表经过这条边）。

4）列出所有节点。

5）利用Excel中“sumif”函数对各节点进行有条件求和。

6）设置目标函数为权数与变量乘积后求和。

7）所有的边最多只能走一次。

8）运行“规划求解”得到最优解。

9）根据最优解画出网络图，去除多余的那一条边。

运行“规划求解”，具体参数如图4。

由于在参数设定中不能直接设置去除哪一条边，所以规划求解得到的最优解是m个点，m条边的图形，形成了一个圈。我们还需要将圈里的最长边去除，最终得到最小生成树。根据excel中求得的最优解得到如图5所示的连接图，其中V2，V3，V7形成了一个圈，不符合树的定义，需要将这个圈里最长边V2V3除掉，得到最小树的解为72-15=57，与人工计算得到的解完全一致。

【参考文献】

[1]邱爽.借助Excel 规划求解找寻最小生成树[J].科技信息，2010（05）：75.

[责任编辑：田吉捷]