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

王繼強

(山東財經大學數學與數量經濟學院， 濟南 250014)

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

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

1 問題陳述

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

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

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

2 模型與求解

2.1 圖模型與算法

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

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

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

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

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

2.2 數學規劃模型I與求解

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

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

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

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

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

綜上，建立最小支撐樹問題的數學規劃模型I為

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

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

2.3 數學規劃模型II與求解

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

目標函數：

約束條件：

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

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

其次，為保證最小支撐樹的無圈性，受旅行商問題的建模思想[9]啟發，對于圖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，矛盾！

綜上，建立最小支撐樹問題的數學規劃模型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是一個混合整數規劃問題，其求解可借助LINGO軟件完成。

3 實證——光纖網絡鋪設

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

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

通信公司擬為該地鋪設高速光纖網絡，要求覆蓋所有建筑物，且造價最低。試為該公司設計一個最優的光纖網絡鋪設方案[10]。

經分析知，最優的光纖網絡鋪設方案對應著圖2中網絡圖的一個最小支撐樹。

3.1 經典算法

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

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

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

3.2 數學規劃模型I

注意到圖2中有3個簡單圈和3個復合圈，根據模型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上運行，返回主要結果：

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

據此知，最優解為x13=x24=x34=x47=x58=x67=x78=1，其余xij=0。從而，最優光纖網絡鋪設方案如圖3所示。

3.3 數學規劃模型II

根據模型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上運行，返回主要結果：

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

據此知，最優解為x13=x24=x34=x47=x58=x67=x78=1，其余xij=0。從而，最優光纖網絡鋪設方案亦如圖3所示。

顯然，兩個經典算法、模型I、模型II得到的結果完全一致，即最優光纖網絡鋪設方案相同，當然造價也相同(與光纖總鋪設長度24成正比)。

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

4 結束語

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

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