最小生成樹-數(shù)學(xué)建模-文檔資料

1、123趙根趙根趙明趙明趙亮趙亮趙麗趙麗趙雷趙雷趙虹趙虹趙雨趙雨趙霞趙霞趙云趙云趙梅趙梅趙松趙松類似于自類似于自然界中的然界中的樹樹形象地表形象地表示家族示家族4 56123458691571037生成樹或支撐樹12345869157103如何簡便地得到左圖的生成樹？它應(yīng)有幾條邊？8確定應(yīng)在哪些站點(diǎn)之間鋪設(shè)通訊線路，是否可看作是在相應(yīng)的加權(quán)圖中構(gòu)造最小費(fèi)用的生成樹的問題？9最小生成樹最大生成樹1011如果生成樹如果生成樹*T 的權(quán)的權(quán))(*Tw是是G的所有生成樹的權(quán)中最的所有生成樹的權(quán)中最小者，則稱小者，則稱*T 是是G的的最小生成樹最小生成樹 ，簡稱為，簡稱為 最小樹最小樹，即，即)(min)

2、(*TwTwT=，式中取遍，式中取遍G的所有生成樹的所有生成樹T. 定義定義設(shè)設(shè)),(1EVT =是賦權(quán)圖是賦權(quán)圖),(EVG =的一棵生的一棵生成樹，稱成樹，稱T中全部邊上的權(quán)數(shù)之和為中全部邊上的權(quán)數(shù)之和為生成樹的權(quán)生成樹的權(quán)，記為，記為)(Tw，即，即=1)()(EeewTw. 12最小生成樹算法及其MATLAB程序?qū)崿F(xiàn)131324586915710314 1) 選擇邊選擇邊e1，使得，使得w(e1)盡可能?。槐M可能??；2) 若已選定邊若已選定邊 ，則從，則從ieee,.,21,.,21ieeeE中選取中選取 ，使得，使得:1iei) 為無圈圖，為無圈圖，,.,121ieeeG ii) 是

3、滿足是滿足i)的盡可能小的權(quán)，的盡可能小的權(quán)，)(1iew 3) 當(dāng)?shù)诋?dāng)?shù)?)步不能繼續(xù)執(zhí)行時(shí)，則停止步不能繼續(xù)執(zhí)行時(shí)，則停止. 步驟步驟定理定理 由由Kruskal算法構(gòu)作的任何生成樹算法構(gòu)作的任何生成樹,.,121*=eeeGT都是最小生成樹都是最小生成樹.1512345839157106B: 圖的邊權(quán)矩陣圖的邊權(quán)矩陣;T: 生成樹的邊集生成樹的邊集;C: 生成樹的權(quán)生成樹的權(quán);t: 頂點(diǎn)所屬子樹的編號(hào)頂點(diǎn)所屬子樹的編號(hào)1712345869157103b=1 1 1 2 2 3 3 4; 2 4 5 3 5 4 5 5; 8 1 5 6 7 9 10 3;19123456173202122

4、2324機(jī)器機(jī)器 123456789加工加工的零的零件件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,10625|MM|MM|) j , i (jiji=建模|MM|MM|) j , i (jiji=建模 1) 1) (i,j)=0(i,j)=0和和 (i,j)=1(i,j)=1分別分別表示什么？表示什么？2) 2) 表達(dá)了什么？表達(dá)了什么？27建模模型求解912547863.51.5.14.87.67.750912547863.5.5.14.67.75030 你能給出對(duì)應(yīng)于該機(jī)器分組的零件分類嗎？912547863.5.5.14

5、.67.750模型結(jié)果31 設(shè)是兩點(diǎn)設(shè)是兩點(diǎn)i與與j之間的距離，或之間的距離，或1（1表示連接，表示連接，0表示不連接），并假設(shè)頂點(diǎn)表示不連接），并假設(shè)頂點(diǎn)1是生成樹的根是生成樹的根.則則ijd0ijx=( , )1min ; s.t. 1,() 1,1,() ijiji jAjj Vjij Vd xxxi=根至少有一條邊連接到其他邊除根外，每個(gè)點(diǎn)只有一條邊進(jìn)入（各邊不構(gòu)成圈） 32例例 （最優(yōu)連線問題）我國西部的（最優(yōu)連線問題）我國西部的SV地區(qū)共有地區(qū)共有1個(gè)城市（標(biāo)個(gè)城市（標(biāo)記為記為1）和）和9個(gè)鄉(xiāng)鎮(zhèn)（標(biāo)記為個(gè)鄉(xiāng)鎮(zhèn)（標(biāo)記為2-10）組成，該地區(qū)不久將用）組成，該地區(qū)不久將用上天然氣，其中

6、城市上天然氣，其中城市1含有井源含有井源.現(xiàn)要設(shè)計(jì)一供氣系統(tǒng)，使得現(xiàn)要設(shè)計(jì)一供氣系統(tǒng)，使得從城市從城市1到每個(gè)鄉(xiāng)鎮(zhèn)（到每個(gè)鄉(xiāng)鎮(zhèn)（2-10）都有一條管道相連，并且鋪設(shè)）都有一條管道相連，并且鋪設(shè)的管子的量盡可能的少的管子的量盡可能的少. 下表給出了城鎮(zhèn)之間的距離下表給出了城鎮(zhèn)之間的距離.求求SV地區(qū)的最優(yōu)連線地區(qū)的最優(yōu)連線.3334 解：解： 按照數(shù)學(xué)規(guī)劃寫出相應(yīng)的按照數(shù)學(xué)規(guī)劃寫出相應(yīng)的LINGO程序，程序，MODEL: 1 sets: 2 cities/1.10/:level; !level(i)= the level of city; 3 link(cities, cities): 4 di

7、stance, !The distance matrix; 5 x; ! x(i,j)=1 if we use link i,j; 6 endsets 35 7data: !Distance matrix, it need not be symmetirc; 8 distance = 0 8 5 9 12 14 12 16 17 22 9 8 0 9 15 16 8 11 18 14 22 10 5 9 0 7 9 11 7 12 12 17 11 9 15 7 0 3 17 10 7 15 15 12 12 16 9 3 0 8 10 6 15 15 13 14 8 11 17 8 0 9

8、14 8 16 14 12 11 7 10 10 9 0 8 6 11 15 16 18 12 7 6 14 8 0 11 11 16 17 14 12 15 15 8 6 11 0 10 17 22 22 17 15 15 16 11 11 10 0; 18 enddata36 19n=size(cities); !The model size; 20! Minimize total distance of the links; 21min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j); 22!There must be an arc out of

9、 city 1; 23sum(cities(i)|i #gt# 1: x(1,i)=1; 24!For city i, except the base (city 1); 25for(cities(i) | i #gt# 1 : 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we link j and i;37 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j)

10、31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of city is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,level(i),999999); 36 level(i)=n-1-(n-2)*x(1,i); 37 ); 38! Make the xs 0/1; 39for(link : bin(x); END38利用水平變量利用水平變量(level)來保證所選的邊不構(gòu)成圈來保證所選的邊不構(gòu)成圈.Global optimal solution found at iteration: 34Objective value: 60.00000 Variable Value Reduced Cost X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000