運籌學(xué)6(圖與網(wǎng)絡(luò)分析).ppt
《運籌學(xué)6(圖與網(wǎng)絡(luò)分析).ppt》由會員分享，可在線閱讀，更多相關(guān)《運籌學(xué)6(圖與網(wǎng)絡(luò)分析).ppt（69頁珍藏版）》請在裝配圖網(wǎng)上搜索。
西安理工大學(xué)工商管理學(xué)院,運籌學(xué)OperationsResearch,運籌學(xué)OperationsResearch,,,Chapter8圖與網(wǎng)絡(luò)分析GraphandNetwork,1.圖與網(wǎng)絡(luò)的基本知識樹3.最短路問題4.最大流問題,,,C,B,A,引例：哥尼斯堡七橋問題,您能從A、B、C或D任意一點出發(fā)走遍7座橋并且每座橋只走一次最后回到原出發(fā)點嗎？,D,E.Euler提出(1736年）：,中國郵路問題：管梅谷（1962年）提出一個郵遞員，負責(zé)某一地區(qū)的信件投遞。他每天要從郵局出發(fā)，走遍該地區(qū)所有街道再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？,我們在實際生活、生產(chǎn)和科研活動中經(jīng)?？吹皆S多的網(wǎng)絡(luò)，如互聯(lián)網(wǎng)、通信網(wǎng)、公路網(wǎng)、管道網(wǎng)、銷售網(wǎng)等。對網(wǎng)絡(luò)進行研究是希望解決其中的一些優(yōu)化問題，網(wǎng)絡(luò)最優(yōu)化能為人們管理和控制這些網(wǎng)絡(luò)系統(tǒng)提供一套有效的方法。,例某家電配送中心需要為多個銷售點送貨，配送中心與銷售點以及銷售點之間的相對位置和運輸情況可以用圖來表示。其中，點v1，v2，…，v7代表銷售點，邊表示運輸路線。若已知每條路線行走所需的時間，請幫助配送中心管理人員設(shè)計一條送貨路線，使送貨車輛用最短的時間送完貨物，并回到配送中心。,,基本的網(wǎng)絡(luò)最優(yōu)化問題有4個，即最小樹問題，最短路問題、最大流問題、最小費用最大流問題。這些問題的數(shù)學(xué)模型實際上大都是線性規(guī)劃問題，但使用線性規(guī)劃的單純形法去求解，過程非常繁瑣，本章介紹的網(wǎng)絡(luò)分析方法能有效的解決這些問題。,圖Ｇ可定義為點和邊的集合，記作,式中Ｖ是點的集合，Ｅ是邊的集合。注意上面定義的圖Ｇ區(qū)別于幾何學(xué)中的圖。在幾何學(xué)中，圖中點的位置、線的長度和斜率等都十分重要，而這里只關(guān)心圖中有多少點以及哪些點之間有線相連，如果給圖中的點和邊賦以具體的含義和權(quán)數(shù)，如距離、費用、容量等，把這樣的圖稱為網(wǎng)絡(luò)圖，記作Ｎ。圖和網(wǎng)絡(luò)分析的方法已廣泛應(yīng)用于物理、化學(xué)、控制論、信息論、計算機科學(xué)和經(jīng)濟管理等各個領(lǐng)域。,8.1圖與網(wǎng)絡(luò)的基本知識,如圖8-1,定義1端點，關(guān)聯(lián)邊，相鄰若有邊e可表示為e=[vi,vj],稱vi和vj是邊e的端點，反之稱邊e為點vi或vj的關(guān)聯(lián)邊。若點vi、vj與同一邊關(guān)聯(lián)，稱點vi和vj相鄰；若邊ei和ej具有公共的端點，稱邊ei和ej相鄰。,,例如圖8－1，,v2和v4是邊e6的端點，反之邊e6是點v2、v4的關(guān)聯(lián)邊。點v2、v4相鄰；邊e6與e5、e4相鄰。,圖8－1,e2可記作：,一、圖與網(wǎng)絡(luò)的基本概念,定義2環(huán)，多重邊，簡單圖如果邊e的兩個端點相重，稱該邊為環(huán)。如圖8－１中邊e1為環(huán)。如果兩個點之間的邊多于一條，稱為多重邊，如圖8－１中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。,定義3次，奇點，偶點，孤立點與某一個點vi相關(guān)聯(lián)的邊的數(shù)目稱為點vi的次（也叫做度），記作d(vi)。圖６－１中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點稱作奇點，次為偶數(shù)的點稱作偶點，次為0的點稱作孤立點。,定理1任何圖中，頂點次數(shù)的總和等于邊數(shù)的2倍。,定理2任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。,定義4有向圖：如果圖的每條邊都有一個方向則稱為有向圖,定義5混合圖：如何圖G中部分邊有方向則稱為混合圖,有向圖,定義6有向圖中，以Vi為起始點的邊數(shù)稱為點Vi的出次，用表示；有向圖中，以Vi為終點的邊數(shù)稱為點Vi的入次，用表示。,結(jié)論1：Vi點的出次與入次之和就是該點的次。,結(jié)論2：有向圖中，所有頂點的入次之和等于所有頂點的出次之和。,定義7：子圖、生成子圖（支撐子圖）,圖G1={V1、E1}和圖G2={V2，E2}如果稱G1是G2的一個子圖。若有則稱G1是G2的一個支撐子圖（部分圖）。圖8-2（a）是圖6-1的一個子圖，圖8-2（b）是圖8-1的支撐子圖，注意支撐子圖也是子圖,子圖不一定是支撐子圖。,,定義8網(wǎng)絡(luò)（賦權(quán)圖）：,設(shè)圖G＝（V，E），對G的每一條邊(vi,vj)相應(yīng)的有一條數(shù)w(vi,vj)(或記為wij)，wij稱為邊(vi,vj)的權(quán),賦有權(quán)的圖G稱為網(wǎng)絡(luò)（賦權(quán)圖）。,這里的權(quán)數(shù)可以是時間、費用、距離等，視不同背景代表不同的含義。,賦權(quán)圖,定義9鏈、路、回路（圈）▲無向圖中有些點和邊的交替序列對任意vi,t－1和vit(2≤t≤k)均相鄰，稱μ從v0到vk的鏈。,,,圖8－1中，μ1={v5,e8,v3,e3,v1,e2,v2,e4,v3,e7,v5}是一條鏈，μ1中因頂點v3重復(fù)出現(xiàn)，不能稱作路。,二、連通圖,▲如果鏈中所有的頂點v0，v1，…，vk也不相同，這樣的鏈稱初等鏈（或路）。,▲如果鏈中各邊e1,e2…,ek互不相同稱為簡單鏈。,▲當(dāng)v0與vk重合時稱為回路（或圈），如果邊不重復(fù)稱為簡單回路，如果邊不重復(fù)點也不重復(fù)則稱為初等回路。,是一條鏈也是一條路。是一條回路并且是簡單回路。,定義10連通圖,若在一個圖中，如果每一對頂點之間至少存在一條鏈，稱這樣的圖為連通圖，否則稱該圖是不連通的。圖8－1是連通圖。,μ3={v4,e7,v3,e3,v1,e2,v2,e6,v4},●歐拉回路,定義11連通圖G中，若存在一條回路，經(jīng)過每邊一次且僅一次，則稱這條回路為歐拉回路。具有歐拉回路的圖稱為歐拉圖（E圖）。,哥尼斯堡七橋問題：尋找一條歐拉回路,,定理3無向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中無奇點。,七橋問題：d(A)=3,d(B)=3,d(C)=5,d(D)=3有四個奇點，故不是歐拉圖,定理4有向連通圖G是歐拉圖，當(dāng)且僅當(dāng)G中每個頂點的出次等于入次。,●中國郵路問題,討論：奇偶點圖上作業(yè)法,v1,v2,v3,v4,v5,v6,v7,v8,v9,8.2樹,●樹的概念,樹是圖論中結(jié)構(gòu)最簡單但又十分重要的圖，在許多領(lǐng)域都有應(yīng)用。如：運動員抽簽結(jié)構(gòu)圖,定義樹、生成樹：,①無圈的連通圖稱為樹；②若G1是G2的一個支撐子圖并且是一棵樹，則稱G1是G2的一棵生成樹。,圖8－3(a)是一棵樹，圖8－3(b)是圖8－1的一棵生成樹。,v1,v1,圖8－1,圖8－3(a),圖8－3(b),定理：圖G=（V，E）有生成樹的充分必要條件為G是連通圖。,●生成樹的尋求方法,在圖Ｇ中，每步選出一條邊使它與已選邊不構(gòu)成圈，直到選夠n-1條邊為止。,（１）深探法步驟：①任取一點v，給v以標(biāo)號０；②若某點u已得標(biāo)號i，檢查其端點w是否已標(biāo)號；③若端點w未標(biāo)號，則給w以標(biāo)號i+1;重復(fù)②若端點均已標(biāo)號，則退到標(biāo)號i－1的點，重復(fù)②。,,,,,,,,,,,,,,,,,,,,,０,１,２,３,４,５,６,７,８,９,１０,１１,１２,１３,,,,,,,,,,,,,,(2)廣探法,①任取一點v，給v以標(biāo)號０；②檢查其所有端點wi是否已標(biāo)號；若端點w未標(biāo)號，則給所有wi以標(biāo)號i+1;③對標(biāo)號i+1的點重復(fù)②。,,,,,,,,,,,,,,,,,,,,,０,１,１,１,１,２,２,２,２,２,３,３,４,３,,,,,,（3）破圈法在圖Ｇ中任意取一個圈，從圈上任意舍棄一條邊，將這個圈破掉；重復(fù)上述步驟，直到圖Ｇ中沒有圈為止。,,例：某鄉(xiāng)有9個自然村，其鄉(xiāng)間道路如下圖，要求：以v0村為中心沿道路架設(shè)有線廣播網(wǎng)絡(luò)，應(yīng)如何架設(shè)？,●最小生成樹,定義：設(shè)G＝[V,E]是一個連通圖，每一條邊ei∈E具有長度C(ei)≥0,G的任意生成樹T各條邊的長度之和稱為樹T的長度，記為C（T）。長度最小的生成樹稱為最小樹。,最小樹的應(yīng)用：電信網(wǎng)絡(luò)（計算機網(wǎng)絡(luò)、電話專用線網(wǎng)絡(luò)、有線電視網(wǎng)絡(luò)等等）的設(shè)計低負荷運輸網(wǎng)絡(luò)的設(shè)計，使得網(wǎng)絡(luò)中提供鏈接的部分（如鐵路、公路等等）的總成本最小高壓輸電線路網(wǎng)絡(luò)的設(shè)計電器設(shè)備線路網(wǎng)絡(luò)（如數(shù)字計算機系統(tǒng)）的設(shè)計，使得線路總長度最短連接多個場所的管道網(wǎng)絡(luò)設(shè)計,求最小樹是在一個無向連通圖G中求一棵最小生成樹。,避圈法（加邊法）：去掉G中所有邊，得到n個孤立點；然后加邊；,加邊的原則：從最短邊開始添加，加邊的過程中不能形成圈，直到連通（n－1條邊）。,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,MinC(T)=15,求最小樹的方法：避圈法和破圈法,,破圈法：任取一圈，去掉圈中最長邊，直到無圈。,,,,,,,,,,,,,,,,,v1,v2,v3,v4,v5,v6,4,3,5,2,1,,,,,,,,,,,,,得到最小樹：,MinC(T)=15,●根樹及其應(yīng)用,定義有向樹：若一個有向圖是一棵樹，則稱這個有向圖為有向樹。,定義若有向樹T恰有一個結(jié)點的入次為0，其余各點入次均為1，則稱T為根樹。,入次為0的點，稱為根,出次為0的點，稱為葉,其它頂點，稱為分枝點,根到某頂點vi的道路長度，稱為vi點的層次。,定義在根樹T中，若每個頂點的出次小于或等于m，則稱T為m叉樹。若每個頂點的出次恰好等于m或零，則稱T為完全m叉樹。,當(dāng)m=2時，稱為二叉樹、完全二叉樹。,記二叉樹各葉子的權(quán)為pi，根到各葉子的距離（層次）為li二叉樹的總權(quán)數(shù)：,最優(yōu)二叉樹：滿足總權(quán)最小的二叉樹稱為最優(yōu)二叉樹。霍夫曼（DAHuffman)給出了一個求最優(yōu)二叉樹的算法，又稱霍夫曼樹。,例：最優(yōu)檢索問題用計算機進行圖書分類?，F(xiàn)有五類圖書共100萬冊，其中有A類50萬冊，有B類20萬冊，C類5萬冊，D類10萬冊，E類15萬冊。問如何安排分檢過程，可使總的運算次數(shù)最??？,算法步驟：1.將s個葉子按權(quán)由小至大排序；2.將二個具有最小權(quán)的葉子合并成一個分枝點，其權(quán)為p1+p2；將新的分枝點作為一個葉子，合并，…,解：構(gòu)造一棵具有5個葉子的最優(yōu)二叉樹，其葉子的權(quán)分別為50，20，5，10，15.步驟如下：1.將5個葉子按權(quán)由小到大排序：5，10，15，20，502.找出二個最小權(quán)的葉子，合并成一個分枝點，其權(quán)為15；,依次，繼續(xù)。,,,,,,,總權(quán)為：,,,,分檢過程是：先把A類50萬冊從總數(shù)中分檢出來，其次將B類20萬冊分檢出來，然后再將E類15萬冊分檢出來，最后再將D、C分檢出來。,8.3最短路問題,有些問題，如選址、管道鋪設(shè)時的選線、設(shè)備更新、投資、某些整數(shù)規(guī)劃和動態(tài)規(guī)劃的問題，也可以歸結(jié)為求最短路的問題。因此這類問題在生產(chǎn)實際中得到廣泛應(yīng)用。,求最短路有兩種算法，一是求從某一點至其它各點之間最短離的狄克斯屈拉(Dijkstra)算法；另一種是求網(wǎng)圖上任意兩點之間最短的矩陣算法。,最短路問題，就是從給定的網(wǎng)絡(luò)圖中找出一點到各點或任意兩點之間距離最短的一條路.,渡河問題,一老漢帶了一只狼、一只羊、一棵白菜想要從南岸過河到北岸，河上只有一條獨木舟，每次除了人以外，只能帶一樣?xùn)|西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，問應(yīng)該怎樣安排渡河，才能做到既把所有東西都運過河去，并且在河上來回次數(shù)最少？這個問題就可以用求最短路方法解決。,設(shè)：M—人W—狼S—羊V—白菜,渡河方案共有10種，構(gòu)造如下一個圖，每條邊的距離為1，問題變?yōu)榍笠粭l從MWSV到φ的最短路。,北岸,南岸,●狄克斯屈拉(Dijkstra)標(biāo)號算法,點標(biāo)號：b(j)—起點vs到點vj的最短路長；,邊標(biāo)號：k(i，j)=b(i)+dij，,步驟：1.令起點的標(biāo)號；b(s)＝0。,先求有向圖的最短路，設(shè)網(wǎng)絡(luò)圖的起點是vs,終點是vt,以vi為起點vj為終點的弧記為（i，j）,距離為dij,2.找出所有vi已標(biāo)號vj未標(biāo)號的弧集合B=｛（i，j）｝如果這樣的弧不存在或vt已標(biāo)號則計算結(jié)束；,3.計算集合B中弧k(i，j)=b(i)+dij的標(biāo)號,4.選一個點標(biāo)號返回到第2步。,【例】求下圖v1到v7的最短路長及最短路線,0,8,6,2,,2,5,4,4,,11,14,7,5,10,,7,12,11,v7已標(biāo)號，計算結(jié)束。從v1到v7的最短路長是11,最短路線是：v1v4v6v7,,,,,,●無向圖最短路的求法,無向圖最短路的求法只將上述步驟2改動一下即可。,點標(biāo)號：b(i)—起點vs到點vj的最短路長；,邊標(biāo)號：k(i，j)=b(i)+dij，,步驟：1.令起點的標(biāo)號；b(s)＝0。,3.計算集合B中邊標(biāo)號：k[i，j]=b(i)+dij,4.選一個點標(biāo)號:返回到第2步。,2.找出所有一端vi已標(biāo)號另一端vj未標(biāo)號的邊集合B=｛[i，j]｝如果這樣的邊不存在或vt已標(biāo)號則計算結(jié)束；,【例】求下圖v1到各點的最短路及最短距離,0,4,5,2,,2,3,10,,3,9,6,12,6,,4,11,,6,,6,18,8,12,24,,8,24,,18,所有點都已標(biāo)號，點上的標(biāo)號就是v1到該點的最短距離，最短路線就是紅色的鏈。,●有負權(quán)的最短路算法,假設(shè)圖中沒有負回路。如下圖是一條負回路，最短路權(quán)無下界。,當(dāng)vi到vj之間沒有弧連接時，令lij＝＋∞,列表迭代計算：,設(shè)vs到vj經(jīng)過vi到達vj，則vs到vj的最短距離為：,迭代：,【例】求下圖v1到v8的最短路長及最短路線,2,0,－3,6,11,0,2,0,－3,6,6,15,0,2,0,－3,3,6,14,10,(表中空格為＋∞),020-336910,采用”反向追蹤”的方法找出從v1到v8的最短路.,已知:P(v1,v8)=10，而P(v1,v8)=min{P(v1,vi)+li8},尋找：P(v1,v6）+l68=6+4=10,記下：v6→v8,再檢查：P(v1,v6）=6,尋找：P(v1,v3）+l36=0+6=6,記下：v3→v6→v8,………,v1→v2→v3→v6→v8,再檢查：P(v1,v3）=0,尋找：P(v1,v2）+l23=2+(-2)=0,記下：v2→v3→v6→v8,8.4最大流問題,許多系統(tǒng)中都涉及到流量問題，例如網(wǎng)絡(luò)系統(tǒng)中有信息流、公路系統(tǒng)中有車輛流、金融系統(tǒng)中有現(xiàn)金流等等。對于這些包含了流量問題的系統(tǒng)，我們往往需要求出其系統(tǒng)的最大流量。例如，某公路系統(tǒng)的容許通過的最大車輛數(shù)，某網(wǎng)絡(luò)系統(tǒng)的最大信息流量等，以便于對某個系統(tǒng)加以認(rèn)識并進行管理。,例某石油公司建有一個可以把石油從采地輸送到不同銷售點的管道網(wǎng)絡(luò)，如下圖。由于管道的直徑變化，使得各段管道（vi,vj）的最大通過能力（容量）cij也是不一樣的，cij的單位為萬加侖/小時。要求我們制定一個輸送方案，將石油從v1輸送到v6，使得輸送的石油達到最大,●基本概念,容量：在某時期內(nèi)弧(i，j)上的最大通過能力。記為C(i，j)或Cij在上圖中，C12=4，C13＝8，C23＝4等，怎樣安排運輸方案，才能使在某一時期內(nèi)從v1運到v6的物資最多，這樣的問題就是最大流問題，,網(wǎng)絡(luò)中所有流起源于一個叫做發(fā)點的節(jié)點（源）,所有的流終止于一個叫做收點的節(jié)點,其余所有的節(jié)點叫做中間點（轉(zhuǎn)運點）,通過每一條弧的流只允許沿著弧的箭頭方向流動,目標(biāo)是使得從發(fā)點到收點的總流量最大,,,8.4最大流問題,流量：弧(i，j)的實際通過量，記為f(i，j)或fij,可行流：如果fij滿足：1.對于所有弧(i，j)有0≤fij≤Cij,則稱流量集合｛fij｝為網(wǎng)絡(luò)的一個可行流，簡記為f。,以下假設(shè)網(wǎng)絡(luò)是一個簡單連通圖。,2.對于中間點點vm有：,鏈：從發(fā)點到收點的一條路線（弧的方向不一定都同向）稱為鏈。從發(fā)點到收點的方向規(guī)定為鏈的方向。,前向?。号c連的方向相同的弧稱為前向弧。,后向弧：與連的方向相反的弧稱為后向弧。,增廣鏈設(shè)f是一個可行流，如果存在一條從vs到vt的鏈，滿足：,1.所有前向弧上fij0,則該鏈稱為增廣鏈,①,②,③,④,⑤,⑥,,,,,,容量,流量,【定理】設(shè)網(wǎng)絡(luò)G的一個可行流f，如果存在一條從vs到vt的增廣鏈，那么就可改進一個值更大的可行流f1，并且valf1>valf,【證】設(shè)valf＝v,對改進的可行流f1：,●最大流的標(biāo)號算法,步驟1.找出第一個可行流，例如所有弧的流量fij=0,2.用標(biāo)號的方法找一條增廣鏈A：發(fā)點標(biāo)號（△，∞），,B：選一個已標(biāo)號的點vi，對于vi的所有未給標(biāo)號的鄰接點，按下列規(guī)則處理：如果是前向弧并且有fij下載提示(請認(rèn)真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認(rèn)領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
14.9 積分
| 下載 |
還剩頁未讀，繼續(xù)閱讀
- 配套講稿：
如PPT文件的首頁顯示word圖標(biāo)，表示該PPT已包含配套word講稿。雙擊word圖標(biāo)可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
- 運籌學(xué) 網(wǎng)絡(luò)分析
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
相關(guān)資源
更多
正為您匹配相似的精品文檔
相關(guān)搜索
鏈接地址：http://m.kudomayuko.com/p-3273641.html