運籌學第八章圖與網(wǎng)絡分析ppt課件

《運籌學第八章圖與網(wǎng)絡分析ppt課件》由會員分享，可在線閱讀，更多相關《運籌學第八章圖與網(wǎng)絡分析ppt課件（56頁珍藏版）》請在裝配圖網(wǎng)上搜索。

運籌學,趙明霞 山西大學經(jīng)濟與管理學院,1,第八章 圖與網(wǎng)絡分析,圖與網(wǎng)絡的基本概念 樹 最短路問題 最大流問題 最小費用最大流問題,2,柯尼斯堡七橋問題,歐拉回路：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題 哈密爾頓回路：經(jīng)過每點且僅一次 貨郎擔問題、快遞送貨問題,3,第一節(jié) 圖與網(wǎng)絡的基本概念,圖是由點和邊構成，可以反映一些對象之間的關系。 例如：在一個人群中，對相互認識這個關系我們可以用圖來表示，圖8.1就是一個表示這種關系的圖。,4,描述對象之間關系， 研究特定關系之間的內(nèi)在規(guī)律， 圖中點的相對位置如何、點與點之間聯(lián)線的長短曲直，對于反映對象之間的關系并不是重要的。,5,如果我們把上面例子中的“相互認識”關系改為“認識” 的關系，那么只用兩點之間的聯(lián)線就很難刻畫他們之間的關系了，這是我們引入一個帶箭頭的聯(lián)線，稱為弧。,6,無向圖：由點和邊構成的圖，記作G =（V，E）。 有向圖：由點和弧構成的圖，記作D =（V，A）。 無向圖是有向圖的基礎圖G(D) 有限圖 無限圖,7,G=(V,E) 關聯(lián)邊(m)：ei 端（頂）點(n)：vi, vj 點相鄰(同一條邊)： v1, v3 邊相鄰(同一個端點)：e2, e3 環(huán)：e1 多重邊： e4, e5,8,簡單圖：無環(huán)無多重邊 多重圖：多重邊,完全圖：每一對頂點間都有邊（?。┫噙B的簡單圖,9,次（d）：結點的關聯(lián)邊數(shù)目 d(v3)=4，偶點 d(v2)=3，奇點 d(v1)=4 d(v4)=1，懸掛點 e6, 懸掛邊 d(v5)=0，孤立點,出次：d+(vi) 入次：d-(vi) d (vi) = d+(vi) + d-(vi),定理1 頂點次數(shù)總和等于邊數(shù)的兩倍。 定理2 次為奇數(shù)的頂點必為偶數(shù)個。,10,若 ,則G’是G的子圖，G是G’的母圖 若 ,則G’是G的真子圖， 若 ,則G’是G的支撐（生成）圖。,11,鏈：點邊交替序列 閉鏈：v1 v2 v3 v4 v1 開鏈：v1 v2 v3 邊不同，簡單鏈：v3 v4 v5v1v6v5 邊不同且結點不同，初等鏈：v1 v2 v3 v4 v5v6 圈：閉鏈，且至少有3個不同結點，v2 v3 v4 v2 初等圈：初等閉鏈，v1 v2 v3 v4 v1,12,路：有向圖：弧的方向與鏈的方向一致 開路:v1v2v4v5 回路：第一個點和最后一個點相同。v1v2v4v5v1,13,連通圖：若任何兩個不同的點之間，至少存在一條鏈，則G為連通圖。 賦權圖：對一個圖的每一條邊（?。?vi,vj)，相應地有一個數(shù)wij，則稱圖G為賦權圖，wij稱為邊(vi,vj)上的權。 網(wǎng)絡：賦權連通圖 無向圖：開鏈即開路，閉鏈即回路 有向圖：弧的方向與鏈的方向一致。,14,柯尼斯堡七橋問題,歐拉回路：經(jīng)過每邊且僅一次 厄尼斯堡七橋問題、郵路問題 充要條件：無向圖中無奇點，有向圖每個頂點出次等于入次,15,16,第二節(jié) 樹,樹是圖論中的重要概念，所謂樹就是一個無圈的連通圖。,圖8-4中，(a)就是一個樹，而(b)因為圖中有圈所以就不是樹， (c)因為不連通所以也不是樹。,16,樹的基本性質 任意兩點間有且僅有一條鏈 不相鄰兩點間添加一條邊，有且僅有一個圈 任意去掉一條邊，得不連通圖. 存在懸掛點 m=n-1,17,18,,生成（支撐）樹,若 ,則G’是G的支撐（生成）樹。,18,19,1、破圈算法 步驟： （1）在給定的賦權的連通圖上任找一個圈。 （2）在所找的圈中去掉一個權數(shù)最大的邊（如果有兩條或兩條以上的邊都是權數(shù)最大的邊，則任意去掉其中一條）。 （3）如果所余下的圖已不包含圈，則計算結束，所余下的圖即為最小樹，否則返回第1步。,最小生成樹問題就是指在一個賦權的連通的無向圖G中找出一個生成樹，并使得這個生成樹的所有邊的權數(shù)之和為最小。,19,20,例8.1,20,2、避圈算法 步驟： （1）任找一個點S，其余各點就是 。 （2）在連接S與 的所有邊中，選擇權數(shù)最小的邊(i, k)； （3）將最小邊(i, k)的另一個端點移入S； （4）若 則停止，否則返回（2）。,21,22,例8.1,22,有向樹：不考慮方向時是樹 根樹（外向樹）：只有一個頂點入次為0，其余頂點入次為1 根：入次為0的頂點 葉：出次為0的頂點 分支點 層次：根到頂點的長度,23,m叉樹：每個頂點的出次小于等于m 完全m叉樹：每個頂點的出次等于m或0,24,霍夫曼樹：最優(yōu)二叉樹,25,第三節(jié) 最短路問題,最短路問題： 對一個賦權的有向圖D中的指定的兩個點Vs(起點)和Vt（終點）找到一條從 Vs 到 Vt 的路，使得這條路上所有弧的權數(shù)的總和最小，這條路被稱之為從Vs到Vt的最短路。這條路上所有弧的權數(shù)的總和被稱為從Vs到Vt的距離。,26,適用于：每條弧（邊）的賦權數(shù)wij ≥0 優(yōu)點：能夠求出某點至各點的最短路 基本思想： T(j) （tentative label）——從始點s到j點的最短路長上界，稱為試探性標號; P(j) （permanent label）——從始點s到j點的最短路長，稱為永久性標號.,一、狄氏標號法（Dijkstra算法）,27,例8-9,基本步驟 標號T(j)→P(j),28,29,最長路問題 例8-10（7-9）設某臺新設備的年效益及年均維修費、更新凈費用如表。試確定今后5年內(nèi)的更新策略，使總收益最大。,30,31,網(wǎng)絡中心（r點）,例8-11 某連鎖企業(yè)有6個銷售點，問倉庫應建在哪個地點，可使各銷售點離倉庫較近？,32,33,各點間的最短距離,二、Floyd算法,34,例8-12 求任意兩點間的最短路,35,36,37,38,容量網(wǎng)絡(網(wǎng)絡)：N=(V, A, c) 或 N=(V, A)，最大流量cij = c(i,j) 網(wǎng)絡流： 可行流：s發(fā)點，t收點 可行流流量：,第四節(jié) 最大流問題,39,割(截)集： S中各點聯(lián)通，S 中各點聯(lián)通 始點在S，終點在S 的集合，稱為一個分離發(fā)點s和收點t的割集，（S,S） 割集容量： 最小割：最小的割集容量,40,定理8-10：網(wǎng)絡任一可行流的流量恒不超過任一割集的容量。 定理8-11：最大流 = 最小割,41,增廣（容）鏈： 為從發(fā)點s到收點t的一條鏈，且前向弧均非飽和，后向弧均非零流。 最大流：流量最大的可行流。 可行流為最大流的充要條件：不存在從s到t的增廣鏈,42,（一）線性(整數(shù))規(guī)劃法,43,例8-13,44,（二）網(wǎng)絡分析法 增廣鏈調(diào)整法,45,Ford—Fulkerson標號法 基本思想：先確定一個初始可行流，再找增容鏈，調(diào)整流量，直到找不到增容鏈為止。雙標號（i, b(j)），b(j)—當前最大可調(diào)容量 運算步驟： 發(fā)點s標號（0, ∞ ）； 給所有相鄰點標號 正向弧且 ，則 j 標號（i, b(j)） ，則 j 不標號 逆向弧且 ，則 j 標號（-i, b(j)） 檢查標號 調(diào)整量,46,,例8-13,（1）計算機編程,47,,（2）手算,f*=11,48,49,50,最小費用最大流問題：給了一個帶收發(fā)點的網(wǎng)絡N=(V,A,c,d)，對每一條弧（i，j），除了給出容量cij外，還給出了這條弧的單位流量的費用dij，要求一個最大流f，并使得總運送費用最小。,先求出此網(wǎng)絡圖中的最大流量f。 在最大流量f的所有解中，找出一個最小費用的解,（一）線性(整數(shù))規(guī)劃法,第五節(jié) 最小費用最大流問題,51,例8-15,第一步,第二步,52,對偶網(wǎng)絡法：N=(V,A)，N’=(V,A’,w) xij = 0, 0 xij cij, xij = cij，,（二）網(wǎng)絡分析法,53,定理8-7：對偶網(wǎng)絡中的最短路必是原網(wǎng)絡的最小費用增容鏈。 定理8-8：在流量為f的最小費用流上，按最小費用增容鏈調(diào)整流量后，仍為新流量上的最小費用流。 基本思想：找出對偶網(wǎng)絡的最短路，沿此路調(diào)整流量，直到最大流量。 運算步驟,54,55,作 業(yè),8.1 8.6 8.8 8.10 8.17,56,