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