王淑云

【摘 要】最小生成樹在社會生活中應用廣泛。利用Excel中的“規(guī)劃求解”功能簡單巧妙地求解出最小生成樹。

【關鍵詞】Excel；規(guī)劃求解；最小生成樹

物流點之間道路的選擇，城市、企業(yè)內部網絡線路鋪設，自來水管路的布置，天然氣管路的安放等等涉及到我們生活方方面面，這些都可以用《運籌學》的知識來減少成本，優(yōu)化線路。Excel的計算功能非常強大，利用Excel的“規(guī)劃求解”功能求解最小生成樹應用到上述方面可以產生較好的經濟意義。

任意兩點之間至少有一條邊相連的網絡圖叫做連通圖，一個不含圈的連通圖稱為樹。根據(jù)樹的性質，對于有m個點，n（n≥m）條邊的網絡圖經過去邊之后，最終得到m個點、m-1條邊的樹。如果對網絡圖各邊賦權，則權數(shù)和最小的樹稱之為最小生成樹。應用到生活當中則是線路最短、成本最小的網絡圖。在傳統(tǒng)的運籌學里求解最小生成樹有避圈法和破圈法，避圈法和破圈法對點和邊較少的網絡圖求解最小生成樹具有簡單方便的優(yōu)點。但在點和邊較多的情況下，則避圈法和破圈法有些不知所措。Excel是常用的辦公軟件，它所含的“規(guī)劃求解”附件具有強大的計算功能，國內外學者也研究過利用Excel中的“規(guī)劃求解”來求最小生成樹，邱爽[1]曾借助Excel規(guī)劃求解找尋最小生成樹，但需要定義每個點的流入量、流出量、凈流入量和流入流出合計量，對于復雜的網絡圖，很容易漏掉一些點的流入流出量。也有一些專門的軟件可以求解最小生成樹，但終究不如excel軟件使用普遍。

對于一個網絡圖，每一條邊都可能成為樹的枝，最小生成樹要求經過網絡圖里每一個節(jié)點，所以用excel求解最小生成樹時首先需要將任意一點出發(fā)的每一條線路全部列舉出來，而且還需要將反向的線路也列舉出來。這在Excel中使用復制粘貼功能很容易實現(xiàn)。根據(jù)樹的定義，連通圖必須經過每一個節(jié)點，并且網絡圖里的邊最多經過一次，這樣就構成了規(guī)劃求解的約束條件。現(xiàn)在以一個網絡圖為例來求解最小生成樹。

有V1、V2、V3、V4、V5、V6、V7七個點構成如圖1，各邊權數(shù)如圖所示，求最小生成樹。

用Excel求解的基本步驟如圖3所示：

1）列出所有正向和反向的邊（以流入流出表示線段的首尾端點）。

2）列出各邊的權數(shù)。

3）設置0-1變量（0代表不經過這條邊，1則代表經過這條邊）。

4）列出所有節(jié)點。

5）利用Excel中“sumif”函數(shù)對各節(jié)點進行有條件求和。

6）設置目標函數(shù)為權數(shù)與變量乘積后求和。

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

8）運行“規(guī)劃求解”得到最優(yōu)解。

9）根據(jù)最優(yōu)解畫出網絡圖，去除多余的那一條邊。

運行“規(guī)劃求解”，具體參數(shù)如圖4。

由于在參數(shù)設定中不能直接設置去除哪一條邊，所以規(guī)劃求解得到的最優(yōu)解是m個點，m條邊的圖形，形成了一個圈。我們還需要將圈里的最長邊去除，最終得到最小生成樹。根據(jù)excel中求得的最優(yōu)解得到如圖5所示的連接圖，其中V2，V3，V7形成了一個圈，不符合樹的定義，需要將這個圈里最長邊V2V3除掉，得到最小樹的解為72-15=57，與人工計算得到的解完全一致。

【參考文獻】

[1]邱爽.借助Excel 規(guī)劃求解找尋最小生成樹[J].科技信息，2010（05）：75.

[責任編輯：田吉捷]