數(shù)學(xué)建模提高班專題六網(wǎng)絡(luò)優(yōu)化模型及案例分析資料

數(shù)學(xué)建模提高班專題六網(wǎng)絡(luò)優(yōu)化模型及案例分析資料第1頁/共96頁從農(nóng)夫怎樣過河談起農(nóng)夫過河獨(dú)木橋一般過河問題的解決策略選課問題第2頁/共96頁農(nóng)夫過河3第3頁/共96頁農(nóng)夫過河擺渡人F狼W羊G菜C4第4頁/共96頁

南岸狀態(tài)：

16種，其中WG,GC,WGC，從而FC,FW,F為不允許狀態(tài)，F(xiàn)WGCFWGFWCFGCFGOCGWWC10個(gè)允許狀態(tài)：農(nóng)夫過河5第5頁/共96頁FWGCFWGFWCFGCFGOCGWWC尋求圖中從頂點(diǎn)“FWGC”到頂點(diǎn)“O”的最短路徑，這樣的路徑有幾條？求出最優(yōu)的渡河方案。想語言描述時(shí)未顯示的關(guān)系躍然紙上農(nóng)夫過河6第6頁/共96頁FWGCFWGFWCFGCFGOCGWWCFWGCFWGFWCFGCFGOCGWWC農(nóng)夫過河7第7頁/共96頁獨(dú)木橋8第8頁/共96頁一般過河問題的解決策略多少種狀態(tài)狀態(tài)如何轉(zhuǎn)換花的時(shí)間怎么計(jì)算最后求什么9第9頁/共96頁選課問題學(xué)校要為一年級的研究生開設(shè)六門基礎(chǔ)數(shù)學(xué)課：統(tǒng)計(jì)(S)，數(shù)值分析(N)，圖論(G)，矩陣論(M)，隨機(jī)過程(R)和數(shù)理方程(P)。按培養(yǎng)計(jì)劃，注冊的學(xué)生必須選修其中的一門以上，你作為教務(wù)管理人員，要設(shè)法安排一個(gè)課表，使每個(gè)學(xué)生所選的課程，在時(shí)間上不會(huì)發(fā)生沖突。10第10頁/共96頁選課問題11第11頁/共96頁選課問題為什么會(huì)出現(xiàn)時(shí)間上的沖突？時(shí)間沖突的本質(zhì)是什么？如何表示課程在時(shí)間上沖突？如果把一門課程看成圖中的頂點(diǎn)，那么連接兩點(diǎn)的邊表示什么？12第12頁/共96頁SNGRPM?完成上述表示課程沖突關(guān)系的線圖直觀、清晰地表達(dá)已知信息的方式13第13頁/共96頁圖是一種思考問題的方法圖有兩個(gè)基本要素--頂點(diǎn)和邊頂點(diǎn)表示事物邊表示兩個(gè)事物之間的關(guān)系增加第三個(gè)要素--邊的權(quán)值可以表示關(guān)系深淺、大小、重要等程度用圖來思考問題本質(zhì)是考慮事物之間的聯(lián)系14第14頁/共96頁圖是一種思考問題的方法圖可以畫出來v1v2v5v6v7v4v3abjkcghidfe15第15頁/共96頁圖是一種思考問題的方法圖也可以用矩陣來表示，最常用的是鄰接矩陣v1v2v5v6v7v4v3abjkcghidfe16第16頁/共96頁鄰接矩陣的優(yōu)點(diǎn)：容易理解容易轉(zhuǎn)換為具體的圖便于計(jì)算機(jī)編程計(jì)算圖是一種思考問題的方法17第17頁/共96頁最短路問題固定起點(diǎn)的最短路每對頂點(diǎn)之間的最短路選址問題第18頁/共96頁固定起點(diǎn)的最短路最短路是一條路徑，且最短路的任一段也是最短路．

假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹．

因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．19第19頁/共96頁20第20頁/共96頁算法步驟：21第21頁/共96頁

TOMATLAB(road1)22第22頁/共96頁23第23頁/共96頁

12

34

5

6

7

