孫建英

(青島理工大學(xué) 琴島學(xué)院， 山東 青島 266106 )

圖論模型是數(shù)學(xué)建模中一類非常重要的模型，它的應(yīng)用非常廣泛。購買機票、設(shè)備更新、配送路線選擇等，都屬于最短路徑問題；景區(qū)的旅游車輛的最大通行量、石油管道的最大輸送量等，都屬于最大流問題；電線的架設(shè)問題、居民區(qū)的供水管道問題等，都屬于最小支撐樹問題。Matlab2014a平臺中的圖論工具箱，可以實現(xiàn)圖論模型的快速求解，不必編寫復(fù)雜的程序，對計算機不是很懂的學(xué)者也可以很快地掌握。本文從3個實例出發(fā)，詳細(xì)介紹了如何利用圖論工具箱快速準(zhǔn)確地求解圖論模型中的最短路、最大流和最小支撐樹問題，對圖論模型的進一步研究有重要意義和實用價值。

1 預(yù)備知識

1.1 圖論工具箱

Matlab2014a平臺下圖論工具箱中的相關(guān)函數(shù)，如表1所示。

表1 Matlab 圖論工具箱中的相關(guān)函數(shù)

1.2 稀疏矩陣

稀疏矩陣是指零元素很多，非零元素比較少的矩陣。

稀疏矩陣的存儲方式：a(i,j)=m，其中，a表示稀疏矩陣，i表示非零元素的行標(biāo)，j表示非零元素的列標(biāo)，m表示非零元素的數(shù)值。

稀疏矩陣的使用說明：1)有向圖中，可以直接使用Matlab中的sparse命令,把鄰接矩陣轉(zhuǎn)化為稀疏矩陣；2)無向圖中，由于Matlab只存儲下三角矩陣中的非零元素，要先把鄰接矩陣轉(zhuǎn)置，再應(yīng)用sparse命令。

2 實例仿真

2.1 最短路問題

例1購買機票問題[1]：某集團公司在六個城市C1,C2,…,C6中有分公司，從Ci到Cj的直飛航程票價如表2所示(“-”表示無直飛航班)。如今，集團巡視組要分別從C1出發(fā)到其他城市去檢查工作。請問：應(yīng)該如何安排航班，方可使得票價最低？

表2 各分公司所在城市之間的航程票價(單位：元)

解：Matlab程序：

clc,clear

a=zeros(6);

a(1,2)=850;a(1,4)=1400;a(1,5)=750;a(1,6)=600;

a(2,3)=1000;a(2,4)=800;a(2,6)=500;

a(3,4)=650;a(3,5)=820;

a(4,5)=1300;a(4,6)=1250;

a(5,6)=950;

a=a’;

a=sparse(a);

b=[1:6];

[price,path]=graphshortestpath(a,1,b,’Directed’,0)

運行結(jié)果：

price=

0 850 1570 1400 750 600

點擊工作區(qū)中的path，出現(xiàn)path變量表，見表3。

表3 path變量

結(jié)果分析：C1直達(dá)到C2，C4，C5，C6，票價分別為850，1400，750，600；C1經(jīng)C5

轉(zhuǎn)機到C3，票價為750+820=1570。

2.2 最大流問題

例2管道輸流問題[1]： 某石油公司擁有一個管道輸送網(wǎng)絡(luò)系統(tǒng)，如圖1所示，使用該系統(tǒng)將石油從開采地A輸送到銷售地G。由于管道(以兩個地點之間的弧表示)直徑的變化，各段管道的容量是不一樣的，弧上的數(shù)字意味著各管道的最大容量(單位：萬加侖/小時)。請問：欲使得從開采地A到銷售地G每小時輸送的石油量最大，應(yīng)采取什么樣的配送方案？最大配送量是多少萬加侖？

解：Matlab程序：

clc,clear

a=zeros(7);

a(1,2)=6;a(1,3)=8;a(2,4)=3;a(2,5)=6;

a(3,4)=4;a(3,6)=1;a(3,7)=3;

a(4,5)=3;

a(5,7)=5;a(6,7)=4;

b=sparse(a);

[Maxflow,path]=graphmaxflow(b,1,7);

Path=sparse(path);

Maxflow

view(biograph(Path,[],’ShowArrows’,’on’,’ShowWeights’,’on’))

運行結(jié)果：

Maxflow=9

圖1 石油輸送量最大的配送方案

2.3 最小支撐樹問題

例3電線架設(shè)問題[2]：如圖2，S、A、B、C、D、E、T代表村鎮(zhèn)，它們間連線表明各村鎮(zhèn)間現(xiàn)有道路交通情況，連線旁數(shù)字代表道路的長度?，F(xiàn)要求沿途中道路架設(shè)電線，使上述村鎮(zhèn)全部通上電，應(yīng)如何架設(shè)使總的線路長度為最短？

解：Matlab程序：

圖2 線路最短的電線架設(shè)方案

clc,clear

a=zeros(7);

a(1,2)=2;a(1,3)=5;a(1,4)=4;

a(2,3)=2;a(2,5)=7;

a(3,4)=1;a(3,5)=5;a(3,6)=3;

a(4,6)=4;

a(5,6)=1;a(5,7)=5;

a(6,7)=7;

a=a’;

a=sparse(a);

[ST,pred]=graphminspantree(a,’Method’,’Kruskal’);

st=full(ST);

treelength=sum(sum(st))

view(biograph(st,[],’ShowArrows’,’off’,’ShowWeights’,’on’))

運行結(jié)果：

treelength=14

3 結(jié)語

圖論中的最短路、最大流和最小支撐樹問題，在Matlab2014a平臺下，可以利用圖論工具箱快速地得到最優(yōu)解。其實，運籌學(xué)中的很多模型，像整數(shù)線性規(guī)劃和目標(biāo)規(guī)劃問題[3]等，也可以借助Matlab實現(xiàn)快速求解。但是還有很多問題，例如有初始可行流的最大流問題和最小費用最大流問題等，目前，Matlab沒有相應(yīng)的函數(shù)可以直接求解，要轉(zhuǎn)化成線性規(guī)劃模型，再利用Matlab或者lingo軟件求解[4]。Matlab軟件已成為解決圖論問題的強有力的工具，可以幫助科研工作者及時、準(zhǔn)確地作出決策。