【正文】 。 按照網絡特征，最短路徑是如何分類的？ Floyd算法的基本思想是什么？ 資源分配主要研究哪些問題？ ? 小結與習題 按 Dijkstra算法求解右圖所示的最短路徑。算法結束。 每條弧 前向可增流量 及 反向可增流量 分別為 ???????????ijijijijijij cxcxa若若,? ????????????0,0,ijijijij xxa若若???????????ijijijijijijij cxcxxc若若,0,??????????0,00,ijijijij xxx若若?167。 ? ? ? ?? ?? ? Evv ijijXx jiij xa,m in167。 最小費用最大流問題就是 其中， X*為 G的最大流的集合。 流分析（ 14） 二、最小費用最大流問題 最小費用最大流 ： 在最大流集合中尋找一個費用最小的最大流。即為最大流。 流分析（ 13） 去掉各點標號，從 vs開始，重新標號。根據 δ t= 1調整可行流，得到新的可行流 f′ 如下圖。 vt又得到標號，標號過程結束。根據 δ t= 3調整可行流，得到新的可行流 f′ 如下圖。 流分析（ 11） vt又得到標號，標號過程結束。 流分析（ 10） 去掉各點標號，從 vs開始，重新標號。 根據 δ t= 2調整可行流，得到新的可行流 f′ 如下圖。 167。 流分析（ 7） 檢查 V1，在弧（ v1， v3）上， X13=0， C13=4， X13C13，給 v3標號 (1， δ 3），其中， δ 3= min{C13X13,δ 1}= min{4, 3}=3 檢查 V2，同理，給 v4標號 (2， δ 4）， 其中， δ 4= min{C24X24,δ 2}= min{2,5}=2 167。 流分析（ 6） 例：求下圖所示網絡的最大流。 （ 2）按下述關系調整網絡中的可行流： （ 3）去掉圖中所有標號，對可行流 {xij′ }重新進行第一步。 流分析（ 5） 標號法求最大流的基本步驟 ： 第二步： 增流 。 （ 1）若所有已標號點都已被檢查，而收點沒有得到標號，則進行第三步； （ 2）找一個標號未檢查的頂點 vi進行檢查： 對?。?vi,vj） ,若 xij?c ij，且 vj未標號，則給 vj一個標號（ +vi,δ j),其中 δ j= min{cij – xij,δ i} 對弧（ vj,vi） ,若 xji0，且 vj未標號，則給 vj一個標號（ vi,δ j), 其中 δ j= min{xji,δ i} （ 3）如果收點已得到標號，則進行第二步；否則返回（ 1）。 流分析（ 4） 標號法求最大流的基本步驟 ： 第一步： 標號與檢查 。 可增流鏈 ：若一條鏈中的每條前向?。?vi,vj）都有 xij cij,每條反向?。?vk,vl）都有 xkl0 ，則稱這樣的鏈為該可行流的可增流鏈。 前向弧 ：鏈上與鏈方向相同的弧。 流分析（ 3） 二、最大流解法 —— 標號法 標號法的基本思想 ：給初始可行流 f取零流，表示網絡開始不運輸任何資源；然后在滿足條件的情況下，逐漸增加流量，直到無法增加流量為止，這時的可行流便是最大流。 最大流問題： 在可行流中找出流值最大者。（容量限制） 零流 ： 若流 f={xij}滿足下列條件 ,則稱 f為零流。 流分析（ 2） 可行流 ： 若流 f={xij}滿足如下兩個條件 ,則稱 f為 G的可行流。 幾個基本概念 ： 發(fā)點 vs：資源的運出點（源）； 收點 vt：資源的運入點（匯）； cij：表示網絡弧（ vi,vj）的容量； cj：表示網絡結點 vj的容量； 流量 xij ：地理網絡中的流是指定在弧集合 E中的實值函數f={xij},xij稱為對應網絡邊的流量。 網絡流優(yōu)化 即是根據某種優(yōu)化指標（如時間最少，費用最低，路徑最短、運量最大等）找出網絡物流的最優(yōu)方案的過程。 167。 （ 4） 重復第 2步和第 3步直到兩步都無新的替換為止 。 167。 ③若②中選擇的點所減少的目標方程的值大于①中選擇的點所增加的目標方程的值，用②中的點代替①中的點，并更新目標方程，再回到①重復檢驗；否則轉入步驟（ 3）。 （ 2） 供應點全局性調整 ： ①檢驗當前解中所有供應點，選定一個準備刪去，且刪去只引起最小目標方程值的增加。 全局 /區(qū)域性交換式算法 ： 該算法是一種效率較高的啟發(fā)式方法。 要求 距離最小 時，令 Mij=ω idij,則原目標方程轉化為 若要求 所有的需求點在一給定的服務半徑 S內 ，則對 Mij修改如下 ????????? ?? ?nimjiji xM1 1m in??????????sdsddMijijijiij ,?167。 資源分配（ 5） P中心問題解的性質 ： （ 1）每一個供應點都位于其所服務的需求點的中央； （ 2）所有的需求點都分配給與之最近的供應點； （ 3）從最優(yōu)的解集中移去一個供應點并用一個不在解集中的候選點代替，會導致目標函數值的增加。 資源分配（ 4） 三、 P中心定位與分配問題： P中心定位與分配問題 即要求所有需求點到供應點的加權距離最小，是定位與分配的基礎問題。,2,1, jkmkddbt ikijiij?????其他情況供給受,0,1 jiijQPX167。 tij和 dij分別是供應點 Qj對需求點 Pi提供的供應量和兩點間的距離。 167。 資源的定位 ：指已知需求，確定在哪里布設最合適的供應點，即尋找最佳的供應點。 資源分配的研究問題 包括： （ 1）需求點和供應點都確定的情況下，現在資源的分配，如物資配送； （ 2）新增供應點，如新的變電所選址； （ 3）新增需求點，如新建居民地。 最佳路徑的表現形式 167。 最佳路徑的表現形式 對任一種最佳路徑，其表現形式多種多樣，其中包括兩點間的最佳路徑，多點間指定順序最佳路徑，多點間最佳順序最佳路徑，回到起始點最佳路徑，兩源最佳路徑，多源最佳路徑等。 如將網絡中每條弧的權值定義為能過該弧的時間，就可定義通行時間最短的路徑。 例： 如圖表示從 V1到 V2的兩條路徑，每條邊上的數字表示容量。對于任何 e＝(vi,vj)∈E ， cij為邊 (vi,vj)的容量。 由于 則最大可靠路徑的完好概率為： ? ? ? ? ? ????PEe ijpPp? ?? ? ? ?? ? ??????????????PEeijPEeij ppPp? ? ? ?? ? ? ???? ???????PEe ijPEe ijPEe ijpp lnln?? ? ? ? ???????? ?? ???? PEeijPEeijp ?e xpijij pln???167。 P是Ｇ中的兩點間的一條有向路徑，定義Ｐ的完好概率為 則Ｇ中這兩點間完好概率最大的有向路徑稱為這兩點的 最大可靠路徑 。 一、最大可靠路徑 設 G＝ V,E是一個非空的簡單有限圖。 167。 在算法實現和改進中，主要涉及三個方面的問題：