824第24頁/共96頁每對頂點(diǎn)之間的最短路1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟25第25頁/共96頁算法的基本思想26第26頁/共96頁算法原理——求距離矩陣的方法27第27頁/共96頁算法原理——求路徑矩陣的方法在建立距離矩陣的同時(shí)可建立路徑矩陣R．即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在R(k)中，依次求時(shí)求得，可由來查找任何點(diǎn)對之間最短路的路徑．)(nR28第28頁/共96頁i

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：29第29頁/共96頁算法步驟30第30頁/共96頁

TO

MATLAB

(road2(floyd))31第31頁/共96頁

選址問題--中心問題

TOMATLAB

(road3(floyd))32第32頁/共96頁S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處.33第33頁/共96頁

選址問題--重心問題34第34頁/共96頁最小生成樹問題樹圖最小生成樹Kruskal算法Prim算法第35頁/共96頁趙根趙明趙亮趙麗趙雷趙虹趙雨趙霞趙云趙梅趙松樹圖——直觀形象的表示工具類似于自然界中的樹形象地表示家族36第36頁/共96頁樹：

沒有圈的連通圖

樹中任意兩點(diǎn)間有唯一路徑。

樹的邊數(shù)恰好為頂點(diǎn)數(shù)減1。

樹圖——直觀形象的表示工具37第37頁/共96頁

城市電信局有許多業(yè)務(wù)如收費(fèi)，營業(yè)，112，114等，希望在全市范圍實(shí)現(xiàn)計(jì)算機(jī)聯(lián)網(wǎng)服務(wù)，共享各種資源。一個(gè)主要關(guān)心的問題是：用數(shù)據(jù)通訊線把一組站點(diǎn)聯(lián)結(jié)起來，而不允許通訊線在非站點(diǎn)處相交，如何連接可使通訊線的花費(fèi)最?。恳河?jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)38第38頁/共96頁12345869157103引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)最經(jīng)濟(jì)的網(wǎng)絡(luò)不應(yīng)該有任何封閉的回路。39第39頁/共96頁引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)生成樹或支撐樹(spanningtree)：G的子圖且是樹，其頂點(diǎn)集等于G的頂點(diǎn)集；12345869157103如何簡便地得到左圖的生成樹？它應(yīng)有幾條邊？想40第40頁/共96頁確定應(yīng)在哪些站點(diǎn)之間鋪設(shè)通訊線路，是否可看作是在相應(yīng)的加權(quán)圖中構(gòu)造最小費(fèi)用的生成樹的問題？引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)41第41頁/共96頁最小生成樹最大生成樹引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)想1)一個(gè)完全圖Kn有多少不同的生成樹？2)如何求其最小生成樹?42第42頁/共96頁

10個(gè)頂點(diǎn)的完全圖，其不同的生成樹就有一億棵。一般地，n個(gè)頂點(diǎn)的完全圖，其不同的生成樹個(gè)數(shù)為nn-2。

30個(gè)頂點(diǎn)的完全圖就有3028個(gè)生成樹，求最小生成樹時(shí)用窮舉法是無效的。引例：計(jì)算機(jī)網(wǎng)絡(luò)的線路設(shè)計(jì)43第43頁/共96頁最小生成樹與算法如果生成樹*T的權(quán))(*Tw是G的所有生成樹的權(quán)中最小者，則稱*T是G的最小生成樹，簡稱為最小樹，即)}({min)(*TwTwT?=，式中取遍G的所有生成樹T.

定義設(shè)),(1EVT=是賦權(quán)圖),(EVG=的一棵生成樹，稱T中全部邊上的權(quán)數(shù)之和為生成樹的權(quán)，記為)(Tw，即??=1)()(EeewTw.

44第44頁/共96頁P(yáng)rim算法Kruskal算法最小生成樹算法及其MATLAB程序?qū)崿F(xiàn)算法的MATLAB程序?qū)崿F(xiàn)45第45頁/共96頁基本思想:

最初把圖的n個(gè)頂點(diǎn)看作n個(gè)分離的部分樹，每個(gè)樹具有一個(gè)頂點(diǎn)，算法的每一步選擇可連接兩分離樹的邊中權(quán)最小的邊連接兩個(gè)部分樹，合二為一,部分樹逐步減少，直到只有一個(gè)部分樹（n-1步之后）便得到最小生成樹。Kruskal算法13245869157103時(shí)間復(fù)雜度:O(m)其中m為圖的邊數(shù)46第46頁/共96頁Kruskal算法1)選擇邊e1，使得w(e1)盡可能??；2)若已選定邊，則從中選取，使得:i)為無圈圖，ii)是滿足i)的盡可能小的權(quán)，3)當(dāng)?shù)?)步不能繼續(xù)執(zhí)行時(shí)，則停止.

步驟定理

由Kruskal算法構(gòu)作的任何生成樹都是最小生成樹.47第47頁/共96頁Kruskal算法123458391571061號子樹

2號子樹

