孫建英
(青島理工大學(xué) 琴島學(xué)院, 山東 青島 266106 )
圖論模型是數(shù)學(xué)建模中一類(lèi)非常重要的模型,它的應(yīng)用非常廣泛。購(gòu)買(mǎi)機(jī)票、設(shè)備更新、配送路線選擇等,都屬于最短路徑問(wèn)題;景區(qū)的旅游車(chē)輛的最大通行量、石油管道的最大輸送量等,都屬于最大流問(wèn)題;電線的架設(shè)問(wèn)題、居民區(qū)的供水管道問(wèn)題等,都屬于最小支撐樹(shù)問(wèn)題。Matlab2014a平臺(tái)中的圖論工具箱,可以實(shí)現(xiàn)圖論模型的快速求解,不必編寫(xiě)復(fù)雜的程序,對(duì)計(jì)算機(jī)不是很懂的學(xué)者也可以很快地掌握。本文從3個(gè)實(shí)例出發(fā),詳細(xì)介紹了如何利用圖論工具箱快速準(zhǔn)確地求解圖論模型中的最短路、最大流和最小支撐樹(shù)問(wèn)題,對(duì)圖論模型的進(jìn)一步研究有重要意義和實(shí)用價(jià)值。
Matlab2014a平臺(tái)下圖論工具箱中的相關(guān)函數(shù),如表1所示。
表1 Matlab 圖論工具箱中的相關(guān)函數(shù)
稀疏矩陣是指零元素很多,非零元素比較少的矩陣。
稀疏矩陣的存儲(chǔ)方式:a(i,j)=m,其中,a表示稀疏矩陣,i表示非零元素的行標(biāo),j表示非零元素的列標(biāo),m表示非零元素的數(shù)值。
稀疏矩陣的使用說(shuō)明:1)有向圖中,可以直接使用Matlab中的sparse命令,把鄰接矩陣轉(zhuǎn)化為稀疏矩陣;2)無(wú)向圖中,由于Matlab只存儲(chǔ)下三角矩陣中的非零元素,要先把鄰接矩陣轉(zhuǎn)置,再應(yīng)用sparse命令。
例1購(gòu)買(mǎi)機(jī)票問(wèn)題[1]:某集團(tuán)公司在六個(gè)城市C1,C2,…,C6中有分公司,從Ci到Cj的直飛航程票價(jià)如表2所示(“-”表示無(wú)直飛航班)。如今,集團(tuán)巡視組要分別從C1出發(fā)到其他城市去檢查工作。請(qǐng)問(wèn):應(yīng)該如何安排航班,方可使得票價(jià)最低?
表2 各分公司所在城市之間的航程票價(jià)(單位:元)
解: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)
運(yùn)行結(jié)果:
price=
0 850 1570 1400 750 600
點(diǎn)擊工作區(qū)中的path,出現(xiàn)path變量表,見(jiàn)表3。
表3 path變量
結(jié)果分析:C1直達(dá)到C2,C4,C5,C6,票價(jià)分別為850,1400,750,600;C1經(jīng)C5
轉(zhuǎn)機(jī)到C3,票價(jià)為750+820=1570。
例2管道輸流問(wèn)題[1]: 某石油公司擁有一個(gè)管道輸送網(wǎng)絡(luò)系統(tǒng),如圖1所示,使用該系統(tǒng)將石油從開(kāi)采地A輸送到銷(xiāo)售地G。由于管道(以兩個(gè)地點(diǎn)之間的弧表示)直徑的變化,各段管道的容量是不一樣的,弧上的數(shù)字意味著各管道的最大容量(單位:萬(wàn)加侖/小時(shí))。請(qǐng)問(wèn):欲使得從開(kāi)采地A到銷(xiāo)售地G每小時(shí)輸送的石油量最大,應(yīng)采取什么樣的配送方案?最大配送量是多少萬(wàn)加侖?
解: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’))
運(yùn)行結(jié)果:
Maxflow=9
圖1 石油輸送量最大的配送方案
例3電線架設(shè)問(wèn)題[2]:如圖2,S、A、B、C、D、E、T代表村鎮(zhèn),它們間連線表明各村鎮(zhèn)間現(xiàn)有道路交通情況,連線旁數(shù)字代表道路的長(zhǎng)度?,F(xiàn)要求沿途中道路架設(shè)電線,使上述村鎮(zhèn)全部通上電,應(yīng)如何架設(shè)使總的線路長(zhǎng)度為最短?
解: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’))
運(yùn)行結(jié)果:
treelength=14
圖論中的最短路、最大流和最小支撐樹(shù)問(wèn)題,在Matlab2014a平臺(tái)下,可以利用圖論工具箱快速地得到最優(yōu)解。其實(shí),運(yùn)籌學(xué)中的很多模型,像整數(shù)線性規(guī)劃和目標(biāo)規(guī)劃問(wèn)題[3]等,也可以借助Matlab實(shí)現(xiàn)快速求解。但是還有很多問(wèn)題,例如有初始可行流的最大流問(wèn)題和最小費(fèi)用最大流問(wèn)題等,目前,Matlab沒(méi)有相應(yīng)的函數(shù)可以直接求解,要轉(zhuǎn)化成線性規(guī)劃模型,再利用Matlab或者lingo軟件求解[4]。Matlab軟件已成為解決圖論問(wèn)題的強(qiáng)有力的工具,可以幫助科研工作者及時(shí)、準(zhǔn)確地作出決策。
長(zhǎng)春大學(xué)學(xué)報(bào)2018年8期