王淑云

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

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

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

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

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

有V1、V2、V3、V4、V5、V6、V7七個(gè)點(diǎn)構(gòu)成如圖1，各邊權(quán)數(shù)如圖所示，求最小生成樹。

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

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

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

3）設(shè)置0-1變量（0代表不經(jīng)過這條邊，1則代表經(jīng)過這條邊）。

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

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

6）設(shè)置目標(biāo)函數(shù)為權(quán)數(shù)與變量乘積后求和。

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

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

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

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

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

【參考文獻(xiàn)】

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

[責(zé)任編輯：田吉捷]