第8講最短路問題_第1頁
第8講最短路問題_第2頁
第8講最短路問題_第3頁
第8講最短路問題_第4頁
第8講最短路問題_第5頁
已閱讀5頁,還剩56頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

數(shù)學建模與數(shù)學實驗網(wǎng)絡優(yōu)化

最短路問題

圖論是應用非常廣泛的運籌學分支,它已經(jīng)廣泛地應用于物理學控制論,信息論,工程技術,交通運輸,經(jīng)濟管理,電子計算機等各項領域。

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

3.子圖二、圖的矩陣表示1.關聯(lián)矩陣2.鄰接矩陣返回定義有序三元組G=(V,E,)稱為一個圖,如果:圖的定義定義定義常用術語:(1)端點相同的邊稱為環(huán).(2)若一對頂點之間有兩條以上的邊聯(lián)結,則這些邊稱為重邊.(3)有邊聯(lián)結的兩個頂點稱為相鄰的頂點,有一個公共端點的邊

稱為相鄰的邊.(4)邊和它的端點稱為互相關聯(lián)的.

(5)既沒有環(huán)也沒有重邊的圖,稱為簡單圖.(6)任意兩頂點都相鄰的簡單圖,稱為完備圖,記為Kn,其中n

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

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

求賦權圖中從給定點到其余頂點的最短路.2)求賦權圖中任意兩點間的最短路.固定起點的最短路假設在u0-v0的最短路中只取一條,則從u0到其余頂點的最短路將構成一棵以u0為根的樹.

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

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中位點值取為無窮大endendend

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

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

endlzMATLAB(road1new)使用Dijkstra應注意:1.可以求任意兩點間的最短路。2.最短路不唯一,但最短路值相等。3.弧值非負,只能求最小,不能求最大。設起點為1,終點為n,引入0-1變量xij,邊(i,j)在最短路上,則xij=1,對起點和終點以外的任意一個頂點,如果說明從i出發(fā)的所有邊中必然有一條在最短路上,即最短路經(jīng)過該頂點,則從其它頂點到該頂點的邊中必然有一條邊在最短路上,所以有最短路問題的0-1規(guī)劃法對于頂點1和頂點n,則必然滿足:0-1規(guī)劃的最短路模型為22233122232231232例求下圖點P0到點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.注:這種模型算法只能計算起點到終點的最短距離.每對頂點之間的最短路1.求距離矩陣的方法2.求路徑矩陣的方法3.查找最短路路徑的方法(一)算法的基本思想(三)算法步驟(二)算法原理算法的基本思想算法原理——求距離矩陣的方法算法原理——

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

j算法原理——

查找最短路路徑的方法pkp2p1p3q1q2qm則由點i到j的最短路的路徑為:算法步驟D:d(i,j)為i到j的距離.R:r(i,j)為i到j之間的插入點.輸入帶權鄰接矩陣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練習求以下網(wǎng)絡圖中從頂點到其余各頂點的最短路。主程序:w=[0526infinfinf;inf0infinf3infinf;inf30574inf;infinfinf0inf64;infinfinfinf0inf5;infinfinfinf101;infinfinfinfinfinf0];[D,R]=floyd(w)結果: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為最小,故應將消防站設在v3處.R=1222222123336622355225554555333456622255676666667

選址問題--重心問題可見,在第3或第5個礦點建造礦廠都可以使運力達到最小值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實驗作業(yè)

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論