數(shù) 學(xué) 建 模光纖問(wèn)題

1、數(shù)學(xué)建模計(jì)算實(shí)驗(yàn)報(bào)告數(shù)學(xué)建模課程組廣西科技大學(xué)數(shù)學(xué)建模計(jì)算實(shí)驗(yàn)報(bào)告學(xué)生姓名：學(xué)號(hào)：一、實(shí)驗(yàn)題目名稱:光纖鋪設(shè)問(wèn)題實(shí)驗(yàn)內(nèi)容：設(shè)有七個(gè)城市v1 ,v2 ,v3 ,v4 ,v5 ,v6 ,v7。它們之間有通信光纖連通，其布置 如下圖G且線段上數(shù)值為每條光纖的造價(jià)（單位十萬(wàn)元）。問(wèn)至少有幾條光纖不出故障，城 市間的通信才不會(huì)中斷，若要造一個(gè)主十網(wǎng)絡(luò)，這些不出故障的光纖應(yīng)如何分布，才能使總 的造價(jià)最低？圖B三、實(shí)驗(yàn)?zāi)康模航⒛Ｐ颓蟪霰３殖鞘型ㄐ挪恢袛嗟淖钚」饫w數(shù)，并求如何分布 這些光纖使得造價(jià)最低。四、問(wèn)題分析和建模方向:對(duì)于問(wèn)題一，這是一個(gè)求G圖的生成樹(shù)的問(wèn)題，分析 易知G的生成樹(shù)有6條邊，即至少需要

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

3、,j!=1，除根外，每個(gè)頂點(diǎn)只有一條邊進(jìn)入各邊不構(gòu)成圖對(duì)G各頂點(diǎn)編號(hào)1到7找到各邊的權(quán)的矩陣表示（注：沒(méi)有的變則取其值超過(guò)所有邊權(quán)之和 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六、模型建立與求解(算法，程序):求最小生成樹(shù)：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)問(wèn)題二生成樹(shù)和它們的分布：sets:cities/1.7/； level;!level(i)=M市 i 和水平；link(cities,cities);distance, !權(quán)值矩陣；x;!權(quán)值矩陣可以是不對(duì)稱的；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%最小目標(biāo)函數(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);七、結(jié)果分析與模型檢驗(yàn):第一問(wèn)得結(jié)果：tree=1 1 0 1 0 1 0 0 0 1 1 0 value=16,branch=1 ;從而結(jié)論為最小生成樹(shù)的權(quán)位16 (十萬(wàn)元)。而邊，v1v2,v1v7,v1v6,v2v3,v4v6,v4v3被選中。這說(shuō)明若要操持城市通信不中斷則必須有6條邊不損壞他們分別是v1v2,v1v7,v1v6,v2v3,v4v6,v4v3，問(wèn)題二的的結(jié)果為：目標(biāo)值=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八、評(píng)價(jià)與改進(jìn)方向：九、總結(jié)及心