案例3網(wǎng)絡中的服務及設施布局

PAGEPAGE7圖論與網(wǎng)絡案例：網(wǎng)絡中的服務及設施布局一、問題的提出長虹街道近年來新建了11個居民小區(qū)，各小區(qū)的大致位置及相互間的距離（單位：100m）如圖所示。各居民小區(qū)的居民人數(shù)為：①3000，②3500，③3700，④5000，⑤3000，⑥2500，⑦2800，⑧4500，⑨3300，⑩4000，⑾3500。試幫助決策。117002483596114865645657584666745長虹街道11個居民小區(qū)位置及相互間道路示意圖（1）在11個小區(qū)內(nèi)準備共建一套醫(yī)務所、郵局、儲蓄所、綜合超市等服務設施，應建于哪一居民小區(qū)，使得對居民來說感到方便？（2）電信部門擬建寬帶網(wǎng)鋪設到各小區(qū)，應如何鋪設最為經(jīng)濟？（3）一個考察小組從小區(qū)①出發(fā)，經(jīng)⑤、⑧、⑩小區(qū)（考察順序不限），最后到小區(qū)⑨再離去，試幫助選擇一條最短的考察路線。二、解決的問題準備首先用Matlab求任意兩點間的最短路的矩陣算法，求出任意兩個小區(qū)之間的最短路。clear;clc;M=10000;a(1,:)=[0,4,M,6,M,M,8,M,M,M,M];a(2,:)=[zeros(1,2),7,5,M,M,M,M,M,M,M];a(3,:)=[zeros(1,3),M,6,5,M,M,M,M,M];a(4,:)=[zeros(1,4),5,M,M,6,M,M,M];a(5,:)=[zeros(1,5),4,M,8,6,M,M];a(6,:)=[zeros(1,6),M,M,7,M,M];a(7,:)=[zeros(1,7),4,M,5,M];a(8,:)=[zeros(1,8),4,M,5];a(9,:)=[zeros(1,9),M,6];a(10,:)=[zeros(1,10),6];a(11,:)=zeros(1,11);b=a+a';path=zeros(length(b))fori=1:11forj=1:11fork=1:11ifb(i,j)>b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path根據(jù)求解結果，11個居民小區(qū)之間的最短距離結果如下表：11個居民小區(qū)相互之間距離單位：百米小區(qū)小區(qū)①②③④⑤⑥⑦⑧⑨⑩⑾①041161115812161317②407510121211151716③117011651914122418④6511059106101511⑤1110650412861712⑥15125940161172113⑦8121910121604859⑧121114681140495⑨1615121067840126⑩131724151721591206⑾17161811121395660三、問題（1）的求解問題（1）：在11個小區(qū)內(nèi)準備共建一套醫(yī)務所、郵局、儲蓄所、綜合超市等服務設施，應建于哪一居民小區(qū)，使對居民來說感到方便？由于在某一個小區(qū)建立一套公共設施，應該考慮所有居民都使用公共設施最方便，即：所有居民都趕往公共設施所在地，行駛的路程最小即為最方便。以各小區(qū)的人數(shù)作為權數(shù),乘以到各個小區(qū)的距離然后按列求和，總和最小的那個小區(qū)建公共設施最合適。①②③④⑤⑥⑦⑧⑨⑩⑾①012000330001800033000450002400036000480003900051000②140000245001750035000420004200038500525005950056000③407002590004070022200185007030051800444008880066600④300002500055000025000450005000030000500007500055000⑤330003000018000150000120003600024000180005100036000⑥375003000012500225001000004000027500175005250032500⑦224003360053200280003360044800011200224001400025200⑧540004950063000270003600049500180000180004050022500⑨528004950039600330001980023100264001320003960019800⑩520006800096000600006800084000200003600048000024000⑾595005600063000385004200045500315001750021000210000∑395900379500457800300200324600409400358200285700339800480900388600因此,一套醫(yī)務所、郵局、儲蓄所、綜合超市等服務設施應該建在第8小區(qū)，使對居民總體來說感到方便。四、問題（2）的求解問題（2）：電信部門擬建寬帶網(wǎng)鋪設到各小區(qū)，應如何鋪設最為經(jīng)濟？這是最小生成樹問題，因此求該網(wǎng)絡的最小生成樹。用lingo10.0編程如下：sets:cities/1..11/:level;!level(i)=thelevelofcity;link(cities,cities):distance,!Thedistancematrix;x;!x(i,j)=1ifweuselinki,j;endsetsdata:!Distancematrix,itneednotbesymmetirc;enddatan=@size(cities);!Themodelsize;!Minimizetotaldistanceofthelinks;min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));!Theremustbeanarcoutofcity1;@sum(cities(i)|i#gt#1:x(1,i))>=1;!Forcityi,exceptthebase(city1);@for(cities(i)|i#gt#1:!Itmustbeentered;@sum(cities(j)|j#ne#i:x(j,i))=1;!level(j)=levle(i)+1,ifwelinkjandi;@for(cities(j)|j#gt#1#and#j#ne#i:level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i););!Thelevelofcityisatleast1butnomoren-1,andis1ifitlinkstobase(city1);@bnd(1,level(i),999999);level(i)<=n-1-(n-2)*x(1,i););!Makethex's0/1;@for(link:@bin(x));主要計算結果：Globaloptimalsolutionfound.Objectivevalue:47.00000Objectivebound:47.00000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:61X(1,2)1.0000004.000000X(2,4)1.0000005.000000X(4,5)1.0000005.000000X(4,8)1.0000006.000000X(5,6)1.0000004.000000X(6,3)1.0000005.000000X(7,10)1.0000005.000000X(8,7)1.0000004.000000X(8,9)1.0000004.000000X(8,11)1.0000005.000000其余皆為零。畫出最小生成樹圖如下：1717002483596114545655445電信部門擬建寬帶網(wǎng)鋪設到各小區(qū)，應按照最小生成樹的線路鋪設最為經(jīng)濟，所要鋪設的長度為4700m。五、問題（3）的求解問題（3）：一個考察小組從小區(qū)①出發(fā)，經(jīng)⑤、⑧、⑩小區(qū)（考察順序不限），最后到小區(qū)⑨再離去，試幫助選擇一條最短的考察路線。這是一個哈密頓圈的問題。先用LINGO10.0編程求出哈密頓圈。sets:cities/1..11/:level;!level(i)=thelevelofcity;link(cities,cities):distance,!Thedistancematrix;x;!x(i,j)=1ifweuselinki,j;endsetsdata:!Distancematrix,itneednotbesymmetirc;enddatan=@size(cities);!Themodelsize;!Minimizetotaldistanceofthelinks;min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));!Forcityi;@for(cities(i):!Itmustbeentered;@sum(cities(j)|j#ne#i:x(j,i))=1;!Itmustbedeparted;@sum(cities(j)|j#ne#i:x(i,j))=1;!level(j)=levle(i)+1,ifwelinkjandi;@for(cities(j)|j#gt#1#and#j#ne#i:level(j)>=level(i)+x(i,j)-(n-2)*(1-x(i,j))+(n-3)*x(j,i);););!Makethex's0/1;@for(link:@bin(x));!Forthefirstandlaststop;@for(cities(i)|i#gt#1:level(i)<=n-1-(n-2)*x(1,i);level(i)>=1+(n-2)*x(i,1););求解基本結果如下：Globaloptimalsolutionfound.Objectivevalue:59.00000Objectivebound:59.00000Infeasibilities:0.000000Extendedsolversteps:0Totalsolveriterations:547X(1,2)1.0000004.000000X(2,3)1.0000007.000000X(3,6)1.0000005.000000X(4,1)1.0000006.000000X(5,9)1.0000006.000000X(6,5)1.0000004.000000X(7,8)1.0000004.000000X