摘 要：為了使在一個地區(qū)中鋪設(shè)光纖網(wǎng)的費用最小，應(yīng)抽象簡化該地區(qū)的情況，并設(shè)計一個程序，將這個問題抽象為最小生成樹的問題，通過LINGO軟件來實現(xiàn)。文章建立的最小生成樹模型的數(shù)據(jù)與公式完全的分離從而使得應(yīng)用特別容易，此外，利用軟件進行求解以使那些無法人工計算的最小生成數(shù)問題的求解變得很容易。

關(guān)鍵詞：最小生成樹；LINGO；優(yōu)化布局

中圖分類號：F062.4 文獻標識碼：A 文章編號：1008-4428（2018）06-0144-02

一、 引 言

為了得到在一個地區(qū)中鋪設(shè)光纖網(wǎng)費用最小的方案，首先應(yīng)抽象簡化該地區(qū)的情況，并設(shè)計一個程序，將這個問題抽象為最小生成樹的問題，通過LINGO軟件來實現(xiàn)。設(shè)計一個程序，使其成本最低。LINGO語言創(chuàng)建的模型直觀簡潔；由于@FOR、@SUM等語句不受循環(huán)和求和上下限的限制，在修改的時候，不需要改動目標函數(shù)和約束條件，因此容易擴展；數(shù)據(jù)初始化部分與其他部分相分離，因此，對于相同模型的不同數(shù)據(jù)進行計算時，其他語句不變，只需要改動數(shù)據(jù)部分；集合是LINGO非常獨特的概念，集合中的成員可以自由地起名字，沒有任何限制；可以根據(jù)需求來確定集合的使用數(shù)量，同時既可以代表已知常量，又可以代表決策變量；通過使用集合或者@FOR、@SUM等操作函數(shù)等簡潔語言來描述經(jīng)常使用的規(guī)劃模型中的目標函數(shù)和約束條件，即使有大量的決策變量和數(shù)據(jù)，語句也不會因此而增加。

在圖論中，無圈的連通圖稱作樹。例如12個城鎮(zhèn)的一個光纖網(wǎng)就構(gòu)成一棵樹。而我們將一個問題可選擇的方案畫成圖也構(gòu)成一棵樹。在一個連通圖G中，我們選擇適當?shù)倪厑順?gòu)成一個子圖并保留G中全部頂點，這個子圖就稱作圖G的生成樹。該生成樹的權(quán)就是各邊的權(quán)數(shù)之和。最小生成樹為使連通圖G的權(quán)數(shù)最小的生成樹。

在我們的生活中，許多的實際問題都可以通過求最小生成樹的問題來求解。例如，如何修理公路或橋梁來連接一些地區(qū)；如何架設(shè)通信網(wǎng)絡(luò)或電話線來連接幾個地區(qū)；如何修水渠或自來水管道以連接水源和待灌溉的土地，如何設(shè)置物流站點等等問題。文章是通過一個G地區(qū)鋪設(shè)光纖的范例來說明此類問題的解決的。

二、 G地區(qū)鋪設(shè)光纖優(yōu)化布局的模型選擇

鋪設(shè)光纖優(yōu)化布局問題可以近似描述為尋找一系列重心點之間的1個弧集合，這些弧把所有的重心點連接起來，并且這些弧的長度之和最小，跟最小生成樹的定義極其類似，因此鋪設(shè)光纖優(yōu)化布局的問題可以抽象為一個近似的最小生成樹問題。

假設(shè)G地區(qū)在平原地區(qū)，且該地區(qū)由12個城鎮(zhèn)組成，我們分別將其編號為1到12，相互之間的距離如下表1所示。首先設(shè)定由1城市往其余11個城市鋪設(shè)光纖，即1表示為生成樹的樹根。每兩個城鎮(zhèn)之間的距離設(shè)定由下表1表示。由于受地形條件限制較少，因此每兩個地區(qū)之間鋪設(shè)光纖距離近似為兩地之間的距離。且單位距離鋪設(shè)光纖的費用為1，求使得在該地區(qū)鋪設(shè)光纖總費用最小的架線方案。

在現(xiàn)實生活中，許多的實際問題都可以用最小生成樹的問題來解決。例如：如何修理公路來連接一些地區(qū)；如何架設(shè)通信網(wǎng)絡(luò)來連接幾個地區(qū)；如何修水渠來連接水源和待灌溉的土地等等問題。本文是通過一個G地區(qū)鋪設(shè)光纖的范例來說明此類問題的解決。鋪設(shè)光纖優(yōu)化布局問題可以看作尋找一系列重心點之間的弧且使這些弧的長度之和最小的1個弧集合，這些弧把所有的重心點連接起來，并且這些弧的長度之和最小，跟最小生成樹的定義極其類似，因此鋪設(shè)光纖優(yōu)化布局的問題可以抽象為一個近似的最小生成樹問題。

關(guān)于最小生成樹問題，有以下概念，如果一個無向圖是相互連通不包含有圈的，則稱該圖為樹。如果有向圖中的某一個頂點可以到達其余的任意頂點，則稱此頂點為圖G的根。如果有向圖G的基礎(chǔ)圖是樹且有根，則G是有向樹。關(guān)于樹的定理有：①設(shè)G是有限的無向圖，如果頂點度滿足d（v）2，V，則G有圈。②每棵樹至少有一個頂點的度為1。③G是連通圖且邊數(shù)小于頂點數(shù)，則圖G中至少有一個頂點的度為1。④設(shè)G是具有n個頂點的無向連通圖，則G是樹的必要充分條件是G有n-1條邊。

