基于最小生成樹的G地區(qū)鋪設(shè)光纖優(yōu)化布局模型

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

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

中圖分類號(hào)：F062.4 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1008-4428（2018）06-0144-02

一、 引 言

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

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

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

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

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

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

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

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

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

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

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

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

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

參考文獻(xiàn)：

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

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

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

作者簡(jiǎn)介：

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