數(shù)學(xué)建模與數(shù)學(xué)實(shí)驗(yàn)網(wǎng)絡(luò)優(yōu)化

最短路問題

圖論是應(yīng)用非常廣泛的運(yùn)籌學(xué)分支，它已經(jīng)廣泛地應(yīng)用于物理學(xué)控制論，信息論，工程技術(shù)，交通運(yùn)輸，經(jīng)濟(jì)管理，電子計(jì)算機(jī)等各項(xiàng)領(lǐng)域。

對于科學(xué)研究，市場和社會生活中許多關(guān)于管理、組織與計(jì)劃中的優(yōu)化問題，都可以用圖論的理論和方法來加以解決。例如，1、各種通信線路的架設(shè)，輸油管道的鋪設(shè)，鐵路或者公路交通網(wǎng)絡(luò)的合理布局等問題。2、在企業(yè)管理中，如何制訂管理計(jì)劃或設(shè)備購置計(jì)劃，使收益最大或費(fèi)用最小問題。圖論介紹3、在組織生產(chǎn)中，如何使各工序銜接好，才能使生產(chǎn)任務(wù)完成得既快又好。4、在現(xiàn)有交通網(wǎng)絡(luò)中，如何使調(diào)運(yùn)的物資數(shù)量多且費(fèi)用最小。實(shí)驗(yàn)?zāi)康膶?shí)驗(yàn)內(nèi)容2．會用MATLAB軟件求最短路1．了解最短路的算法及其應(yīng)用1．圖論的基本概念2．最短路問題及其算法3．最短路的應(yīng)用4．建模案例：最優(yōu)截?cái)嗲懈顔栴}5．實(shí)驗(yàn)作業(yè)圖論的基本概念一、圖的概念1．圖的定義2．頂點(diǎn)的次數(shù)

3．子圖二、圖的矩陣表示1．關(guān)聯(lián)矩陣2．鄰接矩陣返回定義有序三元組G=(V,E,)稱為一個圖,如果：圖的定義定義定義常用術(shù)語：（１）端點(diǎn)相同的邊稱為環(huán)．（２）若一對頂點(diǎn)之間有兩條以上的邊聯(lián)結(jié)，則這些邊稱為重邊．（３）有邊聯(lián)結(jié)的兩個頂點(diǎn)稱為相鄰的頂點(diǎn)，有一個公共端點(diǎn)的邊

稱為相鄰的邊．（４）邊和它的端點(diǎn)稱為互相關(guān)聯(lián)的．

（５）既沒有環(huán)也沒有重邊的圖，稱為簡單圖．（６）任意兩頂點(diǎn)都相鄰的簡單圖，稱為完備圖，記為Kn，其中n

為頂點(diǎn)的數(shù)目．（7）若V=XUY,X∩Y=?,且X中任兩頂點(diǎn)不相鄰，Y中任兩頂點(diǎn)不相鄰，則稱G為二元圖；若X中每一頂點(diǎn)皆與Y中一切頂點(diǎn)相鄰，則G稱為完備二元圖，記為Km,n，其中m,n分別為X與Y的頂點(diǎn)數(shù)目．返回完備圖二元圖完備二元圖頂點(diǎn)的次數(shù)例在一次聚會中，認(rèn)識奇數(shù)個人的人數(shù)一定是偶數(shù).返回子圖返回關(guān)聯(lián)矩陣注：假設(shè)圖為簡單圖鄰接矩陣注：假設(shè)圖為簡單圖賦權(quán)圖最短路問題及其算法一、基本概念二、固定起點(diǎn)的最短路三、每對頂點(diǎn)之間的最短路基本概念樹及其性質(zhì)定義連通且不含圈的無向圖稱為樹G1G2G3樹樹葉分枝點(diǎn)樹枝不是樹森林定理

設(shè)G是具有n個頂點(diǎn)的圖，則下述命題等價：1)G是樹（G無圈且連通）；2)G無圈，且有n-1條邊；3)G連通，且有n-1條邊；4)G無圈，但添加任一條新邊恰好產(chǎn)生一個圈;5)G連通，且刪去一條邊就不連通了（即G為最小連通圖）；6)G中任意兩頂點(diǎn)間有唯一一條路.最短路問題主要內(nèi)容及應(yīng)用：最短路問題是圖論應(yīng)用的基本問題，很多實(shí)際問題，如線路的布設(shè)、運(yùn)輸安排、運(yùn)輸網(wǎng)絡(luò)最小費(fèi)用流等問題,都可通過建立最短路問題模型來求解.最短路問題的兩種方法：Dijkstra和Floyd算法.1)