3號子樹給每個(gè)子樹一個(gè)不同的編號48第48頁/共96頁初始化：j0,T,c0,k0；對所有頂點(diǎn)i,t(i)i.jj+1t(B(1,j))t(B(2,j))TT(B(1,j),B(2,j)),cc+B(3,j),kk+1，i0t(i)=max{t(B(1,j)),t(B(2,j))t(i)min{t(B(1,j)),t(B(2,j)),k=n-1或j=mT,c整理邊權(quán)矩陣NYi=n終止NYYii+1NYNB:圖的邊權(quán)矩陣;T:生成樹的邊集;C:生成樹的權(quán);t:頂點(diǎn)所屬子樹的編號第49頁/共96頁Kruskal算法

例:用Kruskal算法求引例中的加權(quán)圖的最小生成樹。12345869157103b=[11122334;24535455;815679103];邊權(quán)矩陣：50第50頁/共96頁b=[11122334;24535455;815679103];[B,i]=sortrows(b',3);B=B’;m=size(b,2);n=5;t=1:n;k=0;T=[];c=0;fori=1:mift(B(1,i))~=t(B(2,i))k=k+1;T=[T,B(1:2,i)];c=c+B(3,i);%修改過tmin=min(t(B(1,i)),t(B(2,i)));tmax=max(t(B(1,i)),t(B(2,i))); forj=1:n ift(j)==tmax t(j)=tmin;endendend

ifk==n-1break;endendT,c第51頁/共96頁程序運(yùn)行結(jié)果：T=14452325c=17Kruskal算法12345617352第52頁/共96頁P(yáng)rim算法●

基本思想：任選一個(gè)頂點(diǎn)v0開始，連接與v0最近的頂點(diǎn)v1,得子樹T1，再連接與T1最近的頂點(diǎn)v2得子樹T2，如此繼續(xù)下去，直到所有頂點(diǎn)都用到為止?！?/p>

時(shí)間復(fù)雜度：O(n2),n為圖的頂點(diǎn)數(shù)53第53頁/共96頁P(yáng)rim算法54第54頁/共96頁提示Kruskal算法和Prim算法都蘊(yùn)涵了貪婪法的思想，是貪婪法；貪婪法的基本思想：把解看成是由若干個(gè)部件構(gòu)成，每一步求出解的一個(gè)部件（不是從整體或長遠(yuǎn)的角度考慮，只是局部或當(dāng)前的最好選擇）。求出的一個(gè)個(gè)部件組合而作為最終的解。55第55頁/共96頁貪婪法可被用于各種各樣問題的處理。該法只是一種試探法，計(jì)算上簡便有效，可提供正確解的一個(gè)近似。但一般情況下，不能保證輸出的解是正確的。其正確性需要證明，這往往比較困難。已證明,求最小生成樹的Kruskal算法和Prim算法都是正確的

注意56第56頁/共96頁

分組技術(shù)是設(shè)計(jì)制造系統(tǒng)的一種方法，它把生產(chǎn)零件的機(jī)器分組，相應(yīng)地把需生產(chǎn)的零件分類，使零件跨組加工的情形盡量少，最理想的情況是使每個(gè)零件的加工，都在組內(nèi)完成。假設(shè)有13種零件，需在9臺(tái)機(jī)器上加工。在各臺(tái)機(jī)器上加工的零件號在下表中給出。范例：制造系統(tǒng)的分組技術(shù)57第57頁/共96頁范例：制造系統(tǒng)的分組技術(shù)機(jī)器123456789加工的零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,10658第58頁/共96頁

設(shè)用Mi表示需由機(jī)器i加工的零件集，對任意兩臺(tái)機(jī)器i,j,定義相異度：范例：制造系統(tǒng)的分組技術(shù)建模59第59頁/共96頁“”：對稱差，分子：在機(jī)器i但不在機(jī)器j上加工，或在機(jī)器j但不在機(jī)器i上加工的零件數(shù)。分母：或在機(jī)器i，或在機(jī)器j上加工的零件數(shù)。顯然01建模1)(i,j)=0和(i,j)=1分別表示什么？2)表達(dá)了什么？想第60頁/共96頁構(gòu)造加權(quán)圖

以機(jī)器為頂點(diǎn)，作一個(gè)完全圖，每條邊(i,j)被賦予權(quán)(i,j)。原問題的轉(zhuǎn)化加權(quán)圖的最小生成樹是由那些相異度最小的邊構(gòu)成的連通圖，如果希望把機(jī)器分成k個(gè)組，就繼續(xù)刪去最小生成樹上權(quán)最大的k-1條邊。于是得到k個(gè)分離的子樹，每棵樹的頂點(diǎn)集就構(gòu)成各機(jī)器組。建模61第61頁/共96頁對表1給出的數(shù)據(jù)，加權(quán)圖的邊權(quán)矩陣如下：[111111112222222333333444445555666778;234567893456789456789567896789789899;0.510.890.141111110.621111111110.50.870.670.750.7511111111011]

用Kruskal算法可求出最小生成樹，在前面給出的Kruskal算法的MATLAB程序中，邊權(quán)矩陣b的值改為此處的邊權(quán)矩陣，頂點(diǎn)數(shù)n改為9即可。模型求解第62頁/共96頁T=7815123946474513c=4.4300912547863.51.5.14.87.67.750機(jī)器的分組：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750第63頁/共96頁

你能給出對應(yīng)于該機(jī)器分組的零件分類嗎？機(jī)器的分組：{3，9}，{1，2，5}，{4，6，7，8}。912547863.5.5.14.67.750想模型結(jié)果64第64頁/共96頁

設(shè)是兩點(diǎn)i與j之間的距離，或1（1表示連接，0表示不連接），并假設(shè)頂點(diǎn)1是生成樹的根.則最小生成樹問題的0-1規(guī)劃模型65第65頁/共96頁最小生成樹問題的0-1規(guī)劃模型例（最優(yōu)連線問題）我國西部的SV地區(qū)共有1個(gè)城市（標(biāo)記為1）和9個(gè)鄉(xiāng)鎮(zhèn)（標(biāo)記為2--10）組成，該地區(qū)不久將用上天然氣，其中城市1含有井源.現(xiàn)要設(shè)計(jì)一供氣系統(tǒng)，使得從城市1到每個(gè)鄉(xiāng)鎮(zhèn)（2--10）都有一條管道相連，并且鋪設(shè)的管子的量盡可能的少.下表給出了城鎮(zhèn)之間的距離.求SV地區(qū)的最優(yōu)連線.66第66頁/共96頁最小生成樹問題的0-1規(guī)劃模型67第67頁/共96頁最小生成樹問題的0-1規(guī)劃模型

解：按照數(shù)學(xué)規(guī)劃寫出相應(yīng)的LINGO程序，MODEL:1]sets:2]cities/1..10/:level;!level(i)=thelevelofcity;3]link(cities,cities):4]distance,!Thedistancematrix;5]x;!x(i,j)=1ifweuselinki,j;6]endsets

