基于LINGO的最小支撐樹問題的模型與解法

王繼強

(山東財經(jīng)大學數(shù)學與數(shù)量經(jīng)濟學院， 濟南 250014)

網(wǎng)絡(luò)設(shè)計問題是離散最優(yōu)化和計算機設(shè)計領(lǐng)域中的一個重要問題，它要求人們從網(wǎng)絡(luò)圖中找出滿足某種特征的一個子圖來。比如最短路問題、最大流問題、旅行商問題(TSP)、中國郵路問題及本文要研究的最小支撐樹問題等都屬于這類問題。顧名思義，最小支撐樹問題就是要從賦權(quán)連通圖中找出一個權(quán)最小的支撐樹。這一問題在理論上有重要應(yīng)用，如最短路問題、TSP、匹配問題、Steiner樹問題等問題的解決；它在現(xiàn)實中也有很多應(yīng)用，如場站建設(shè)、城市規(guī)劃、超大規(guī)模集成電路(very large scale integration, VLSI)設(shè)計、交通道路布局、通信網(wǎng)絡(luò)架設(shè)等[1-2]。

就算法復雜度而言，最小支撐樹問題并不屬于NP-困難問題，即它可以在關(guān)于問題輸入規(guī)模的多項式函數(shù)的時間內(nèi)完成求解。Kruscal算法、Prim算法都是求解最小支撐樹問題的經(jīng)典算法，但它們都是僅僅使用了組合最優(yōu)化思想直接在圖上完成操作的，而未能盡可能地利用問題本身的代數(shù)特征，建立數(shù)學規(guī)劃模型，借助現(xiàn)代高性能計算軟件(如LINGO、MATLAB、1stOpt等)完成問題的求解過程[3-4]。顯然，在大數(shù)據(jù)時代，經(jīng)典算法費時費力，給人以笨拙之感；對于圖的規(guī)模相對較大的情形，“建模+軟件”解法更貼近生產(chǎn)生活的實際需求。

1 問題陳述

在圖與網(wǎng)絡(luò)理論中，用點表示對象，邊表示對象之間的關(guān)系，這樣的“點-邊”二元結(jié)構(gòu)就是圖。如有需要，可給圖的邊賦予一個數(shù)字作為權(quán)，是為賦權(quán)圖。根據(jù)邊有無方向，圖可分為無向圖和有向圖。本文中所指的圖均為賦權(quán)無向圖，簡稱賦權(quán)圖。圖G中一個點邊交錯構(gòu)成的非空有限序列稱為G的鏈，其中點不重合的鏈稱為路，始、終點重合的路稱為圈。任兩點之間都至少有一條路的圖稱為連通圖。點、邊都取自圖G的圖稱為G的子圖，其中點與G完全相同的子圖稱為G的支撐子圖。不含有圈的連通圖稱為樹。圖G中本身是樹的支撐子圖稱為G的支撐樹。賦權(quán)圖G中一個所有邊的權(quán)之和最小的支撐樹稱為G的最小支撐樹。于是，最小支撐樹問題就是要從賦權(quán)圖中找到一個最小支撐樹，其正式表述為：

給定一個賦權(quán)圖G=(V,E,W)，其中V={1,2,…,n}為點集，E?V×V為邊集，點i和點j之間有邊ij，邊ij的權(quán)為wij∈W。設(shè)T是G的一個支撐樹，定義T的權(quán)為其所有邊的權(quán)之和。試從圖G中找出一個最小支撐樹。

當邊ij不存在或i=j時，規(guī)定其權(quán)為“+∞”。在編寫程序時，權(quán)“+∞”可用一個充分大的正數(shù)代替。

2 模型與求解

2.1 圖模型與算法

如前所述，最小支撐樹問題在圖模型上就是要從賦權(quán)圖中找到一個權(quán)最小的支撐樹。

作為最小支撐樹問題的圖算法，Kruscal算法和Prim算法都利用了支撐樹的根本特征[5-8]：作為支撐子圖，T須占有圖G的全部點；作為樹，T須連通且無圈。

Kruscal算法堅持在無圈的前提下，優(yōu)先選取權(quán)最小的邊這一原則，從圖G的邊中逐次選入n-1條邊，故又稱避圈法。

