數(shù) 學 建 模光纖問題

1、數(shù)學建模計算實驗報告數(shù)學建模課程組廣西科技大學數(shù)學建模計算實驗報告學生姓名：學號：一、實驗題目名稱:光纖鋪設問題實驗內容：設有七個城市v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7。它們之間有通信光纖連通，其布置 如下圖G且線段上數(shù)值為每條光纖的造價（單位十萬元）。問至少有幾條光纖不出故障，城 市間的通信才不會中斷，若要造一個主十網絡，這些不出故障的光纖應如何分布，才能使總 的造價最低？圖B三、實驗目的：建立模型求出保持城市通信不中斷的最小光纖數(shù)，并求如何分布 這些光纖使得造價最低。四、問題分析和建模方向:對于問題一，這是一個求G圖的生成樹的問題，分析 易知G的生成樹有6條邊，即至少需要

2、6條光纖不出故障才能保持城市通信。 對于問題二造主干網，使總造價最低則是個求最優(yōu)生成樹的問題（Kruskal）。五、模型假設與變量符合說明：將G的邊按權從小到大的順序設為e1,e2,.,e7，取T= el, 在從el開始一次將排好序的邊加入到T中，使加入后由T到處的子圖（即由T作為邊集，T中的變相關聯(lián) 的點作為點集所確定的子圖）不含圈，直至T中含有n-1條邊。注：不夠成圈的方法是標號法。對于問題 二：設dij是兩個點i與j之間的權，xij之間=0或1 （1表示連接，0則表示不連接），選定其中一個定 點為根比如頂點1,則有 Min dij xijSt xij=1根至少有一條連接到其它點xij=1

3、,j!=1，除根外，每個頂點只有一條邊進入各邊不構成圖對G各頂點編號1到7找到各邊的權的矩陣表示（注：沒有的變則取其值超過所有邊權之和 W=0 1 100 100 100 3 21 0 4 3 100 100 2100 4 0 6 100 100 100100 3 6 0 5 1 5100 100 100 5 0 6 1003 100 100 1 6 0 42 2 100 5100 4 0六、模型建立與求解(算法，程序):求最小生成樹：function tree,value,branch=mintree(edge,vitex)for i=1:e_numminmark-=min(markv(ed

4、ge(eorder(i),2),markv(edge(eorder(i),3);maxmark-=max(markv(edge(eorder(i),2),markv(edge(eorder(i),3);if minmark=0&maxmark=0branch=branch+1;markv(edge(eorder(i),2)=branch;markv(edge(eorder(i),3)=branch;value=value+eup(i);tree(eorder(i)=1;elseif minmark=0markv(edge(eorder(i),2)=maxmark;markv(edge(eord

5、er(i),3)=maxmark;value=value+epu(i);tree(eurder(i)=1;elseif minmark=maxmark&minmark0markv(find(markv=maxmark)=minmark;for jj=maxmark:branchmarkv(find(markv=jj)=jj-1;branch=branch-1;end end帶入數(shù)據(jù)：edge=1 1 2;2 1 7;2 2 7;3 1 6;4 6 7;4 2 3;6 3 4;3 2 4;5 4 7;1 4 6;5 4 5;6 5 6; tree,value,branch=mintree(edg

6、e,7)問題二生成樹和它們的分布：sets:cities/1.7/； level;!level(i)=M市 i 和水平；link(cities,cities);distance, !權值矩陣；x;!權值矩陣可以是不對稱的；distance =0 1 100 100 100 3 2; 1 0 4 3 100 100 2; 100 4 0 6 100 100 100; 100 3 6 0 5 1 5; 100 100 100 5 0 6 100; 3 100 100 1 6 0 4; 2 2 100 5 100 4 0;enddata%最小目標函數(shù)：min=sum(lin(i,j) i#ne#j;

7、distance(i,j)*x(i,j);sum(cities)|i#gt#1:x(1,i)=1;N=size(citese);!The model size;!for city i,except the base (city 1);for(cities(i)|i#gt#1;sum(cities(j) #ne# i； x(j,i)=1;);for(cities(i)|i#gt#1;!level(j)=level(i)+1,if we link j and i;for(cities(j)|j#gt#1 #and# j #ne#i)Lenel(j=level(i)+x(i,j)-(n-2)*(1-

8、x (i, j) ) + (n-3)*x(i,j);七、結果分析與模型檢驗:第一問得結果：tree=1 1 0 1 0 1 0 0 0 1 1 0 value=16,branch=1 ;從而結論為最小生成樹的權位16 (十萬元)。而邊，v1v2,v1v7,v1v6,v2v3,v4v6,v4v3被選中。這說明若要操持城市通信不中斷則必須有6條邊不損壞他們分別是v1v2,v1v7,v1v6,v2v3,v4v6,v4v3，問題二的的結果為：目標值=16，解為：X(1,2)1.000000X(2 ,3)1.000000X(2,4)1.000000X(2,7)1.000000X(4,5)1.000000X(4,6)1.000000八、評價與改進方向：九、總結及心