68第68頁/共96頁最小生成樹問題的0-1規(guī)劃模型

7]data:!Distancematrix,itneednotbesymmetirc;8]distance=08591214121617229]809151681118142210]5907911712121711]91570317107151512]12169308106151513]14811178091481614]12117101090861115]161812761480111116]1714121515861101017]2222171515161111100;18]enddata69第69頁/共96頁最小生成樹問題的0-1規(guī)劃模型

19]n=@size(cities);!Themodelsize;20]!Minimizetotaldistanceofthelinks;21]min=@sum(link(i,j)|i#ne#j:distance(i,j)*x(i,j));22]!Theremustbeanarcoutofcity1;23]@sum(cities(i)|i#gt#1:x(1,i))>=1;24]!Forcityi,exceptthebase(city1);25]@for(cities(i)|i#gt#1:26]!Itmustbeentered;27]@sum(cities(j)|j#ne#i:x(j,i))=1;28]!level(j)=levle(i)+1,ifwelinkjandi;70第70頁/共96頁最小生成樹問題的0-1規(guī)劃模型29]@for(cities(j)|j#gt#1#and#j#ne#i:30]level(j)>=level(i)+x(i,j)31]-(n-2)*(1-x(i,j))+(n-3)*x(j,i);32]);33]!Thelevelofcityisatleast1butnomoren-1,34]andis1ifitlinkstobase(city1);35]@bnd(1,level(i),999999);36]level(i)<=n-1-(n-2)*x(1,i);37]);38]!Makethex's0/1;39]@for(link:@bin(x));END71第71頁/共96頁最小生成樹問題的0-1規(guī)劃模型利用水平變量(level)來保證所選的邊不構(gòu)成圈.Globaloptimalsolutionfoundatiteration:34Objectivevalue:60.00000VariableValueReducedCostX(1,2)1.0000008.000000X(1,3)1.0000005.000000X(3,4)1.0000007.000000X(3,7)1.0000007.000000X(4,5)1.0000003.000000X(5,8)1.0000006.000000X(7,9)1.0000006.000000X(9,6)1.0000008.000000X(9,10)1.00000010.0000072第72頁/共96頁最小生成樹問題的0-1規(guī)劃模型連接這10個(gè)城鎮(zhèn)的最小距離為60公里，其連接情況如下.SV地區(qū)的