Prim算法堅持在連通的前提下，優(yōu)先去除權(quán)最大的邊這一原則，從圖G的邊中逐次刪掉多余的|E|-n+1條邊，故又稱破圈法。

Kruscal算法和Prim算法一立一破，殊途同歸，完美地詮釋了“有破有立，破立結(jié)合”的辯證思想。

2.2 數(shù)學規(guī)劃模型I與求解

為建立最小支撐樹問題的數(shù)學規(guī)劃模型，特引入0-1決策變量：

同樣，可以利用0-1變量寫出約束條件如下：

首先，最小支撐樹中須含有n-1條邊，即

其次，最小支撐樹中須不含有圈(不論是簡單圈，還是復合圈)，為此須使圖G中每一個圈都至少去掉一條邊，即

式中：e(C)為圈C的邊數(shù)。

綜上，建立最小支撐樹問題的數(shù)學規(guī)劃模型I為

xij=0,1；i,j=1,2,…,n。

易見，模型I是一個0-1整數(shù)規(guī)劃問題，其求解可借助LINGO軟件完成。

2.3 數(shù)學規(guī)劃模型II與求解

同數(shù)學規(guī)劃模型I，引入0-1變量xij(i,j=1,2,…,n)。于是，有

目標函數(shù)：

約束條件：

首先，為保證最小支撐樹的連通性，設(shè)點1是始點，則最小支撐樹中須至少有1條邊離開點1，即

同時，除始點1外，最小支撐樹中須有且僅有1條邊進入其他各點，即

其次，為保證最小支撐樹的無圈性，受旅行商問題的建模思想[9]啟發(fā)，對于圖G的每一個點j，引入一個輔助變量uj≥0，對于每一條邊ij，追加約束條件：

ui-uj+nxij≤n-1。

圖1 反例Fig.1 Counterexample

例如，在圖1中，12341顯然是一個圈。而且，該圈顯然滿足上述前兩個約束條件，但不滿足第3個約束條件：

u1-u2+4x12≤3，

u2-u3+4x23≤3，

u3-u4+4x34≤3，

u4-u1+4x41≤3。

這是因為將上述4式左右兩邊分別相加，有

4(x12+x23+x34+x41)≤12。

又由圖1知，x12=x23=x34=x41=1，故16≤12，矛盾！

綜上，建立最小支撐樹問題的數(shù)學規(guī)劃模型II：

ui-uj+nxij≤n-1,

i,j=1,…,n;i≠j，

xij=0,1,i,j=1,…,n,

uj≥0,j=1,…,n。

易見，模型II是一個混合整數(shù)規(guī)劃問題，其求解可借助LINGO軟件完成。

3 實證——光纖網(wǎng)絡(luò)鋪設(shè)

圖2所示為某地8個建筑物的位置、相互之間的道路及其長度。

圖2 建筑物布局Fig.2 The layout of buildings

通信公司擬為該地鋪設(shè)高速光纖網(wǎng)絡(luò)，要求覆蓋所有建筑物，且造價最低。試為該公司設(shè)計一個最優(yōu)的光纖網(wǎng)絡(luò)鋪設(shè)方案[10]。

經(jīng)分析知，最優(yōu)的光纖網(wǎng)絡(luò)鋪設(shè)方案對應(yīng)著圖2中網(wǎng)絡(luò)圖的一個最小支撐樹。

3.1 經(jīng)典算法

使用Kruscal算法，依次選取邊58、47、24、34、13、67、78(共7條)，得最小支撐樹即光纖鋪設(shè)方案如圖3所示。

使用Prim算法，依次刪掉邊45、36、12(共3條)，得最小支撐樹即光纖鋪設(shè)方案亦如圖3所示。

圖3 光纖鋪設(shè)方案Fig.3 The laying plan of optical fiber network

3.2 數(shù)學規(guī)劃模型I

注意到圖2中有3個簡單圈和3個復合圈，根據(jù)模型I，采用簡約模式編寫LINGO程序代碼如下：

min=7*x12+4*x13+3*x24+3*x34+8*x36+8*x45+2*x47+x58+5*x67+6*x78;

x12+x13+x24+x34+x36+x45+x47+x58+x67+x78=7;

x12+x13+x24+x34<=3;

x34+x36+x47+x67<=3;

x45+x47+x58+x78<=3;

x12+x13+x24+x36+x47+x67<=5;

x34+x36+x45+x58+x67+x78<=5;