求賦權(quán)圖中從給定點(diǎn)到其余頂點(diǎn)的最短路.2)求賦權(quán)圖中任意兩點(diǎn)間的最短路.固定起點(diǎn)的最短路假設(shè)在u0-v0的最短路中只取一條，則從u0到其余頂點(diǎn)的最短路將構(gòu)成一棵以u0為根的樹．

因此,可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路．基本思想：最短路是一條路徑，且最短路的任一段也是最短路。算法步驟：

MATLAB(road1)

12

34

5

6

7

8返回w=[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1whilek<nfori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendendll=l;fori=1:nforj=1:kifi~=s(j)ll(i)=ll(i);elsell(i)=inf;endendendlv=inf;fori=1:nifll(i)<lvlv=ll(i);v=i;endend

s(k+1)=vk=k+1u=s(k)endlzMATLAB(road1)w=[0218infinfinfinf;20inf61infinfinf;1inf07infinf9inf;8670512inf;inf1inf503inf9;infinfinf13046;infinf92inf403;infinfinfinf9630]n=size(w,1);w1=w(1,:);

fori=1:nl(i)=w1(i);z(i)=1;ends=[];s(1)=1;u=s(1);k=1

whilek<nfori=1:nforj=1:kifi~=s(j)ifl(i)>l(u)+w(u,i)l(i)=l(u)+w(u,i);z(i)=u;endendendend

%求vll=l;fori=1:nforj=1:kifi==s(j)ll(i)=inf;%S中位點(diǎn)值取為無窮大endendend

lv=min(ll);%求ll的最小值v=find(ll==lv);%最小值所在位置

s(k+1)=vk=k+1u=s(k)

endlzMATLAB(road1new)使用Dijkstra應(yīng)注意：1.可以求任意兩點(diǎn)間的最短路。2.最短路不唯一，但最短路值相等。3.弧值非負(fù)，只能求最小，不能求最大。設(shè)起點(diǎn)為1，終點(diǎn)為n，引入0-1變量xij,邊(i,j)在最短路上，則xij=1，對起點(diǎn)和終點(diǎn)以外的任意一個頂點(diǎn)，如果說明從i出發(fā)的所有邊中必然有一條在最短路上，即最短路經(jīng)過該頂點(diǎn)，則從其它頂點(diǎn)到該頂點(diǎn)的邊中必然有一條邊在最短路上，所以有最短路問題的0-1規(guī)劃法對于頂點(diǎn)1和頂點(diǎn)n，則必然滿足：0-1規(guī)劃的最短路模型為22233122232231232例求下圖點(diǎn)P0到點(diǎn)P11的最短距離。Model:sets:cities/P0,P1,P2,P3,P4,P5,P6,P7,P8,P9,P10,P11/;roads(cities,cities)/P0,P1P0,P4P1,P2P1,P5P4,P8P4,P5P2,P3P2,P6P8,P9P5,P9P5,P6P9,P10P6,P10P10,P11P6,P7P3,P7P7,P11/:w,x;endsetsdata:!Herearethedistancesthatcorrespondtoabovelinks;w=12223332221223232;Enddatan=@size(cities);min=@sum(roads:w*x);@for(cities(i)|i#ne#1#and#i#ne#n:@sum(roads(i,j):x(i,j))=@sum(roads(j,i):x(j,i)));@sum(roads(i,j)|i#eq#1:x(i,j))=1;@sum(roads(i,j)|j#eq#n:x(i,j))=1;@for(roads:@bin(x));end最短路的Lingo程序

Globaloptimalsolutionfound.Objectivevalue:

8.000000VariableValueReducedCostN12.000000.000000W(P0,P1)1.0000000.000000W(P0,P4)2.0000000.000000W(P1,P2)2.0000000.000000W(P1,P5)2.0000000.000000W(P4,P8)3.0000000.000000W(P4,P5)3.0000000.000000W(P2,P3)3.0000000.000000W(P2,P6)2.0000000.000000W(P8,P9)2.0000000.000000W(P5,P9)2.0000000.000000W(P5,P6)1.0000000.000000W(P9,P10)2.0000000.000000W(P6,P10)2.0000000.000000W(P10,P11)3.0000000.000000W(P6,P7)

2.0000000.000000

W(P3,P7)3.0000000.000000W(P7,P11)2.0000000.000000

X(P0,P1)1.0000000.000000X(P0,P4)0.0000000.000000X(P1,P2)0.0000000.000000

X(P1,P5)1.0000000.000000X(P4,P8)0.0000000.000000X(P4,P5)0.0000002.000000X(P2,P3)0.0000000.000000X(P2,P6)0.0000001.000000X(P8,P9)0.0000004.000000X(P5,P9)0.0000002.000000

X(P5,P6)1.0000000.000000X(P9,P10)0.0000000.000000X(P6,P10)0.0000001.000000X(P10,P11)0.0000000.000000

X(P6,P7)1.0000000.000000X(P3,P7)0.0000003.000000

X(P7,P11)1.0000000.000000即P0到P11的最短距離為8，路徑為P0—P1—P5—P6—P7—P11.注：這種模型算法只能計(jì)算起點(diǎn)到終點(diǎn)的最短距離.每對頂點(diǎn)之間的最短路1．求距離矩陣的方法2．求路徑矩陣的方法3．查找最短路路徑的方法（一）算法的基本思想（三）算法步驟（二）算法原理算法的基本思想算法原理——求距離矩陣的方法算法原理——

求路徑矩陣的方法在建立距離矩陣的同時可建立路徑矩陣R．即當(dāng)k被插入任何兩點(diǎn)間的最短路徑時，被記錄在R(k)中，依次求時求得，可由來查找任何點(diǎn)對之間最短路的路徑．)(nRi

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)i到j(luò)的最短路的路徑為：算法步驟D:d(i,j)為i到j(luò)的距離．R：r(i,j)為i到j(luò)之間的插入點(diǎn)．輸入帶權(quán)鄰接矩陣W插入v1插入v2插入v3插入v4插入v5

MATLAB

(road2(floyd))function[D,R]=floyd(a)n=size(a,1);D=afori=1:nforj=1:nR(i,j)=j;endendR

fork=1:nfori=1:nforj=1:nifD(i,k)+D(k,j)<D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=k;endendendkDRend主程序road2.m：a=[09inf3inf;902inf7;inf2024;3inf20inf;inf74inf0];[D,R]=floyd(a)5657536411423練習(xí)求以下網(wǎng)絡(luò)圖中從頂點(diǎn)到其余各頂點(diǎn)的最短路。主程序：w=[0526infinfinf;inf0infinf3infinf;inf30574inf;infinfinf0inf64;infinfinfinf0inf5;infinfinfinf101;infinfinfinfinfinf0];[D,R]=floyd(w)結(jié)果：D=0526767Inf0InfInf3Inf8Inf305545InfInfInf0764InfInfInfInf0Inf5InfInfInfInf101InfInfInfInfInfInf0R=1234636123456512346661234667123456712345671234567一、可化為最短路問題的多階段決策問題二、選址問題1．中心問題2．重心問題返回可化為最短路問題的多階段決策問題返回

選址問題--中心問題MATLAB(road3(floyd))S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=10,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6為最小,故應(yīng)將消防站設(shè)在v3處.R=1222222123336622355225554555333456622255676666667

選址問題--重心問題可見，在第3或第5個礦點(diǎn)建造礦廠都可以使運(yùn)力達(dá)到最小值70。(example3）輸入：D=[0358778.5;3025445.5;5203267.5;8530156.5;7421045.5;7465401.5;8.55.57.56.55.51.50];Q=[3271614]';M=D*Qzuixiao=min(M)k=find(M==zuixiao)輸出：M=13278709270106130zuixiao=70k=35實(shí)驗(yàn)作業(yè)

生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是如何選取合理的生產(chǎn)率.生產(chǎn)率過高，導(dǎo)致產(chǎn)品大量積壓，使流動資金不能及時回籠；生產(chǎn)率過低，產(chǎn)品不能滿足市場需要，使生產(chǎn)部門失去獲利的機(jī)會.可見，生產(chǎn)部門在生產(chǎn)過程中必須時刻注意市場需求的變化，以便適時調(diào)整生產(chǎn)率，獲取最大收益.某生產(chǎn)廠家年初要制定生產(chǎn)策略，已預(yù)知其產(chǎn)品在年初的需求量為a=6萬單位，并以b=1萬單位/月速度遞增.若生產(chǎn)產(chǎn)品過剩，則需付單位產(chǎn)品單位時間（月）的庫存保管費(fèi)C2=0.2元；若產(chǎn)品短缺，則單位產(chǎn)品單位時間的短期損失費(fèi)C3=0.4元.假定生產(chǎn)率每調(diào)整一次帶有固定的調(diào)整費(fèi)C1=1萬元，問：工廠應(yīng)如何制定當(dāng)年的生產(chǎn)策略，使工廠的總損失最小？P119習(xí)題1答案：D=03545352510350152030254515010203535201001025