下面是關(guān)于LINGO的程序設(shè)計的一些問題：①LINGO用來表示模型中的事物中的集合是一組相關(guān)對象組成的集合，是從實際問題到數(shù)學(xué)問題的抽象，分為初始集合和衍生集合。②集合的三要素為集合的名稱、屬性、元素。初始集合定義的格式為：集合的名稱/集合的元素/：集合的屬性。③數(shù)據(jù)的初始化部分以DATA開始，ENDDATA結(jié)束是對上述集合中的元素賦值，數(shù)據(jù)間用格式或逗號做間隔。④@SUM函數(shù)表示求和，函數(shù)的調(diào)用格式如：MIN=@SUM（LINKS（M，N）：C（M，N）×X（M，N））。⑤求和括號內(nèi)表示集合名稱的為參數(shù)（LINKS（M，N）），第二個參數(shù)（C（M，N）×X（M，N））為求和的運算對象。需要根據(jù)系統(tǒng)內(nèi)自帶函數(shù)相應(yīng)的邏輯關(guān)系與表達格式來生成約束表達式。

而LINGO建模語言也有很多優(yōu)點：首先，運用LINGO語言建立的模型相對來說比較直觀簡潔。其次，由于@FOR、@SUM等語句不受循環(huán)和求和上下限等條件的限制，對于LINGO語言建立的模型在修改時不需要改動目標函數(shù)和約束條件，因此更容易擴展。除此之外，數(shù)據(jù)初始化部分與其他部分相分離，因此對于相同模型的不同數(shù)據(jù)進行計算時，其他語句不變，只需要改動數(shù)據(jù)部分即可。同時，集合是LINGO非常獨特的概念，集合中的成員可以任意地起名字。設(shè)置集合的屬性時可以根據(jù)需求來確定其使用數(shù)量，同時集合既可以代表已知的常量，也可代表決策變量。最后，可以以簡潔的語句使用集合或者@FOR、@SUM等操作函數(shù)描述頻繁使用的規(guī)劃模型中的目標函數(shù)和約束條件，而組成模型的語句也不會因該模型具有大量的決策變量和數(shù)據(jù)而增加。

三、 G地區(qū)鋪設(shè)光纖最優(yōu)化模型

鋪設(shè)光纖優(yōu)化布局問題可以近似描述為尋找一系列重心點之間的1個弧集合，這些弧把所有的重心點連接起來，并且這些弧的長度之和最小，跟最小生成樹的定義極其類似，因此鋪設(shè)光纖優(yōu)化布局的問題可以抽象為一個近似的最小生成樹問題。首先假設(shè)單位距離的光纖費用為1，進而我們以整個G地區(qū)鋪設(shè)光纖的總費用，即總距離最小作為目標。當?shù)趇個城市與第j個城市之間由光纖相互連接時（i和j為1到12的整數(shù)，且i≠j），dij表示兩個城市i和j之間的距離，xij=0或1（1表示連接，0表示不連接），并假設(shè)城市1是此生成樹的根。則目標函數(shù)為min∑（i，j）∈Adijxij；s.t.∑j∈Vx1j≥1，（根至少有一條邊連接到其他點）∑j∈Vxji=1，i≠1，（除根外，每個點只有一條邊進入且各邊不構(gòu)成圈）。

經(jīng)過LINGO運算，得到如下結(jié)果：

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的運算結(jié)果，我們得到了一個由11條邊構(gòu)成的使得總和最小的最小生成樹。各個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個地區(qū)相互之間的和的最小值是50，即鋪設(shè)光纖最優(yōu)方案長度為50，即鋪設(shè)光纖總費用為50，鋪設(shè)光纖優(yōu)化布局問題可以近似描述為尋找一系列重心點之間的1個弧集合，這些弧把所有的重心點連接起來，并且這些弧的長度之和最小，跟最小生成樹的定義極其類似，因此鋪設(shè)光纖的優(yōu)化布局問題可以抽象為一個近似的最小生成樹問題。由LINGO的運算結(jié)果我們得到了一個由11條邊構(gòu)成的，并且使得總和最小的最小生成樹。因此，使得鋪設(shè)光纖費用最小的連接這幾個地區(qū)各個邊的距離如上，所有邊的總距離的最小值是50，即鋪設(shè)光纖最優(yōu)方案的總距離為50，總費用也為50。

參考文獻：

[1]余為波，王濤.基于圖論的艦船通道路線優(yōu)化[J].中國艦船研究，2008（1）：18-22.

[2]許自昌.基于最小生成樹的渠道系統(tǒng)優(yōu)化布局模型[J].農(nóng)業(yè)工程學(xué)報，2017，1（1）.

[3]曲建華，崔巖，徐廣印，姚新勝，應(yīng)繼來.基于最小生成樹的河南省高速公路多義性路徑標識站設(shè)置[J].河南科學(xué)，2012，5（5）.

作者簡介：

毛瀟瀟，女，河南開封人，河南財經(jīng)政法大學(xué)經(jīng)濟學(xué)院數(shù)量經(jīng)濟學(xué)碩士研究生。