x12+x13+x24+x36+x45+x58+x67+x78<=7;

@bin(x12);@bin(x13);@bin(x24);@bin(x34);@bin(x36);

@bin(x45);@bin(x47);@bin(x58);@bin(x67);@bin(x78);

在LINGO12.0上運行，返回主要結(jié)果：

Global optimal solution found.

Objective value: 24.00000

Objective bound: 24.00000

Infeasibilities: 0.000000

Extended solver steps: 0

Total solver iterations: 0

Variable Value Reduced Cost

X12 0.000000 7.000000

X13 1.000000 4.000000

X24 1.000000 3.000000

X34 1.000000 3.000000

X36 0.000000 8.000000

X45 0.000000 8.000000

X47 1.000000 2.000000

X58 1.000000 1.000000

X67 1.000000 5.000000

X78 1.000000 6.000000

據(jù)此知，最優(yōu)解為x13=x24=x34=x47=x58=x67=x78=1，其余xij=0。從而，最優(yōu)光纖網(wǎng)絡(luò)鋪設(shè)方案如圖3所示。

3.3 數(shù)學規(guī)劃模型II

根據(jù)模型II，采用集合模式編寫LINGO程序代碼如下：

model:

sets:

vertex/1..8/:u;

link(vertex,vertex):c,x;

endsets

data:

c=0 7 4 100 100 100 100 100

7 0 100 3 100 100 100 100

4 100 0 3 100 8 100 100

100 3 3 0 8 100 2 100

100 100 100 8 0 100 100 1

100 100 8 100 100 0 5 100

100 100 100 2 100 5 0 6

100 100 100 100 1 100 6 0;

enddata

min=@sum(link:c*x);

@sum(vertex(j)|j#gt#1:x(1,j))>=1;

@for(vertex(j)|j#gt#1:@sum(vertex(i)|i#ne# j:x(i,j))=1;);

n=@size(vertex);

@for(link(i,j)|i#ne#j:u(i)-u(j)+n*x(i,j)<=n-1);

@for(link:@bin(x));

在LINGO12.0上運行，返回主要結(jié)果：

Global optimal solution found.

Objective value: 24.00000

Objective bound: 24.00000

Infeasibilities: 0.000000

Extended solver steps: 2

Total solver iterations: 107

Variable Value Reduced Cost

N 8.000000 0.000000

U(1) 0.000000 0.000000

U(2) 3.000000 0.000000

U(3) 1.000000 0.000000

U(4) 2.000000 0.000000

U(5) 5.000000 0.000000

U(6) 4.000000 0.000000

U(7) 3.000000 0.000000

U(8) 4.000000 0.000000

X(1, 3) 1.000000 4.000000

X(3, 4) 1.000000 3.000000

X(4, 2) 1.000000 3.000000

X(4, 7) 1.000000 2.000000

X(7, 6) 1.000000 5.000000

X(7, 8) 1.000000 6.000000

X(8, 5) 1.000000 1.000000

據(jù)此知，最優(yōu)解為x13=x24=x34=x47=x58=x67=x78=1，其余xij=0。從而，最優(yōu)光纖網(wǎng)絡(luò)鋪設(shè)方案亦如圖3所示。

顯然，兩個經(jīng)典算法、模型I、模型II得到的結(jié)果完全一致，即最優(yōu)光纖網(wǎng)絡(luò)鋪設(shè)方案相同，當然造價也相同(與光纖總鋪設(shè)長度24成正比)。

考慮到模型I需要預(yù)先找出圖G的所有圈，再對其逐一寫出無圈性的約束條件，不便于編寫集合模式的LINGO程序，略顯煩瑣；相對而言，模型II適于集合模式編程，更為便捷。

4 結(jié)束語

分析了最小支撐樹問題經(jīng)典算法的局限性之后，從最小支撐樹的本質(zhì)特征出發(fā)，建立了兩種模式的數(shù)學規(guī)劃模型，基于LINGO軟件的應(yīng)用實例表明模型是科學有效的。

利用“數(shù)學規(guī)劃模型+高效計算軟件”模式解決最小支撐樹問題的思想和方法可望為現(xiàn)實生產(chǎn)生活中涉及大規(guī)模數(shù)據(jù)計算的許多工程設(shè)計問題的解決提供思想借鑒和方法參考。